聚类分析 Cluster Analysis

---

肝到爆炸呜呜呜

一、什么是聚类分析

关键词

1️⃣ 簇 Cluster：数据对象的集合，相同簇中的数据彼此相似，不同簇中的数据彼此相异。

2️⃣ 聚类分析 Cluster analysis：根据数据特征找到数据中的相似性，并将相似的数据聚集(分组)到一个簇中。

3️⃣ 无监督学习 Unsupervised learning：并没有为数据给出预先定义好的类别

---

好啦，我们现在有了理论储备啦！就让我们一起走进聚类分析吧~

聚类分析在我们的生活中并不陌生，甚至是随处可见的：比如商场的促销活动呀，城市规划的地块评估呀，生物学中基因的分组呀，GIS中的空间模式分布评估呀，还有各种标签tag什么的。在数据挖掘领域中，聚类分析常常用于：

• 作为一个深入了解数据分布的独立工具(As a stand-along tool to get insight into data distribution)
• 作为其他算法的预处理过程(As a preprocessing step for other algorithms)

这样一个依托于无监督的分组方法，结果可是随心所欲千奇百怪的哦，比如在动漫角色特征聚类里，有的聚类方法把灰毛的伊蕾娜分到了白毛组，有的聚类方法则是分到了银发组。

为了避免这种情况，我们需要设定指标去评估一个聚类方法的好坏，让不同的聚类结果之间有了可比性，就能知道哪些是好孩子啦。

一种好的聚类方法可以生成好质量的簇，而这些簇满足：

• 簇内相似性高
• 簇间相似性低

可以理解为，不同学校的小孩子之间应该接触的少，一个学校的小孩子之间应该接触的多。

在这基础上，聚类结果的具体质量应该取决于相似度度量算法，以及它的实现。如果一个聚类还能挖掘一些或者全部的隐藏模式，我们也可以认为它是一个高质量的聚类方法。

The quality of clustering result depends on both the similarity measure used by the method and its implementation.

The quality of a clustering method is also measured by its ability to discover some or all of the hidden patterns.

通常，数据科学家们使用相异度/相似度矩阵 Dissimilarity/Similarity metric来对不同数据特征之间的相似度进行度量，一般是通过距离公式进行，数据$i$和$j$之间的距离可以记作$d(i,j)$。

当然，不同数据类型之间，比如连续数据、布尔型数据、分类数据、语义数据、序数数据，他们所运用的距离度量方法也是不同的。对于距离度量方法的权重分配，也是由数据语义和应用所决定的。

Weights may be assigned to different variables based on applications and data semantics.

相似性度量只是最基本的，下表给出了聚类的一些其他需求：

需求	解释
Scalability	可扩展的
Ability to deal with different types of attributes	能够处理不同属性
Ability to handle dynamic data	能处理动态数据
Discovery of clusters with arbitrary shape	发现任意形状的簇
Minimal requirements for domain knowledge to determine input parameters	对确定输入参数的领域知识的最低要求
Able to deal with noise and outliers	能处理噪声和离群数据
Insensitive to order of input records	对于输入数据顺序的不敏感性
High dimensionality	高维特性
Incorporation of user-specified constraints	合并用户指定的约束条件
Interpretability and usability	可解释性和可应用性

除却聚类方法的评估外，我们也可以基于簇的属性进行评估哦，那么一个普通的簇有什么属性呢？

质心 Centroid

一般是一个簇的中间，可以写作：
$$C=\frac{{\sum }_i^N(t_i)}{N}$$
半径 Radius

簇中点到簇质心的距离的平均（点与中心），写作：
$$R=\sqrt{\frac{{\sum }_i^N(t_i-c{)}^2}{N}}$$
直径 Diameter

簇中所有点之间的平均距离的平方根（点与点)，写作：
$$D=\sqrt{\frac{{\sum }_i^N{\sum }_j^N(t_i-t_j{)}^2}{N(N-1)}}$$

---

二、聚类分析中的数据类型

好了，上一节我们知道了什么是簇，什么是聚类，以及如何评价一个聚类方法的好坏，下面我们就要进一步了解聚类分析是如何运作的。数据挖掘是以数据为主导，以数据为驱动的，抛开具体数据空谈算法是不合理的。所以，我们需要来看看聚类分析中的输入数据究竟都什么牛马。

关键字

