带约束的K-means 聚类算法
1. 前言
上一期学习了K-means聚类算法，聚类是不受到限制的，单纯的无监督学习，但是当存在一些约束时，比如对每一簇的聚类样本点数量有限制，或者每个样本点带需求，每一簇存在满足约束的最大能力，这时候应该怎么添加约束，并且不破坏聚类的效果。
2. 场景构建
假设场景：有一定数量的区域需要分配邮递员配送信件，怎么将区域划分给邮递员？每个区域有一定的需求量，一个邮递员一天的工作量只能满足一定的需求，那么应该怎么将区域划分给邮递员？考虑到成本问题，这里设置一个目标——在满足需求的情况下最小化邮递员数量。
[En]
Suppose the scenario: there are a certain number of areas that need to be assigned postmen to distribute letters, how to divide the areas to postmen? There is a certain demand in each area, and the workload of a postman in a day can only meet a certain demand, so how to divide the area to the postman? Considering the cost, a goal is set here-to minimize the number of postmen while meeting the demand.
这样的场景在快递行业应该很常见，不太清楚实际业务中是怎么分配的，但我觉得带约束的聚类算法应该能求解一个可行解，为了给K-means加约束构想的场景，场景简化了很多，可能不太符合实际，欢迎提建议。
3. 带约束的K-means 聚类设计
K-means聚类算法流程
① 算法说明：由于存在需求约束，那么就存在最小的K（总需求/簇的能力），可以从最小值K开始遍历。而约束就加在（3）将对象分配到最相似的簇中，具体修改为：在满足约束的情况下，将对象分配到最相似的簇中，如果最相似的簇无法容纳，就找第二相似的簇，依次类推。
② 遍历改进：对遍历对象进行一个小的修改，通常K-means是随机/按列表顺序遍历对象，将对象分配到最相似的簇，这里改进为：取所有对象中距离某个簇最近的点，优先分配（这算是随机/按列表顺序遍历对象的一个特殊情况）。