聚类方法整理

#聚类 #聚类算法
21

聚类方法整理

聚类（Clustering）：指按照某个特定的标准把一个数据集分割成不同的类或簇，使得同一个簇内的数据对象的相似性尽可能大，不在同一个簇中的数据对象的差异性也尽可能地大；聚类后同一类的数据尽可能聚集到一起，不同类数据尽量分离。

完整的聚类过程：

  1. 数据准备：特征标准化、降维
  2. 特征选择：从最初的特征中选择最有效的特征，并将其存储在向量中
  3. 特征提取：通过对选择的特征进行转换形成新的突出特征
  4. 聚类：基于某种距离函数进行相似度度量，获取簇
  5. 聚类结果评估：分析聚类结果，如距离误差和SSE等

1. 数据准备

1.1 特征标准化

特征标准化是特征工程中的一部分，顾名思义，就是指对原始数据进行一系列工程处理，将其进行提炼。本质上来讲，特征工程是一个数据表示和展现的过程。实际使用中，特征工程旨在剔除原始数据中的冗余和杂质，进而提炼出更具表征力的特征。

常用的几种标准化方法：

  1. 线性函数归一化（Min-Max Scaling）
对原始特征进行线性变换，将结果映射到

​[0,1]的范围上，从而实现对原始特征的等比例缩放。公式如下：

X_{norm}=\frac{X-X_{min}}{X_{max}-X_{min}}
该方法不足之处在于，当有新数据引入时，所有特征值都需要重新定义。
  1. 零均值标准化（Z-Score Normalization）
一种基于原始特征的均值和标准差进行标准化的方法，它会将特征映射到均值为0，偏差为1的分布上。具体来说，假设特征的均值为

​\mu，标准差为​\sigma，那么归一化的公式为;

z=\frac{x-\mu}{\sigma}
在使用梯度下降的方法求解最优化问题时，标准化/归一化可以加快梯度下降的求解速度，提升模型收敛速度。
  1. ​L_1/L_2范数标准化
如果只是为了统一量纲，那么通过

​L_2范数整体标准化也是可以的，具体方法是求出每个样本特征向量​x的​L_2范数​||x||^2，然后用​x/||x||^2代替原本特征即可。当然​L_1范数标准化也是可以的，即用​x/||x||^1代替原本特征。

  1. 中心化
主要是在PCA降维中，此时我们求出特征

​x的平均值​mean后，用​x-mean代替原特征，也就是特征的均值变成了0，但是方差并不改变。

  1. 其它
在实际案件中可以根据输入数据的情况，形式，一些先验特征来选择特征归一化的方式。其实特征归一化本质上也就是一种映射方式。特征标准化也就是一个预处理的方式，可以对案件最后的输出数据产生有益效果才是根本目的。比如通过

​Sigmoid函数进行归一化映射，只保留注意区域。或是通过​tanh或是​log进行映射，都是可取的方法。

1.2 特征降维

在实际应用中，当特征个数增加到某一个临界点后，继续增加反而会导致分类器的性能变差。

对于高维数据，维度灾难使解决模式识别问题非常困难，此时往往要求首先降低特征向量的维度。

降低特征向量维度的可行性分析：

  • 特征向量往往是包含冗余信息的
  • 有些特征可能与分类问题无关
  • 特征之间存在着很强的相关性

降低维度的方法：

  1. 特征组合：讲几个特征组合在一起，形成新的特征
  2. 特征选择：选择现有的特征集的一个子集

针对不同目标有不同的训练算法：

  • 最小化重构误差（主成分分析，PCA）
  • 最大化类别可分性（线性判别分析，LDA）
  • 最小化分类误差（判别训练，discriminative training）
  • 保留最多细节的投影（投影寻踪，projection pursuit）
  • 最大限度地使各特征之间独立（独立成分分析，ICA）

2. 特征选择

特征选择是特征工程中的重要问题，其目标是寻找最优特征子集。特征选择能剔除不相关或冗余的特征，从而达到减少特征个数，提高模型精确度，减少运行时间的目的

一般流程：

  1. 生成子集：搜索特征子集，为评价函数提供特征子集
  2. 评价函数：评价特征子集的好坏
  3. 停止准则：与评价函数相关，一般是阈值，评价函数达到一定标准后就可停止搜索
  4. 验证过程：在验证数据集上验证选出来的特征子集的有效性

