8.1聚类的基本概念

  • 聚类就是在给定的数据集中根据特征的相似度或者距离，将数据集中的对象归并到若干个类中（事先并不知道，即数据集是没有label的）
    • 聚类是一种无监督学习
  • 聚类问题的求解，首先需要定义样本之间的距离或者相似度

8.1.1相似度和距离

  • 用于聚类的样本数据集D或者样本集合，假设有n个样本，每个样本的有n个属性，那么样本的集合就可以用一个大小为八、聚类Clustering - 图1的矩阵八、聚类Clustering - 图2来表示，矩阵的每一列表示一个样本的m个特征
  • 而常见的定义距离和相似度的方法有：

闵可夫斯基距离：对于两个向量，定义其闵可夫斯基距离为

八、聚类Clustering - 图3%5E%7B%5Cfrac%201p%7D%0A#card=math&code=d%7Bij%7D%3D%5Cleft%28%5Csum%7Bk%3D1%7D%5Em%7Cx%7Bik%7D-x%7Bjk%7D%7C%5Ep%5Cright%29%5E%7B%5Cfrac%201p%7D%0A&height=62&width=189)

闵可夫斯基距离中，当p=1时就是曼哈顿距离，p=2时就是欧式距离，p为八、聚类Clustering - 图4时就是切比雪夫距离，等价于各个坐标数值差的绝对值

马哈拉诺比斯距离：假设样本矩阵八、聚类Clustering - 图5的协方差矩阵是八、聚类Clustering - 图6，则马哈拉诺比斯的距离共识可以表示为：

八、聚类Clustering - 图7%5ETS%5E%7B-1%7D(xi-x_j)%5Cright%5D%0A#card=math&code=d%7Bij%7D%3D%5Cleft%5B%28x_i-x_j%29%5ETS%5E%7B-1%7D%28x_i-x_j%29%5Cright%5D%0A&height=24&width=224)

马哈拉诺比斯距离考虑了各个特征之间的相关性，通过协方差矩阵传递了这种相关性到两个样本的距离中，马哈拉诺比斯距离越大说明相似度越小

相关系数：可以用相关系数来表示样本之间的相似度，(概率论和数理统计中似乎学过这个只是)其定义是：

八、聚类Clustering - 图8(x%7Bkj%7D-%5Cbar%20x_j)%7D%7B%5Csum%5Climits%7Bk%3D1%7D%5Em(x%7Bki%7D-%5Cbar%20x_i)%5E2%5Csum%5Climits%7Bk%3D1%7D%5Em(x%7Bkj%7D-%5Cbar%20x_j)%5E2%7D%0A#card=math&code=r%7Bij%7D%3D%5Cfrac%7B%5Csum%5Climits%7Bk%3D1%7D%5Em%28x%7Bki%7D-%5Cbar%20xi%29%28x%7Bkj%7D-%5Cbar%20xj%29%7D%7B%5Csum%5Climits%7Bk%3D1%7D%5Em%28x%7Bki%7D-%5Cbar%20x_i%29%5E2%5Csum%5Climits%7Bk%3D1%7D%5Em%28x_%7Bkj%7D-%5Cbar%20x_j%29%5E2%7D%0A&height=93&width=251)

  • 其中八、聚类Clustering - 图9表示样本m个特征的平均值

夹角的余弦值：高中立体几何的公示：

八、聚类Clustering - 图10%5E%5Cfrac%2012%7D%0A#card=math&code=s%7Bij%7D%3D%5Cfrac%7B%5Cleft%3C%20x_i%2Cx_j%20%5Cright%3E%7D%7B%7C%7Cx_i%7C%7C_2%5Ctimes%7C%7Cx_j%7C%7C_2%7D%3D%5Cfrac%7B%5Csum%5Climits%7Bk%3D1%7D%5Emx%7Bki%7Dx%7Bkj%7D%7D%7B%5Cleft%28%5Csum%5Climits%7Bk%3D1%7D%5Emx%7Bki%7D%5E2%5Csum%5Climits%7Bk%3D1%7D%5Emx%7Bkj%7D%5E2%5Cright%29%5E%5Cfrac%2012%7D%0A&height=102&width=312)

8.1.2 类和簇的界定

  • 对于一个样本的集合G，有很多种方法来定义这个集合G是不是一个类或者一个簇，常见的定义方式有：
    • 集合G中任意两个点的距离都不超过常数T
    • 对于集合G中的一个样本，一定存在另一个样本使得二者的距离不超过常数T
    • 对于G中的一个样本，它和其他任意一个样本之间的距离的平均值不超过常数T
    • 对于集合G中的样本，任意两个点之间的距离不超过V且所有距离的平均值不超过T
  • 我们可以用一些特征来刻画一个类：
    • 类的均值八、聚类Clustering - 图11，也叫做类的中心：

