《数据挖掘导论》总结之聚类篇

聚类分析将数据划分成有意义的簇,如果目标是划分成有意义的组,则簇应当捕获数据的自然结构。 聚类的目的可以分为2类:

  1. 旨在理解的聚类。比如生物学,信息检索,气候模式,心理学和医学,商业等。

  2. 旨在实用的聚类。旨在汇总数据,压缩数据,有效地发现最近邻。

1. 不同的簇类型

聚类旨在发现有用的簇,毫无疑问,有许多不同的簇概念,例子见图1。QQ截图20130221151415

  1. 明显分离的。簇是对象的集合,其中每个对象到同簇中每个对象的距离比到不同簇的任意对象都近。

  2. 基于原型的。簇是对象的集合,其中每个对象到定义该簇的原型的距离比到其他簇的原型的距离都近。对于有连续属性的数据,簇的原型通常是质心。当质心无意义(分类属性)时,原型通常是中心点,这种簇被看做基于中心的簇。

  3. 基于图的。如果数据用图表示,其中结点是对象,而边代表对象之间的联系,则簇可以定义为连通分支,即相互连通单不对组外对象连通的对象组。基于图的簇一个重要例子是基于邻近的簇,其中每个对象到该簇中某个对象的距离比到不同簇中的任意点距离更近。

  4. 基于密度的。簇是对象的稠密区域,被低密度的区域环绕。

  5. 共同性质的(概念簇)。我们把簇定义为有某种共同性质的对象的集合(包括前面全部),但是可以包含新的簇类型。

2. 基于原型的聚类算法

2.1 K均值

K均值的算法是一种简单的基于原型的聚类算法,伪代码和例子见图2。QQ截图20130221151444 K均值实用误差平方和来作为目标函数,公式如下 \[ SSE=\sum^k_{i=1}\sum_{x\in C_i} dist(c_i,x)^2\] 其中,\(C_i\)是第\(i\)个簇,\(x\)\(C_i\)中的点,\(c_i\)是第\(i\)个簇的均值,dist是欧几里得空间中两个对象之间的标准欧几里得距离。我们对第\(k\)个质心\(c_k\)求解,对SSE求偏导,并求解\(c_k\),如下所示: \[\begin{split} \frac{\partial}{\partial{c_k}}SSE & =\frac{\partial}{\partial{c_k}}\sum^k_{i=1}\sum_{x\in C_i} (c_i-x)^2 \\& =\sum^k_{i=1}\sum_{x\in C_i} \frac{\partial}{\partial{c_k}}(c_i-x)^2 \\& =\sum_{x\in C_{k}}2(c_k-x_k)=0 \\ \end{split}\] \[ \sum_{x\in C_{k}}2(c_k-x_k)=0 \Rightarrow m_kc_k=\sum_{x\in C_{k}}x_k \Rightarrow c_k=\frac{1}{m_k}\sum_{x\in C_{k}}x_k\] 这样,簇的最小化SSE的最佳质心是簇中各点的均值。

2.2 模糊聚类

如果对象分布在明显的分离的组中,则把对象明确分类成不相交的簇比较理想。但是在大部分情况下,数据集中的对象不能划分成明显分离的簇,指派一个对象到一个特定的簇也具有一定的任意性。这时候我们可以对每个对象和每个簇赋予一个权值,指明该对象属于该簇的程度。从数学上讲,\(w_ij\)是对象\(x_i\)属于簇\(C_j\)的权值。

需要注意的是,虽然概率方法也可以提供这样的权值,但是有时候很难确定一个合适的统计模型。在这种情况下,就需要用非概率的聚类技术提供类似的能力。模糊聚类技术基于模糊集合论,并且提供一种产生聚类的自然技术,其中隶属权值 (\(w_{ij}\))具有自然(但非概率)解释。

2.2.1 模糊集合

模糊集合:允许对象以0和1之间的某个隶属度属于一个集合。

2.2.2 模糊簇

假设我们有一个数据点的集合\(\chi=\{x_1,\cdots,x_m\}\),其中每个点\(x_i\)是一个\(n\)维点,即\(x_i=\{x_{i1},\cdots,x_{im}\}\)。模糊簇集\(\{C_1,C_2,\cdots,C_k\}\)\(\chi\)的所有可能模糊子集的一个子集。(意思是点\(x_i\)和每个簇\(C_j\)的隶属度\(w_{ij}\)已经赋值)。还需要满足以下条件: \[\sum^k_{j=1}w_{ij}=1\] \[0<\sum^m_{i=1}w_{ij}<m\] 每个簇\(C_j\)以非零权值至少包含一个点,但不以权值1包含所有点。

2.2.3 模糊c均值

这里我们仅以K均值的模糊版本——模糊c均值(FCM)为例,伪代码见图3。QQ截图20130221151515 这里SSE的定义修改为 \[SSE(C_1,C_2,\cdots,C_k)=\sum^k_{i=1}\sum_{x\in C_i}w^p_{ij}dist(c_i,x)^2\] 是传统K均值的SSE的加权版本,这里p是权值影响的指数。 计算得到的质心变为 \[c_j=\frac{\sum^m_{i=1}w_{ij}^p x_i}{\sum^m_{i=1} w_{ij}^p}\] 还需要在满足限制条件的情况下更新权值\(w_{ij}\),公式为 \[ w_{ij}=(1/dist(x_i,c_j)^2)^{\frac{1}{p-1}}/(\sum^k_{q=1}(1/dist(x_i,c_q)^2)^{\frac{1}{p-1}})\] 模糊聚类的例子见图4。QQ截图20130221151556