三大类方法：

  • 过滤法（Filter）：按照==发散性==或==相关性==对各个特征进行评分，设定阈值或者待选择特征的个数进行筛选
  • 包装法（Wrapper）：根据目标函数（预测效果评分）,每次选择若干特征，或者排除若干特征
  • 嵌入法（Embedded）：先使用某些机器学习的模型进行训练，得到各个特征的权值系数，根据系数从大到小选择特征（类似于Filter不过需要通过训练获取系数）

2.1 过滤法

过滤法的基本思想是：分别对每个特征​x_i，计算​x_i相对于类别标签​y的信息量​S(i)，得到​n个结果。然后将​n个​S(i)按照从大到小排序，输出前​k个特征。显然，这样复杂度大大降低。那么关键的问题就是使用什么样的方法来度量​S(i)，我们的目标是选取与​y关联最密切的一些特征​x_i。

  • Pearson相关系数
皮尔森相关系数是一种最简单的，能帮助理解特征和响应变量之间关系的方法，衡量的是变量之间的线性相关性，结果的取值区间为

​[-1,1] ，​-1表示完全的负相关(这个变量下降，那个就会上升)，​+1表示完全的正相关，​0表示没有线性相关性。Pearson Correlation速度快、易于计算，经常在拿到数据(经过清洗和特征提取之后的)之后第一时间就执行。

Pearson相关系数的一个明显缺陷是，作为特征排序机制，他只对线性关系敏感。如果关系是非线性的，即便两个变量具有一一对应的关系，Pearson相关性也可能会接近 0 。
  • 卡方验证
经典的卡方检验是检验类别型变量对类别型变量的相关性。假设自变量有

​N种取值，因变量有​M种取值，考虑自变量等于​i且因变量等于​j的样本频数的观察值与期望的差距，构建统计量：

\chi^2 = \sum\frac{(A-E)^2}{E}
不难发现，这个统计量的含义简而言之就是自变量对因变量的相关性。
  • 互信息和最大信息系数
经典的互信息也是评价

类别型变量对类别型变量的相关性的，互信息公式如下：

MI(x_i,y)=\sum_{x_i\in0,1}\sum_{y\in0,1}p(x_i,y)\log\frac{p(x_i,y)}{p(x_i)p(y)}
想把互信息直接用于特征选择其实不是太方便：
  1. 它不属于度量方式，也没有办法归一化，在不同数据及上的结果无法做比较
  2. 对于连续变量的计算不是很方便（​X和​Y都是集合，​x_i，​y都是离散的取值），通常变量需要先离散化，而互信息的结果对离散化的方式很敏感

最大信息系数克服了这两个问题。它首先寻找一种最优的离散化方式，然后把互信息取值转换成一种度量方式，取值区间在 [0,1] 。

  • 距离相关系数
距离相关系数是为了克服Pearson相关系数的弱点而生的。在

​x和​x^2这个例子中，即便Pearson相关系数是 0 ，我们也不能断定这两个变量是独立的（有可能是非线性相关）；但如果距离相关系数是 0 ，那么我们就可以说这两个变量是独立的。

尽管有MIC和距离相关系数在了，但当变量之间的关系接近线性相关的时候，Pearson相关系数仍然是不可替代的。

第一、Pearson相关系数计算速度快，这在处理大规模数据的时候很重要。

第二、Pearson相关系数的取值区间是[-1，1]，而MIC和距离相关系数都是[0，1]。这个特点使得Pearson相关系数能够表征更丰富的关系，符号表示关系的正负，绝对值能够表示强度。当然，Pearson相关性有效的前提是两个变量的变化关系是单调的。
  • 方差选择法
过滤特征选择法还有一种方法不需要度量特征

​x_i和类别标签​y的信息量。这种方法先要计算各个特征的方差，然后根据阈值，选择方差大于阈值的特征。

例如，假设我们有一个具有布尔特征的数据集，并且我们要删除超过80％的样本中的一个或零（开或关）的所有特征。布尔特征是伯努利随机变量，这些变量的方差由下式给出:
Var[X] = p(1-p)

2.2 包装法

基本思想：基于hold-out方法，对于每一个待选的特征子集，都在训练集上训练一遍模型，然后在测试集上根据误差大小选择出特征子集。需要先选定特定算法，通常选用普遍效果较好的算法，例如Random Forest，SVM，KNN等等。

