Clustering：K-means Extention
KDF000 2013-03-10
Clustering：K-means Extention
在上篇K-Means介绍中，学习了K-means算法的优点和缺点。本文通过扩展K-Means算法来进一步学习Clustering的相关算法。
在K-Means算法中，使用的距离概念是欧式距离，这个必须在欧式空间中才有效。这个对数据的要求比较高，如果不能使用欧式空间内的距离（Distance）来描述数据点之间的差异（Dissimilarity），K-Means算法就无能为力。假如说现在有这么写数据，是描述这个人的身高、收入、性别等。那么再使用K-Means算法就不再合适。K-Means扩展算法K-Medoid算法能能够从概念上解释这个问题。
k-medoid
K-Medoid算法将数据中心点的选择限制在集合内的数据点上。也就是说簇内中心点必须从簇内数据集中选取。目标函数不变，依然是最小化SSE。
最常见的做法是构造差异矩阵(Dissimilarity Matrix)来表示数据点的差异。由于K-Medoids算法的中心点是在已有的数据集合中选取，相对K-Means算法来说不容易受到误差原因的Outlier的影响，会更加健壮(Robust)一些。
K-Medoid算法的复杂度比K-Means相比增加了一个级别。K-Means算法只要求计算均值(Mean)，时间复杂度为O(N)，而K-Medoid算法则要求迭代枚举簇内每个数据点，复杂度为O(N**2)。
在K-Medoid的wiki上，http://en.wikipedia.org/wiki/K-medoids，有个常见的实现方式：PAM(Partitioning Around Memoid)，该实现方法能够做到全局最优，但是非常慢，具体实现思路大家可以看下wiki。
K-Modoid的两外一种实现是CLARA(CLustering LARge Application),思路比较简单，是从大数据集合中采样，计算样本的Medoid，而不是计算整个数据集合的Medoid。可以针对样本数据进行PAM数据集合寻找Medoid，然后将其作为整个数据集合的Medoid。从算法过程中也能看出来，数据集合的样本采集是非常重要的，所以CLARA只能做到局部最优，而不是像PAM那样全局最优。在R-Project中有CLARA实现，可以参考这里：http://en.wikibooks.org/wiki/Data_Mining_Algorithms_In_R/Clustering/CLARA
Fuzzy C-Means
FCM使用了Fuzzy Logic的概念，说明数据点并不归属于某个cluster，而是以一定的概率(概率并不准确，应该是某种度量)属于所有簇。FCM的目标函数如下：
其中Uij表示数据Xi归属于簇j的度量，||*||是相似度距离。FCM的求解也是迭代求解，和K-Means类似，主要点在于初始化相似度矩阵U，同理使用迭代求解的也只能做到局部最优(Local Optimal)。
熟悉K-Means算法的话，这个迭代和K-Means类似，其收敛条件近似收敛。更为详细的解释可以参考这里：http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/cmeans.html，后面还有个实例来说明。德文wiki里面有个德币的检测，翻译后可以了解一下。http://de.wikipedia.org/wiki/Fuzzy_C-Means
K-Mean++
K-Means算法需要用初始随机种子点来搞，这个随机种子点太重要，不同的随机种子点会有得到完全不同的结果。多次运行选择最小误差就是希望能够跳出局部最优的问题。但是我们希望能够通过慎重选择初始点来解决这个问题：K-Means++算法可以用来解决这个问题，其通过选择选择合适的初始点。
K-Means++中最主要的部分是初始点选择部分：
步骤2中计算最近的D(x)，步骤3中要求每个点根据其D(x)**2的概率分布选择到，这句话是不是比较迷惑。在commons-math的org.apache.commons.math.stat.clustering包中有KMeansPlusPlusCluster的实现，在初始点选择上可以仔细看下：
private static <T extends Clusterable<T>> List<Cluster<T>> chooseInitialCenters(final Collection<T> points, final int k, final Random random) {
final List<T> pointSet = new ArrayList<T>(points);
final List<Cluster<T>> resultSet = new ArrayList<Cluster<T>>();
// Choose one center uniformly at random from among the data points.
final T firstPoint = pointSet.remove(random.nextInt(pointSet.size()));
resultSet.add(new Cluster<T>(firstPoint));
final double[] dx2 = new double[pointSet.size()];
while (resultSet.size() < k) {
// For each data point x, compute D(x), the distance between x and
// the nearest center that has already been chosen.
// Save sum, for later use
int sum = 0;
for (int i = 0; i < pointSet.size(); i++) {
final T p = pointSet.get(i);
final Cluster<T> nearest = getNearestCluster(resultSet, p);
final double d = p.distanceFrom(nearest.getCenter());
sum += d * d;
dx2[i] = sum;
}
// Add one new data point as a center. Each point x is chosen with
// probability proportional to D(x)2
final double r = random.nextDouble() * sum;
for (int i = 0 ; i < dx2.length; i++) {
if (dx2[i] >= r) {
final T p = pointSet.remove(i);
resultSet.add(new Cluster<T>(p));
break;
}
}
}
return resultSet;
}
保存每个点到所选中心点的距离，并且保存距离的平方值到数组中；在后面的等概率比例选择中，数组中保存的值大于随机值时，这个点就加入到中心点中；重复操作直到选择完K个初始值。
需要注意的是K-Means++只是能保证求解质量(Solution Quality)更容易贴近最优解(O(lgK))，并不保证能获得最优解。实际上K-Means及其它方法的目标函数求解都是NP-Hard问题，这些解法都是近似解法。所以希望得到全局最优解的方法貌似只能在数据空间内遍历，这个又是极其不现实的做法。
canopy cluster
Canopy聚类算法的执行过程有以下两个过程：
步骤一：首先应用成本比较低得距离计算方法将数据高效分组，成为Canopy，Canopy之间允许有重叠的部分。不过不允许存在某个数据不归属于任何Canopy的情况。这个过程可以看作是数据预处理阶段。
步骤二：采用严格的距离计算方式计算在单个Canopy中的点，使用传统的聚类方法将他们分配到合适的簇中。Canopy之间不进行相似度计算，仅限于Canopy之内。
在创建Canopy的过程中，假设有数据集合S，并且预设有两个距离阀值T1、T2(T1>T2)；然后选择一个点（随机or固定），计算它与其他点得距离(成本低的距离计算方法，如L1),将距离为T1之内的的数据点放入一个Canopy之内，同时从S中去掉那些与此点距离在T2之内的点；重复整个过程直到S为空为止。删除距离T2之内的点是为了保证这些点不能再作为其它Canopy的中心点。
T1-T2的差值决定了Canopy之间的重叠数据，重叠数据合适的话，能够减小步骤二的计算量；另外确保Canopy之间不会靠的太近，T1和T2的阀值可以使用交叉验证的方式来获得；另外通过步骤一可以获得Canopy的个数可以作为这个K值，在一定程度上减小了选择K的盲目性。
在mahout上有个Canopy算法的实现，初始化Canopy的代码如下，内容也比较简单：
public static List<Canopy> createCanopies(List<Vector> points, DistanceMeasure measure, double t1, double t2) {
List<Canopy> canopies = Lists.newArrayList();
/**
* Reference Implementation: Given a distance metric, one can create
* canopies as follows: Start with a list of the data points in any
* order, and with two distance thresholds, T1 and T2, where T1 > T2.
* (These thresholds can be set by the user, or selected by
* cross-validation.) Pick a point on the list and measure its distance
* to all other points. Put all points that are within distance
* threshold T1 into a canopy. Remove from the list all points that are
* within distance threshold T2. Repeat until the list is empty.
*/
int nextCanopyId = 0;
while (!points.isEmpty()) {
Iterator<Vector> ptIter = points.iterator();
Vector p1 = ptIter.next();
ptIter.remove();
Canopy canopy = new Canopy(p1, nextCanopyId++, measure);
canopies.add(canopy);
while (ptIter.hasNext()) {
Vector p2 = ptIter.next();
double dist = measure.distance(p1, p2);
// Put all points that are within distance threshold T1 into the
// canopy
if (dist < t1) {
canopy.observe(p2);
}
// Remove from the list all points that are within distance
// threshold T2
if (dist < t2) {
ptIter.remove();
}
}
for (Canopy c : canopies) {
c.computeParameters();
}
}
return canopies;
}
对于Canopy还有几点说明：
1：T1、T2的选择影响到步骤二的计算量，Canopy之间的数据重叠率，以及Canopy的数据粒度，可以通过交叉验证来决定。
2：步骤一中轻量距离度量的选择，是Canopy速度计算很重要的一个属性。数据本身的维度属性也比较重要，如果出现"维度灾难"的话，就需要预先的降维处理。
3：Canopy能够消除孤立点，而K-Means则对这种情况无能为力。在步骤一建立Canopies之后，可以对这些Canopy做预处理，删除那些包含数据点数目较少的Canopy，这些Canopy包含孤立点的可能性比较大。
4：Canopy算法倾向于对大数据量进行预处理，以加速Clustering的过程。当由于数据量而使得某类Clustering算法变得不适用时，可以使用Canopy算法进行预处理，对Canopies内进行某Clustering算法。
这些算法都从某种程度上解决了K-Means算法的问题，或者是K-初始值，或者是计算复杂度，或者随机种子等问题。将这些算法放在一起也能看出来算法的改进思路和改进方向，对于我们系统的学习Clustering算法有很大的帮助，以此。
