聚类问题（K-means，系统聚类，SBSCAN算法）

K-means算法

大概的流程

优缺点

步骤

例题：根据消费习惯来对省份进行分类

下面是spss的实操

系统/层次聚类

原理

步骤（以凝聚式聚类为例）

聚类分析需要注意的问题

类型

下面是spss操作

补充：

​编辑

 优缺点

DBSCAN算法

1.原理

算法步骤

K-means算法

一种广泛应用的无监督学习算法，用于将数据集划分为 K 个不同的簇（cluster），使得同一簇内的数据点相似度较高，而不同簇间的数据点相似度较低。

大概的流程

一、指定需要划分的簇[cù]的个数K值)(类的个数)

二、随机地选择K个数据对象作为初始的聚类中心(不一定要是我们的样本点);

三、计算其余的各个数据对象到这K个初始聚类中心的距离，把数据对象划归到距离它最近的那个中心所处在的簇类中:

四、调整新类并且重新计算出新类的中心;

五、循环步骤三和四，看中心是否收敛(不变)，如果收敛或达到迭代次数则停止循环:

六、结束

优缺点

优点

简单快速：算法原理简单，易于理解和实现，计算复杂度相对较低，在处理大规模数据集时表现良好。

聚类效果较好：对于球形分布的数据，通常能得到不错的聚类结果，在许多实际应用中能有效地发现数据中的自然分组结构。

缺点

需预先指定簇的数量K ：然而，在实际应用中，合适的 K值往往难以确定。不同的  值可能导致不同的聚类结果，选择不当可能无法准确反映数据的内在结构。

对初始簇中心敏感：初始簇中心的选择会影响最终的聚类结果。不同的初始值可能导致算法收敛到不同的局部最优解，从而得到差异较大的聚类结果。

对噪声和离群点敏感：由于簇中心是通过数据点的均值计算得到的，噪声和离群点可能会对簇中心的位置产生较大影响，进而影响聚类效果。

步骤

可以使用K-means++算法对选择初始化聚类中心进行优化:初始化的聚类种的中心之间尽可能的相隔远一点

步骤一:随机选取一个样本作为第一个聚类中心;

步骤二:计算每个样本与当前已有聚类中心的最短距离(即与最近一个聚类中心的距离)，这个值越大，表示被选取作为聚类中心的概率较大;最后，用轮盘法(依据概率大小来进行抽选)选出下一个聚类中心;

步骤三:重复步骤二，直到选出K个聚类中心。选出初始点后，就继续使用标准的K-means算法了

类似迪杰斯特拉算法但是是每次大概率选择最远的路,更新最近的.

例题：根据消费习惯来对省份进行分类

下面是spss的实操

分析->分类->k均值聚类

下面表示分为两类(这里的k要设置的方便解释)

迭代可以调整最大迭代次数

保存可以保存得出的一些额外的数据

选项

系统/层次聚类

聚类分析中的一种重要方法，它能够构建出一棵具有层次结构的聚类树，展示数据点之间的亲疏关系。

原理

基本思想：系统聚类基于数据点之间的相似性度量，通过不断合并或分裂数据点，形成具有层次结构的聚类结果。它假设数据点之间存在一种自然的层次关系，这种关系可以通过聚类树直观地展现出来。

相似性度量：常用的相似性度量方法包括欧氏距离、曼哈顿距离等用于衡量数值型数据点之间的距离，以此反映它们的相似程度。距离越小，数据点之间的相似性越高。

步骤（以凝聚式聚类为例）

1.初始化：将每个数据点看作一个单独的类，此时类的数量等于数据点的数量。

2.计算类间距离：使用选定的距离度量方法（如欧氏距离），计算每两个类之间的距离。常用的样品之间的距离计算方法有：(xik表示第i个样品的第k个指标)

1)绝对值距离:

2)欧式距离法:

(下面的都不常用)

3)minkowshi距离:

4)chebyshev距离:

5)马氏距离:

比如将高三,8班的30个人,根据他们的6科考试成绩来分类

指标和指标之间的距离:

1)相关系数:

2)夹角余弦:

比如根据高三8班的30个人的成绩,将6门课分为2类

类和类之间的距离:

我们记

1)最短距离法:

取两个类中各取一个点得到的最短距离为类间距离

2)重心法:

两个类之间的距离等于两个类的重心的距离

3.合并类：找到距离最近的两个类，将它们合并为一个新类。

4.更新距离矩阵：由于类的合并，需要重新计算新类与其他类之间的距离，更新距离矩阵。

5.判断终止条件：重复步骤 2 - 4，直到所有数据点都合并到一个类中，或者满足某个终止条件（如达到预设的类的数量）

流程图:

最后会变成如下的图:

(类似霍夫曼树)

聚类分析需要注意的问题

1.对于一个实际问题要根据分类的目的来选取指标，指标选取的不同分类结果一般也不同。

2.样品间距离定义方式的不同，聚类结果一般也不同。

3.聚类方法的不同，聚类结果一般也不同(尤其是样品特别多的时候)。最好能通过各种方法找出其中的共性。

4.要注意指标的量纲，量纲差别太大会导致聚类结果不合理。

5.聚类分析的结果可能不令人满意，因为我们所做的是一个数学的处理，对于结果我们要找到一个合理的解释。

类型

凝聚式聚类：从每个数据点作为一个单独的类开始，然后逐步合并相似的类。具体来说，每次迭代时，算法会计算所有类之间的距离，将距离最近的两个类合并为一个新类，这个过程不断重复，直到所有数据点都合并到一个类中，最终形成一棵聚类树。