2.3 嵌入法

  • 基于惩罚项的特征选择法，通过​L_1正则项来选择特征：​L_1正则方法具有稀疏解的特征，因此天然具备特征选择的特性。
  • 基于学习模型的特征排序，这种方法的思路是直接使用要用的机器学习算法，针对每个单独的特征征和响应变量建立预测模型。假如某个特征和响应变量之间的关系是非线性的，可以用基于树的方法（决策树、随机森林）、或者扩展的线性模型等。基于树的方法比较易于使用，因为他们对非线性关系的建模比较好，并且不需要太多的调试。但要注意过拟合问题，因此树的深度最好不要太大，再就是运用交叉验证。通过这种训练对特征进行打分获得相关性后再训练最终模型。

3. 特征提取

通过对选择的特征进行转换形成新的突出特征

在图像处理中，可以将特征分为

初级特征：

  • 灰度值
  • 梯度值（​x方向，​y方向，幅值）
  • 像素位置
  • 梯度方向

局部特征：

描述一块区域，使其具有高可区分度。局部特征应有特点：可重复性，可区分性，准确性，有效性，鲁棒性。

  1. SIFT特征描述子（尺度不变特征变换）
  2. HOG特征
  3. SURF特征描述子
  4. ORB特征描述子
  5. LBP特征描述子
  6. HAAR

上述所有特征都是已有的一些特征提取手段，各自有其自身的特性。但是实际情况是多变的，需要考虑的方面有很多，适用程度不同，所以也就需要通过上述特征标准化、降维，特征选择以及这一步特征提取获取实际问题中需要的特征。这一步骤中每一个特征都可以进行展开，在这些特征的基础上进行改进。而在改进的过程中还会有若干个问题有待解决。

在使用这些特征的时候一定要想好这个特征代表了什么，这些特征相近的集合（簇类）能够代表什么。一切使用都要在有逻辑支撑的条件下。

4. 聚类

聚类是一种目的，将一组数据通过无监督的方式聚成若干簇类。获取簇类有很多种方法，不过无论通过哪种聚类方法都离不开数据的相似度度量。

4.1 数据相似度度量方法

4.1.1 ​L_p范数/闵可夫斯基（Minkowski）距离

d(x,y) = [\sum_{i=1}^{n}(x_i-y_i)^p]^{\frac{1}{p}}

其中在​p=1,2,\infty时，分别对应了曼哈顿距离，欧几里得距离与切比雪夫距离。

这几个距离的缺点：

  • 没有考虑各个特征之间的量纲，不过在特征标准化时就可以解决此问题
  • 没有考虑各个特征分布的期望和方差等统计量

4.1.2 杰卡德相似系数（Jaccard）

J(A,B)=\frac{|A\cap B|}{|A\cup B|}

杰卡德相似系数主要用于计算符号度量或布尔值度量的个体间的相似度，因为个体的特征属性都是由符号度量或者布尔值标识，因此无法衡量具体差异值的大小，只能获得是否相同这个结果。

4.1.3 余弦相似度（cosine sililarity）

余弦相似度用向量空间中两向量夹角的余弦值作为衡量两个个体之间差异的大小。余弦值越接近1表示两个向量越相似。

\cos\theta=\frac{A\cdot B}{|A|\times|B|}

余弦相似度相比于距离度量，其更加注重两个向量在方向上的差异，而非距离或者长度差异。

4.1.4 皮尔逊相关系数（Pearson Correlation Coefficient）

皮尔逊相关系数（Pearson Correlation）是衡量向量相似度的一种方式。输出范围为-1到+1，其中0代表无相关性，负值代表负相关，正值代表正相关。皮尔逊相关系数在欧几里德距离上做出了优化，对向量的值做了中心化处理，即对两个向量中的所有维度都减去元素的平均值，中心化后所有维度的平均值基本为0；然后对中心化结果求余弦距离，但余弦距离的计算要求每个向量中所有的值都必须非空，若两个向量v1=(3,2,4)、v2=(-1,2,null)，则无法进行余弦距离计算的。皮尔逊相关系数把向量中所有null维度赋值为0，再对结果进行余弦计算。

Pearson = \frac{\sum_{i=1}^{n}(x_i-\bar{x})(y_i-\bar{y})}{\sqrt{\sum_{i=1}^{n}(x_i-\bar{x})^2}\sqrt{\sum_{i=1}^{n}(y_i-\bar{y})^2}}

两个向量X、Y，计算出的皮尔逊相关系数含义做如下理解：

  1. 当相关系数为0时，X和Y两向量不相关
  2. 当X的值增大（减小），Y值减小（增大），X和Y两向量负相关，相关系数在-1.0到0.0之间。
  3. 当X的值增大（减小），Y值增大（减小），X和Y两向量正相关，相关系数在0.0到+1.0之间。

