Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

1.重点归纳

1）聚类的核心概念是相似度（similarity）或距离（distance），有多种相似度或距离的定义。因为相似度直接影响聚类的结果，所以其选择是聚类的根本问题。

（1）闵可夫斯基距离（Minkowski distince），p=2时为欧氏距离，p=1时为曼哈顿距离。

（2）马哈拉诺比斯距离（马氏距离）

（3）相关系数

（4）余弦相似度

2）类与类之间的距离

（1）最短距离或单连接

（2）最长距离或完全连接

（3）中心距离：两个类中心的距离。

（4）平均距离：任意两个样本之间的距离的平均值。

3）层次聚类两种方法

（1）聚合聚类开始将每个样本各自分到一个类，之后将相距最近的两类合并，建立一个新的类，重复此操作直到满足停止条件。

（2）分裂聚类开始将所有样本分到一个类，之后将已有类中相距最远的样本分到两个新的类，重复此操作直到满足停止条件。

（3）聚合聚类需要预先确定的三个要素：距离或相似度、合并规则、停止条件。

4）0-1规格化

由于数据之间的量纲不相同，不方便比较，所以需要将数据统一到0~1的范围，将其转化为无量纲的纯数值，便于不同单位或量级的指标能够进行比较和加权。

5）k均值聚类

（1）模型：k均值聚类的目标是将n个样本分到k个不同的类或簇中，属于硬聚类。K均值聚类的模型是一个从样本到类的函数。

（2）策略：k均值聚类的策略是通过损失函数的最小化选取最优的划分或函数C*，采用欧氏距离平方作为样本之间的距离，最小化样本与其所属类的中心之间的距离的总和为损失函数（成本函数时各个类畸变程度之和）。

（3）总体特性

• 基于划分的聚类方法
• 类别数k事先指定
• 以欧氏距离平方表示样本之间的距离，以中心或样本均值表示类别
• 以样本和其所属类的中心之间的距离的总和为最优化的目标函数
• 得到的类别是平坦的，非层次化的
• 算法时迭代算法，不能保证得到全局最优

（4）评估方法

• 轮廓系数（Sihouette Coefficient）结合了聚类的凝聚度（Cohesion）和分离度（Separation），用于评估聚类的效果。
• CH指标（Calinski-Harabaz Index）：CH指标通过计算类中各点与类中心的距离平方和来独立类内的紧密度，通过计算各类中心与数据集中心点距离平方和来度量数据的分离度，CH指标由分离度和紧密度的比值得到。

（5）k值选择方法一

• 尝试用不同的k值聚类，检查各自得到聚类结果的“质量”，推测最优的k值。
• 聚类结果的质量可以用类的平均直径类衡量。一般地，类别数变小时，平均直径会增加，类别数变大超过某个值以后，平均直径会不变；而这个值就是最优的k值。

（6）k值选择方法二：肘部法则

• 肘部法则会把不同k值的成本函数值画出来，随着k值的增大，平均畸变程度（成本函数）会减少。随着k值继续增大，平均畸变程度改善效果会不断减少。
• k值增大过程中，畸变程度的改善效果下降幅度最大的位置对应的值就是肘部，对应的k值为最优聚类数量。

注：上图是k值从1到2时，平均畸变程度变化最大，因此最佳k值是2。

2.聚类方法

1）聚类是针对给定的样本，依据它们特征的相似度或距离，将其归并到若干个“类”或“簇”的数据分析问题。

（1）相似的样本聚集在相同的类，不相似的样本分散在不同的类。

（2）样本之间的相似度或距离起着重要作用。

2）聚类的目的是通过得到的类或簇来发现数据的特点或对数据进行处理。

3）聚类算法很多，最常用的距离算法：层次聚类（hierarchical clustering）和k均值聚类（k-mean clustering）。

层次聚类又有聚合（自下而上）和分裂（自上而下）两种方法。

3.聚类的基本概念

1）相似度或距离

（1）聚类的核心概念是相似度（similarity）或距离（distance），有多种相似度或距离的定义。因为相似度直接影响聚类的结果，所以其选择是聚类的根本问题。

（2）闵可夫斯基距离（Minkowski distince）

