A Framework for Minimal Clustering Modification via Constraint Programming
研究的问题
好的聚类算法通常会受到异常属性的影响，本文着力研究如何用一种低成本且简单有效的方式来优化受到异常属性干扰的聚类，实现每个聚类的最大凝聚力。
研究动机
一个比较好的聚类算法可能会因为少数属性（坏/异常的属性值）的影响而表现糟糕，花费大量成本重新聚类不是个好主意，更好的方法是通过删除不需要的属性来最低限度地修改聚类。之前的研究仅仅着重于聚类算法的好坏，将聚类结果归之于算法的好坏，而本文的研究重点是基于约束编程框架进一步优化那些好的聚类算法的聚类结果。
先进性与贡献
本文提出的方法从最初的聚类算法开始，基于约束编程框架，在删除不良属性的同时对其进行最小程度的修改，这省去了重新聚类的成本。对于其他现成聚类簇，该方法也可以做出进一步优化。同时，这种方法可以为任何聚类算法提供反馈。通过生成新的最小修改聚类，同时保留大部分原始数据，使得我们不用担心信息的过度丢失。
具体方法
- 首先多次使用某种聚类算法对原始数据集进行聚类，得到最佳的聚类集群。
- 接着计算所有属性在所有类中的直径，得到初始直径矩阵D（每行为一个类，每列为一个属性）。
- 观察计算结果并制定收紧策略： 修改后的直径矩阵D’[i, j] = m D[i, j]（其中m为修改参数，0<m<=1）。
- 计算约束条件“上限 – 下限 <= D’”所需要的具体数值。每个类中关于每个属性的上限和下限：
- 上限：类中各个属性值与最小属性值之差的最大值，再加该类中的最小属性值
- 下限：类中各个属性值与最大属性值之差的最小值，再加该类中的最大属性值
- 根据得到的约束条件，在约束编程框架中得到可行解，即一个进步了的聚类结果。
- 重新计算新的类直径矩阵，若对结果不满意可多次调整收紧策略，最终达到满意的聚类结果。
优缺点及思考
本文所提出的聚类优化方法，是基于某种比较好的聚类算法，在不做重新聚类的情况下，基于约束编程框架最小限度的修改聚类，以达到各个聚类内的凝聚力最大的效果。这种方法需要我们提供反馈，即我们对聚类结果的评价，我们需要告诉程序应该修改哪一个类中的哪一个属性直径，以便于程序不去考虑那些异常属性对聚类的影响。
一种效果更好的方法是让类中的任意两点的属性距离都不大于我们限定的属性直径，但这样做将需要很大内存和CPU，这很低效。因此本文改进方法，仅仅限制类内属性的最大差距，这样在不影响优化效果的同时极大的提高了效率并节省类开支。
这种方法在实施的过程中会将那些受到不良属性影响的实例点移动到最适合他们的类中。基于约束编程框架，根据我们限定的约束条件，达到“类内距离最小、类间距离最大”的效果。
本文的研究重点是一步步缩紧约束条件，在约束编程框架下得到更好的可行解。那么进一步探索，是否可以找到一些方法，可以通过修改聚类或者聚类数量，达到一种更广泛和适用性更强的修改框架。
2018.9.24