1️⃣ 数据矩阵 Data matrix：数据矩阵就是把数据堆叠在一起形成的二维表啦，每一行是一个记录record，每一列是一个属性class, feature, attribute... etc.，可以写作如下形式：
$$\left[\begin{array}{ccc}{x}_{11}& \cdots & x_{1n}\\ ⋮& & ⋮\\ x_{m1}& \cdots & x_{mn}\end{array}\right]$$
2️⃣ 相异矩阵 Dissimilarity matrix：用于衡量各个数据之间的相异程度，等于$1-相似度$，所以元素自己和自己之间的相异度是0啦：
$$\left[\begin{array}{ccc}0& & \\ ⋮& 0& \\ d(n,1)& \cdots & 0\end{array}\right]$$

---

从上文聚类好坏的讨论中，我们提到不同数据之间的相似性需要采用不同的距离度量方式，在聚类分析中，常见的数据源大致可分为六种：

类型	解释
Interval-scaled variables	数值变量
Binary variables	二值数据
Nominal variables	名义数据
Ordinal variables	顺序数据
Ration-scaled variables	比率尺度数据
Variables of mixed type	混合数据

1️⃣ 数值变量

我们对这类数据的处理是需要先进行标准化将其进行区间缩放的，标准化方法称为z得分(z-score)法：
$$z_{if}=\frac{x_{if}-m_f}{s_f}$$
其中，
$$m_f=\frac{x_{1f}+x_{2f}+...+x_{nf}}{n}$$
也就是数据集中$f$属性的平均值；
$$s_f=\frac{\sum |x_{if}-m_f|}{n}$$
也就是采用绝对值替代开平方算法的标准差，z-score与标准差标准化的区别就在于使用了绝对值。使用平均绝对偏差，要比使用标准差更加稳健。

Using mean absolute deviation is more robust than using standard deviation.

好啦，标准化完后，我们就可以用距离度量公式计算相似性啦，距离度量公式有很多，例如欧氏距离、马氏距离、切比雪夫距离、曼哈顿距离、闵可夫斯基距离、汉明距离、余弦距离等等，这里我们介绍闵可夫斯基距离。
$$d(i,j){=}^q\sqrt{\sum |x_{in}-x_{jn}|}$$
当$q$取1，就成了曼哈顿距离，当$q$取2，就成了欧氏距离。

---

2️⃣ 二值变量

对于一个二值数据表，我们可以写作：

其中，数据之间的对称性度量表示为：
$$d(i,j)=\frac{b+c}{a+b+c+d}$$
不对称性度量表示为：
$$d(i,j)=\frac{b+c}{a+b+c}$$
在不对称矩阵中，我们需要注意的是后面那个不对称性度量。

---

3️⃣ 名义数据

这类数据呢，一般来说不具备可比性。比如小明小红小芳，红黄蓝什么的。

目前主流的处理方法有两种：

第一种，简单匹配。
$$d(i,j)=\frac{p-m}{p}$$
其中，$p$表示总的名义数据数量，$m$表示两个数据匹配到的数据次数。

第二种，构建one-hot编码。

第一种方法常在简单处理中使用，而第二种一般多见于机器学习和深度学习。

---

4️⃣ 序数数据

这类数据相较于名义数据，虽然还是属于定性数据范畴但是带上了可比性哦。比如：大中小，优良差什么的。

对其的处理分为三步：

第一步，将其按照大小排列，用大小次序代替数据值。
r i f ∈ { 1 , . . . , M f } r_{if}\in\{1,...,M_f\} rif​∈{1,...,Mf​}
第二步，将数据的范围缩放到$[0,1]$区间：
$$z_{if}=\frac{r_{i}f-1}{M_f-1}$$
第三步，通过数值的方式，对数据的不相似性进行计算。

---

5️⃣ 比率数据

比率数据是一个非线性的尺度，一般不同比率之间的差距是指数倍的。对其进行的处理分为三步：

首先先取对数，使其区间缩放：
$$y_{if}=log(x_{if})$$
接着，假设他们是一个连续数据，并将他们的秩作为定序数据

最后，在利用处理区间缩放数据的方式对其进行计算。

---

6️⃣ 混合数据