八、聚类Clustering - 图12

  • 类的直径：八、聚类Clustering - 图13
    • 类和类之间的距离，也叫做连接linkage，也可以有多种定义方式
  • 最短距离（单连接）：两个类的样本之间的最短距离
  • 最长距离（完全连接）：两个类的样本之间的最长的距离
  • 中心距离：两个类的中心之间的距离
  • 平均距离：两个类之间的任意两个样本之间的距离的平均值

8.2 层次聚类

  • 层次聚类是假设类别之间存在层次结构，将样本聚合到层次化的类里面去，分为
    • 自顶向下的聚类(分裂)
    • 自底向上的聚类(聚合)
  • 聚合算法需要先确定三个要素，要素之间的组合就可以形成一系列的聚类算法
    • 定义距离或者相似度
    • 确定合并的规则
    • 确定算法停止的条件

8.2.1 聚合聚类

  • 算法的步骤
    • 对于n个样本点计算其距离，构成一个八、聚类Clustering - 图14的矩阵
    • 构造n个不同的类，每个类只包含一个样本
    • 合并类间距离最小的两个类，以最短距离为类间距离，构造一个新类
    • 计算新的类和当前各个类的距离，如果类的个数为1则停止计算，否则返回上一步
  • 最后输出的结果：
    • 一个包含所有样本的类和其中的各个子类

8.3 K-means算法

8.3.1基本概念

  • k均值聚类是一种基于样本集合划分的聚类算法，k均值将样本集合划分称为k个子集，每个样本只属于一个类，因此是一种硬聚类的算法
  • 对于给定的样本集合八、聚类Clustering - 图15，每个样本由一个特征向量表示，我们将样本集合划分成k个八、聚类Clustering - 图16类，且满足八、聚类Clustering - 图17和八、聚类Clustering - 图18，我们用C来表示这样的一种划分关系，一种划分关系也就对应着一种K均值分类的结果
    • 划分C是一种多对一的函数，八、聚类Clustering - 图19%3DG_j#card=math&code=C%28x_i%29%3DG_j)表明八、聚类Clustering - 图20最后被划分到了八、聚类Clustering - 图21类别中
  • K均值聚类在训练的过程中通过损失函数最小化来选择最优的划分函数C

8.3.2损失函数

  • 采用欧式距离，并用所有点到其所在类的中心的欧式距离的平方和作为损失函数：

八、聚类Clustering - 图22%3D%5Csum%7Bl%3D1%7D%5Ek%5Csum%7BC(i)%3Dl%7D%7C%7Cxi-%5Cbar%20x_l%7C%7C%5E2%0A#card=math&code=W%28C%29%3D%5Csum%7Bl%3D1%7D%5Ek%5Csum_%7BC%28i%29%3Dl%7D%7C%7Cx_i-%5Cbar%20x_l%7C%7C%5E2%0A&height=57&width=208)

  • 因此实际上K均值聚类就是求解一个最优化的问题：

八、聚类Clustering - 图23%3D%5Carg%5Cmin%5Csum%7Bl%3D1%7D%5Ek%5Csum%7BC(i)%3Dl%7D%7C%7Cxi-%5Cbar%20x_l%7C%7C%5E2%0A#card=math&code=C%5E%2A%3D%5Carg%5Cmin%20W%28C%29%3D%5Carg%5Cmin%5Csum%7Bl%3D1%7D%5Ek%5Csum_%7BC%28i%29%3Dl%7D%7C%7Cx_i-%5Cbar%20x_l%7C%7C%5E2%0A&height=57&width=365)

8.3.3 K均值聚类的学习过程

  • K均值的学习过程首先要随机选K个样本作为初始的K个类的中心点，然后进行如下步骤：
  • 对于每个样本点，计算其与K个类的中心点，然后在选择最近的中心点所在的类作为该样本点的类
  • 第二步的循环完成之后，在每个类中找到使得到该类中的所有样本点距离最小的中心点，使得该类中距离，也就是该类的样本中所有点的均值

八、聚类Clustering - 图24%3Dl%7D%20xi%0A#card=math&code=m_l%3D%5Cfrac%201%20n_l%20%5Csum%7BG%28i%29%3Dl%7D%20x_i%0A)

  • 然后回到第二步用新的K个中心点计算出新的分类，重复上述步骤直到划分结果不再改变，就得到了K均值聚类的最终结果

8.3.4 K均值聚类的算法特性

  • K均值聚类属于启发式的方法，不能保证收敛到全局的最优，初始中心的选择会直接影响聚类的结果，要注意的时候类中心的移动往往不会有非常大的波动
  • 不同的类别数K会带来不同的聚类结果，一般来说分类的平均直径会随着K的增大先减小后不变

