数据挖掘第四章 聚类分析

数据挖掘 聚类

---

数据挖掘技术与原理主目录：
目录

第三章目录：

---

4.1 概述

简单的描述，聚类(clustering)是将数据集划分为若干相似对象组成的多个组(group)或簇(cluster)的过程，使得同一组中对象间的相似度最大化，不同组中对象间的相似度最小化。

目的：类间相似度最大化，类间相似度最小化。簇的个数不确定。

从机器学习的角度看，聚类是一种无监督的机器学习方法，即事先对数据集的分布没有任何的了解，它是将物理或抽象对象的集合组成为由类似的对象组成的多个类的过程。

聚类也可以是不明确的，不同的角度可能产生不同的聚类结果

4.1.1 聚类分析研究的主要内容

1. 模式识别(包括特征提取或选择)
2. 适合于数据领域的模式相似性定义
3. 聚类或划分算法
4. 数据摘要
5. 输出结果的评估

4.1.2 数据挖掘对聚类算法的要求

聚类是一个富有挑战的研究领域，数据挖掘对聚类的典型要求如下：
1. 可伸缩性
2. 处理不同类型属性的能力
3. 发现任意形状的聚类
4. 用于决定输入参数的领域知识最小化
5. 对于输入记录顺序不敏感
6. 高维性
7. 处理噪音和异常数据的能力
8. 基于约束的聚类
9. 可解释性

4.1.3 典型聚类方法简介

• 基于划分的方法：划分成类子集
• 基于层次的聚类：构建系统发生树

4.2 基于划分的聚类算法

给定一个n个对象或元组的数据库，一个划分方法构建数据的k个划分，每个划分表示一个聚类，并且$k<=n$。也就是说，它将数据划分为k个组，同时满足如下的要求：
(1)每个组至少包含一个对象
(2)每个对象必须属于且只属于一个组

划分式聚类算法需要预先指定簇数目或簇中心，通过反复迭代运算，逐步降低目标函数的误差值，当目标函数值收敛时，得到最终聚类结果。

这种方法分为基于质心的划分方法和基于中心的划分方法。

4.2.1 基于k-means聚类算法

k-means聚类算法
是一种基于质心的划分方法

从数据集D中任意选择k个数据对象作为初始簇中心；
repeat
    for 数据集D中每个对象P do
        计算对象P到k个簇中心的距离
        将对象P指派到与其最近(距离最短)的簇；
    end for
    计算每个簇中对象的均值，作为新的簇的中心(选择簇超球面的中心点)
until k个簇的簇中心不再发生变化

不足：
1. 簇的个数难以确定；
2. 聚类结果对初始值的选择比较敏感；
3. 采用爬山式技术寻找最优解，容易陷入局部最优解；
4. 对噪音和异常数据敏感；
5. 不能用于发现非凸形状的簇，或具有各种不同大小的簇。

4.2.2 二分k-means算法

为了得到k个簇，将所有点的集合分裂成两个簇，从中选取一个继续分裂，如此重复直到产生k个簇。

初始化簇表，使之包含由所有的点组成的簇
Repeat
    从簇表中选取一个簇(SSE最大的那个)。
    {对选定的簇进行多次二分“试验”}
    For i=1 to 试验次数 do
        使用基于基本k-means，二分选定的簇 #即2-means
    End for
    从二分试验中选取具有最小总SSE的两个簇
    将这两个簇添加到簇表中  #选取最优的二划分
Until簇表中包含k个簇

4.2.3 k-means聚类算法的拓展

聚类表示和数据对象之间相似度的定义是最基础的问题

这里介绍一种简单的聚类表示方法，并对Minkowski距离进行推广以使聚类算法可以有效处理含分类属性的数据。

将数值型属性和分类型属性分开考虑

一个簇可以由其摘要信息来代表。

对于数值属性，距离的定义和之前一样，可以使用欧氏距离，也可以使用曼哈顿距离。

对于分类属性，两个簇之间的距离定义为：

$$diff(C_1^{(i)},C_2^{(i)}) = 1- \frac{1}{|C_1|\cdot |C_2|}\sum_{p_i\in C_i}{Freq_{C_1|D_i}(p_i)\cdot Freq_{C_2|D_i}(p_i)}$$

其中，$C_1$和$C_2$表示两个簇，$C_1^{(i)}$表示$C_1$簇在$D_i$属性上的投影，$|C_1|$表示$C_1$簇的个数；$Freq_{C_1|D_i}(p_i)$表示$C_1$在属性$D_i$属性上和样例$p_i$的$D_i$属性值相同的那个值在该属性$D_i$中的频度。

即，使用两个簇中该分类属性$D_i$的取值向量之间的点积的标准化表示两个簇之间的相似度，用1-相似性就得到了距离。

对于分类属性，样例p和样例q在属性i上的距离可以定义为：