一种常用的权衡多种属性距离的公式如下所示：
$$d(i,j)=\frac{{\sum }_{f=1}^p{\sigma }_{ij}^{(f)}{d}_{ij}^{(f)}}{{\sum }_{f=1}^p{\sigma }_{ij}^{(f)}}$$
其中，${\sigma }_{ij}^{(f)}$是一个二值量，当两个数据同时具有属性列$f$时，这个值取到$1$，否则，在任意数据缺失该属性列，或者当$f$是一个非对称属性，且$x_{if}=x_{jf}=0$时取到$0$。$d$的计算则是根据属性类型，应用各自的公式。

---

好了，说完了每种类型以及距离度量后，我们来做个小练习吧！

这样一组数据中，Test-1是分类数据，Test-2是定序数据，Test-3则是比率数据。

我们现在要计算整张表的数据相异度矩阵。

根据混合数据计算公式，我们需要分别对不同种的属性计算距离。

首先是对Test-1的分类数据，我们采用简单匹配规则进行计算，得到的相异矩阵为：
$$\left[\begin{array}{ccccc}0& & & & \\ 1& 0& & & \\ 1& 1& 0& & \\ 0& 1& 1& 0& \end{array}\right]$$
对于Test-2的定序数据，我们需要先转换成rank值，然后进行区间缩放，最后距离公式进行计算，这里我们选用的是曼哈顿距离

原始数据	Rank值	缩放值
excellent	3	1
fair	1	0
good	2	0.5
excellent	3	1

计算的结果为：

d(1,0)	1
d(2,0)	0.5
d(2,1)	0.5
d(3,0)	0
d(3,1)	1
d(3,2)	0.5

$$\left[\begin{array}{ccccc}0& & & & \\ 1& 0& & & \\ 0.5& 0.5& 0& & \\ 0& 1& 0.5& 0& \end{array}\right]$$

对于Test-3，我们先对取对数，然后将对数视作数值型数据进行规范化后，再计算距离。

规范化公式为：
$$y=\frac{x-min}{max-min}$$

原始数据	对数	缩放值
445	2.65	0.75
22	1.34	0
164	2.21	0.5
1210	3.08	1

于是T3最终的结果为：
$$\left[\begin{array}{ccccc}0& & & & \\ 0.75& 0& & & \\ 0.25& 0.5& 0& & \\ 0.25& 1& 0.5& 0& \end{array}\right]$$
综合三个属性列，计算结果为：
$$d(i,j)=\frac{d_1(i,j)+d_2(i,j)+d_3(i,j)}{3}$$

$$\begin{gathered} \left[\begin{array}{ccccc}0& & & & \\ \frac{0.75+1+1}{3}& 0& & & \\ \frac{0.25+0.5+1}{3}& \frac{0.5+0.5+1}{3}& 0& & \\ \frac{0.25+0+0}{3}& \frac{1+1+1}{3}& \frac{0.5+0.5+1}{3}& 0& \end{array}\right] \\ =\left[\begin{array}{ccccc}0& & & & \\ 0.92& 0& & & \\ 0.58& 0.67& 0& & \\ 0.08& 1& 0.67& 0& \end{array}\right] \end{gathered}$$

---

三、主要聚类算法的分类

我们终于要进入聚类分析的核心：聚类分析算法啦!

根据算法之间的异同，我们可以将他们分为五大类(没错，这也算是一种聚类)。

1️⃣ 分区方法

• 构建各种分区，然后通过准则对他们进行评估，例如均方差。
• 典型方法：k-means, k-medoids, CLARANS

2️⃣ 层次方法

• 使用某些准则创建数据的层次分解
• 典型方法：Diana, Agnes, BIRCH, ROCK, CHAMELEON

3️⃣ 基于密度的方法

• 基于连通性和密度函数
• 典型方法：DBSACN, OPTICS, DenClue

4️⃣ 基于格网的方法

• 基于多粒度的结构
• 典型方法：STING, WaveCluster, CLIQUE

5️⃣ 基于概率统计学模型

• 典型方法：EM

---

四、分区方法 Partitioning Methods

基本概念

将有n个对象的数据库D按照规则(如最小平方和)划分成k个簇。

经典算法

1️⃣ K-Means聚类

• 初始化：给定k个随机初始化的中心点
• 迭代：计算每个簇当前的质心
• 计算每个点到点前簇中心的距离，并将他们分配进最近的簇

时间复杂度：$O(tkn)$，$n$是对象个数，$k$是簇个数，$t$是迭代次数。

通常条件下会止于全局最优解。