通常通过以下取值范围判断向量的相关程度：

  1. 0.8-1.0 极度相关
  2. 0.6-0.8 强相关
  3. 0.4-0.6 中等程度相关
  4. 0.2-0.4 弱相关
  5. 0.0-0.2 极弱相关或无相关

4.1.5 相对熵（K-L距离）

D(p||q)=\sum_{x}p(x)\log\frac{p(x)}{q(x)}=E_{p(x)}\log\frac{p(x)}{q(x)}

4.1.6 Hellinger距离

D_{\alpha}(p||q)=\frac{2}{1-\alpha^2}(1-\int{p(x)^{\frac{1+\alpha}{2}}q(x)^{\frac{1-\alpha}{2}}dx)}

4.2 簇间距离度量

在数据相似度度量确定之后对于聚类来说还需要确定一种簇间距离度量方式，以下是现有的一些度量方式。（​C_i,C_j为两个簇）

  1. Single-link：两个簇间的距离为两个簇间距离最近的两个点之间的距离，会在聚类过程中产生链式效应，可能会出现非常大的Cluster。
D(C_i,C_j)=\min_{x\subseteq C_i,y\subseteq C_j}d(x,y)
  1. Complete-link：两个簇间的距离为两个簇间距离最远的两个点之间的距离，可以避免链式效应，对异常样本点非常敏感，容易产生不合理的Cluster。
D(C_i,C_j)=\max_{x\subseteq C_i,y\subseteq C_j}d(x,y)
  1. UPGMA：Single-link与Complete-link的折中，两个簇间的距离为两个簇间所有点距离的均值
D(C_i,C_j)=\frac{1}{||C_i||||C_j||}\sum_{x\subseteq C_i,y\subseteq C_j}d(x,y)
  1. WPGMA ：两个簇间的距离的加权平均值，加权是为了使两个簇对距离的计算的影响在同一层次上，而不受簇大小的影像，具体公式和采用的权重方案有关。

4.3 聚类方法

为方便大纲完整情况，对于每一类聚类方法使用一级标题作为划分。

划分式聚类方法

划分式聚类方法需要事先指定簇类的数目或者聚类中心，通过反复迭代，直到最后达到“簇内的点足够近，簇间的点足够远”的目标。经典的划分式聚类方法有K-means及其变体K-means++、bi-Kmeans、kernel K-means等

1. K-means

1.1 经典的K-means算法的流程如下：

  1. 选择初始化的​k个样本作为初始聚类中心​a=a_1,a_2,\dots,a_k
  2. 针对数据集中每个样本​x_i，计算它到​k个聚类中心的距离并将其分到距离最小的聚类中心所对应的类中
  3. 针对每个类别​a_j，重新计算它的聚类中心​a_j=\frac{1}{|c_i|}\sum_{x\in c_i}x（即属于该类的所有样本的质心）
  4. 重复上面2，3两步操作，直到达到某个终止条件（迭代次数、最小误差变化等）

假设​x_i(i=1,2,\dots,n)是数据点，​a_j(j=1,2,\dots,k)是初始化的数据中心，那么目标函数就可以写成：

\min\sum_{i=1}^{n}\min_{j=1,2,\dots,k}||x_i-a_j||^2

1.2 优点

  • 容易理解，聚类效果不错，虽然是局部最优但是往往局部最优即可
  • 处理大数据集的时候，该算法可以保证较好的伸缩性
  • 当簇近似高斯分布的时候，效果非常好
  • 算法复杂度低

1.3 缺点

  • ​k值需要人为设定，不同的​k值得到的结果不一样
  • 对初始质心点敏感，不同的选取方式会得到不同的结果
  • 对异常数据敏感
  • 样本只能归为一类，不适合多分类的任务
  • 不适合太离散的分类、样本类别不平衡的分类、非凸形状的分类

因为离群点或者噪声数据会对均值产生较大的影响，导致中心偏移，因此还需要对数据进行异常点检测。

1.4 ​k值选取

因为​k值的选取对K-means的影响很大，这也是K-means最大的缺点，常见的选取​k值得方法有：手肘法、Gap statistic方法

1.4.1 手肘法

手肘法的核心指标是SSE（误差平方和）：

SSE = \sum_{j=1}^{k}\sum_{p\in C_i}|p-a_j|^2

上式中，​C_i是第​i个簇类，​p是​C_i中的样本点，​a_j是​C_i的质心，SSE是所有样本的聚类误差，代表了聚类效果的好坏。

image-20220819172707858

