【机器学习】——聚类算法小结

阳光穿透心脏的1/2处 2022-05-22 08:29 980阅读 0赞

**聚类算法小结**

【聚类定义】

聚类定义: 聚类算法将一系列文档聚团成多个子集或簇（cluster），其目标是建立类内紧密、类间分散的多个簇。换句话说，聚类的结果要求簇内的文档之间要尽可能相似，而簇间的文档之间则要尽可能不相似。

聚类是无监督学习（unsupervisedlearning）的一种最普遍的形式。无监督也意味着不存在对文档进行类别标注的人类专家。聚类中，数据的分布和组成结构决定最后的类别归属。

聚类将数据集中的样本划分为若干个通常是不相交的子集，每个子集称为一个簇（cluster），每个簇对应一个潜在概念或类别。当然这些类别在执行聚类算法之前是未知的，聚类过程是自动形成簇结构，簇所对应的概念语义由使用者命名。

形式化地说，假定样本集D=\{x1,x2,…,xm\}包含m个无标记样本，每个样本xi=\{xi1; xi2;…;xin\}是一个n维特征向量（属性），则聚类算法将样本集D划分为k个不相交的簇\{Cl|l=1,2,…,k\}，其中Cl∩l≠l’Cl’=∅且D=Ul=1…kCl。相应地，用Rj∈\{1,2,…,k\}表示样本xj的簇标记(cluster label)，即xj∈CRj。聚类的结果可用包含m个元素的簇标记向量R=(R1;R2;…;Rm)表示。

聚类既能作为一个单独过程，用于寻找数据内在的分布结构，也可作为分类等其他学习任务的前驱过程。如在一些商业应用中需对新用户的类型进行判别，但定义用户类型对商家来说可能不太容易，此时可先对用户进行聚类，根据聚类结果将每个簇定义为一个类，然后再基于这些类训练分类模型，用于判别新用户的类型。

聚类算法的一个关键输入是距离计算方法。计算距离时采用的是二维平面上的距离计算方法。基于这种距离计算方法在图中得出了三个不同的簇。在文档聚类当中，距离计算方法往往采用欧氏距离。不同的距离计算方法会导致不同的聚类效果。因此，距离的计算方法是影响聚类结果的一个重要因素。

扁平聚类（flat clustering）算法会给出一系列扁平结构的簇，它们之间没有任何显式的结构来表明彼此的关联性。而层次聚类（hierarchical clustering）算法则会产生层次性的聚类结果。

了解硬聚类和软聚类之间的差别也相当重要。硬聚类（hardclustering）计算的是一个硬分配（hard ssignment）过程，即每篇文档仅仅属于一个簇。而软聚类(soft clustering)算法的分配过程是软的，即一篇文档的分配结果是在所有簇上的一个分布。在软分配结果中，一篇文档可能对多个簇都具有隶属度。

【聚类算法及用例】

聚类划分：

（1）划分聚类  k-means、k-medoids、k-modes、k-medians、kernelk-means

（2）层次聚类  Agglomerative 、divisive、BIRCH、ROCK、Chameleon

（3）密度聚类 DBSCAN、OPTICS

（4）网格聚类  STING

（5）模型聚类  GMM

（6）图聚类  Spectral Clustering（谱聚类）

**1. K-means算法**

K-means算法首先随机选择k个对象，每个对象代表一个聚类的质心。对于其余的每一个对象，根据该对象与各聚类质心之间的距离，把它分配到与之最相似的聚类中。然后，计算每个聚类的新质心。重复上述过程，直到准则函数会聚。通常采用的准则函数是平方误差准则函数。

K-means聚类算法的具体步骤如下：

1) 从数据集中选择k个质心C1，C2，… ，Ck作为初始的聚类中心；

2) 把每个对象分配到与之最相似的聚合。每个聚合用其中所有对象的均值来代表，“最相似”就是指距离最小。对于每个点Vi，找出一个质心Cj，使它们之间的距离d(Vj，Cj)最小，并把Vi分配到第j组；

3) 把所有的点都分配到相应的组之后，重新计算每个组的质心Cj；

4) 循环执行第2)步和第3)步，直到数据的划分不再发生变化。

该算法具有很好的可伸缩性，其计算复杂度为O(nkt)，其中，t是循环的次数。K-means聚类算法的不足之处在于它要多次扫描数据库，此外，它只能找出球形的类，而不能发现任意形状的类。还有，初始质心的选择对聚类结果有较大的影响，该算法对噪声很敏感。

**2. K-medoids算法**

K-medoids算法的过程和上述k-means的算法过程相似，唯一不同之处是：k-medoids算法用类中最靠近中心的一个对象来代表该聚类，而k-means算法用质心来代表聚类。在k-means算法中，对噪声非常敏感，因为一个极大的值会对质心的计算带来很大的影响。而k-medoid算法中，通过用中心来代替质心，可以有效地消除该影响。