$$dif(p_i,q_i)=\left\{ \begin{aligned} & 1 \quad p_i \neq q_i\\ & 0 \quad p_i = q_i\\ \end{aligned} \right.$$

对于连续数值属性或顺序属性，样例p和样例q在属性i上的距离可以定义为：

$$|p_i-q_i|$$

因此，对于分类属性，两个样例p和q之间的距离 (所有属性)可以定义为：

$$d(p,q)=\lgroup\sum_{i=1}^{m}{dif(p_i,q_i)^x}\rgroup^{\frac{1}{x}}$$

对于分类属性，样例p和簇$C_1$在$D_i$之间的距离可以定义为：

$$diff(p_i,C_1^{(i)}) = 1 - \frac{Freq_{C_1|D_i}{(p_i)}}{|C_1|}$$

4.2.4 k-medoids算法

在簇中，随机选择一个非中心点去替换中心点，计算代价，若代价小于0，则进行替代，否则不进行替代。

4.3 层次聚类算法

• 自下而上聚合层次聚类方法
• 自顶向下分解层次聚类方法

自下而上聚合层次聚类方法

类似于系统发生树

缺点：

• 不能够回溯，即后一步无法修正前一步错误的划分
• 效率很低: $O(n^2)$

层次聚类改进方法

4.3.1 BIRCH

(Balanced Iterative Reducing and Clustering Using Hierarchies)
聚类特征CF是一个三维向量，汇总了对象簇的信息。给定簇中n个m维对象或点，则该簇的CF定义如下：

$$CF = <n, LS, SS>$$

其中，LS是n个数据各维的和(维数等于簇的属性个数)，SS是n个数据各维的平方和。

簇的聚集：两个簇的聚集得到的CF是两个子簇CF值的和(各维数对应和)。

$$x_0 = \frac{\sum_{i=1}^{n}{x_i}}{n} = \frac{LS}{n}$$

质心坐标$x_0$可以通过LS得到。一个样例点到簇的距离可以通过计算样例点到质心的距离来得到。

$$R = \sqrt{\frac{\sum_{i=1}^{n}{(x_i-x_0)^2}}{n}} = \sqrt{\frac{nSS-LS^2}{n^2}}$$

簇的聚集程度(方差)，即离中心点之间的距离$R$可以通过LS和SS得到。

$$D = \sqrt{\frac{\sum_{i=1}^{n}\sum_{j=1}^{n}{(x_i-x_j)^2}}{n(n-1)}} = \sqrt{\frac{2nSS-2LS^2}{n(n-1)}}$$

簇的聚集程度也可以使用簇内任意两个距离和$D$来表示，也可以通过LS和SS得到。

CF树是一个高度平衡的树，它具有两个参数：分支因子和阈值$T$。分支因子表示一个节点的最大子树个数，阈值则是表示一个子树表示的簇的最大半径的大小。

4.3.2 基于密度的聚类算法

通常将簇看作是数据空间中被低密度区域(代表噪声)分割开的稠密对象区域。基于密度的方法包括：

• DBSCAN
• OPTICS

DBSCAN算法：

一种基于高密度连通区域的聚类方法，该算法将具有足够高密度的区域划分为簇，并在具有噪声的空间数据库中发现任意形状的簇，它将簇定义为密度相连的点最大的集合。点分为三类：
(1)稠密区域内部的点
(2)稠密区域边缘上的点
(3)稀疏碍于中的点

给定对象集合$D$，对象之间的距离函数为distance，邻域半径为$Eps$，表示一个点多大范围内的点算邻居点。

Eps邻域：给定对象半径Eps内的邻域称为该对象的Eps邻域。我们用$N_{Eps}{(p)}$表示点p的Eps半径内的点的集合。

$$N_{Eps}{(p)} = {q | q在数据集D中，distance(p,q) <= Eps}$$

$MinPts$表示给定邻域$N_{Eps}{(p)}$包含的点的最小数目，用来决定点p是簇的核心部分还是边界或是噪声。

• 核心对象：如果对象的Eps邻域包含至少MinPts个的对象，则称该对象为核心对象。
• 边界点：边界点的Eps邻域内的点个数少于MinPts，但是它落在某个核心店的邻域内。
• 噪音点：既不是核心点，也不落在核心点的邻域内。

直接密度可达：

如果对象p在核心对象q的Eps邻域内，则称p从q出发时是直接密度可达的。

4.4 基于模型的聚类算法

4.4.1 期望最大化方法EM

期望最大化算法是一种流行的迭代求精算法，EM不是把每个对象指派到特定的簇，而是根据一个代表隶属概率的权重将每个对象指派到簇。

利用划分的概率值打上软标签。最初初始化正态分布函数的$\mu$，然后通过计算得到概率软标签，然后进行迭代调整参数$\mu$(实质上是很多个参数)，最后得到稳定的标签。