手肘法的核心思想是：随着聚类数k的增大，样本划分会更加精细，每个簇的聚合程度会逐渐提高，那么误差平方和SSE自然会逐渐变小。并且，当k小于真实聚类数时，由于k的增大会大幅增加每个簇的聚合程度，故SSE的下降幅度会很大，而当k到达真实聚类数时，再增加k所得到的聚合程度回报会迅速变小，所以SSE的下降幅度会骤减，然后随着k值的继续增大而趋于平缓，也就是说SSE和k的关系图是一个手肘的形状，而这个肘部对应的k值就是数据的真实聚类数。当然，这也是该方法被称为手肘法的原因。

1.4.2 轮廓系数法

该方法的核心指标是轮廓系数，某个样本点​x_i的轮廓系数定义如下：

S=\frac{b-a}{max(a,b)}

其中，​a是​x_i与同簇的其它样本的平均距离，称为凝聚度，​b是​x_i与最近簇中所有样本的平均距离，称为分离度。而最近簇的定义是：

C_j = \arg \min_{C_k}\frac{1}{n}\sum_{p\in C_k}|p-x_i|^2

其中​p是某个簇​C_k中的样本。事实上，就是用​x_i到某个簇所有的样本平均距离作为衡量该点到该簇的距离后，选择离​x_i最近的一个簇作为最近簇。

求出所有样本的轮廓系数后再求平均值就得到了平均轮廓系数。平均轮廓系数的取值范围为​[-1,1]，且簇内样本的距离越近，簇间样本距离越远，平均轮廓系数越大，聚类效果越好。那么，平均轮廓系数最大的​k便是最佳聚类数。

1.4.3 Gap Statistic

Gap(k)=E(\log{D_k})-\log{D_k}
image-20220819172743150

上式中​D_k为损失函数，这里​E(\log{D_k})指的是​\log{D_k}的期望。这个数值通常通过蒙特卡洛模拟产生，我们在样本里所在的区域中按照均匀分布随机产生和原始样本数一样多的随机样本，并对这个随机样本做K-means，从而得到一个​D_k。如此往复多次，可以得到多个​\log{D_k}。求这些数值的平均值就得到了​E(\log{D_k})的近似值。最终可以计算Gap Statistic。而Gap Statistic取得最大值所对应的​k就是最佳的​k值。

1.4.4 核函数

基于欧式距离的 K-means 假设了了各个数据簇的数据具有一样的的先验概率并呈现球形分布，但这种分布在实际生活中并不常见。面对非凸的数据分布形状时我们可以引入核函数来优化，这时算法又称为核 K-means 算法，是核聚类方法的一种。核聚类方法的主要思想是通过一个非线性映射，将输入空间中的数据点映射到高位的特征空间中，并在新的特征空间中进行聚类。非线性映射增加了数据点线性可分的概率，从而在经典的聚类算法失效的情况下，通过引入核函数可以达到更为准确的聚类结果。

1.5 ISODATA

ISODATA 的全称是迭代自组织数据分析法。它解决了 K 的值需要预先人为的确定这一缺点。而当遇到高维度、海量的数据集时，人们往往很难准确地估计出 K 的大小。ISODATA 就是针对这个问题进行了改进，它的思想也很直观：当属于某个类别的样本数过少时把这个类别去除，当属于某个类别的样本数过多、分散程度较大时把这个类别分为两个子类别。

ISODATA在K-means算法的基础上，增加对聚类结果的合并和分裂两个操作，当聚类结果某一类中样本数太少，或两个类间的距离太近，或样本类别远大于设定类别数时，进行合并，当聚类结果某一类中样本数太多，或某个类内方差太大，或样本类别远小于设定类别数时，进行分裂。

image-20220819152152704

ISODATA算法基本步骤和思路

（1） 选择某些初始值。可选不同的参数指标，也可在迭代过程中人为修改，以将N个模式样本按指标分配到各个聚类中心中去。

（2） 计算各类中诸样本的距离指标函数。

（3）~（5）按给定的要求，将前一次获得的聚类集进行分裂和合并处理（（4）为分裂处理，（5）为合并处理），从而获得新的聚类中心。

（6） 重新进行迭代运算，计算各项指标，判断聚类结果是否符合要求。经过多次迭代后，若结果收敛，则运算结束。