K-medoids算法首先随机选择k个对象，每个对象代表一个聚类，把其余的对象分别分配给最相似的聚类。然后，尝试把每个中心分别用其他非中心来代替，检查聚类的质量是否有所提高。若是，则保留该替换。重复上述过程，直到不再发生变化。

常见的k-medoids算法有PAM(Partitioning Around Medoids)算法、CLARA(Clustering LARge Application)算法、CLARANS(Clustering LARge Application based uponRandomized Search)算法。当存在“噪声”和孤立点数据时，k-medoids算法比可k-means更健壮，这是因为中心点不像平均值那么容易被极端数据影响。但是，k-medoids算法的执行代价比k-means高。

**【算法实例】**

一.PAM聚类算法：

选用簇中位置最中心的对象，试图对n个对象给出k个划分；代表对象也被称为是中心点，其他对象则被称为非代表对象；最初随机选择k个对象作为中心点，该算法反复地用非代表对象来代替代表对象，试图找出更好的中心点，以改进聚类的质量；在每次迭代中，所有可能的对象对被分析，每个对中的一个对象是中心点，而另一个是非代表对象。对可能的各种组合，估算聚类结果的质量；一个对象Oi可以被使最大平方-误差值减少的对象代替；在一次迭代中产生的最佳对象集合成为下次迭代的中心点。

对比kmeans：k-means是每次选簇的均值作为新的中心，迭代直到簇中对象分布不再变化。其缺点是对于离群点是敏感的，因为一个具有很大极端值的对象会扭曲数据分布。那么我们可以考虑新的簇中心不选择均值而是选择簇内的某个对象，只要使总的代价降低就可以。kmedoids算法比kmenas对于噪声和孤立点更鲁棒，因为它最小化相异点对的和（minimizes a sum of pairwise dissimilarities ）而不是欧式距离的平方和（sum of squared Euclidean distances.）。一个中心点（medoid）可以这么定义：簇中某点的平均差异性在这一簇中所有点中最小。

二.算法描述：

wiki上有对pam算法的解释，这里着重对维基百科的例子进行介绍：[k-medoids][]

k-medoid聚类算法的最常见实现为Partitioning Around Medoids (PAM)算法，PAM利用了贪婪搜索，不一定可以找到最优解，但是比穷尽搜索更快。

输入：簇的数目k和包含n个对象的数据

输出：k个簇，使得所有对象与其距离最近中心点的相异度总和最小

1. 初始化：随机挑选n个点中的k个点作为中心点。

2. 将其余的点根据距离划分至这k个类别中。

3. 当损失值减少时：

1）对于每个中心点m，对于每个非中心点o：

i）交换m和o，重新计算损失（损失值的大小为：所有点到中心点的距离和）

ii）如果总的损失增加则不进行交换

另外的一个解释，和上面一样：

1） 任意选择k个对象作为初始的簇中心点

2） Repeat

3） 指派每个剩余对象给离他最近的中心点所表示的簇

4） Repeat

5） 选择一个未被选择的中心点Oi

6） Repeat

7） 选择一个未被选择过的非中心点对象Oh

8） 计算用Oh代替Oi的总代价并记录在S中

9） Until 所有非中心点都被选择过

10） Until 所有的中心点都被选择过

11） If 在S中的所有非中心点代替所有中心点后的计算出总代价有小于0的存在，then找出S中的用非中心点替代中心点后代价最小的一个，并用该非中心点替代对应的中心点，形成一个新的k个中心点的集合；

12） Until 没有再发生簇的重新分配，即所有的S都大于0.

三. 例子：

对下列表中（图1）的10个数据聚类， k=2.可以看到这里每个数据的维度都为2。

![1055519-20171102225130873-1337967409.png][]           ![1055519-20171102225505857-681080820.png][]

图1                                                                               图2

1. 随机挑选k=2个中心点：c1=（3，4） ， c2=（7，4）.那么将所有点到这两点的距离计算出来（图2），可以看到黑体为到两个中心点距离较小的距离值。那么根据图2，我们可以对所有数据点进行归类：

Cluster1 = \{(3,4)(2,6)(3,8)(4,7)\}

Cluster2 = \{(7,4)(6,2)(6,4)(7,3)(8,5)(7,6)\}

很容易算出此时的损失值cost为：20

![1055519-20171102225841123-1288897683.png][]

2. 挑选一个非中心点O’，让我们假定挑选的为X7 ，即O‘=（7，3）。那么此时这两个中心点暂时变成了c1(3,4) and O′(7,3)，那么我们要计算一下这一替换措施所带来的损失cost：

![1055519-20171102230206623-1699966022.png][]               ![1055519-20171102230223451-1343070688.png][]

图3                                                                                                                                图4

正如图3和图4所见，此时的cost（很好计算，黑体数值的和）变成了：  total cost = 3+4+4+2+2+1+3+3 = 22

