聚类分析知识介绍

1.聚类理论

当你观察某些数据源时，很可能会发现数据以某种形式形成聚类(cluster)。比如考察一个城市的城区中，居民收入的分布，一般可以发现低等收入、中等收入、高等收入和富豪人群在居住地上会形成聚类。类似的还有考察一个网站的用户分布情况，一般可以发现不同年龄的用户在关注点上形成聚类。

聚类的一个通俗的定义是，将物理或抽象对象的集合分成由类似的对象组成的多个类的过程被称为聚类。俗话说：“物以类聚，人以群分”，由聚类所生成的簇是一组数据对象的集合，这些对象与同一个簇中的对象彼此相似，与其他簇中的对象相异。

一个聚类对商务分析的支持例子是，我们可以在用户样本中使用聚类分析，发现客户群，进而知道各类客户的特征，可以针对各种不同客户投放广告，这要比对所有客户都投放一模一样的广告要好得多。

(1)模型

对我们来说，每个输入都是d维空间中的一个向量，因此我们必须想方设法地把我们的原始输入转化成数字(这有时不是那么简单)。

k-均值算法(k-means)是一种最简单的聚类分析方法，它通常需要首先选出聚类k的数目，然后把输入划分成集合S(1)-S(k)，并使得聚类中每个数据到其所在聚类的均值(中心对象)的距离的平方之和最小化，这可以借助迭代算法来解决。

步骤如下：

1. 首先从d维空间中选出k个数据点作为初始聚类的均值(即中心点)。
2. 计算每个数据点到这些聚类的均值(即聚类中心)的距离，然后把各个数据点分配给距离它最近的那个聚类。
3. 如果所有数据点都不再被重新分配，就停止并保持现有聚类。
4. 如果仍然有数据点被重新分配，则重新计算均值，并返回第2步。

K-均值算法的核心代码：

class KMeans:
    def __init__(self, k):
        self.k = k          # 聚类数目k
        self.means = None   # 聚类均值列表
    # 计算与输入最接近的聚类
    def classify(self, input):
        return min(range(self.k),
                   key=lambda i: squared_distance(input, self.means[i]))
    # 计算过程
    def train(self, inputs):
        self.means = random.sample(inputs, self.k)  # 初始时状态时,从inputs中随机选取k个不同元素
        assignments = None
        while True:
            # 计算当前情况下,所有输入点的聚类分配情况
            new_assignments = map(self.classify, inputs)
            # 如果所有数据点不再被重新分配,就保持现有聚类并返回
            if assignments == new_assignments:
                return
            # 否则重新计算均值
            assignments = new_assignments
            for i in range(self.k):
                # 分别获取每个聚类中的所有点
                i_points = [p for p, a in zip(inputs, assignments) if a == i]
                # 为防止除零错误,要先判断每个聚类点集合长度是否为0
                if i_points:
                    self.means[i] = vector_mean(i_points) # 计算各个聚类中点坐标的均值

在解释上面KMeans的代码之前，有必要先来看几个公式和概念。

1. 计算点和点之间的距离(这里用欧几里得距离)，下面公式中，m是聚类中心，x是数据点，维度为r：

1. 更新簇平均值公式：

1. 计算准则函数E：

代码解析：

1. 在__init__方法(python中的类构造函数)中，需要事先指定聚类数self.k，怎么选择这个k值在后面会说明。self.means是各个聚类均值的列表，所以len(self.means) == self.k。

2. classify方法中，接受一个inputs参数，inputs参数在我们例子中是一个二维点坐标列表。关键的是下面这行代码：

return min(range(self.k), key=lambda i: squared_distance(input, self.means[i]))

classify会针对input(这里就是一个坐标)，计算它到所有聚类中心点的距离的最小值，并返回那个中心点所在聚类的下标。

1. 计算过程，K-Means的计算是一个迭代过程，会不断逼近最优解。

# 计算过程
def train(self, inputs):
    self.means = random.sample(inputs, self.k)  # 初始时状态时,从inputs中随机选取k个不同元素
    assignments = None
    while True:
        # 计算当前情况下,所有输入点的聚类分配情况
        new_assignments = map(self.classify, inputs)
        # 如果所有数据点不再被重新分配,就保持现有聚类并返回
        if assignments == new_assignments:
            return
        # 否则重新计算均值
        assignments = new_assignments
        for i in range(self.k):
            # 分别获取每个聚类中的所有点
            i_points = [p for p, a in zip(inputs, assignments) if a == i]
            # 为防止除零错误,要先判断每个聚类点集合长度是否为0
            if i_points:
                self.means[i] = vector_mean(i_points) # 计算各个聚类中点坐标的均值