• 距离越大相似度越小。
• m维特征样本和样本的闵可夫斯基距离：
• p=1时为曼哈顿距离：
• p=2时为欧氏距离：
• 时为切比雪夫距离：

（3）马哈拉诺比斯距离（马氏距离）

• 另一种常用的相似度，考虑各个特征之间的相关性并与各个特征的尺度无关。马氏距离越大相似度越小。
• 样本集合X的协方差矩阵为S，m维特征样本和样本的马哈拉诺比斯距离：
• S为单位矩阵时，马氏距离就是欧氏距离，所以马氏距离是欧氏距离的推广。

（4）相关系数

• 样本之间的相似度也可以用相关系数（correlation coefficient）来表示，相关系数的绝对值越接近于1，表示样本越相似；越接近于0，表示样本越不相似。
• 相关系数公式：就是用、的协方差除以的标准差和的标准差，可以看成一种剔除了两个变量量纲影响、标准化后的特殊协方差。
• 可以反映两个变量变化时是同向还是反向，如果同向变化就为正，反向变化就为负。

（5）夹角余弦

• 夹角余弦越接近1，表示样本越相似；越接近0，表示样本越不相似。
  • 分子是两个向量的点积，相同位置的特征值相乘再求和。
  • 分母是两个样本的向量长度。

（6）用距离度量相似度时，距离越小样本越相似；用相关系数时，相关系数越大样本越相似。不同的相似度度量得到的结果并不一定一致，所以聚类时，选择适合的距离或相似度非常重要。

2）类或簇

（1）通过聚类得到的类或簇，本质上是样本的子集。

• 硬聚类：一个样本只能属于一个类，或类的交集为空集。
• 软聚类：一个样本可以属于多个类，或类的交集不为空集。

（2）类的均值，又称为类的中心

表示G中样本的个数

（3）类的直径（diameter），是类中任意两个样本之间的最大距离

表示样本和之间的距离

（4）类的样本散布矩阵与协方差矩阵

• 类的样本散布矩阵（scatter matrix）
• 类的样本协方差矩阵

3）类与类之间的距离

类与类之间的距离D(p,q)，也称为连接。

（1）最短距离或单连接

（2）最长距离或完全连接

（3）中心距离：两个类中心的距离。

（4）平均距离：任意两个样本之间的距离的平均值。

4.层次聚类

1）层次聚类假设类之间存在层次结构，将样本聚到层次化的类中。

（1）层次聚类两种方法

• 聚合（agglomerative）：自下而上聚类。
• 分裂（divisive）：自下而上

（2）层次聚类属于硬聚类

（3）聚合聚类开始将每个样本各自分到一个类，之后将相距最近的两类合并，建立一个新的类，重复此操作直到满足停止条件。

（4）分裂聚类开始将所有样本分到一个类，之后将已有类中相距最远的样本分到两个新的类，重复此操作直到满足停止条件。

2）聚合聚类需要预先确定的三个要素

（1）距离或相似度：闵可夫斯基距离、马哈拉诺比斯距离、相关系数、夹角余弦。

（2）合并规则：一般是类间距离最小、类间距离可以是最短距离、最长距离、中心距离、平均距离。

（3）停止条件：可以是类的个数达到阈值、类的直径超过阈值。

3）如果采用欧氏距离为样本之间距离；类间距离最小为合并规则，其中最短距离为类间距离；类的个数为1为停止条件。

（1）计算n个样本两两之间的欧氏距离{dij}

（2）构造n个类，每个类只包含一个样本

（3）合并类间距离最小的两个类，其中最短距离为类间距离，构建一个新类

（4）计算新类与当前各类的距离。若类的个数为1，终止计算，否则回到上一步。

5.k均值聚类

1）k均值聚类将样本集合划分为k个子集，构成k个类，将n个样本分到k个类中，每个样本到其所属类的中心的距离最小。

2）模型：k均值聚类的目标是将n个样本分到k个不同的类或簇中，属于硬聚类。K均值聚类的模型是一个从样本到类的函数。

3）策略

（1）k均值聚类的策略是通过损失函数的最小化选取最优的划分或函数C*。

（2）采用欧氏距离平方作为样本之间的距离。