分裂式聚类：与凝聚式聚类相反，它从所有数据点都属于一个大类开始，然后逐步将大类分裂成更小的类。每次迭代时，算法会选择一个类进行分裂，使得分裂后的两个子类之间的差异尽可能大，直到每个数据点都成为一个单独的类，同样形成一棵聚类树。

(这里讲解的是凝聚式)

下面是spss操作

分析->分类->系统聚类:

如下的选择:

统计可以不用管,图可以如下的选择,帮助我们更加直观的反应一些数据

方法里面可以选择之前的距离计算的方法:

如果量纲有差异就可以进行标准化,这里都是元,可以不进行标准化

保存可以选择K的数量和解的范围

得出的谱系图

那么我们就可以根据这个图来选择这个K的值(可以自己根据图区估计)

也可以根据下面的肘部法则来确定最优的k

各个类畸变程度之和:各个类的畸变程度等于该类重心与其内部成员位置距离的平方和;假设一共将n个样本划分到K个类中(K≤n-1,即至少有一类中有两个元素)

在部分多元统计教材中，J又被称为聚合系数。聚合系数折线图:横坐标为聚类的类别数K，纵坐标为聚合系数J

根据下面的表格来画出肘部图

复制到excel中,插入图表

根据k=5的时候，下降的趋势缓和，K<5畸变程度较大（k==3也可以解释）

下面我们就按照K=3去分类

生成如下的结果：

补充：

图表的绘制：

图表->图表构建器->加入x和y，根据分出来的类分色，将省份作为标签

 优缺点

优点:

不需要预先指定聚类数量：与 K - means 聚类不同，系统聚类不需要事先确定要划分的类的数量，聚类结果的层次结构可以展示不同粒度下的数据分组情况，用户可以根据实际需求和聚类树的结构来选择合适的聚类数量。

聚类结果展示直观：聚类树能够直观地展示数据点之间的亲疏关系和聚类的层次结构，有助于用户理解数据的内在结构和分布特征。

缺点:

计算复杂度高：每次迭代都需要计算所有类之间的距离，随着数据点数量和类数量的增加，计算量会迅速增大，时间复杂度较高，不适合处理大规模数据集。

一旦合并或分裂不可撤销：在凝聚式聚类中，一旦两个类被合并，后续步骤无法撤销这个操作。如果在某个阶段选择了不恰当的合并，可能会导致最终聚类结果不理想。同样，分裂式聚类中一旦类被分裂，也无法恢复。

DBSCAN算法

基于密度的空间聚类算法，它是一种无监督学习算法，主要用于在具有噪声的数据集中发现任意形状的簇，并识别出数据集中的噪声点。

1.原理

核心概念：

邻域:对于数据集中的一个点p，给定半径r，以点p为中心，r为半径的区域内的所有点构成点p的r-邻域，记为 N r(p)。

核心点:如果点p的r-邻域内包含的点数大于或等于某个阈值 MinPts，则点p被称为核心点。核心点意味着在其周围一定范围内有足够多的数据点，表明该区域具有较高的数据密度。

边界点:如果点q在某个核心点p的-邻域内，但点q的r-邻域内的点数小于 MinPts，则点q是边界点。边界点依赖于核心点来确定其所属的簇。

噪声点:既不是核心点也不是边界点的点被认为是噪声点，这些点通常是孤立的，在其周围没有足够的数据点形成有意义的簇。

密度可达:如果存在一条从核心点p到点q的点链，其中链上的每个点都在其前一个点的r-邻域内，且链上的第一个点是核心点，那么称点q从核心点p密度可达。

密度相连:如果存在一个核心点o，使得点p和点q都从点o密度可达，那么称点p和点q密度相连。

聚类原理:DBSCAN 通过检查数据集中每个点的-邻域来确定该点是核心点、边界点还是噪声点。然后基于核心点的密度可达关系将数据点划分为不同的簇，密度相连的数据点构成一个簇。

算法步骤

1，初始化，确定r和MinPts，两个参数的选择对聚类结果有重要影响，通常需要根据数据的特点和经验进行调整。

2，遍历数据集：

对于数据集中的每个点 p:计算点 p的 r - 邻域 Nr(p),

1）如果领域中的点的数量大于MinPts，那么p就是核心点，创建一个新的簇C,并且将p及其密度可达的所有点加入C中。

2）如果领域中的点的数量小于MinPts，则 p不是核心点。如果 p尚未被分配到任何簇中，则将p标记为噪声点。

3,重复聚类：重复步骤2，知道数据点都被处理完毕。

 优缺点

优点：

能够发现任意形状的簇：不像 K - means 等算法倾向于发现球形的簇，DBSCAN 可以根据数据点的密度分布发现任意形状的簇，适用于各种复杂的数据分布情况。

对噪声点不敏感：可以直接识别并标记出数据集中的噪声点，而 不会将噪声点错误地划分到某个簇中，使得聚类结果更加准确和可靠。

无需预先知道要形成的簇类的数量：与 K - means 等需要预先指定聚类数量的算法不同，DBSCAN 根据数据的密度自动确定簇的数量，减少了用户对聚类数量先验知识的依赖。

缺点：

参数选择困难：r和MinPts 的选择对聚类结果影响很大，但没有通用的方法来确定最优值。不合适的参数可能导致聚类结果不理想，例如将过多的点标记为噪声点，或者将不同的簇合并为一个簇。

计算复杂度较高：在最坏情况下，DBSCAN 的时间复杂度为O(N^2)，其中N是数据点的数量。对于大规模数据集，计算量较大，可能需要较长的运行时间。

不适合高维数据：随着数据维度的增加，数据点之间的距离度量变得不太可靠，密度的概念也变得模糊，导致聚类效果下降。这是因为在高维空间中，数据点趋于稀疏，传统的基于距离的密度定义不再有效，即所谓的 “维度灾难” 问题。