首先从inputs中随机选取k个不同元素作为聚类的起始中心点。然后进入一个while True无限循环，在这个循环中，会不断计算输入中各个点分配给k个聚类的情况，assignments变量保存的是每个输入元素上个循环时所对应的聚类下标，一旦当前assignments和新计算出的assignments相等(意思是各个元素不再被重新分配聚类)，则退出，表示聚类完毕。

在无限循环中，分别获取每个聚类中的所有点，然后计算各个聚类中点坐标的均值，这里会用到”更新簇平均值公式“，然后把每个聚类的中心点更新为这个均值。

1. 执行代码

if __name__ == "__main__":
    inputs = [[-14,-5],[13,13],[20,23],[-19,-11],[-9,-16],[21,27],[-49,15],[26,13],[-46,5],[-34,-1],[11,15],[-49,0],[-22,-16],[19,28],[-12,-8],[-13,-19],[-41,8],[-11,-6],[-25,-9],[-18,-3]]
    random.seed(0)
    clusterer = KMeans(3)
    clusterer.train(inputs)
    print "3-means:"
    print clusterer.means
    print
    # 作图
    means_xs, means_ys = zip(*clusterer.means)
    xs, ys = zip(*inputs)
    plt.plot(means_xs, means_ys, 'ro')
    plt.plot(xs, ys, 'bs')
    plt.axis([-60, 40, -30, 40])
    plt.show()

结果如下：

3-means:
[[-43.800000000000004, 5.4], [-15.888888888888888, -10.333333333333332],         [18.333333333333332, 19.833333333333332]]

画图结果(蓝色点为输入数据点，红色为聚类中心)：

把聚类k值换成2试试：

if __name__ == "__main__":
    inputs = [[-14,-5],[13,13],[20,23],[-19,-11],[-9,-16],[21,27],[-49,15],[26,13],[-46,5],[-34,-1],[11,15],[-49,0],[-22,-16],[19,28],[-12,-8],[-13,-19],[-41,8],[-11,-6],[-25,-9],[-18,-3]]
    random.seed(0)
    clusterer = KMeans(2)
    clusterer.train(inputs)
    print "2-means:"
    print clusterer.means
    means_xs, means_ys = zip(*clusterer.means)
    xs, ys = zip(*inputs)
    plt.plot(means_xs, means_ys, 'ro')
    plt.plot(xs, ys, 'bs')
    plt.axis([-60, 40, -30, 40])
    plt.show()

结果如下：

2-means:
[[-25.857142857142854, -4.714285714285714], [18.333333333333332, 19.833333333333332]]

画图结果：

(2)聚类数目k值的选择

刚才直接指定了k=3和k=2两种情况，有点完全靠蒙的感觉，因此一定有一种方法来帮助我们选择k值。

一个比较好理解的方法是以误差(即每个数据点到聚类中心的距离)的平方和作为k的函数，并画出该函数的图像，在其“弯曲”出寻找合适的k值。

# 聚类误差
def squared_clustering_errors(inputs, k):
    """finds the total squared error from k-means clustering the inputs"""
    clusterer = KMeans(k)
    clusterer.train(inputs)
    means = clusterer.means
    assignments = map(clusterer.classify, inputs)
    return sum(squared_distance(input,means[cluster])
               for input, cluster in zip(inputs, assignments))
# 绘制聚类误差
def plot_squared_clustering_errors(plt):
    ks = range(1, len(inputs) + 1)
    errors = [squared_clustering_errors(inputs, k) for k in ks]
    plt.plot(ks, errors)
    plt.xticks(ks)
    plt.xlabel("k")
    plt.ylabel("total squared error")
    plt.show()

    # 计算所有k产生的误差(k取值范围是1-len(inputs))
    print "errors as a function of k"
    for k in range(1, len(inputs) + 1):
        print k, squared_clustering_errors(inputs, k)
    print
    plot_squared_clustering_errors(plt) # 画图

结果：

errors as a function of k
1 15241.35
2 4508.73809524
3 1209.05555556
4 986.638888889
5 940.333333333
6 633.833333333
7 430.75
8 279.0
9 183.583333333
10 304.583333333
11 192.666666667
12 442.666666667
13 234.833333333
14 82.0
15 120.5
16 42.0
17 73.0
18 12.5
19 65.0
20 0.0

图像：

在k=3出有一个拐点，可以看到从k=1到k=3的误差下降趋势非常明显，从k=3之后，误差下降趋于平缓，到k=20时误差为0(这等于每个数据点自己形成一个聚类，自己是自己的中心点)。从数学角度来看，这个误差函数是k的函数，当它的导数从一个很大的值突然趋于0时，这个值就很适合作为聚类数目。