高维数据的聚类算法

      实验室周汇报&＃xff0c;刚好轮到讲子空间聚类&＃xff0c;上网查了一下&＃xff0c;发现文章特别少&＃xff0c;于是决定把我这几天查到的资料共享一下。中间部分是我自己的理解&＃xff0c;文章后面放了ppt的pdf版本。

下面就开始了.....

      聚类算法是人工智能、数据挖掘等领域的关键技术之一&＃xff0c;有着广泛的应用。随着大数据时代的到来&＃xff0c;产生了大量不一致数据、混合类型数据和部分值缺失的数据等。典型的聚类算法对这些数据集聚类时遇到难题。例如在高维稀疏数据中&＃xff0c;簇类只存在部分属性构成的子空间中&＃xff0c;这些数据集从全维空间来讲根本不存在簇类。一般来说&＃xff0c;样本之间的差异往往是由若干个关键的特征所引起的&＃xff0c;如果能恰当的找出这些重要特征&＃xff0c;对建立合理的聚类或分类模型都将起到积极的作用。因此提出了子空间聚类。

      子空间聚类算法是指把数据的原始特征空间分割为不同的特征子集&＃xff0c;从不同的子空间角度考察各个数据簇聚类划分的意义&＃xff0c;同时在聚类过程中为每个数据簇寻找到相应的特征子空间。总得来说&＃xff0c;子空间聚类的任务主要有两个&＃xff1a;1&＃xff09;发现可以聚类的子空间&＃xff08;属性子集&＃xff09;&＃xff1b;2&＃xff09;在相应的子空间上聚类。子空间聚类算法实际上是将传统的特征选择技术和聚类算法进行结合&＃xff0c;在对数据样本聚类划分的过程中&＃xff0c;得到各个数据簇对应的特征子集或者特征权重。根据目前的研究结果&＃xff0c;子空间聚类可以分为硬子空间聚类和软子空间聚类两种形式。两者之间的区别是什么呢&＃xff0c;下面进行解释。

       硬子空间聚类算法能识别不同类所在的精确子空间&＃xff0c;与硬子空间聚类不同的是&＃xff0c;软子空间聚类不需要为每一个类找到精确的子空间&＃xff0c;而是给每个类的特征赋予不同的权值&＃xff0c;利用这些权值来衡量每维特征在不同类中的贡献&＃xff0c;即软子空间聚类为每类找到一个软子空间。简单地说&＃xff0c;硬子空间聚类中&＃xff0c;一个属性必须且只能属于一个子空间&＃xff0c;聚类在这些子空间中进行&＃xff0c;属性在每个子空间中的权值要么是0&＃xff0c;要么是1。软子空间聚类是在全维空间对整个数据集聚类&＃xff0c;每个子空间包含所有属性&＃xff0c;但是每个属性被赋予[0,1]不同的权值&＃xff0c;属性权值描述了属性与对应子空间之间的关联程度&＃xff0c;权值越大说明该属性在这个子空间越重要&＃xff0c;与该子空间的关联性也就越强。

      更具体而言&＃xff0c;根据搜索方式的不同&＃xff0c;硬子空间聚类方法又可分为自底向上的子空间搜索算法和自顶向下的子空间搜索算法&＃xff1b;对于软子空间聚类方法而言&＃xff0c;根据特征加权系数不确定性表示方式的不同&＃xff0c;可以分为模糊加权软子空间聚类和熵加权软子空间聚类。

      首先来介绍一下硬子空间聚类中的自底向上子空间聚类算法。

     自底向上子空间聚类算法一般都是基于网格密度&＃xff0c;采用自底向上搜索策略进行的子空间聚类算法。它先将原始特征空间分为若干个网格&＃xff0c;再以落到某网格中样本点的概率表示该子空间的密度情况。对于密度超过一定阈值的子空间作为密集单元进行保留&＃xff0c;而对非密集子空间进行舍弃。经典的自底向上子空间聚类方法有最早的静态网格聚类算法CLIQUE。CLIQUE算法采用了基于网格和密度的方法。首先对每个属性进行等分&＃xff0c;整个数据空间就被分成一个超长方体集合&＃xff0c;对每个单元进行数据点计数&＃xff0c;大于某个阈值的单元称稠密单元&＃xff0c;然后对稠密单元进行连接构成类。算法按如下&＃xff1a;

优点&＃xff1a;
CLIQUE算法可自动发现最高维的子空间。CLIQUE对元组的输入顺序不敏感&＃xff0c;无需假设任何规范的数据分布。算法随输入数据的大小线性地扩展。当数据维数增加时具有良好的可伸缩性。
缺点&＃xff1a;