8.3.5 K-means算法的代码实现

  • 注：这个做法比较垃圾，没有实现向量化的运算
  1. def kmeans(x, k):
  2.     """
  3.     KMEANS K-Means clustering algorithm
  5.         Input:  x - data point features, n-by-p maxtirx.
  6.                 k - the number of clusters
  8.         OUTPUT: idx  - cluster label
  9.                 centers - cluster centers, K-by-p matrix.
  10.                 iteration_number - cluster centers of each iteration, (iter, k, p)
  11.                         3D matrix.
  12.     """
  14.     # begin answer
  15.     def get_current_center(centers, k, x):
  16.         dist = np.zeros(k)
  17.         for j in range(k):
  18.             dist[j] = np.linalg.norm((centers[j] - x))
  19.         min_idx = np.argmin(dist)
  20.         return min_idx
  22.     def get_new_center(index, x, k):
  23.         count = 0
  24.         sum_x = np.zeros((1, x.shape[1]))
  25.         for i in range(len(index)):
  26.             if index[i] == k:
  27.                 count += 1
  28.                 sum_x += x[i]
  29.         return sum_x / count
  31.     N, p = x.shape
  32.     max_iter, iteration = 2, 0
  33.     idx = np.zeros(N, dtype=np.int32)
  34.     centers = np.zeros((k, p))
  35.     iteration_number = np.zeros((max_iter + 1, k, p))
  37.     # 初始化K个不同的center，随机选择数据集中的点作为中心
  38.     first_centers = np.random.randint(0, N, k)
  39.     for i in range(k):
  40.         centers[i] = x[first_centers[i]]
  41.     iteration_number[0] = centers
  42.     while iteration < max_iter:
  43.         # 开始迭代，每次先根据中心求出点与中心的距离，然后选择最小的点
  44.         for i in range(N):
  45.             idx[i] = get_current_center(iteration_number[iteration], k, x[i])
  46.         for i in range(k):
  47.             res = get_new_center(idx, x, i)
  48.             centers[i] = res
  49.         iteration += 1
  50.         iteration_number[iteration] = centers
  52.     # end answer
  54.     return idx, centers, iteration_number

8.4 谱聚类Spectral Clustering

8.4.1 图分割的观点

  • 谱聚类将数据点看成图中的节点
    • 每两个节点之间都有一条边连接，每条边有一定的权重W
    • 权重高表示两个点比较相近，权重地代表不相似
  • 举类操作就可以看作是图的分割，我们可以把K聚类的目标等价为将图划分成K个不同的部分
    • 我们可以将需要切掉的边的权重设置的尽可能小，对于二聚类问题，我们可以定义：

八、聚类Clustering - 图25%3D%5Csum%7Bi%5Cin%20A%2C%20%20j%5Cin%20B%7Dw%7Bij%7D%0A#card=math&code=%7Bcut%7D%28A%2C%20B%29%3D%5Csum%7Bi%5Cin%20A%2C%20%20j%5Cin%20B%7Dw%7Bij%7D%0A)

  • 因此我们的目标就可以变成将这个cut函数最小化，即：

八、聚类Clustering - 图26%0A#card=math&code=%5Cmin%7Bcut%7D%28A%2CB%29%0A)

  • 但是cut函数只考虑了各个cluster之间的边，而没有考虑内部的边，因此我们可以定义计算内部距离之和的函数association：

八、聚类Clustering - 图27%3D%5Csum%7Bi%5Cin%20A%2Cj%5Cin%20A%7Dw%7Bij%7D%0A#card=math&code=assoc%28A%2CA%29%3D%5Csum%7Bi%5Cin%20A%2Cj%5Cin%20A%7Dw%7Bij%7D%0A)

  • 因此我们制定新的分割标准，同时顾及到cluster内部和外部的各条边，并使得分割的结果更加平衡，用V来表示图G中所有的顶点构成的集合，定义Normalized-Cut：

八、聚类Clustering - 图28%3D%5Cfrac%7B%7Bcut%7D(A%2C%20B)%7D%7Bassoc(A%2CV)%7D%2B%5Cfrac%7B%7Bcut%7D(A%2C%20B)%7D%7Bassoc(B%2CV)%7D%0A#card=math&code=Ncut%28A%2CB%29%3D%5Cfrac%7B%7Bcut%7D%28A%2C%20B%29%7D%7Bassoc%28A%2CV%29%7D%2B%5Cfrac%7B%7Bcut%7D%28A%2C%20B%29%7D%7Bassoc%28B%2CV%29%7D%0A)

8.4.2 Normalize-Cut的计算

  • 我们可以定义一系列量来表示，假设图中共有八、聚类Clustering - 图29个不同的节点八、聚类Clustering - 图30，其接邻矩阵记为八、聚类Clustering - 图31，那么对于二聚类问题，我们可以记八、聚类Clustering - 图32如果该节点是A类的，否则记为-1，令：