算法流程：

  1. 输入​N个模式样本​\{x_i,i=1,2,\dots.N\}

    预选​N_c个初始聚类中心​\{z_1,z_2,\dots,z_{N_c}\}，它可以不等于所要求的聚类中心的数目，其初始位置可以从样本中任意选取。

    预选：​K=预期的聚类中心数目；

    ​\theta_N=每一聚类域中最少的样本数目，若少于此数即不作为一个独立的聚类；

    ​\theta_S=一个聚类域中最少的样本数目，若少于此数即不作为一个独立的聚类；

    ​\theta_c=两个聚类中心间的最小距离，若小于此数，两个聚类需进行合并；

    ​L=在一次迭代运算中可以合并的聚类中心的最多对数；

    ​I=迭代运算的次数。

  2. 将​N个模式样本分给最近的聚类​S_j，假若​D_j=\min\{||x-z_i||,i=1,2,\dots,N_c\}，即​||x-z_j||的距离最小，则​x\in S_j。

  3. 如果​S_j中的样本数目​S_j<\theta_N，则取消该样本子集，此时​N_c减去1。

（此处对应基本步骤一）

  1. 修正各聚类中心：
z_j=\frac{1}{N_j}\sum_{x\in S_j}x,j=1,2,\dots,N_c
  1. 计算各聚类域​S_j中模式样本与各聚类中心间的平均距离
\bar{D_j}=\frac{1}{N_j}\sum_{x\in S_j}||x-z_j||,j=1,2,\dots,N_c
  1. 计算全部模式样本和其对应聚类中心的总平均距离
\bar{D}=\frac{1}{N}\sum_{j=1}^{N}N_j\bar{D_j}

（此处对应基本步骤二）

  1. 判别分裂、合并及迭代运算
    1. 若迭代运算次数已达到​I次，即最后一次迭代，则置​\theta_c=0，转至第11步。
    2. 若​N_c\le \frac{K}{2}，即聚类中心的数目小于或等于规定值的一半，则转至第8步，对已有聚类进行分裂处理。
    3. 若迭代运算的次数是偶数次，或​N_c\ge 2K，不进行分裂处理，转至第11步；否则，转至第8步，进行分裂处理

（以上对应基本步骤三）

  1. 计算每个聚类中样本距离的标准差向量
\sigma_j=(\sigma_{1j},\sigma_{2j},\dots,\sigma_{nj})^T
其中向量的各个分量为：
\sigma_{ij}=\sqrt{\frac{1}{N_j}\sum_{k=1}^{N_j}(x_{ik}-z_{ij})^2}
式中，

​i=1,2,\dots,n为样本特征向量的维数，​j=1,2,\dots,N_c为聚类数，​N_j为​S_j中的样本个数。

  1. 求每一标准差向量​\{\sigma_j,j=1,2,\dots,N_c\}中的最大分量，以​\{\sigma_{jmax},=1,2,\dots,N_c\}代表。

  2. 在任一最大分量集​\{\sigma_{jmax},j=1,2,\dots,N_c\}中，若有​\sigma_{jmax}>\theta_S，同时又满足如下两个条件之一：

    1. ​\bar{D_j}>\bar{D}和​N_j>2(\theta_N+1)，即​S_j中样本总数超过规定值一倍以上，
    2. ​N_c\le\frac{K}{2}

    则将​z_j分裂为两个新的聚类中心和，且​N_c加1。中对应于​\sigma_{jmax}的分量加上​k\sigma_{jmax}；中对应于​\sigma_{jmax}的分量减去​k\sigma_{jmax}。

    如果本步骤完成了分裂运算，则转至第2步，否则继续

（以上对应基本步骤四，进行分裂处理）

  1. 计算全部聚类中心的距离
D_{ij}=||z_i-z_j||,i=1,2,\dots,N_c-1;j=i+1,\dots,N_c
  1. 比较​D_{ij}与​\theta_c的值，将​D_{ij}<\theta_c的值按最小距离次序递增排列，即
\{D_{i1j1},D_{i2j2},\dots,D_{iLjL}\}
式中

​D_{i1j1}<D_{i2j2}<\cdots<D_{iLjL}。

  1. 将距离为​D_{ikjk}的两个聚类中心​Z_{ik}和​Z_{jk}合并，得到新的中心为：
z_k^*=\frac{1}{N_{ik}+N_{jk}}[N_{ik}z_{ik}+N_{jk}z_{jk}],k=1,2,\dots,L
式中，被合并的两个聚类中心向量分别以其聚类域内的样本数加权，使

​Z_k^*为真正的平均向量。

（以上步骤对应基本步骤五，进行合并处理）

  1. 如果是最后一次迭代运算（即第​I次），则算法结束；否则，若需要操作者改变输入参数，转至第1步；若输入参数不变，转至第2步.在本步运算中，迭代运算的次数每次应加1。