CLIQUE算法应用了一种剪枝技术来减少密集单元候选集的数目&＃xff0c;但可能遗失一些密集。如果一个密集存在于k维空间中&＃xff0c;那么它的所有子空间映射都是密集的。在自底向上的算法中&＃xff0c;为了发现一个k维的密集所有的子空间都应该被考虑&＃xff0c;但如果这些子空间在被剪掉的空间中&＃xff0c;那么这个密集就永远不可能发现了。由于算法中的很多步骤都大大简化&＃xff0c;以及很多步骤用的是近似算法&＃xff0c;所以聚类结果的精准性可能会降低。

      那么接下来就是硬子空间聚类的自顶向下子空间聚类算法。

      自顶向下子空间聚类算法主要是基于数据投影技术&＃xff0c;运用迭代搜索策略进行的子空间聚类方法。投影聚类就是将空间数据投影到某若干维上&＃xff0c;将高维数据转换为低维子空间&＃xff0c;在低维子空间上根据数据间的相似性进行聚类。具体而言&＃xff0c;首先将整个样本划分为C个数据簇&＃xff0c;对于每个数据簇赋予相同的权值&＃xff0c;并为每一类的各个特征赋予不同权重。然后利用迭代策略对这些初始化分不断进行改进和更新&＃xff0c;产生新的权重和聚类划分。由于在大规模数据集中&＃xff0c;多次迭代所需的计算复杂度相对高&＃xff0c;因此&＃xff0c;这类算法通常利用采样技术提高其算法的性能。PROCLUS是最早且最经典的自顶向下子空间聚类算法。PROCLUS算法首先选取整个样本集的小部分数据作为初始样本&＃xff0c;再从中选取C个聚类中心通过迭代策略对数据簇的质量进行改进。其执行过程分为三个阶段&＃xff1a;

a.初始化阶段&＃xff1a;对整个数据集进行随机抽样&＃xff0c;利用贪心策略得到一个潜在中心点集合的超集M&＃xff0c;并且保证每个数据簇至少包含一个样本点在这个超集中&＃xff1b;

b.迭代阶段&＃xff1a;从超集M中随机选择C个聚类中心&＃xff0c;将随机抽取到的新中心替换当前集合中不好的样本点&＃xff0c;直到获得更优的中心点集。然后按照上述过程反复迭代&＃xff0c;直到所得的聚类中心点的集合达到稳定。同时&＃xff0c;以各个子空间包含的样本点到其对应的聚类中心的平均距离作为该数据簇的半径&＃xff0c;找到各个数据簇对应的特征子集&＃xff1b;

c.改进阶段&＃xff1a;对每个数据簇的聚类中心再次进行扫描以确定其对应的特征子集&＃xff0c;并在该特征子集上计算样本点到聚类中心的曼哈顿距离&＃xff0c;进行新的划分&＃xff0c;同时去掉孤立点。

实验结果表明&＃xff0c;PROCLUS算法适合发现超球面形状的数据簇&＃xff0c;但PROCLUS算法在聚类过程中&＃xff0c;需要确定三个参数&＃xff1a;簇的数量、簇的平均维数、最小偏差&＃xff1b;所以PROCLUS算法对数据集的参数设置比较敏感&＃xff0c;但由于PROCLUS算法使用了采样技术&＃xff0c;在聚类速度方面要明显由于CLIQUE算法。

      好的&＃xff0c;硬子空间聚类算法就讲到这里。下面来介绍软子空间聚类算法。首先先引入一个基本算法模糊c均值聚类算法简称FCM&＃xff0c;这个算法是在K-means的基础上进行改进的。如果不太了解k-means的建议先去看一下k-means算法&＃xff0c;不难&＃xff0c;以后的讲解全都是基于已经掌握了k-means的基础上。

FCM其实就是在k-means的基础上加入了模糊这个概念。解释一下模糊这个概念&＃xff0c;指的是一个对象可以以不同程度同时属于多个类。举个例子&＃xff0c;比如说点A可以既属于簇类1也属于簇类2&＃xff0c;但是属于簇类1的概率为0.8&＃xff0c;属于簇类2的概率为0.2。这也是软硬子空间聚类的最本质区别。在硬子空间中&＃xff0c;点A仅也只能属于一个簇类。那么FCM算法的原理是通过优化目标函数得到每个样本点对所有类中心的隶属度&＃xff0c;从而决定样本点的类属以达到自动对样本数据进行分类的目的。C指的是聚类的数目。模糊的程度用模糊函数   表示。集合X中的元素x对簇A的隶属程度。

      FCM算法的输入&＃xff1a;一个待聚类的数据集X&＃xff0c;每个数据有p个特征。
                       输出&＃xff1a;1&＃xff09;一个c行n列的隶属阵U&＃xff1b;c是聚类数目&＃xff0c;n是数据集中元素的个数
                                     矩阵U可以表示分类的结果&＃xff0c;Uij表示第j个样本点隶属于第i类的概率

                                 2&＃xff09;聚类中心向量V&＃xff0c;c行p列