八、聚类Clustering - 图33

八、聚类Clustering - 图34%0A#card=math&code=D%3D%5Cmathrm%7Bdiag%7D%28d_1%2Cd_2%2C%5Cdots%2Cd_N%29%0A)

八、聚类Clustering - 图35

  • 而根据之前的定义，我们可以推出：

八、聚类Clustering - 图36%3Dassoc(A%2CV)-assoc(A%2CA)%3Dassoc(B%2CV)-assoc(B%2CB)%0A#card=math&code=cut%28A%2CB%29%3Dassoc%28A%2CV%29-assoc%28A%2CA%29%3Dassoc%28B%2CV%29-assoc%28B%2CB%29%0A)

  • 我们可以用D来表示assoc函数的值：

八、聚类Clustering - 图37%3D%5Csum%7Bi%5Cin%20A%2Cj%5Cin%20V%7Dw%7Bij%7D%3D%5Cfrac%2014(1%2Bx)%5ETD(1%2Bx)%5C%5Cassoc(B%2CV)%3D%5Csum%7Bi%5Cin%20B%2Cj%5Cin%20V%7Dw%7Bij%7D%3D%5Cfrac%2014(1-x)%5ETD(1-x)%5C%5Cassoc(A%2CA)%3D%5Csum%7Bi%5Cin%20A%2Cj%5Cin%20A%7Dw%7Bij%7D%3D%5Cfrac%2014(1%2Bx)%5ETW(1%2Bx)%5C%5Cassoc(B%2CB)%3D%5Csum%7Bi%5Cin%20B%2Cj%5Cin%20B%7Dw%7Bij%7D%3D%5Cfrac%2014(1-x)%5ETW(1-x)%0A#card=math&code=assoc%28A%2CV%29%3D%5Csum%7Bi%5Cin%20A%2Cj%5Cin%20V%7Dw%7Bij%7D%3D%5Cfrac%2014%281%2Bx%29%5ETD%281%2Bx%29%5C%5Cassoc%28B%2CV%29%3D%5Csum%7Bi%5Cin%20B%2Cj%5Cin%20V%7Dw%7Bij%7D%3D%5Cfrac%2014%281-x%29%5ETD%281-x%29%5C%5Cassoc%28A%2CA%29%3D%5Csum%7Bi%5Cin%20A%2Cj%5Cin%20A%7Dw%7Bij%7D%3D%5Cfrac%2014%281%2Bx%29%5ETW%281%2Bx%29%5C%5Cassoc%28B%2CB%29%3D%5Csum%7Bi%5Cin%20B%2Cj%5Cin%20B%7Dw%7Bij%7D%3D%5Cfrac%2014%281-x%29%5ETW%281-x%29%0A)

  • 那么cut可以表示为：

八、聚类Clustering - 图38%3D%5Cfrac%2014(1%2Bx)%5ET(D-W)(1%2Bx)%0A#card=math&code=cut%28A%2CB%29%3D%5Cfrac%2014%281%2Bx%29%5ET%28D-W%29%281%2Bx%29%0A)

  • 这样一来，Ncut可以进行计算：

八、聚类Clustering - 图39

  • 其中八、聚类Clustering - 图40，进一步我们令：

八、聚类Clustering - 图41-b(1-x)%0A#card=math&code=y%3D%281%2Bx%29-b%281-x%29%0A)

  • 在接着通过一连串的运算之后，我们最终的优化目标就变成了：

八、聚类Clustering - 图42y%7D%7By%5ETDy%7D%5C%5C%5Cmathrm%20%7Bs.t%5Cquad%7D%20y%5ETD1%3D0%0A#card=math&code=%5Cmin%20%5Cfrac%7By%5ET%28D-W%29y%7D%7By%5ETDy%7D%5C%5C%5Cmathrm%20%7Bs.t%5Cquad%7D%20y%5ETD1%3D0%0A)

  • 我们令八、聚类Clustering - 图43，那么这个矩阵八、聚类Clustering - 图44就叫做这张图的Graph Laplacian，并且这是一个半正定的矩阵
  • 一通莫名其妙的优化过后得到的结论就是最优时候的y就是拉普拉斯矩阵L的最大特征值所对应的特征向量

8.4.3 谱聚类算法的具体步骤

  • 对于一个K聚类问题，如果K超过2，我们可以进行若干次二聚类最终得到K聚类的结果，因此我们只考虑二聚类
  • 对于一个二聚类问题，谱聚类算法的步骤如下：
    • 构建图G：
      • 使用KNN图
      • 或者使用heat kernel
    • 计算特征值：
      • 计算拉普拉斯矩阵L的特征值和特征向量
      • 将图G中的点通过特征向量映射到一个低维表示当中去
    • 使用传统的聚类算法如K-Means