1.6 K-means++

K-means++是针对K-means中初始质心点选取的优化算法，该算法的流程与K-means相似，区别在于对初始质心的选取，该部分的算法流程如下：

  1. 随机选取一个中心点​a_1;
  2. 计算数据到之前​n各聚类中心最远的距离​D(x)，并以一定概率​\frac{D(x)^2}{\sum{D(x)^2}}选择新中心点​a_i；
  3. 重复第二步

简单来说，K-means++就是选择离已选中心点最远的点。这也比较符合常理，聚类中心当然是互相离得越远越好。

下图为二者对比区别：

image-20220819142154344

image-20220819142203736

缺点

难以并行化。所以K-means II改变取样策略，并非按照K-means++那样每次遍历只取一个样本点，而是每次遍历取样​k个，重复该取样过程​\log{(n)}次，则得到​k\log{(n)}个样本点组成的集合，然后从这些点中选取​k个。一般情况不需要​\log{(n)}次取样，5次即可。

2. bi-Kmeans

一种度量聚类效果的指标是SSE(Sum of Squared Error)，他表示聚类后的簇离该簇的聚类中心的平方和，SSE越小，表示聚类效果越好。bi-Kmeans是针对Kmeans算法会陷入局部最优的缺陷进行的改进算法。该算法基于SSE最小化的原理，首先将所有的数据点视为一个簇，然后将该簇一分为二，之后选择其中一个簇继续进行划分，选择哪一个簇进行划分取决于对其划分是否能最大程度地降低SSE的值。

该算法的流程如下：

  1. 将所有点视为一个簇
  2. 当簇的个数小于​k时
    1. 对每一个簇
      1. 计算总误差
      2. 在给定的簇上面进行K-means聚类（​k=2）
      3. 计算将该簇一分为二之后的总误差
    2. 选取使得误差最小的那个簇进行划分操作

该方法是一个全局最优的方法，所以每次计算出来的SSE值基本也是一样的（不排除有部分随即分错的情况）

基于密度的聚类方法

K-means系算法对于凸性数据具有良好的效果，能够根据距离来讲数据分为球状类的簇，但对于非凸形状的数据点就有些无能为力了，当K-means算法在环形数据的聚类时，分类效果如下所示：

image-20220819162918176

1. DBSCAN

从上图可以看出，K-means聚类产生了错误的结果，这个时候就需要用到基于密度的聚类方法了，该方法需要定义两个参数​\varepsilon和​M，分别表示密度的邻域半径和邻域密度阈值。

在介绍DBSCAN之前需要先介绍几个概念，考虑集合​X=\{x^{(1)},x^{(2)},\cdots,x^{(n)}\}，​\varepsilon表示定义密度的邻域半径，设聚类的邻域密度阈值为​M，则有以下定义：

  • ​\varepsilon邻域
N_{\varepsilon}(x)=\{y\in X|d(x,y)<\varepsilon\}
  • 密度（desity） ​x的密度为：
\rho(x)=|N_{\epsilon}(x)|

  • 核心点（core-point）

    设

    ​x\in X，若​\rho(x)\ge M，则称​x为​X的核心点，记​X中所有核心点构成的集合为​X_c，记所有非核心点构成的集合为​X_{nc}。

  • 边界点（border-point）

    若​x\in X_{nc}，且​\exists y\in X，满足

    y\in N_{\varepsilon}(x)\cap X_c

    即​x的​\varepsilon邻域中存在核心点，则称​x为​X的边界点，记​X中所有的边界点构成的集合为​X_{bd}。

    此外，边界点也可以这么定义：若​x\in X_{nc}，且​x落在某个核心点的​\varepsilon邻域内，则称​x为​X的一个边界点，一个边界点可能同时落入一个或多个核心点的​\varepsilon邻域。

  • 噪声点（noise-point）

    若​x满足：

    x\in X,x\notin X_{c}\text{且}x\notin X_{bd}

则称​x为噪声点。

如下图所示，设​M=3，则​A为核心点，​B、​C是边界点，而​N是噪声点。

image-20220820162001284

1.1 算法流程

  1. 标记所有对象为unvisited

  2. 当有标记对象时

    1. 随机选取一个unvisited对象​p
    2. 标记​p为visited
    3. 如果​p的​\varepsilon邻域内至少有​M个对象，则
      1. 创建一个新的簇​C，并把​p放入​C中
      2. 设​N是​p的​\varepsilon邻域内的集合，对​N中的每个点​p'
        1. 如果点​p'是unvisited
          1. 标记​p'为visited
          2. 如果​p'的​\varepsilon邻域至少有​M个对象，则把这些点添加到​N
          3. 如果​p'还不是任何簇的成员，则把​p'添加到​C
      3. 保存​C
    4. 否则标记​p为噪声