缺点：

• 不适用于分类数据(只能计算数值)
• 需要指定聚类簇的个数
• 无法处理有噪声的情况和异常值
• 不适合发现非凸型的簇

变化

🏷 处理分类数据：k-modes算法

• 用模式(modes)代替原先的均值
• 基于新的不相似度量方式处理分类对象
• 使用一种基于频率的方式对簇进行更新

🏷 处理混合数据：k-prototype

🏷 期望最大化扩展

• 基于加权度量进行计算

🏷 处理异常数据：k-Medoids算法

• 采用簇中最中心的点来代替原先的均值，此时，这个中心点是实际存在的点

实现

import random
import math

# 随机生成100个点
points=[(random.randint(-50,50),random.randint(-50,50)) for i in range(100)]

def k_Means(poi,k=5,epochs=100):

    # 初始化
    centroid=[] # 质心点
    cluster=[[0]*(len(poi[0]))+[0] for i in range(k)] # 记录一个簇中所有点每一个维度上坐标的总和，以及簇点的个数，这步是方便计算罢了
    PoiClass=[-1 for i in range(len(poi))]# 映射表，输出每个点对应的类
    Break=[-1 for i in range(len(poi))] # 用来控制逻辑，比如当这个表跟映射表的差距小于2时，我们就不迭代了

    # 随机选取中心点
    # 无放回抽样
    for i in range(k):
        if (v:=random.choice(poi)) not in centroid:
            centroid.append(v)

    # 计算每个点的欧氏距离
    def edis(x,y):
        return math.sqrt(sum([(x[i]-y[i])**2 for i in range(len(x))]))

    # 开始迭代
    for i in range(epochs):

        # 计算每个点到中心的距离
        for pId,p in enumerate(poi):
            dis,idx=2e31,0
            for Idx,c in enumerate(centroid):
                if (v:=edis(p,c))<dis:
                    dis,idx=v,Idx # 获取最小值时候的坐标
            # 簇统计量，方便计算
            for i in range(len(p)):
                cluster[idx][i]+=p[i]
            cluster[idx][-1]+=1 # 簇的数量
            # 更新映射表
            PoiClass[pId]=idx

        # 重新计算每个簇的中心，这个中心是平均值，并不一定是存在的点
        for i,v in enumerate(cluster):
            new_c=[]
            for j in range(len(v)-1):
                new_c.append(v[j]/v[-1])
            centroid[i]=new_c
            cluster[i]=[0]*len(poi[0])+[0] # 将常量清零
        # 设置终止迭代条件
        if sum(PoiClass[i]==Break[i] for i in range(len(poi)))>=len(poi):
            return PoiClass
        Break=PoiClass[:]
    return PoiClass

---

五、层次方法 Hierarchical Methods

这类方法并不需要设置初始的聚类簇k，但是需要设置终止条件。例如：

相较于分区的方法，层次方法是一种基于概念级的，不需要人为给定簇大小的方法，他能够远距离的获取相似对象。

下面我们来介绍几个经典算法：

1️⃣ AGNES (Agglomerative Nesting)

• 由Kaufmann和Rousseeuw在1990年提出
• 使用单链路方法和相异矩阵
• 合并相异度最小的点
• 采用一种非下降的方式进行合并
• 最终，所有的点都会属于一个集群

2️⃣ DIANA (Divisive Analysis)

• 还是那两人在同一年提出的
• 就是AGNES的逆变换

主要缺点：

• 不能很好的进行扩展，时间复杂度至少是$O(n^2)$级别
• 不能撤销之前的操作，类似于马尔科夫链

集成基于距离和层次的聚类算法

• BIRCH(1996) 采用cf -树，逐步调整子聚类质量

• ROCK (1999)

• CHAMELEON(1999)

3️⃣ BIRCH

BIRCH是一种聚合层次聚类，他构建了一个CF树(Clustering Feature Tree)，用于增量生长。

阶段一 Phase 1

扫描数据库，生成一个在内存中的初始CF树(数据的多层次压缩，试图保留数据固有的聚类模式)

阶段二 Phase 2

使用聚类算法对CF树的节点进行聚类

CF要素是一个记录了点数量，坐标向量，坐标平方和的要素，用这些属性去描述数据。

CF树是一个高度平衡树，它分层级的去存储了CF要素。

构建CF树有两个要素：