（3）定义样本与其所属类的中心之间的距离的总和为损失函数（成本函数时各个类畸变程度之和）。

（4）k均值聚类就是求解最优化问题

4）算法

（1）k均值聚类的算法是一个迭代的过程，每次迭代包括两个步骤

• 首先选择k个类的中心，将样本逐个指派到其最近的中心的类中，得到聚类结果；
• 然后更新每个类的样本的均值，作为新的中心；重复以上两个步骤，直到收敛为止。

（2）k均值聚类算法实现，复杂度是O(mnk)（m：维数，n：样本个数，k：类别个数）

1. 初始化。令t=0，随机 选择k个样本作为初始化聚类中心
2. 对样本进行聚类。对固定的类中心，计算每个样本到类中心的距离，将每个样本指派到与其最近的中心的类中，构成聚类结果。
3. 计算新的类中心。对聚类结果，计算当前各个类中的样本的均值，作为新的类中心。
4. 如果迭代收敛或符合停止条件，输出。否则，令t=t+1，返回第2步。

5）算法特性

（1）总体特性

• 基于划分的聚类方法
• 类别数k事先指定
• 以欧氏距离平方表示样本之间的距离，以中心或样本均值表示类别
• 以样本和其所属类的中心之间的距离的总和为最优化的目标函数
• 得到的类别是平坦的，非层次化的
• 算法时迭代算法，不能保证得到全局最优

（2）收敛性

k均值属于启发式方法，不能保证收敛全局最优，初始中心的选择会直接影响聚类的结果。

（3）初始类的选择

• 选择不同的初始中心，会得到不同的聚类结果。
• 初始中心的选择：比如可以用层次化聚类对样本进行聚类，得到k个类时停止，然后从每个类中选择一个与中心距离最近的点。

（4）类别数k的选择

• 实际应用中最优的k值是不知道的
• 解决方法：尝试用不同的k值聚类，检查各自得到聚类结果的“质量”，推测最优的k值。
• 聚类结果的质量可以用类的平均直径类衡量。一般地，类别数变小时，平均直径会增加，类别数变大超过某个值以后，平均直径会不变；而这个值就是最优的k值。

5.外部资料补充

1）0-1规格化

由于数据之间的量纲不相同，不方便比较，所以需要将数据统一到0~1的范围，将其转化为无量纲的纯数值，便于不同单位或量级的指标能够进行比较和加权。

2）评估方法一：轮廓系数（Sihouette Coefficient）结合了聚类的凝聚度（Cohesion）和分离度（Separation），用于评估聚类的效果。

（1）该值处于-1~1之间，值越大，表示效果越好。

（2）计算方法

• 对于第i个元素xi，计算xi与其同一个簇内的所有其他元素距离的平均值ai，用于量化簇内的凝聚度。
• 选择外的一个簇b，计算xi与b中所有点的平均距离，遍历所有其他簇，找到最近的这个平均距离bi，用于量化簇之间分离度。
• 对于元素xi，轮廓系数
• 计算所有x的轮廓系数，求出平均值即为当前聚类的整体轮廓系数。

（3）sklearn中的轮廓系数计算：sklearn.metrics.sihouette_score。

3）评估方法二：CH指标（Calinski-Harabaz Index）

（1）CH指标通过计算类中各点与类中心的距离平方和来独立类内的紧密度，通过计算各类中心与数据集中心点距离平方和来度量数据的分离度，CH指标由分离度和紧密度的比值得到。

（2）CH值越大代表着类自身越紧密，类与类之间越分散，即更优的距离结果。

（3）sklearn中CH计算：sklearn.metrics.calinski_harabaz_score。

4）k值选择方法：肘部法则

（1）肘部法则会把不同k值的成本函数值画出来，随着k值的增大，平均畸变程度（成本函数）会减少，每个类包含的样本数会减少，于是样本离其中心会更近。

（2）随着k值继续增大，平均畸变程度改善效果会不断减少。

（3）k值增大过程中，畸变程度的改善效果下降幅度最大的位置对应的值就是肘部，对应的k值为最优聚类数量。

注：上图是k值从1到2时，平均畸变程度变化最大，因此最佳k值是2。