此时的cost为22，比之前的cost=20要大，所以这次替换的损失变大啦，我们最终不进行这次替换。

这仅仅是X7 替代了c2点，我们应该计算除了c1和c2点外的所有点外分别替代c1和c2，将这些替换后的损失都计算出来，看看有没有比20小的损失，如果有那么我们就将这个最小损失对应的中心点对作为新的中心点对。至此才完成了一次迭代。重复迭代直至收敛。

#!/usr/bin/env python3
 # -*- coding: utf-8 -*-
 """
 Created on Sun Oct 22 20:31:32 2017
 
 @author: LPS
 """
 
 import numpy as np
 import pandas as pd
 import copy
 
 df = np.loadtxt('waveform.txt',delimiter=',') # 载入waveform数据集，22列，最后一列为标签0，1，2
 s= np.array(df)
 print(s.shape)
 print(s[0:10])
 
 data0 = s[s[:,s.shape[1]-1]==0][:100] # 取标签为0的前100个样本
 data1 = s[s[:,s.shape[1]-1]==1][:100] # 取标签为1的前100个样本
 data2 = s[s[:,s.shape[1]-1]==2][:100] # 取标签为2的前100个样本
 
 data = np.array([data0,data1,data2]) 
 data = data.reshape(-1,22) 
 
 def dis(data_a, data_b):
 return np.sqrt(np.sum(np.square(data_a - data_b), axis=1)) # 返回欧氏距离
 
 def kmeans_wave(n=10, k=3, data=data):
 data_new = copy.deepcopy(data) # 前21列存放数据，不可变。最后1列即第22列存放标签，标签列随着每次迭代而更新。
 data_now = copy.deepcopy(data) # data_now用于存放中间过程的数据
 
 center_point = np.random.choice(300,3,replace=False)
 center = data_new[center_point,:20] # 随机形成的3个中心，维度为（3，21）
 
 
 distance = [[] for i in range(k)]
 distance_now = [[] for i in range(k)] # distance_now用于存放中间过程的距离
 lost = np.ones([300,k])*float('inf') # 初始lost为维度为（300，3）的无穷大
 
 for j in range(k): # 首先完成第一次划分，即第一次根据距离划分所有点到三个类别中
 distance[j] = np.sqrt(np.sum(np.square(data_new[:,:20] - np.array(center[j])), axis=1))
 data_new[:, 21] = np.argmin(np.array(distance), axis=0) # data_new 的最后一列，即标签列随之改变，变为距离某中心点最近的标签，例如与第0个中心点最近，则为0
 
 for i in range(n): # 假设迭代n次
 
 for m in range(k): # 每一次都要分别替换k=3个中心点，所以循环k次。这层循环结束即算出利用所有点分别替代3个中心点后产生的900个lost值
 
 for l in range(300): # 替换某个中心点时都要利用全部点进行替换，所以循环300次。这层循环结束即算出利用所有点分别替换1个中心点后产生的300个lost值
 
 center_now = copy.deepcopy(center) # center_now用于存放中间过程的中心点
 center_now[m] = data_now[l,:20] # 用第l个点替换第m个中心点
 for j in range(k): # 计算暂时替换1个中心点后的距离值
 distance_now[j] = np.sqrt(np.sum(np.square(data_now[:,:20] - np.array(center_now[j])), axis=1))
 data_now[:, 21] = np.argmin(np.array(distance), axis=0) # data_now的标签列更新，注意data_now时中间过程，所以这里不能选择更新data_new的标签列
 
 lost[l, m] = (dis(data_now[:, :20], center_now[data_now[:, 21].astype(int)]) \
 - dis(data_now[:, :20], center[data_new[:, 21].astype(int)])).sum() # 这里很好理解lost的维度为什么为300*3了。lost[l,m]的值代表用第l个点替换第m个中心点的损失值
 
 if np.min(lost) < 0: # lost意味替换代价，选择代价最小的来完成替换
 index = np.where(np.min(lost) == lost) # 即找到min(lost)对应的替换组合
 index_l = index[0][0] # index_l指将要替代某个中心点的候选点
 index_m = index[1][0] # index_m指将要被替代的某个中心点，即用index_l来替代index_m
 
 center[index_m] = data_now[index_l,:20] #更新聚类中心
 
 for j in range(k):
 distance[j] = np.sqrt(np.sum(np.square(data_now[:, :20] - np.array(center[j])), axis=1))
 data_new[:, 21] = np.argmin(np.array(distance), axis=0) # 更新参考矩阵,至此data_new的标签列得以更新，即完成了一次迭代
 
 return data_new # 最后返回data_new，其最后一列即为最终聚好的标签
 
 
 if __name__ == '__main__':
 data_new = kmeans_wave(10,3,data)
 print(data_new.shape)
 print(np.mean(data[:,21] == data_new[:,21])) # 验证划分准确度