2.3 混合模型的聚类

基于统计模型的聚类假设数据是由一个统计过程产生的,并且通过找出最佳拟合数据的统计模型来描述数据,其中统计模型用分布和该分布的一组参数描述。而混合模型使用若干统计分布对应于一个簇,而每个分布的参数提供对应簇的描述。混合模型在之前的文章里有介绍,这里就略过。

2.4 自组织映射

自组织特征映射(SOM)基于神经网络观点的聚类和数据可视化技术,详细见书。

3.基于密度的聚类算法

3.1 DBSCAN

DBSCAN算法属于基于密度的聚类算法,相对抗噪声,可以处理任意形状和大小的簇。算法将点分为三类:

  1. 核心点(core point).点在基于密度的簇内部,点的邻域由距离函数和用户指定的聚类参数Eps决定。

  2. 边界点:不是核心点,但它落在某个核心点的邻域内。在图5中,点B是边界点。边界点可能落在多个核心点的邻域内。

  3. 噪声点:既非核心点又非边界点.在图5中,点C是噪声点。QQ截图20130221151727

伪代码见图6。QQ截图20130221151740

3.2 基于网格的聚类

基于网格的聚类将数据空间划分成网格单元,然后由足够稠密的网格单元形成簇。网格是一种在低维空间中组织数据集的有效方法,算法伪代码见下图7。QQ截图20130221151803

例子见图8。QQ截图20130221151814

3.3 子空间聚类

之前的聚类算法都是使用所有的属性来发现簇,如果仅考虑特征子集(即数据的子空间),则发现的簇很可能因为子空间的不同而不同。有两个里有可以推断子空间的簇有意义:

  1. 数据的少量属性的集合可以聚类,而其余属性是随机分布的。

  2. 在某些情况下,不同维集合中存在不同的簇。比如商品在特定的月份可能表示类似行为。

图9是子空间的示例。QQ截图20130221151835

3.3.1 CLIQUE算法

CLIQUE算法是系统地发现子空间簇的基于网格的聚类算法。检查每个子空间寻找簇是不现实的,因为这样子空间是维度的指数。CLIQUE依赖于以下性质:

如果一个点集在k维(属性(上)形成一个基于密度的簇,则相同的点集在这些维的所有可能的子集上也是基于密度的簇的一部分。

CLIQUE使用的方法与Apriori算法的先验原理十分类似,一个邻接的,形成簇的k维单元集忽略k维中的一个维之后得到的k-1维的单元集也是邻接的,并且每个低维单元包含对应高维单元的所有点,还可能包含附加的点。这样,低维单元的密度大于等于高维单元的密度。算法伪代码见图10。QQ截图20130221151858

DENCLUE和核密度估计详细见书。

4. 基于图的聚类算法

4.1 稀疏化

m个数据点的\(m\times m\)邻近度矩阵可以用一个稠密图表示,图中每个结点与其他所有节点相连接,任何一对结点之间的权值反映它们之间的邻近性。对于大部分数据集,对象只与少量对象高度相似,与其他对象相似性很弱,所以我们可以稀疏化邻近度矩阵。图11中列出了稀疏化的理想过程。QQ截图20130221151915

4.2 最小生成树聚类

见图12。QQ截图20130221151929 OPOSSUM和Chameleon详见书。

4.3 共享最近邻相似度

在某些情况下,依赖于相似度和密度的标准的方法的聚类技术不能产生理想的聚类结果。相似性的SNN解决以下两个问题:

  1. 传统的相似度在高位数据上相似度低的问题。一个对象的大多数最近邻通常属于同一个类,但是同一个中类对象之间相似性低,不能用直接相似度衡量。

  2. 密度不同的问题。见图13。QQ截图20130221151954

在上述两种情况下,相似性的SNN方法基于以下思想:

如果两个点都与一些相同的点相似,则即使直接的相似度度量不能指出,它们也相似。

算法见图14,用相似度的共享最近邻(Shared Nearest Neighbor,SNN)定义量化。QQ截图20130221152008

例子见图15。QQ截图20130221152019

Jarvis——Patrick算法,SNN密度详见书。

5. 其他

5.1 凝聚层次聚类

层次聚类常用树状图(dendrogram)的图表示。伪代码见图16.QQ截图20130221152101QQ截图20130221152055 簇之间的邻近度通常有三种定义。 1.单链(single link)。不同的两个簇的两个最近点之间的邻近度。 2.全链(complete link)。不同的两个簇的两个最远点之间的邻近度。 3.组平均(group average)。不同簇所有点对邻近度的平均值。 图17给出了示例。QQ截图20130221152113

更多具体内容请见《数据挖掘导论》。 参考文献: 《数据挖掘导论》,人民邮电出版社。