下面用例子解释一下。左边的图表示属于为188个数据点&＃xff0c;数据有2个属性&＃xff0c;需要聚成4个簇。右边的图解释了隶属阵U。横坐标表示这188个点&＃xff0c;纵坐标的范围是0-1。对于每一个数据点而言&＃xff0c;对于每一个簇的隶属度之和&＃61;1。

那么&＃xff0c;FCM算法的目标函数是&＃xff1a;

含义&＃xff1a;各个点到各个聚类中心的距离之和。Uij表示隶属度值&＃xff0c;元素j对类别i的隶属程度&＃xff1b;m是一个模糊化程度的参数&＃xff0c;也叫模糊加权指数&＃xff1b;dij表示在欧式距离下元素j与中心点i之间的距离&＃xff0c;dij&＃61;xj-vi。

聚类要达到的最终效果就是类内相似度最小&＃xff0c;类间相似度最大&＃xff0c;这个时候点和中心的加权距离之和达到最小。那么要成立。

对于有约束条件的求极值问题&＃xff0c;一般使用拉格朗日乘子法解决。
基本的拉格朗日乘子法就是求函数f(x1,x2,...)在约束条件g(x1,x2,...)&＃61;0下的极值的方法。

构造一个约束条件&＃xff1a;

拉格朗日函数&＃xff1a;

利用数学方法进行求导计算&＃xff0c;这里我就不放计算过程了&＃xff0c;不是很难。得到U和V的最优解&＃xff1a;

这里已经得到了U与V的最优解&＃xff0c;只需要不停地进行迭代就可以了。

下面说说FCM中m的取值

当m&＃61;1时&＃xff0c;目标函数就是类内加权均方误差和函数。m影响目标函数的凹凸性&＃xff0c;控制着聚类的模糊性即控制着样本在模糊类间的分享程度。因此m的取值必然会对模糊聚类的性能产生重要的影响。最佳取值范围在[1.5,2.5]之间。

FCM中c的取值

我们都知道聚类的目的就是将数据分类并尽量使类间的距离尽可能的大而类内的数据点距离尽可能的小。
 

总体样本的中心向量为&＃xff1a;

聚类数c的自适应函数&＃xff1a;

举个栗子&＃xff1a;

好的&＃xff0c;趁热打铁&＃xff0c;接下来我们就需要引进模糊加权聚类算法&＃xff08;FWSC&＃xff09;。

目标函数&＃xff1a;

代表特征模糊加权指数。

与FCM算法比较&＃xff0c;多了一个特征加权系数矩阵。对每一个簇类的每一个特征都加了一个系数&＃xff0c;扩大了某些重要特征对簇类的影响程度。经过计算可以得到&＃xff1a;

算法与FCM的过程一样&＃xff0c;只是多了一个模糊特征加权指数。

好的&＃xff0c;下面来介绍软子空间聚类算法中的熵加权子空间聚类算法&＃xff08;EWSC&＃xff09;。在介绍这个算法之前&＃xff0c;首先介绍一下信息熵这个概念。

         Ent(D)的值越小&＃xff0c;则D的纯度越高

对于软子空间的信息熵为&＃xff1a;

目标函数&＃xff1a;

是熵加权指数&＃xff0c;EWSC表示利用熵表示第k个数据特征对第i个数据簇的不确定程度。

通过计算可以得到&＃xff1a;

算法与FCM类似。

那么对于FWSC,EWSC算法&＃xff0c;模糊加权指数&＃xff0c;特征加权指数&＃xff0c;熵加权指数取多少合适呢&＃xff0c;这个由于过程太过复杂&＃xff0c;而且还涉及一些其他的聚类算法&＃xff0c;就不一一介绍&＃xff0c;但是给出了一个范围。

满足这两个条件时&＃xff0c;算法效果可以达到最佳。

最后来说一下这两个算法的优缺点。软子空间聚类技术基本思想是&＃xff0c;给数据集中的各类别赋予不同的特征权重向量&＃xff0c;用来表示聚类过程中各特征对此类别贡献的大小&＃xff0e;在聚类过程中&＃xff0c;每一维特征对各个类别都有不同的贡献&＃xff0c;因此每一类都有不同的特征权重向量&＃xff0c;从而在整个特征空间中形成了若干个“软子空间”&＃xff0c;聚类过程就是在各个“软子空间”中进行的。与其他子空间聚类算法相比&＃xff0c;熵加权软子空间聚类算法EWSC 对于文本和基因等高维数据均可以得到更好的聚类结果。但观察已有的软子空间聚类算法可以发现&＃xff0c;FWSC 和EWSC 只有在获得全部数据样本到当前聚类中心的模糊隶属度以后&＃xff0c;才迭代更新得到新的聚类中心和特征加权系数。