**总结**：划分方法具有线性复杂度，聚类的效率高的优点。然而，由于它要求输入数字k确定结果簇的个数，并且不适合于发现非凸面形状的簇，或者大小差别很大的簇，所以这些启发式聚类方法对在中小规模的数据库中发现球状簇很适用。为了对大规模的数据集进行聚类，以及处理复杂形状的聚类，基于划分的方法需要进一步的扩展。

**1.2 层次方法（hierarchical method）**

层次方法对给定数据对象集合进行层次的分解。根据层次的分解如何形成，层次的方法可以分为凝聚的和分裂的\[30\]。凝聚的方法，也称为自底向上的方法，一开始将每个对象作为单独的一个组，然后相继地合并相近的对象或组，直到所有的组合并为一个（层次的最上层），或者达到一个终止条件。分裂的方法，也称为自顶向下的方法，一开始将所有的对象置于一个簇中，在迭代的每一步中，一个簇被分裂为更小的簇，直到最终每个对象在单独的一个簇中，或者达到一个终止条件。

主要的凝聚聚类算法有CURE,CHAMELEON,BIRCH,ROCK等。

**1．BIRCH算法**

BIRCH(Balanced Iterative Reducing andClustering using Hierarchies)算法使用了一种叫做CF-树(聚类特征树，即ClusteringFeature Tree)的分层数据结构，来对数据点进行动态、增量式聚类。CF-树是存储了层次聚类过程中的聚类特征信息的一个加权平衡树，树中每个节点代表一个子聚类，并保持有一个聚类特征向量CF。每个聚类特征向量是一个三元组，存储了一个聚类的统计信息。聚类特征向量中包含了一个聚类的三个统计信息：数据点的数目N，这N个数据点的线性和，以及这N个数据点的平方和SS。一个聚类特征树是用于存储聚类特征CF的平衡树，它有两个参数：每个节点的最大子节点数和每个子聚类的最大直径。当新数据插入时，就动态地构建该树。与空间索引相似，它也用于把新数据加入到正确的聚类当中。

BIRCH算法的主要目标是使I/0时间尽可能小，原因在于大型数据集通常不能完全装入内存中。BIRCH算法通过把聚类分为两个阶段来达到此目的。首先通过构建CF-树对原数据集进行预聚类，然后在前面预聚类的基础上进行聚类。

**2．CURE算法**

CURE(Clustering Using Representative)算法选择基于质心和基于代表对象方法之间的中间策略。它不用单个质心或对象来代表一个簇，而是选择数据空间中固定数目的具有代表性的点。针对大型数据库，CURE采用随机取样和划分两种方法的组合：一个随机样本首先被划分，每个划分再被部分聚类。

**3．ROCK算法**

CURE算法不能处理枚举型数据，而ROCK算法是在CURE基础之上适用于枚举数据的聚结分层聚类算法。通过把两个聚类的聚集相互连接度(aggregateinterconnectivity)与用户定义的静态相互连接模型相比较，从而度量两个聚类之间的相似度。其中，两个聚类的相互连接度是指两个聚类之间的交叉连接数目，而连接link(pi,pj)是指这两点之间的共同邻居数。换句话说，聚类相似度是用不同聚类中又共同邻居的点的数目来确定的。

ROCK算法首先用相似度阀值和共同邻居的概念，从给定的数据相似度矩阵中构建一个稀疏图，然后对该稀疏图使用分层聚类算法进行聚类。

**4．Chameleon算法**

Chameleon（变色龙）是一个利用动态模型的层次聚类算法。算法思想是：首先通过一个图划分算法将数据对象聚类为大量相对较小的子聚类，然后用一个凝聚的层次聚类算法通过反复地合并子类来找到真正的结果簇。它既考虑了互连性，又考虑了簇间的近似度，特别是簇内部的特征，来确定最相似的子簇\[31\]。

Chameleon跟CURE和DBSCAN相比，在发现高质量的任意形状的聚类方面有更强的能力。但是，在最坏的情况下，高维数据的处理代价可能对n个对象需要O(n2)的时间。

**总结：**层次的方法的缺陷在于，一旦一个步骤（合并或分裂）完成，它就不能被撤消，该技术的一个主要问题是它不能更正错误的决定。有两种方法可以改进层次聚类的结果：（a）在每层划分中，仔细分析对象间的“联接”，例如CURE中的做法。（b）综合层次凝聚和迭代的重定位方法。首先用自底向上的层次算法，然后用迭代的重定位来改进结果。

**1.3 基于密度的方法（density-based method）**

绝大多数划分方法基于对象之间的距离进行聚类，这样的方法只能发现球状的簇，而在发现任意形状的簇上遇到了困难。随之提出了基于密度的另一类聚类方法，其主要思想是：只要邻近区域的密度（对象或数据点的数目）超过某个阈值，就继续聚类。也就是说，对给定类中的每个数据点，在一个给定范围的区域中必须至少包含某个数目的点。这样的方法可以用来过滤“噪声”孤立点数据，发现任意形状的簇。常见的基于密度的聚类算法有DBSCAN,OPTICS,DENCLUE等。

