基于划分的聚类——基于形心的K均值，K众数和K中值

前面提到分类（Classification）和聚类（Clustering）的区别。作为无监督学习，聚类在生成聚簇（Cluster）的时候，其聚簇数甚至是不能确定的。在做美赛D题的时候，我们最后使用了K均值的算法来为国家进行聚类，我写的是Python的代码。
一组属性组成的数据记录可以用一个N维向量表示。我们假若用这样一幅二维图像表示数据集，聚类便是努力使相邻的样本聚合到同一个簇。

图中所示的情况当然是很理想的，样本很明显地分成四个聚合。实际情况很可能是这样的

这幅图的样本分布就没那么明显了

《数据挖掘》一书介绍了在聚类分析中的四类方法。这里要讲的三种都属于基于划分（Partition）的方法，对于要生成的簇数k，划分会生成k个簇（不排除空簇），使得同簇内的对象相似，而不同簇的相异。

形心
我们用一个簇的形心，类似一个抽象几何体的中心点来表示一个簇，则属于该簇的所有点与其形心都有一个距离值，一个簇的质量（类似物理上的质量概念）可以用它的簇内变差（每个样例点与形心的欧几里德距离）度量，定义：

E即是对每个簇求其质量后各簇的质量总和。基于这一概念的划分方法不同之处其实在于如何定义形心这一概念。一个好的聚簇方案，其质量一定是尽可能小的，也就是说，每一个样例点到其簇的形心都尽可能小，以确保其被分配到最优的簇。然而枚举这些方案的复杂度是很高的，我们需要采用贪心策略的做法。

K-均值
K均值（K-Means）的算法把簇的形心定义为簇内点的均值。伪代码如下：

function K-Means-Clustering(examples, k)
returns a set of k clusters
    select k initial centroids from examples randomly //选取初始点
    do
        for instance in examples
            instance.cluster = cluster with argmin(dist(ci, instance)) //选择最近形心
        for c in clusters
            c.ci = average(for e in c) //更新形心
    while nothing change any more
    return clusters

这个过程是迭代的，首先随机选出k个样例作为k个簇的起始中心点，然后为每个对象分配到最近（最相似）的簇。这个算法循环地努力优化簇内变差，每一次的迭代，中心点都会被重新计算，然后下一次分配。
这个算法很有启发性，但也有很明显的局限。因为其起始点的随机性，比如说第一幅图中四个明显区分开的聚簇，如果我们初始选择的中心点有几个都在同一个聚簇，那结果会很难看。又或者如下图的例子：

左边是理想的方案，但若随机选取的初始中心在两个簇的边界处，最终结果有可能会出现部分边界交叉的情况（交叉是相对于理想方案来讲的）。正因K均值的方法受其初始点的随机性影响，所以往往在运行时会在多次结果中取折衷的方案，又或者是利用一些先验知识选择中心点以替代随机。美赛时我们对国家的数据进行聚簇的最终方案，也是先选择了几类国家作为初始中心点。看到一篇有趣的博客是对亚洲杯各国的数据进行聚簇的，有兴趣的可以看看。【哈哈哈哈哈哈哈国足
编程细节上如何结束迭代？我们都知道计算机在浮点数运算的时候精度是一个很大的问题，什么条件下判断聚簇方案在经过一次迭代后没有发生变化从而结束循环？《集体智慧编程》一书中给出的方案是为每个样例记录其上一次分到的类，若一次迭代中没有任何样例的聚簇发生变化，则终止。在赛时我还没看这本书，用的是记录每次中心点的位置，当中心点没有发生变化（具体表现是前后的改变距离小于一个很小的浮点数）时结束。现在看来是前一个方法准确。
对象总数为n，k是簇数，t为迭代次数，则K均值的复杂度是。局限性很明显，K均值对离群点和噪声敏感。因为是计算均值，也就是说考虑中心点的时候，离群点和其他点有着同等的贡献率。过分的离群值会严重扭曲理想的均值。

K众数
当我们用向量表示一个样例，其每个维我们假定为连续值。那么当我们需要面对离散值，或者说标称属性呢？离散的情况使得均值无法计算，这时候我们采用计算众数作为中心点。同时欧几里德距离要换成标称距离，也就是转换离散值为连续值。通过统计频率的方法来更新。决策树分类时美国国会投票的例子就可以用这个方法。我的转换方法是yes和no对应正负一，unknown对应0。

K众数对美国国会数据聚类代码：

#K-mode
import random
import copy
from math import *
class instance():
    def __init__(self, party, votes):
        self.party = party
        self.votes = votes
        self.classification = None
dataFile = open('dataset.txt', 'r')
datas = dataFile.readlines()
database = []
for line in datas:
    line = line[:-2]
    attrs = line.split(',')
    member = instance(attrs[0], attrs[1:])
    database.append(member)
def normDistance(vector1, vector2):
    total = 0
    normDict = {"y" : 1, "?" : 0, "n" : -1}
    for i in range(0, len(vector1.votes)):
        total += pow(normDict[vector1.votes[i]] - normDict[vector2.votes[i]], 2)
    return sqrt(total)
def kMode(dataSet, k):
    selectIndex = [2, 8]
    centroids = []
    for i in selectIndex:
        cent = copy.deepcopy(dataSet[i])
        centroids.append(cent)
    clusterChanged = True
    times = 0
    while clusterChanged:
        clusterChanged = False
        times += 1
        for record in dataSet:
            minIndex = 0
            minDist = 1000000000000
            for i in range(k):
                dist = normDistance(centroids[i], record)
                if dist < minDist:
                    minDist = dist
                    minIndex = i
            if record.classification != minIndex:
                record.classification = minIndex
                clusterChanged = True
        counter = []
        for i in range(k):
            init = []
            for j in range(len(centroids[0].votes)):
                init.append({"y" : 0, "?" : 0, "n" : 0})
            counter.append(init)
        for record in dataSet:
            for i in range(len(record.votes)):
                counter[record.classification][i][record.votes[i]] += 1
        for i in range(k):
            for j in range(len(centroids[i].votes)):
                maxVote = 0
                for op in counter[i][j]:
                    if counter[i][j][op] > maxVote:
                        maxVote = counter[i][j][op]
                        maxOption = op
                centroids[i].votes[j] = maxOption
    print "iteration time: %d" % times
    return centroids
cen = kMode(database, 2)
for i in range(2):
    print "cluster %d" % i
    stat = {"democrat" : 0, "republican" : 0}
    for record in database:
        if record.classification == i:
            stat[record.party] += 1
    print stat
    print ""

聚类结果还是说得过去的。。。=-=

K众数（K-modes）实际只是K均值的一个变体，其思路是一致的。在混合数值和标称值的数据中，两种方法实际可以结合使用。

K中值
不要和基于代表对象的K中心点混淆。K中值这个算法虽然《数据挖掘》一书中没提到，但大家在发现前面的问题后其实很容易可以想到。在数字图像处理中，类似的情况是椒盐噪声的去除，椒盐噪声一定程度上可以类比成离群值。如果我们使用均值滤波来去除，其效果一定没有中值滤波好，正是因为均值滤波中噪声会对最终结果有一定贡献率，而中值则是直接从样本中选取样例。
K中值在重新计算中心点的时候，使用的是曼哈顿中值，即

新中心点的每一维的值，都是其簇内样例中对应维的中值。K中值能够减少K均值的敏感性。

密集恐惧症者表示完全受不了某些聚类的效果图。。。。。。。。。。