• 分支系数：子项的最大数量
• 阈值：叶子结点上子簇的最大直径

大概跟这个一样。

算法步骤：

• 将每个对象插入到最近的叶子结点
• 如果一个叶子结点的直径超过阈值，那么将被分类
• 更新CF要素以及该路径上所有祖先
• 如果CF树的大小太大，从叶节点重新构建树，不重新扫描原始对象
• 两个参数（分支因子，阈值），控制树的大小

复杂度

• $O(n)$
• 只需要一次扫描就行，$IO$开销很小

缺点

▪只处理数字数据，并对数据记录的顺序敏感

▪不擅长任意形状的集群

4️⃣ CURE

CURE算法是一种采用表征量进行聚类的算法。

算法步骤

• 将每个独立点作为一个分割聚类开始
• 合并周围的簇，直到每个簇包含超过c个点
• 对于每个簇，使用c个散列点作为代表
• 如果有超过k个簇，那么将会合并表征量最接近的簇，并且更新代表点

选择表征点

• 首先先选择一个离簇平均值最远的点
• 然后，选择(c-2)个最远点采样点
• 将散列点朝着均值缩小$\alpha$
• 于是，每个散列点$p$的表征都有：$p+\alpha (mean-p)$

合并

• 两个簇表征点最小的欧氏距离

特点

• 由于存在多个代表点，所以CURE可以用于发现任意形状的簇
• 对于异常值不敏感
  • 由于向平均值做了缩小
• 时间复杂度为：$O(n^{2}log(n))$
• 对于大规模的数据库，还是要进行分区和采样的

---

六、 基于密度的方法 Density-Based Methods

特点

• 发现任意形状的簇
• 能够处理噪声
• 需要密度参数作为终止条件
• 复杂度是$O(n^2)$

一般来说，基于密度的方法有两个主要的参数：

1️⃣ n邻域

• 点半径n内的邻域

2️⃣ 最小点

• 邻域内包含的最小点数量

核心对象

如果一个点邻域内的点超过了最小点数量，那么这个点就是一个核心对象(core object)

直接密度可达

• 一个点$p$是一个点$q$的直接密度可达点
  • $p$属于$q$的邻域
  • $q$是一个核心对象

例如：

密度可达

如果$p$可以由$q$的直接可达链得到，那么$p$称为$q$的密度可达点。

这个意思是，$o$是$q$的直接可达点，$p$是$o$的直接可达点，于是有：
$$q->o->p$$

密度连接

密度连接点表示如果$p$和$q$都是$o$的密度可达点，那么$p$和$q$称为密度连接点

下面我们介绍一个老大哥：DBSCAN

算法步骤

• 设置每个对象为未访问

• 随机选择一个未访问的点$p$,标记$p$表示访问

• 如果p的半径为$n$的邻域中至少存在MinPts个对象

  • 我们就创建一个新的簇，并将$p$加入$c$
  • 设N 是$p$邻域中对象的集合
  • 对在$N$中的每个点$p^{\prime }$
    • 如果$p^{\prime }$是未访问的
      • 标记$p^{\prime }$为访问节点
      • 如果这个$p^{\prime }$也是核心节点，那么将它范围内的点加入到$N$
    • 如果$p^{\prime }$还不是任何簇中的成员，我们就把$p^{\prime }$加入$c$
  • 输出簇$c$

• 否则，标记$p$为噪声

• 重复以上直到每个点被访问

实现

def DBSCAN(poi,radius=1,MinPts=5):
    def edis(x,y):
        return math.sqrt(sum((x[i]-y[i])**2 for i in range(len(x))))
    unvisit=set([i for i in range(len(poi))]) # 创建访问表
    Clusters=[-1]*len(poi) # 一个hash表，判断哪个点对应哪个簇
    c=0

    while len(unvisit):
        # 随机选一个中心点
        p=random.choice(list(unvisit))
        unvisit.remove(p)
        # 邻域展开！
        neighbor=set()
        for id,pn in enumerate(poi):
            if edis(poi[p],pn)<=radius:
                neighbor.add(id)
        if len(neighbor)>=MinPts:
            # 创建一个新的簇
            Clusters[p]=c
            # 遍历邻域点
            while neighbor:
                id=neighbor.pop()
                if id in unvisit:
                    unvisit.remove(id)
                    # 找他的邻域
                    n=set()
                    for Id,pi in enumerate(poi):
                        if edis(poi[id],pi)<radius:
                            n.add(Id)
                    if len(n)>=MinPts:
                        # 合并
                        neighbor|=n
                    # 如果这个点不属于任何簇，将其加入c
                if Clusters[id]==-1:
                    Clusters[id]=c
        # 否则，我们认为p是一个噪声(-1)
            c+=1
    return Clusters