**1. DBSCAN算法**

DBSCAN(Density-Based Spatial Clusteringof Application with Noise)是一个基于高密度连接区域的密度聚类方法。DBSCAN通过检查数据库中每个点的ε-邻域来寻找聚类。如果一个点p的ε-邻域包含多于MinPts个点，则创建一个以p作为核心对象的新簇。然后，DBSCAN反复地寻找从这些核心对象直接密度可达的对象，这个过程可能涉及一些密度可达簇的合并。当没有新的点可以被添加到任何簇时，该过程结束。

**2. OPTICS算法**

OPTICS(Ordering Points To Identify theClustering Structure)通过对象排序识别聚类结构。OPTICS没有显式地产生一个数据集合簇，它为自动和交互的聚类分析计算一个簇次序（cluster ordering）。这个次序代表了数据的基于密度的聚类结构。它包含的信息，等同于从一个宽广的参数设置范围所获得的基于密度的聚类。也就是说，对于一个恒定的参数MinPts值，可以同时处理一组距离参数值。

OPTICS在选择参数方面具有比DBSCAN较高的灵活性，在采用空间索引时，复杂度为O(nlogn)，和DBSCAN时间复杂度相同。但是，它需要额外的空间存储每个对象的核心距离和一个适当的可达距离。

**3． DENCLUE算法**

DENCLUE(DENsity based CLUstEring)是一个基于一组密度分布函数的聚类算法。它是对k-means聚类算法的一个推广：k-means算法得到的是对数据集的一个局部最优划分，而DENCLUE得到的是全局最优划分。

DENCLUE算法有一个坚实的数学基础，概括了其他的聚类方法，包括基于划分的、层次的、及基于位置的方法；同时，对于有大量“噪声”的数据集合，它有良好的聚类特征；对于高维数据集合的任意形状的聚类，它给出了一个基于树的存储结构来管理这些单元，因此比一些有影响的算法（如DBSCAN）速度要快。但是，这个方法要求对密度参数σ和噪声阈值ξ进行仔细的选择，如果选择不当则可能显著地影响聚类结果的质量。

**1.4 基于网格的方法（grid-based method）**

基于网格的方法把对象空间量化为有限数目的单元，形成了一个网格结构。所有的聚类操作都在这个网格结构（即量化的空间）上进行。基于网格的聚类算法主要有STING,WaveCluster, CLIQUE等。

**1．STING算法**

STING(Statistical Information Grid-basedmethod)是一种基于网格的多分辨率聚类技术，它将空间区域划分为矩形单元。针对不同级别的分辨率，通常存在多个级别的矩形单元，这些单元形成了一个层次结构：高层的每个单元被划分为多个低一层的单元。关于每个网格单元属性的统计信息（例如平均值、最大值和最小值）被预先计算和存储。这些统计信息用于回答查询。

STING有几个优点：（i）由于存储在每个单元中的统计信息提供了单元中的数据不依赖于查询的汇总信息，所以基于网格的计算是独立于查询的；（ii）网格结构有利于并行处理和增量更新；（iii）该方法的主要优点是效率很高：STING扫描数据库一次来计算单元的统计信息，因此产生聚类的时间复杂度是O(n)，其中n是对象的数目。在层次结构建立后，查询处理时间是O(g)，这里g是最低层网格单元的数目，通常远远小于n。该算法的缺点：由于STING采用了一个多分辨率的方法进行聚类分析，STING聚类的质量取决于网格结构的最低层的粒度。如果粒度比较细，处理的代价会显著增加；但是，如果网格结构最低层的力度太粗，将会降低聚类分析的质量；而且，STING在构建一个父亲单元时没有考虑孩子单元和其相邻单元之间的关系，因此，结果簇的形状是isothetic，即所有的聚类边界或者是水平的，或者是竖直的，没有对角的边界。尽管该技术有快速的处理速度，但可能降低簇的质量和精确性。

**2． WaveCluster算法**

WaveCluster(Clustering with Wavelets)采用小波变换聚类，它是一种多分辨率的聚类算法，它首先通过在数据空间上加一个多维网格结构来汇总数据，然后采用一种小波变换来变换原特征空间，在变换后的空间中找到密集区域。

WaveCluster的计算复杂度是O(n)，能有效地处理大数据集合；发现任意形状的簇；成功地处理孤立点；对于输入的顺序不敏感；不要求指定诸如结果簇的数目或邻域的半径等输入参数；在实验分析中，WaveCluster在效率和聚类质量上优于BIRCH，CLARANS和DBSCAN；实验分析也发现WaveCluster能够处理多达20维的数据。但是，对数学建模的知识要求较高\[33\]。

**3． CLIQUE算法**

