数据挖掘(六)---聚类分析：其他问题与算法
2015-11-01 22:16阅读：
转载自http://blog.163.com/zhoulili1987619@126/blog/static/3530820120152951018740/
数据挖掘(六)---聚类分析：其他问题与算法
一、基于原型的聚类
在基于原型的聚类中，簇是对象的集合，其中任何对象离定义该簇的原型比离定义其他簇的原型更近。K均值是一种简单的基于原型的聚类算法，它使用簇中对象的质心作为簇的原型。
这里讨论的聚类方法以一种或多种方式扩展基于原型的概念，如下所述：1)
允许对象属于多个簇。具体地说，对象以某个权值属于每个簇。这样的方法针对这样的事实，即某些对象与多个簇原型一样近。
2)
用统计分布对簇进行建模，即对象通过一个随机过程，由一个被若干统计参数(如均值和方差)刻画的统计分布产生。这种观点推广原型概念，并且可以使用牢固建立的统计学技术。
3)
簇被约束为具有固定的联系。通常，这些联系是指定近邻关系的约束，即两个簇互为邻居的程度。约束簇之间的联系可以简化对数据的解释和可视化。
我们考虑三种特定的聚类算法，来解释这些基于原型的聚类的扩展，模糊c均值使用模糊逻辑和模糊集合论的概念，提出一种聚类方案，它很像K均值，但是不需要硬性地将对象指派到一个簇中。混合模型聚类采取这样的方法，簇集合可以用一个混合分布建模，每个分布对应一个簇。基于自组织映射(SOM)的聚类放大在一个框架(例如二维网格机构)内进行聚类，该框架要求簇具有预先指定的相互联系。
1、模糊聚类
(1)模糊集合
模糊集合论允许对象以0和1之间的某个隶属度属于一个集合，而模糊逻辑允许一个陈述以0和1之间的确定度为真
(2)模糊簇
假定我们有一个数据点的集合X = {x1,...,xm}，其中每个点xi是一个n维点，即xi =
{xi1,...,xin}。模糊簇集C1，C2,...Ck是X的所有可能模糊子集的一个子集(这简单地表示对于每个点xi和每个簇Cj,隶属权值(度)wij已经赋予0和1之间的值。)然而，我们还想将以下合理的条件施加在簇上，以确保簇形成模糊伪划分(fuzzy
psuedo-partition)
1) 给定点xi的所有权值之和为1：
求和wij(对于j从1到k) = 1
2) 每个簇Cj以非零权值至少包含一个点，但不以1权值1包含所有的点：
0 < 求和wij(对于i从1到m) < m
(3)模糊c均值
模糊c均值算法有时称作FCM
基本模糊c均值算法
1：选择一个初始模糊伪划分，即对所有的wij赋值
2：repeat
3： 使用模糊伪划分，计算每个簇的质心
4： 重新计算模糊伪划分，即wij
5:until 质心不发生变化
(替换的终止条件是'如果误差的变化低于指定的阈值'或'如果所有wij的变化的绝对值都低于指定的阈值')
初始化之后，FCM重复地计算每个簇的质心和模糊伪划分，直到划分不再改变。FCM的结构类似于K均值。K均值在初始化之后，交替地更新质心和指派到每个对象到最近的质心。具体地说，计算模糊伪划分等价于指派步骤。与K均值一样，FCM可以解释为试图最小化误差的平方和(SSE),尽管FCM是基于SSE的模糊版本。事实上，K均值可以看到FCM的特例，并且两个算法的行为相当类似.
2、使用混合模型的聚类
(1)混合模型
混合模型将数据看做从不同的概率分布得到的观测值的集合。概率分布可以是任何分布，但是通常是多元正态的，因为这种类型的分布已被人们完全理解，容易从数学上进行处理，并且已经证明在许多情况下都能产生好的结果，这种类型的分布可以对椭球粗建模。
给定几个分布(通常类型相同但参数不同)，随机地选取一个分布并由它产生一个对象。重复该过程m次，其中m是对象的个数。
(2)使用最大似然估计模型参数
给定数据的一个统计模型，必须估计该模型的参数。用于这类任务的标准方法是最大似然估计。
首先，考虑由一维高斯分布产生的m个点的集合。假定点的产生是独立的，则这些点的概率是个体点概率的乘积(再次说明，我们处理的是概率密度，但是为了简化术语，我们称其为概率)。由于概率是一个非常小的树，因此我们一般使用对数概率。
如果均值和标准差的值未知，我们需要找到一个过程来估计他们，一种方法是选择合适的参数值使得数据是最可能的(最似然的)。换言之，选择最大化公式的均值和方差。这种方法在统计学上称作最大似然原理(maximum
likelihood principle)，而使用该原理由数据估计统计分布参数的过程称作最大似然估计(Maximum
Likelihood Estimation ,MLE)
之所以称该原理为最大似然原理，是因为给定一个数据集，数据的概率看做参数的函数，称作似然函数(likelihood
function)。
(3)使用最大似然估计混合模型参数:EM算法
给定符合某分布的数据，估计单个分布的参数。对于大部分常见的分布，参数的最大似然估计由涉及数据的简单公式计算。
EM算法简单地说，给定参数值的一个猜测，EM算法计算每个点属于每个分布的概率，然后使用这些概率，计算参数的新的估计(这些参数是最大化该似然的参数)。该迭代继续下去。知道参数的估计不再改变或改变很小。这样，我们通过一个迭代搜索，仍然使用了最大似然估计。
EM算法
1：选择模型参数的初始集。
(与K均值一样，可以随机地做，也可以用各种方法)
2：repeat
3： 期望步 对于每个对象，计算每个对象属于每个分布的概率，即计算
prob(分布j|xi,Q)
4: 最大化步 给定期望步得到的概率，找出最大化该期望似然的新的参数估计
5：until 参数不再改变
(替换地，如果参数改变低于预先制定的阈值则停止。)
使用EM算法的混合模型聚类的优点和局限性
缺点：EM算法可能很慢，对于具有大量分量的模型可能不切实际；当簇只包含少量数据点，或者数据点近似协线性时，它也不能很好处理，在估计簇的个数，或更一般地，在选择正确的模型形式方面也存在问题。这个问题通常使用贝叶斯方法处理。粗略地说，贝叶斯方法基于由数据得到的估计，给出一个墨香相对于另一个模型的几率。缓和模型在有噪声和离群点时也可能有问题，尽管已经做了一些工作来处理该问题。
优点：混合模型比K均值或模糊c均值更一般，因为它可以使用各种类型的分布。这样，混合模型(基于高斯分布)可以发现不同大小和椭球形状的簇。此外，基于模型的方法提供了一种消除与数据相关联的复杂性的方法，为了看出数据中的模式，常常需要简化数据。如果模型是数据的一个好的匹配的话，用数据拟合一个模型是一种简化数据的好方法。更进一步，模型更容易刻画所产生的簇，因为它们可以用少量参数描述。最后，许多数据集实际上是随机处理的结果，因此应当满足这些模型的统计假设。
3、自组织映射
自组织特征映射(SOFM或SOM)是一种基于神经网络观点的聚类和数据可视化技术。SOM的目标是发现质心的集合(用SOM的术语叫参考向量(reference
vector))，并将数据集中的每个对象指派到提供该对象最佳近似的质心。用神经网络的术语，每个质心都与一个神经元相关联。
(1)SOM算法
SOM的显著特征是它赋予质心(神经元)一种地形(空间)组织。
SOM使用的质心具有预先确定的地形序关系。在训练过程中，SOM使用每个数据点更新最近的质心和在地形序下邻近的质心。以这种方式，对于任意给定的数据集，SOM产生一个有序的质心集合，换言之，在SOM网格中互相靠近的质心比原理的质心更加密切相关，由于这种约束，可以认为二维SOM质心在一个尽可能好地拟合n维数据的二维曲面上。SOM质心也可以看作关于数据点的非线性回归的结果。
基于SOM算法
1：初始化质心
2：repeat
3： 选择下一个对象
4： 确定到该对象最近的质心
5： 更新该质心和附近的质心，即在一个特定邻域内的质心
6：until 质心改变不多或超过某个阈值
7：指派每个对象到最近的质心，并返回质心和簇。
(2)SOM算法的优点与局限性
SOM是一种聚类技术，它将相邻关系强加在结果簇质心上。正因为如此，互为邻居的簇之间比非邻居的簇之间更相关。这种联系有利于聚类结果的解释和可视化。事实上，SOM的这一特点已经用在许多邻域，如可视化Web文档或基因矩阵数据。
SOM的局限性：1) 用户必须选择参数、邻域函数、网格类型和质心个数
2) 一个SOM簇通常并不对应于当个自然簇。
3)SOM却大具体的目标函数。SOM试图找出最好地近似数据的质心的集合，受限于质心之间地地形约束；但是SOM的成功不能用一个函数来表达。这可能使得比较不同SOM聚类的结果是困难的
4) SOM不能保证收敛，尽管实际中它通常收敛
二、基于密度的聚类
1、基于网格的聚类
网格是一种组织数据集的有效方法，至少在低维空间中如此。其基本思想是，将每个属性的可能值分割成许多相邻的区间，创建网格单元的集合(对于这里，我们假定属性值是序数的、区间的或连续的。)每个对象落入一个网格单元，网格单元对应的属性区间包含该对象的值。扫描一遍数据就可以把对象指派到网格单元中，并且还可以同时收集关于每个单元的信息，如单元中的点数。
基本的基于网格的聚类算法
1：定于一个网格单元集
2：将对象指派到合适的单元，并计算每个单元的密度
3：删除密度低于指定的阈值的单元
4：由近邻的稠密单元组形成簇
优点：基于网格的蕨类可能是非常有效的。给定每个属性的划分，单遍数据扫描就可以确定每个对象的网格单元和每个网格单元的技术。此外，监管潜在的单元数量可能很高，但是只需要为非空单元创建网格单元。这样，定义网格、将每个对象指派到一个单元并计算每个单元的密度的时间和空间复杂度仅为你O(m)，其中m是点的个数。如果邻接的、已占据的单元可以有效地访问(例如，通过使用搜索树)，则整个聚类过程将非常搞笑，例如具有O(m
log m
)时间复杂度。正式由于这种原因，密度聚类的基于网格的方法形成了许多聚类算法的基础，如STING、GRIDCLUS、WaveCluster、Bang-Clustering、CLIQUE和MAFIA.
缺点：基于玩个的聚类非常依赖于密度阈值的选择。如果阈值太高，则簇可能丢失。如果阈值太低，则本应分开的两个簇可能被合并。此外，如果存在不同密度的簇和噪声，则也许不能找到适用于数据空间所有部分的单个阈值。
2、子空间聚类
1）CLIQUE(CLustering In
QUEst)是系统地发现子空间簇的基于网格的聚类算法。检查每个子空间寻找簇是不现实的，因为这样的子空间的数量是维度的指数。
CLIQUE依赖如下性质：基于密度的簇的单调性(如果一点点集在k维(属性))上形成一个基于密度的簇，则相同的点集在这些维的所有可能的子集上也是基于密度的簇的一部分。
CLIQUE算法
1：找出对应于每个属性的一维空间中的所有稠密区域。这是稠密的一维单元的集合。
2：k<——2
3:repeat
4: 由稠密的k-1维单元产生所有的候选稠密k维单元
5： 删除点数少于j的单元
6： k<——k+1
7:until 不存在候选稠密k维单元
8：通过取所有邻接的、高密度的单元的并发现簇。
9：使用一小组描述簇中单元的属性值域的不等式概括每一个簇。
优点：它提供给了一种搜索子空间发现簇的有效技术；用一小组不等式概括构成一个簇的单元列表的能力
缺点：CLIQUE发现的簇可以共享对象，允许簇重叠可能大幅度增加簇的个数。
3、DENCLUE :基于密度聚类的一种基于核的方案
DENCLUE(DENsity CLUstEring)
是一种基于密度的聚类算法，它用与每个点相关联的影响函数之和对点集的总密度建模。结果总密度函数将具有局部尖峰(即局部密度最大值)，并且这些局部尖峰用来以自然的方式定义簇。
DENCLUE算法
1：对数据点占据的空间推导密度函数
2：识别局部极大点
(这些是密度吸引点)
3：通过沿密度增长量最大的方向移动，将每个点关联到一个密度吸引点
4：定义与特定的密度吸引点相关联的点构成的簇
5：丢弃密度吸引点的密度小于用户指定阈值j的簇
6：合并通过密度大于或等于j的点半径连接的簇。
优点与局限性：DENCLUE具有坚实的理论基础，因为它基于统计学发展完善的领域——核密度函数和核密度估计，因为这种原因，DENCLUE提供了比其他基于网格的聚类技术和DBSCAN更加灵活、更加精确的计算密度的方法(DBSCAN是DENCLUE的特例)。基于核密度函数的放大本质上计算开销，但是DENCLUE使用基于网格的技术来处理该问题。DENCLUE可能比其他基于密度的聚类技术的计算开销更大。网格的使用对于密度估计的精度可能具有负面影响；并且这使得DENCLUE容易受基于网格的方法共同存在的问题的影响。
4、基于图的聚类
下面是一些重要方法，算法利用这些方法的不同子集
(1)稀疏话邻近度图，只保留对象与其最近邻之间的连接。这种稀疏化对于处理噪声和离群点是游泳的，稀疏话也使得我们可以利用为稀疏图开发的有效图划分算法
(2)基于共享的最近邻个数，定义两个对象之间的相似性度量，该方法基于这样一种观察，即对象和它的最近邻通常属于同一个类。该方法有助于克服高维和变密度簇的问题
(3)定义核心对象并都建环绕他们的簇。为了对基于图的聚类做这件事，需要引入邻近度图或稀疏化的邻近度图的基于密度概念。与DBSCAN一样，围绕核心对象构建簇将产生一种聚类技术，可以发现不同个形状和大小的簇
(4)使用邻近度图中的信息，提供两个簇是否应当合并的更复杂的评估。具体地说，两个簇合并，仅当结果簇具有类似于原来的两个簇的特性。
1、最小生成树(Minimum Spanning
Tree,MST)是一个子图，(1)它没有环，即是一棵树；(2)包含图的所有结点；(3)在所有可能的生成树中它的边的总权值最小。
MST分裂层次聚类算法
1：计算相异度图的最小生成树
2：repeat
3： 断开对应于最大相异度的边，创建一个新的簇
4：until 只剩下单个簇
2、OPOSSUM：使用METIS的稀疏相似度最优划分
OPOSSUM(Optimal Partitioning of Sparse Similarities Using
METIS)是一种专门为诸如文档或购物篮数据等稀疏、高维数据设计的聚类技术
OPOSSUM聚类算法
1：计算稀疏化的相似度图
2：使用METIS，将相似度图划分成k个不同的分支(簇)。
优点与缺点：OPOSSUM简单、速度快。它将数据划分大小粗略相等的簇。根据聚类的目标，这可能看作优点或缺点。由于簇被约束为大小粗略相等，因此簇可能被分裂或合并。然而，如果使用OPOSSUM产生大量簇，则这些簇通常是更大簇的相对纯的片段。事实上，OPOSSUM类似于Chameleon聚类过程的初始化步骤。
2、Chameleon：使用动态建模的层次聚类
凝聚层次聚类技术通过合并两个最相似的簇来聚类，其中簇的相似性定义依赖于具体的算法。
Chameleon算法
1：构造k-最近邻图
2：使用多层图划分算法划分图
3：repeat
4： 合并关于相对互连性和相对接近性而言，最好地保持簇的自相似性的簇
5：until 不再有可以合并的簇。
优点与局限性：Chameleon能够有效地聚类空间数据，即便存在噪声和离群点，并且簇具有不同的形状、大小和密度。Chameleon假定由稀疏化和图划分过程产生的对象组群是子簇，即一个划分中的大部分点属于同一个真正的簇。如果不是，则凝聚层次聚类将混合这些错误，因为它绝对不可能再将已经错误地放到一起的对象分开，这样，当划分过程未产生子簇时，Chameleon就有问题；对于高维数据，常常出现这种情况
计算共享最近邻相似度
1：找出所有点的k-最近邻
2：if 两个点x和y不是相互在对方的k-最近邻中 then
3： similarity(x,y) <—— 0
4: else
5: similarity(x,y) <—— 共享的近邻个数
6：end if
Jarvis-Patrick聚类算法
1：计算SNN相似度
2：使用相似度阈值，稀疏化SNN相似度图
3：找出稀疏化的SNN相似度图的连通分支(簇)
三、可伸缩的聚类算法
1、BIRCH(Balanced Iterative Reducing and Clustering using
Hierarchies)是一种非常有效地聚类技术，用于欧几里得向量空间数据，即平均值有意义的数据。BIRCH能够用一遍扫描有效地对这种数据进行聚类，并可以使用附加的扫描改进聚类，BIRCH还能够有效地处理离群点。
BIRCH基于聚类特征(Clustering
Feature,CF)和CF树的概念。其基本思想是，数据点(向量)的簇可以用三元组(N,LS,SS)表示，其中N是簇中点的个数，LS是点的线性和，而SS是点的平方和。这些是常见的统计量，可以增量地更新，并且可以用来计算许多重要的量，如簇的质心及其方差(标准差)。方差用来度量簇的直径。
BIRCH
1：通过创建汇总数据的CF树，将数据装入内存
2：如果第3阶段需要，构造一颗较小的CF树。T增值，然后重新插入叶结点项(簇)。由于T已增加，某些簇将合并。
3：进行全局聚类。可以使用不同形式的全局聚类(使用所有簇之间的逐对距离的聚类)。然而，我们选取一种凝聚的层次技术。因为聚类特征存放了对于特定聚类类型很重要的汇总信息，可以使用全局聚类算法，就像它用于CF代表的簇中的所有点上一样
4：使用步骤3发现的簇质心，重新分布数据点，从而发现新的簇集合。这克服了可能在BIRCH第一阶段出现的问题。由于页面大小的限制和参数T的缘故，应当在一个簇中的点有时可能被分裂，而应当在不同簇中的点有时可能被合并。此外，如果数据集包含重复点，则这些点根据出现次数的不同，有时可能被聚到不同的类。通过多次重复本阶段，过程将收敛到一个局部最优解。
2、CURE(Clustering Using
REpresentative)是一种聚类算法，它使用各种不同的技术创建一种方法，该方法能够处理大型数据、离群点和具有非球形和非均匀大小的簇的数据。CURE使用簇中的多个代表点来表示一个簇。理论上，这些点捕获了簇的几何形状。第一个代表选择离簇中心最远的点，而其余的点选择离所有已经选取的点最远的点。这样，代表点自然地相对分散。选取的点的个数时一个参数，但是业已发现10或更大的值效果很好。
CURE
1：由数据集抽取一个随机样本。值得注意的是，CURE的文章中有明确的公式，支出为了以较高的概率确保所有的簇都被最少的点代表，样本应当多大。
2：将样本划分成p个大小相等的划分
3：使用CURE的层次聚类算法，将每个划分中的点聚类为m/pq个簇，得到总共m/q个簇。注意，在此处理过程总将删除某些离群点。(m是点的个数，p是划分的个数，q是一个划分中的点的期望压缩)
4：使用CURE的层次聚类算法对上一步发现的m/q个簇进行聚类，知道只剩下k个簇
5：删除离群点。这是删除离群点的第二阶段
6：将所有剩余的数据点指派到最近的簇，得到完全聚类。
四、使用哪种聚类算法
1、聚类的类型：确定聚类的类型与预期的使用相匹配的一个重要因素是算法产生的聚类类型。对于一些应用，如创建生物学分类法，层次是首选的。对于旨在汇总的聚类，划分聚类是常用的。对于其他应用。两种都可能是有用的。
2、簇的类型：簇的类型是否与应用匹配。经常遇到的簇由三种类型：基于原型的、基于图的和基于密度的。基于原型的聚类方案以及某些基于图的聚类方案(全链、质心和Ward)易于产生全局簇，其中每个对象都与簇的原型或簇中其他对象足够靠近。基于密度的聚类技术和某些基于图的聚类技术(如单链)易于产生非全局的簇，因而包含许多像话之间不很相似的对象。如果使用聚类根据地表覆盖将地理区域划分成毗邻的区域，则这些技术比基于原型的方法(如K均值)更合适。
3、簇的特性
：如果我们想在原数据空间的子空间中发现簇，则必须选择项CLIQUE这样的算法，显式地寻找这样的簇。同样，如果我们队强化簇之间的空间联系感兴趣，则SOM或某些相关的方法更合适。此外，对于处理形状、大小和密度变化的簇，聚类算法的能力也有很大区别。
4、数据集合属性的特性：数据集合属性的类型可能决定所有算法的类型。例如：K均值算法只能用于遮掩给的数据：有合适的邻近性度量，使得簇质心的计算是有意义的。对于其他聚类技术，如许多凝聚层次聚类方法，只要可以创建邻近度矩阵，数据集合属性的基本性质就不那么重要。
5、噪声和离群点
6、数据对象的个数
7、属性的个数
8、簇描述：聚类技术常常被忽视的一个方面是如何描述结果簇。原型簇由簇原型的一个小集合简洁地描述。对于混合模型，簇被少量参数(如均值向量和协方差矩阵)的集合描述。这也是非常紧凑和容易理解的表示。
9、算法考虑：算法也有需要考虑的重要方面。算法是非确定性的还是次序依赖的？算法自动地确定簇的个数吗？是否存在某种技术确定各种参数的值？许多聚类算法试图通过最优化一个目标函数来解决聚类问题。该目标与应用目标匹配吗？如果不，及时算法做了很好的工作，发现关于目标函数最优或接近最优的聚类，结果仍然没有意义。此外，大部分目标函数以牺牲较小的簇为代价，偏向于较大的簇。
选择合适的聚类算法设计对所有这些问题，以及特定领域问题的考虑。不存在确定合适技术的公式。尽管如此，可用的关于聚类技术类型的一般知识和对上述问题的考虑，连同对实际应用的密切关注，应当可以帮助数据分析者做出使用哪种(或那些)聚类方法的决策。