print(DBSCAN(points))

结果展示

嗯，离群点被标记为了-1

如何选择距离也会对结果产生很大的影响。

---

七、基于格网的方法 Grid-Based Methods

采用多分辨率网格数据结构

有几种有趣的方法

• STING(一种统计信息网格方法) by Wang, Yang, Muntz)(1997)

• WaveCluster由Sheikholeslami、Chatterjee和Zhang设计

  • 利用小波方法的多分辨率聚类方法

• CLIQUE: Agrawal等人(SIGMOD ’ 98)

  • 在高维数据上处理

我们来看一个算法：STING

描述

• 空间区域被划分为矩形单元格

• 有几个级别的单元对应不同的分辨率级别

• 上层的每个单元都被划分为下一层的一些更小的单元

• 每个单元格的统计信息预先计算和存储，并用于回答查询
• 从低级单元的统计量可以很容易计算出高级单元
• 群集是根据计数、单元格大小等来识别的

有点像高维度的线段树

查询方法

• 使用自顶向下的方法来回答空间数据查询
• 从一个预先选择的层开始-通常有少量的单元
• 对于当前级别中的每个单元格，计算置信区间
• 将不相关的单元格从进一步的考虑中删除
• 完成检查当前层后，继续检查下一层相关单元格
• 重复这一过程，直到到达底层

优势

• 独立查询
• 增量更新
• $O(k$)查询复杂度
• $O(n)$生成复杂度

缺点

• 所有的簇边界都是水平或垂直的，没有检测到对角线边界
• 处理时间取决于每个网格的大小

这类方法用的比较少，所以就简略介绍下了

---

八、异常分析 Outlier Analysis

什么是异常值(极端值、离群点)Outlier？

• 这组对象与其余的数据有很大的不同
  • 可能是由于测量或者执行时的误差引起的
  • 也可能是变量内在可变性引起的

寻找异常值是非常有价值的。

那么如何找到一组数据中不听话的孩子呢？

1️⃣ 可视化

2️⃣ 聚类

3️⃣ 计算方法

• 基于统计学的检测方法
• 基于偏差的检测方法
• 基于距离的检测方法

基于统计学的聚类检查方法

• 假设数据集有一个分布(例如正态分布)，然后使用不一致性检验找到异常值

缺点

• 大多数测试只能对单个属性进行
• 很多时候，数据的分布并不会给出
• 需要输入参数

基于距离的异常值检测方法

• 这个方法不需要统计假设和分布，克服了传统统计学方法的不足

• 基于距离的离群值:如果$A$是数据库中的一个离群值，那么在数据集$T$中，至少有一部分$p$到$A$的距离要超过$d$

• 大致可分为：

  • 基于索引的算法
  • 基于单元的算法

  

1️⃣ 基于索引的算法

• 搜索每个物体$O$的半径为$d$邻居
• 基于多维索引结构，如$kd$树
• 确定每个邻接内的最大目标数量
• 最大开销$O(K{n}^2)$
• 缺点：
  • 树的构建是计算密集型的

2️⃣ 基于单元的算法

• 单元分区

  • 将数据空间分成边长是$d/2k^{1/2}$的单元

  • 每个单元有两层

    • 第一层只有一个单元厚度
    • 第二层则是$2k^{1/2}-1$单元厚度

    

• 异常检测

  • 如果第一层计数为>M，则此单元中无异常值
  • 如果第二层计数<=M，则所有对象都是异常值
  • 否则，检查单元格中的每个对象

  

基于偏差的方法

• 通过检测每个组中的主要特征来识别异常
• “偏离”此描述的对象被认为是异常值

---

九、总结

• 聚类分析根据对象的相似性对对象进行分组，具有广泛的应用

• 可以对各种类型的数据计算相似性度量

• 聚类算法可以分为分区方法、层次方法、基于密度的方法和基于网格的方法

• 异常点检测和分析对于欺诈检测等非常有用，可以通过统计、基于距离或基于偏差的方法进行