CLIQUE(Clustering In QUEst)算法综合了基于密度和基于网格的聚类方法,它的中心思想是:首先，给定一个多维数据点的集合，数据点在数据空间中通常不是均衡分布的。CLIQUE区分空间中稀疏的和“拥挤的”区域（或单元），以发现数据集合的全局分布模式。接着，如果一个单元中的包含数据点超过了某个输入模型参数，则该单元是密集的。在CLIQUE中，簇定义为相连的密集单元的最大集合。

CLIQUE算法能自动发现最高维中所存在的密集聚类；它对输入数据元组顺序不敏感；也不需要假设（数据集中存在）任何特定的数据分布；它与输入数据大小呈线性关系；并当数据维数增加时具有较好的可扩展性。但是，在追求方法简单化的同时往往就会降低聚类的准确性。

**1.5 基于模型的方法（model-based method）**

基于模型的方法为每个簇假定了一个模型，寻找数据对给定模型的最佳拟合。一个基于模型的算法可能通过构建反映数据点空间分布的密度函数来定位聚类。它也基于标准的统计数字自动决定聚类的数目，考虑“噪声”数据或孤立点，从而产生健壮的聚类方法。基于模型聚类方法主要有两种：统计学方法和神经网络方法。

**1．统计学方法**

机器学习中的概念聚类就是一种形式的聚类分析。给定一组无标记数据对象，它根据这些对象产生一个分类模式。与传统聚类不同，后者主要识别相似的对象；而概念聚类则更进一步，它发现每组的特征描述；其中每一组均代表一个概念或类，因此概念聚类过程主要有两个步骤：首先完成聚类；然后进行特征描述。因此它的聚类质量不再仅仅是一个对象的函数；而且还包涵了其它因素，如所获特征描述的普遍性和简单性。

大多概念聚类都采用了统计方法，也就是利用概率参数来帮助确定概念或聚类。每个所获得的聚类通常都是由概率描述来加以表示\[34\]。

COBWEB是一种流行的简单增量概念聚类算法。它的输入对象用分类属性\-值对来描述。它以一个分类树的形式创建层次聚类。分类树的每个节点对应一个概念，包含该概念的一个概率描述，概述被分在该节点下的对象。在分类树某个层次上的兄弟节点形成了一个划分。为了用分类树对一个对象进行分类，采用了一个部分匹配函数沿着“最佳”匹配节点的路径在树中向下移动。寻找可以分类该对象的最好节点。这个判定基于将对象临时置于每个节点，并计算结果划分的分类效用。产生最高分类效用的位置应当是对象节点一个好的选择。但如果对象不属于树中现有的任何概念，则为该对象创建一个新类。

CORWEB的优点在于：他不需要用户输入参数来确定分类的个数，它可以自动修正划分中类的数目。缺点是：首先，它基于这样一个假设：在每个属性上的概率分布是彼此独立的。由于属性间经常是相关的，这个假设并不总是成立。此外，聚类的概率分布表示使得更新和存储类相当昂贵。因为时间和空间复杂度不只依赖于属性的数目，而且取决于每个属性的值的数目，所以当属性有大量的取值时情况尤其严重。而且，分类树对于偏斜的输入数据不是高度平衡的，它可能导致时间和空间复杂性的剧烈变化。

**2．神经网络方法**

神经网络聚类方法是将每个簇描述成一个标本。标本作为聚类的一个“原型”；它不一定对应一个特定的数据实例或对象。可以根据新对象与哪个标本最相似（基于某种距离计算方法）而将它分派到相应的聚类中。可以通过聚类的标本来预测分派到该聚类的一个对象的属性。上一章对此已经作了详细描述，这里不再详述。

【聚类算法比较】

基于划分聚类算法（partition clustering)

<table> 
 <tbody> 
 <tr> 
 <td> k-means： </td> 
 <td> 是一种典型的划分聚类算法，它用一个聚类的中心来代表一个簇，即在迭代过程中选择的聚点不一定是聚类中的一个点，该算法只能处理数值型数据 </td> 
 </tr> 
 <tr> 
 <td> k-modes： </td> 
 <td> K-Means算法的扩展，采用简单匹配方法来度量分类型数据的相似度 </td> 
 </tr> 
 <tr> 
 <td> k-prototypes： </td> 
 <td> 结合了K-Means和K-Modes两种算法，能够处理混合型数据 </td> 
 </tr> 
 <tr> 
 <td> k-medoids： </td> 
 <td> 在迭代过程中选择簇中的某点作为聚点，PAM是典型的k-medoids算法 </td> 
 </tr> 
 <tr> 
 <td> CLARA： </td> 
 <td> CLARA算法在PAM的基础上采用了抽样技术，能够处理大规模数据 </td> 
 </tr> 
 <tr> 
 <td> CLARANS： </td> 
 <td> CLARANS算法融合了PAM和CLARA两者的优点，是第一个用于空间数据库的聚类算法 </td> 
 </tr> 
 <tr> 
 <td> Focused CLARAN： </td> 
 <td> 采用了空间索引技术提高了CLARANS算法的效率 </td> 
 </tr> 
 <tr> 
 <td> PCM： </td> 
 <td> 模糊集合理论引入聚类分析中并提出了PCM模糊聚类算法 </td> 
 </tr> 
 </tbody> 