1.2 聚类效果

当设置不同的​\varepsilon时，会产生不同的结果，如下所示：

preview

当设置不同的​M时，会产生不同的结果，如下图所示

preview

1.3 算法特点

  1. 需要提前确定​\varepsilon和​M的值
  2. 不需要提前设置聚类的个数
  3. 对初值选取敏感，对噪声不敏感
  4. 对米杜不均的数据聚合效果不好

1.3.1 算法总结

  • 一个核心思想：基于密度

    直观效果上来讲，DBSCAN算法可以找到样本点的全部密集区域，并把这些密集区域当作一个一个的聚类簇。

image-20220822090849789

  • 两个算法参数：邻域半径​\varepsilon和最少点数目（邻域密度阈值）minpoint

    算法通过这两个参数来刻画了什么叫做密集，就是说当邻域半径​\varepsilon内的点的个数大于最少点数目minpoints时，就是密集的。

    image-20220822091235210

  • 三种点的类别：核心点，边界点和噪声点

    邻域半径​\varepsilon内样本点的数量大于等于minpoints的点叫做核心点。不属于核心点但在某个核心点的邻域内的点叫做边界点。既不是核心点也不是边界点的是噪声点。

    image-20220822091917948

  • 四种点的关系：密度直达，密度可达，密度相连，非密度相连

    如果​P为核心点，​Q在​P的​R邻域内，那么称​P到​Q密度直达。任何核心点到其自身密度直达，密度直达不具有对称性，如果​P到​Q密度直达，那么​Q到​P不一定密度直达。

    如果存在核心点​P_2,P_3,\dots,P_n，且​P_1到​P_2密度直达，​P_2到​P_3密度直达，​\dots，​P_{(n-1)}到​P_n密度直达，​P_n到​Q密度直达，则​P_1到​Q密度可达。密度可达也不具有对称性。

    如果存在核心点​S，使得​S到​P和​Q都密度可达，则​P和​Q密度相连。密度相连具有对称性，如果​P和​Q密度相连，那么​Q和​P也一定密度相连。密度相连的两个点属于同一个聚类簇。

    如果两个点不属于密度相连关系，则两个点非密度相连。非密度相连的两个点属于不同的聚类簇，或者其中存在噪声点。

    image-20220822092741997

2. Mean-Shift

2.1 Mean-shift的背景

在K-means算法中，最终的聚类效果受初始的聚类中心的影响，K-means++的提出为选择较好的初始聚类中心提供了依据，但是在算法中，簇类数量K仍然需要提前制定，对于类别个数事先未知的数据集，K-means和K-means++还是难以精确求解。

Mean-Shift算法即均值漂移算法，与K-means算法一样基于聚类中心的聚类算法，同时又加入了密度因素。从而能不事先设置簇类数量值。

2.2 算法流程

  1. 在未被标记的数据点中随机选择一个点作为中心center
  2. 找出离center距离在bandwidth之内的所有点，记作集合​M，认为这些点属于簇​c。同时，把这些点属于这个类的概率加1，这个概率将用于最后步骤的分类。
  3. 以center为中心点，计算从center开始到集合​M中每个元素的向量，将这些向量相加，得到向量shift。
  4. center = center + shift。即center沿着shift的方向移动，移动距离是​||shift||。
  5. 重复步骤2，3，4，直到shift变得很小（迭代到收敛），记住此时的center。这个迭代过程中所有遇到的点都应该归类到簇​c。
  6. 如果收敛时当前簇​c的center与其它已经存在的簇​c_2中心的距离小于阈值，那么把​c_2与​c进行合并。否则，把​c作为新的簇类，增加1类。
  7. 重复1，2，3，4，5直到所有的点都被标记访问。
  8. 分类：根据每个类，对每个点的访问频率，取访问频率最大的那个类作为当前点的所属类。
20181120124405992

2.3 均值漂移向量

对于给定的​d维空间​R^d中的​n个样本点​x_i,i=1,2,\dots,n，则对于​x点，其均值漂移向量的基本形式为：

M_h(x)=\frac{1}{k}\sum_{x_i\in S_h}(x_i-x)

3. OPTICS

层次化聚类方法

1. Agglomerative

2. Divisive

其他方法

1. 量子聚类

2. 核聚类

3. 谱聚类