实验室周汇报，刚好轮到讲⼦空间聚类，上⽹查了⼀下，发现⽂章特别少，于是决定把我这⼏天查到的资料共享⼀下。中间部分是我⾃⼰的理解，⽂章后⾯放了ppt的pdf版本。 下⾯就开始了.....
聚类算法是⼈⼯智能、数据挖掘等领域的关键技术之⼀，有着⼴泛的应⽤。随着⼤数据时代的到来，产⽣了⼤量不⼀致数据、混合类型数据和部分值缺失的数据等。典型的聚类算法对这些数据集聚类时遇到难题。例如在⾼维稀疏数据中，簇类只存在部分属性构成的⼦空间中，这些数据集从全维空间来讲根本不存在簇类。⼀般来说，样本之间的差异往往是由若⼲个关键的特征所引起的，如果能恰当的出这些重要特征，对建⽴合理的聚类或分类模型都将起到积极的作⽤。因此提出了⼦空间聚类。
⼦空间聚类算法是指把数据的原始特征空间分割为不同的特征⼦集，从不同的⼦空间⾓度考察各个数据簇聚类划分的意义，同时在聚类过程中为每个数据簇寻到相应的特征⼦空间。总得来说，⼦空间聚类的任务主要有两个：1）发现可以聚类的⼦空间（属性⼦集）；2）在相应的⼦空间上聚类。⼦空间聚类算法实际上是将传统的特征选择技术和聚类算法进⾏结合，在对数据样本聚类划分的过程中，得到各个数据簇对应的特征⼦集或者特征权重。根据⽬前的研究结果，⼦空间聚类可以分为硬⼦空间聚类和软⼦空间聚类两种形式。两者之间的区别是什么呢，下⾯进⾏解释。
硬⼦空间聚类算法能识别不同类所在的精确⼦空间，与硬⼦空间聚类不同的是，软⼦空间聚类不需要为每⼀个类到精确的⼦空间，⽽是给每个类的特征赋予不同的权值，利⽤这些权值来衡量每维特征在不同类中的贡献，即软⼦空间聚类为每类到⼀个软⼦空间。简单地说，硬⼦空间聚类中，⼀个属性必须且只能属于⼀个⼦空间，聚类在这些⼦空间中进⾏，属性在每个⼦空间中的权值要么是0，要么是1。软⼦空间聚类是在全维空间对整个数据集聚类，每个⼦空间包含所有属性，但是每个属性被赋予[0,1]不同的权值，属性权值描述了属性与对应⼦空间之间的关联程度，权值越⼤说明该属性在这个⼦空间越重要，与该⼦空间的关联性也就越强。
更具体⽽⾔，根据搜索⽅式的不同，硬⼦空间聚类⽅法⼜可分为⾃底向上的⼦空间搜索算法和⾃顶向下的⼦空间搜索算法；对于软⼦空间聚类⽅法⽽⾔，根据特征加权系数不确定性表⽰⽅式的不同，可以分为模糊加权软⼦空间聚类和熵加权软⼦空间聚类。
⾸先来介绍⼀下硬⼦空间聚类中的⾃底向上⼦空间聚类算法。
⾃底向上⼦空间聚类算法⼀般都是基于⽹格密度，采⽤⾃底向上搜索策略进⾏的⼦空间聚类算法。它先将原始特征空间分为若⼲个⽹格，再以落到某⽹格中样本点的概率表⽰该⼦空间的密度情况。对于密度超过⼀定阈值的⼦空间作为密集单元进⾏保留，⽽对⾮密集⼦空间进⾏舍弃。经典的⾃底向上⼦空间聚类⽅法有最早的静态⽹格聚类算法CLIQUE。CLIQUE算法采⽤了基于⽹格和密度的⽅法。⾸先
对每个属性进⾏等分，整个数据空间就被分成⼀个超长⽅体集合，对每个单元进⾏数据点计数，⼤于某个阈值的单元称稠密单元，然后对稠密单元进⾏连接构成类。算法按如下：
优点：
CLIQUE算法可⾃动发现最⾼维的⼦空间。CLIQUE对元组的输⼊顺序不敏感，⽆需假设任何规范的数据分布。算法随输⼊数据的⼤⼩线性地扩展。当数据维数增加时具有良好的可伸缩性。
缺点：
CLIQUE算法应⽤了⼀种剪枝技术来减少密集单元候选集的数⽬，但可能遗失⼀些密集。如果⼀个密
集存在于k维空间中，那么它的所有⼦空间映射都是密集的。在⾃底向上的算法中，为了发现⼀个k维的密集所有的⼦空间都应该被考虑，但如果这些⼦空间在被剪掉的空间中，那么这个密集就永远不可能发现了。由于算法中的很多步骤都⼤⼤简化，以及很多步骤⽤的是近似算法，所以聚类结果的精准性可能会降低。
那么接下来就是硬⼦空间聚类的⾃顶向下⼦空间聚类算法。
⾃顶向下⼦空间聚类算法主要是基于数据投影技术，运⽤迭代搜索策略进⾏的⼦空间聚类⽅法。投影聚类就是将空间数据投影到某若⼲维上，将⾼维数据转换为低维⼦空间，在低维⼦空间上根据数据间的相似性进⾏聚类。具体⽽⾔，⾸先将整个样本划分为C个数据簇，对于每个数据簇赋予相同的权值，并为每⼀类的各个特征赋予不同权重。然后利⽤迭代策略对这些初始化分不断进⾏改进和更新，产⽣新的权重
和聚类划分。由于在⼤规模数据集中，多次迭代所需的计算复杂度相对⾼，因此，这类算法通常利⽤采样技术提⾼其算法的性能。PROCLUS是最早且最经典的⾃顶向下⼦空间聚类算法。PROCLUS算法⾸先选取整个样本集的⼩部分数据作为初始样本，再从中选取C个聚类中⼼通过迭代策略对数据簇的质量进⾏改进。其执⾏过程分为三个阶段：
a.初始化阶段：对整个数据集进⾏随机抽样，利⽤贪⼼策略得到⼀个潜在中⼼点集合的超集M，并且
保证每个数据簇⾄少包含⼀个样本点在这个超集中；
b.迭代阶段：从超集M中随机选择C个聚类中⼼，将随机抽取到的新中⼼替换当前集合中不好的样本点，直到获得更优的中⼼点集。然后按照上述过程反复迭代，直到所得的聚类中⼼点的集合达到稳定。同时，以各个⼦空间包含的样本点到其对应的聚类中⼼的平均距离作为该数据簇的半径，到各个数据簇对应的特征⼦集；
c.改进阶段：对每个数据簇的聚类中⼼再次进⾏扫描以确定其对应的特征⼦集，并在该特征⼦集上计算样本点到聚类中⼼的曼哈顿距离，进⾏新的划分，同时去掉孤⽴点。
实验结果表明，PROCLUS算法适合发现超球⾯形状的数据簇，但PROCLUS算法在聚类过程中，需要确定三个参数：簇的数量、簇的平均维数、最⼩偏差；所以PROCLUS算法对数据集的参数设置⽐较敏感，但由于PROCLUS算法使⽤了采样技术，在聚类速度⽅⾯要明显由于CLIQUE算法。
好的，硬⼦空间聚类算法就讲到这⾥。下⾯来介绍软⼦空间聚类算法。⾸先先引⼊⼀个基本算法模糊c均值聚类算法简称FCM，这个算法是在K-means的基础上进⾏改进的。如果不太了解k-means的建议先去看⼀下k-means算法，不难，以后的讲解全都是基于已经掌握了k-means的基础上。
FCM其实就是在k-means的基础上加⼊了模糊这个概念。解释⼀下模糊这个概念，指的是⼀个对象可
以以不同程度同时属于多个类。举个例⼦，⽐如说点A可以既属于簇类1也属于簇类2，但是属于簇类1的概率为0.8，属于簇类2的概率为0.2。这也是软硬⼦空间聚类的最本质区别。在硬⼦空间中，点A仅也只能属于⼀个簇类。那么FCM算法的原理是通过优化⽬标函数得到每个样本点对所有类中⼼的⾪属度，从⽽决定样本点的类属以达到⾃动对样本数据进⾏分类的⽬的。C指的是聚类的数⽬。模糊的程度⽤模糊函数 表⽰。集合X中的元素x对簇A的⾪属程度。
FCM算法的输⼊：⼀个待聚类的数据集X，每个数据有p个特征。
输出：1）⼀个c⾏n列的⾪属阵U；c是聚类数⽬，n是数据集中元素的个数
威尔逊主义矩阵U可以表⽰分类的结果，Uij表⽰第j个样本点⾪属于第i类的概率
2）聚类中⼼向量V，c⾏p列
下⾯⽤例⼦解释⼀下。左边的图表⽰属于为188个数据点，数据有2个属性，需要聚成4个簇。右边的图解释了⾪属阵U。横坐标表⽰这188个点，纵坐标的范围是0-1。对于每⼀个数据点⽽⾔，对于每⼀个簇的⾪属度之和=1。
那么，FCM算法的⽬标函数是：
ccl4含义：各个点到各个聚类中⼼的距离之和。Uij表⽰⾪属度值，元素j对类别i的⾪属程度；m是⼀个模糊
化程度的参数，也叫模糊加权指数；dij表⽰在欧式距离下元素j与中⼼点i之间的距离，dij=xj-vi。
聚类要达到的最终效果就是类内相似度最⼩，类间相似度最⼤，这个时候点和中⼼的加权距离之和达到最⼩。那么
要成⽴。
对于有约束条件的求极值问题，⼀般使⽤拉格朗⽇乘⼦法解决。
基本的拉格朗⽇乘⼦法就是求函数f(x1,x2,...)在约束条件g(x1,x2,...)=0下的极值的⽅法。
构造⼀个约束条件：威特金大学
拉格朗⽇函数：
利⽤数学⽅法进⾏求导计算，这⾥我就不放计算过程了，不是很难。得到U和V的最优解：
这⾥已经得到了U与V的最优解，只需要不停地进⾏迭代就可以了。
下⾯说说FCM中m的取值
当m=1时，⽬标函数就是类内加权均⽅误差和函数。m影响⽬标函数的凹凸性，控制着聚类的模糊性即控制着样本在模糊类间的分享程度。因此m的取值必然会对模糊聚类的性能产⽣重要的影响。最佳取值范围在[1.5,2.5]之间。
FCM中c的取值
我们都知道聚类的⽬的就是将数据分类并尽量使类间的距离尽可能的⼤⽽类内的数据点距离尽可能的⼩。
总体样本的中⼼向量为：
杨不管事件
聚类数c的⾃适应函数：
噻吩磺隆
举个栗⼦：
好的，趁热打铁，接下来我们就需要引进模糊加权聚类算法（FWSC）。
火焰检测
⽬标函数：
代表特征模糊加权指数。
与FCM算法⽐较，多了⼀个特征加权系数矩阵。对每⼀个簇类的每⼀个特征都加了⼀个系数，扩⼤了某些重要特征对簇类的影响程度。经过计算可以得到：
算法与FCM的过程⼀样，只是多了⼀个模糊特征加权指数。
好的，下⾯来介绍软⼦空间聚类算法中的熵加权⼦空间聚类算法（EWSC）。在介绍这个算法之前，⾸先介绍⼀下信息熵这个概念。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议