</table>

基于层次聚类算法：

<table> 
 <tbody> 
 <tr> 
 <td> CURE： </td> 
 <td> 采用抽样技术先对数据集D随机抽取样本，再采用分区技术对样本进行分区，然后对每个分区局部聚类，最后对局部聚类进行全局聚类 </td> 
 </tr> 
 <tr> 
 <td> ROCK： </td> 
 <td> 也采用了随机抽样技术，该算法在计算两个对象的相似度时，同时考虑了周围对象的影响 </td> 
 </tr> 
 <tr> 
 <td> CHEMALOEN（变色龙算法）： </td> 
 <td> 首先由数据集构造成一个K-最近邻图Gk ,再通过一个图的划分算法将图Gk 划分成大量的子图,每个子图代表一个初始子簇,最后用一个凝聚的层次聚类算法反复合并子簇，找到真正的结果簇 </td> 
 </tr> 
 <tr> 
 <td> SBAC： </td> 
 <td> SBAC算法则在计算对象间相似度时，考虑了属性特征对于体现对象本质的重要程度，对于更能体现对象本质的属性赋予较高的权值 </td> 
 </tr> 
 <tr> 
 <td> BIRCH： </td> 
 <td> BIRCH算法利用树结构对数据集进行处理，叶结点存储一个聚类，用中心和半径表示，顺序处理每一个对象，并把它划分到距离最近的结点，该算法也可以作为其他聚类算法的预处理过程 </td> 
 </tr> 
 <tr> 
 <td> BUBBLE： </td> 
 <td> BUBBLE算法则把BIRCH算法的中心和半径概念推广到普通的距离空间 </td> 
 </tr> 
 <tr> 
 <td> BUBBLE-FM： </td> 
 <td> BUBBLE-FM算法通过减少距离的计算次数，提高了BUBBLE算法的效率 </td> 
 </tr> 
 </tbody> 
</table>

基于密度聚类算法：

<table> 
 <tbody> 
 <tr> 
 <td> DBSCAN： </td> 
 <td> DBSCAN算法是一种典型的基于密度的聚类算法，该算法采用空间索引技术来搜索对象的邻域，引入了“核心对象”和“密度可达”等概念，从核心对象出发，把所有密度可达的对象组成一个簇 </td> 
 </tr> 
 <tr> 
 <td> GDBSCAN： </td> 
 <td> 算法通过泛化DBSCAN算法中邻域的概念，以适应空间对象的特点 </td> 
 </tr> 
 <tr> 
 <td> DBLASD： </td> 
 </tr> 
 <tr> 
 <td> OPTICS： </td> 
 <td> OPTICS算法结合了聚类的自动性和交互性，先生成聚类的次序，可以对不同的聚类设置不同的参数，来得到用户满意的结果 </td> 
 </tr> 
 <tr> 
 <td> FDC： </td> 
 <td> FDC算法通过构造k-d tree把整个数据空间划分成若干个矩形空间，当空间维数较少时可以大大提高DBSCAN的效率 </td> 
 </tr> 
 </tbody> 
</table>

基于网格的聚类算法：

<table> 
 <tbody> 
 <tr> 
 <td> STING： </td> 
 <td> 利用网格单元保存数据统计信息，从而实现多分辨率的聚类 </td> 
 </tr> 
 <tr> 
 <td> WaveCluster： </td> 
 <td> 在聚类分析中引入了小波变换的原理，主要应用于信号处理领域。（备注：小波算法在信号处理，图形图像，加密解密等领域有重要应用，是一种比较高深和牛逼的东西） </td> 
 </tr> 
 <tr> 
 <td> CLIQUE： </td> 
 <td> 是一种结合了网格和密度的聚类算法 </td> 
 </tr> 
 <tr> 
 <td> OPTIGRID： </td> 
 </tr> 
 </tbody> 
</table>

基于神经网络的聚类算法：

<table> 
 <tbody> 
 <tr> 
 <td> 自组织神经网络SOM： </td> 
 <td> 该方法的基本思想是--由外界输入不同的样本到人工的自组织映射网络中，一开始时，输入样本引起输出兴奋细胞的位置各不相同，但自组织后会形成一些细胞群，它们分别代表了输入样本，反映了输入样本的特征 </td> 
 </tr> 
 </tbody> 
</table>

基于统计学的聚类算法：

<table> 
 <tbody> 
 <tr> 
 <td> COBWeb： </td> 
 <td> COBWeb是一个通用的概念聚类方法，它用分类树的形式表现层次聚类 </td> 
 </tr> 
 <tr> 
 <td> CLASSIT： </td> 
 </tr> 
 <tr> 
 <td> AutoClass： </td> 
 <td> 是以概率混合模型为基础，利用属性的概率分布来描述聚类，该方法能够处理混合型的数据，但要求各属性相互独立 </td> 
 </tr> 
 </tbody> 
</table>

几种常用的聚类算法从可伸缩性、适合的数据类型、高维性（处理高维数据的能力）、异常数据的抗干扰度、聚类形状和算法效率6个方面进行了综合性能评价，评价结果如表1所示：

<table> 
 <tbody> 
 <tr> 
 <td> 算法名称 </td> 
 <td> 可伸缩性 </td> 
 <td> 适合的数据类型 </td> 
 <td> 高维性 </td> 
 <td> 异常数据的抗干扰性 </td> 
 <td> 聚类形状 </td> 
 <td> 算法效率 </td> 
 </tr> 
 <tr> 
 <td> WaveCluster </td> 
 <td> 很高 </td> 
 <td> 数值型 </td> 
 <td> 很高 </td> 
 <td> 较高 </td> 
 <td> 任意形状 </td> 
 <td> 很高 </td> 
 </tr> 
 <tr> 
 <td> ROCK&nbsp; </td> 
 <td> 很高 </td> 
 <td> 混合型&nbsp; </td> 
 <td> 很高 </td> 
 <td> 很高&nbsp; </td> 
 <td> 任意形状 </td> 
 <td> 一般 </td> 
 </tr> 
 <tr> 
 <td> BIRCH </td> 
 <td> 较高 </td> 
 <td> 数值型&nbsp; </td> 
 <td> 较低&nbsp; </td> 
 <td> 较低&nbsp; </td> 
 <td> 球形&nbsp; </td> 
 <td> 很高 </td> 
 </tr> 
 <tr> 
 <td> CURE&nbsp; </td> 
 <td> 较高 </td> 
 <td> 数值型&nbsp; </td> 
 <td> 一般&nbsp; </td> 
 <td> 很高&nbsp; </td> 
 <td> 任意形状&nbsp; </td> 
 <td> 较高 </td> 
 </tr> 
 <tr> 
 <td> K-Prototypes&nbsp; </td> 
 <td> 一般 </td> 
 <td> 混合型&nbsp; </td> 
 <td> 较低&nbsp; </td> 
 <td> 较低&nbsp; </td> 
 <td> 任意形状&nbsp; </td> 
 <td> 一般 </td> 
 </tr> 
 <tr> 
 <td> DENCLUE&nbsp; </td> 
 <td> 较低 </td> 
 <td> 数值型&nbsp; </td> 
 <td> 较高&nbsp; </td> 
 <td> 一般&nbsp; </td> 
 <td> 任意形状&nbsp; </td> 
 <td> 较高 </td> 
 </tr> 
 <tr> 
 <td> OptiGrid </td> 
 <td> 一般 </td> 
 <td> 数值型&nbsp; </td> 
 <td> 较高&nbsp; </td> 
 <td> 一般&nbsp; </td> 
 <td> 任意形状&nbsp; </td> 
 <td> 一般 </td> 
 </tr> 
 <tr> 
 <td> CLIQUE&nbsp; </td> 
 <td> 较高 </td> 
 <td> 数值型&nbsp; </td> 
 <td> 较高&nbsp; </td> 
 <td> 较高&nbsp; </td> 
 <td> 任意形状&nbsp; </td> 
 <td> 较低 </td> 
 </tr> 
 <tr> 
 <td> DBSCAN&nbsp; </td> 
 <td> 一般 </td> 
 <td> 数值型&nbsp; </td> 
 <td> 较低&nbsp; </td> 
 <td> 较高&nbsp; </td> 
 <td> 任意形状&nbsp; </td> 
 <td> 一般 </td> 
 </tr> 
 <tr> 
 <td> CLARANS&nbsp; </td> 
 <td> 较低 </td> 
 <td> 数值型&nbsp; </td> 
 <td> 较低&nbsp; </td> 
 <td> 较高&nbsp; </td> 
 <td> 球形&nbsp; </td> 
 <td> 较低 </td> 
 </tr> 
 </tbody> 
</table>

[k-medoids]: https://en.wikipedia.org/wiki/K-medoids#Demonstration_of_PAM
[1055519-20171102225130873-1337967409.png]: https://images2017.cnblogs.com/blog/1055519/201711/1055519-20171102225130873-1337967409.png
[1055519-20171102225505857-681080820.png]: /images/20220522/91fc073eb227412880ca6ddbda5fdb8d.png
[1055519-20171102225841123-1288897683.png]: /images/20220522/0252ebe4c3bf4d38861029d2e73a229b.png
[1055519-20171102230206623-1699966022.png]: https://images2017.cnblogs.com/blog/1055519/201711/1055519-20171102230206623-1699966022.png
[1055519-20171102230223451-1343070688.png]: /images/20220522/35690bb1d83444b585965f05d64ee211.png