子空间聚类算法解析课件.ppt

1、研究背景和意义v在过去的几十年里，随着科学技术的进步，数据采集及存贮能力得到了快速发展，很多学科都出现了信息爆炸的现象，研究人员需要面对越来越庞大的观测数据。因此，数据挖掘技术受到大家的广泛关注。v数据挖掘（Data Mining，DM）一般是指从数据库的大量数据中，自动搜索隐藏于其中有着特定价值和规律的信息的过程。此外，数据挖掘也是一种决策支持过程，基于人工智能、机器学习、模式识别、统计学、可视化等技术，分析各种类型的数据，做出归纳性的推理，从中挖掘出潜在模式，帮助各个领域的专家及研究人员做出正确的决策和判断v数据挖掘的主要过程包括数据准备、信息挖掘、结果表达和解释三个处理阶段v数据准备是指

2、从相关的数据源中选取所需的数据样本，将其整合成用于数据分析的样本集；v信息挖掘是指利用各种数据挖掘算法将所得的样本集中包含的规律信息或潜在模式挖掘出来；v结果表达和解释是指尽可能以用户可理解的方式将找出的规律或模式表示出来新的问题和挑战v首先，数据的规模越来越大的，也就是所谓的大规模数据（Large-Scale Data）的问题v其次，数据的特征不断增加，导致数据维数的增加，出现了数据密度稀疏和“维数灾难”等现象，导致出现如下的问题1)很难定义准确的距离度量函数。2)算法的空间复杂度和时间复杂度急剧上升。随着数据维数的渐增，导致各种数据挖掘算法的性能出现明显下降，难以解决实际问题中的实时性问题

3、；3)数据簇之间或数据类之间的差异无法判断。由于高维空间中存在大量冗余的特征，使得在整个特征空间中，各个样本点之间的距离几乎是相等的。v最后，数据挖掘越来越强调多学科的交叉，不仅需要灵活运用统计学、计算机、数学等建模技术，还需要具有生物学、脑科学、证券金融等学科的知识背景v针对于这些问题，人们提出了大规模数据的数据流（Data Stream）分析方法；针对高维数据的特征加权（Feature Weighting）和特征选择（Feature Selection）方法；同时，生物信息学（Bioinformatics）等交叉学科也成为目前数据挖掘领域的研究重点子空间聚类算法v一般来说，样本之间的差异往

4、往是由若干个关键的特征所引起的，如果能恰当的找出这些重要特征，对建立合理的聚类或分类模型将起到积极的作用。这样不仅可以减少模型的建立时间，提高模型预测的准确率，还能有效地提高数据挖掘算法的鲁棒性和适应性。因此，我们希望可以针对数据的高维特征，对其各个特征的重要性进行加权，或者挑选出最重要的特征子集，减少或消除冗余特征以及不相关特征的影响，最大限度地保留和利用原始数据中的关键特征，在这个想法的基础上我们提出了子空间聚类。v子空间聚类算法是指把数据的原始特征空间分割为不同的特征子集，从不同的子空间角度考察各个数据簇聚类划分的意义，同时在聚类过程中为每个数据簇寻找到相应的特征子空间。子空间聚类算法v

5、子空间聚类算法实际上是将传统的特征选择技术和聚类算法进行结合，在对数据样本聚类划分的过程中，得到各个数据簇对应的特征子集或者特征权重。v根据目前的研究结果，子空间聚类可以分为硬子空间聚类和软子空间聚类两种形式。v更具体而言，根据搜索方式的不同，硬子空间聚类方法又可分为自底向上的子空间搜索算法和自顶向下的子空间搜索算法两种；对于软子空间聚类方法而言，根据特征加权不确定性表示方式的不同，可以分为模糊加权软子空间聚类和熵加权软子空间聚类两种自底向上子空间聚类算法v自底向上子空间聚类算法一般是基于网格密度，采用自底向上搜索策略进行的子空间聚类算法。它先将原始特征空间分成若干个网格，再以落到某网格中样本

6、点的概率表示该子空间的密度情况。对于密度超过一定阈值的子空间作为密集单元进行保留，而对非密集的子空间进行舍弃。v经典的自底向上子空间聚类方法有最早的静态网格聚类算法CLIQUE、利用熵理论作为密度度量的 ENCLUS 方法，以及后来提出的通过动态查找策略，得到更加稳定划分结果的子空间聚类算法：MAFIA和 DOC等CLIQUE算法v在高维（多属性）空间中进行聚类，一般的聚类算法要求有一个降维的预处理过程，典型的做法是：（1）由用户指定其中的若干重要属性，从而达到维度的降低；（2）通过属性约简，将一些不重要的属性去掉，经常采用的方法有主成分分析法和粗糙集方法；（3）将数据空间通过不同维度的线性组

7、合变换到一个低维空间中，使得不同点间的间隔在两个空间中近似相同。但是这些方法都存在一定的缺陷，对于前两种方法有丢失有趣的结构或模式的可能。对于第三种方法因为进行了属性的组合，打乱了与原空间的对应关系，使得产生的聚类结果很难解释。vCLIQUE算法采用了基于网格和密度的方法。首先对每个属性进行等分，整个数据空间就被分成一个超长方体集合，对每个单元进行数据点计数，大于某个阈值的单元称这稠密单元，然后对稠密单元进行连接就构成类。不同于其它方法，它可以自动地识别嵌入在数据子空间中的类。右图是识别子空间聚类的示意图在由年龄和工资两维构成的原始空间中没有密集区域，但是在其由工资一维构成的子空间中，存在两个

8、密集区域，形成两个类（1000工资3000和5000工资6000）而在由年龄一维构成的子空间中没有密集区域，不形成任何聚类。算法框架vCLIQUE 聚类算法包含下列步骤：l找出包含密集的子空间：对n维数据空间进行划分，划分为互不相交的矩形单元，同时识别其中的密集单元。l识别聚类：可运用深度优先算法来发现空间中的聚类。l为每个簇生成最小化的描述：对于每个簇来说，它确定覆盖相连的密集单元的最大区域，然后确定最小的覆盖区域。Clique算法的优缺点优点：优点：CLIQUE可自动发现最高维的子空间，高密度聚类存在与这些子空间中。CLIQUE对元组的输入顺序不敏感，无需假设任何规范的数据分布。它随输入数

9、据的大小线性地扩展。当数据维数增加时具有良好的可伸缩性。缺点：缺点：1、子空间剪枝：CLIQUE 算法应用了一种剪枝技术来减少密集单元候选集的数目，但可能遗失一些密集。如果一个密集存在于k维空间中，那么它的所有子空间映射都是密集的。在自底向上的算法中，为了发现一个k维的密集所有的子空间都应该被考虑，但如果这些子空间在被剪掉的空间中，那么这个密集就永远不可能发现了。2、由于算法中的很多步骤都大大简化，以及很多步骤用的是近似算法，所以聚类结果的精确性可能会降低。自顶向下子空间聚类算法v自顶向下子空间聚类算法主要是基于数据投影技术，运用迭代搜索策略进行的子空间聚类方法。具体而言，首先将整个样本集划分

10、为 C 个数据簇，对于每个数据簇赋予相同的权值，并为每一类的各个特征赋予不同权重。然后利用迭代策略对这些初始划分不断进行改进和更新，产生新的权重和聚类划分。由于在大规模数据集中，多次迭代所需的计算复杂度相当高，因此，这类算法通常利用采样技术提高其算法的性能。vPROCLUS 是最早且最经典的自顶向下子空间聚类算法。vPROCLUS 算法（PROjected CLUString）首先选取整个样本集的小部分数据作为初始样本，再从中选取 C 个聚类中心通过迭代策略对数据簇的质量进行改进。其执行过程分为三个阶段：v初始化阶段：对整个数据集进行随机抽样，利用贪心策略得到一个潜在中心点集合的超集 M，并且

11、保证每个数据簇至少包含一个样本点在这个超集中；v迭代阶段：从超集 M 中随机选择 C 个聚类中心，将随机抽取到的新中心替代当前集合中不好的样本点，直到获得更优的中心点集。然后按照上述过程反复迭代，直到所得的聚类中心点的集合达到稳定。同时，以各个子空间包含的样本点到其对应聚类中心的平均距离作为该数据簇的半径，找到各个数据簇对应的特征子集；v改进阶段：对每个数据簇的聚类中心再次进行扫描以确定其对应的特征子集，并在该特征子集上计算样本点到聚类中心的曼哈顿距离，进行新的划分，同时去除孤立点。v实验结果表明，PROCLUS 算法适合发现超球面形状的数据簇。但 PROCLUS 算法在聚类过程中，需要确定三

12、个参数：簇的数量、簇的平均维数、最小偏差；所以 PROCLUS算法对数据集的参数设置比较敏感。但由于 PROCLUS 算法使用了采样技术，在聚类速度方面要明显优于 CLIQUE 算法模糊加权软子空间聚类算法v上述两类硬子空间聚类方法都是利用自底向上或者自顶向下的策略，从全部特征集合中选取某些特征子集组成其相应的子空间；而软子空间聚类算法则是指在聚类过程中，对每个数据簇的各个特征赋予相应的特征加权系数，在聚类过程中得到各个特征在对应数据簇的重要性。与硬子空间聚类方法对比，软子空间聚类算法对数据集的处理具有更好的适应性与灵活性。因此，软子空间聚类算法也受到人们越来越多的关注v具体而言，对于给定的数

13、据集 ，人们希望利用软子空间聚类算法得到 C 个聚类中心 定义 表示第 j 个样本 属于第 i 个聚类中心 的模糊隶属度，则 U 表示整个数据集的模糊隶属度矩阵 。同时，为了更好地发现各个数据簇相应的子空间结构，软子空间聚类算法在聚类过程中对每个数据簇的全部特征都赋予一个特征加权系数。DNRxxxX,211,CivViijujxiv1,1|NjCiuUij模糊加权软子空间聚类算法v由此，定义 表示第 k 个特征对于 第 i 个 数 据 簇 的 重 要 性，则 W 表 示 整 个 数 据 集 的 特 征 加 权 系 数 矩 阵 。根据现有的研究结果，软子空间聚类算法按照其特征加权系数不确定性表示

14、方式的不同，可以分为模糊加权软子空间聚类方法，如 AWA、FWKM、FSC；以及熵加权软子空间聚类算法，如 EWKM、LAC、ESSC等v通过引入特征加权系数 和模糊加权指数 ，模糊加权软子空间聚类算法（Fuzzy Weighting Subspace Clustering，FWSC）的目标函数可以表示成：1,1|DkCiwWijijwijw熵加权软子空间聚类算法v同样，Jing 等人将信息熵引入软子空间聚类方法中，利用熵表示第 k 个数据特征对于第 i 个数据簇的不确定程度，提出了熵加权软子空间聚类算法（Entropy WeightingSubspace Clustering，EWSC）。定

15、义一般化的 EWSC 目标函数：特征选择算法研究v随着大规模数据和高维特征数据的涌现，原有的特征选择算法已难以满足实际的需求，对特征选择的研究呈现出综合性和多样化的趋势。一方面，特征选择技术开始向机器学习领域拓展，利用不同的学习算法对训练样本的特征进行挑选，选出合理的特征子集。另一方面，特征选择技术呈现出系统化、结构化的态势。Dash和 Liu 在对大量特征选择方法进行分析后给出了一个通用的特征选择技术的框架一个特征选择算法主要由生成策略、评价准则、停止条件和结论验证四个部分组成:1.生成策略是指从原始特征集合中生成某些特征子集；2.评价准则是指评价特征子集的相关性，判断生成的特征子集的合理性

16、；3.停止条件是指判断生成的特征子集是否符合起始定义的要求；4.结论验证是指验证所生成的特征子集的有效性特征选择算法类型v根据训练数据集的标记使用情况，特征选择算法可以分为有监督、无监督和半监督三种类型。有监督特征选择算法利用特征和各个数据类标的相关性，决定特征子集的重要性；无监督特征选择算法利用数据的方差或分离性对各个特征的重要性进行判断；半监督特征选择算法则利用少数已标记的数据样本作为附加信息，去提高未标记样本特征选择算法的性能。v根据特征选择算法评估方法的不同，特征选择可以大致分为以下三类：第一类是将特征选择和分类验证过程分离，特征选择的过程和具体的分类器无关，这类算法被称为过滤型方法（

17、Filter Approach）；第二类是封装型方法（WrapperApproach），将特征选择和分类器的设计结合在一起，利用预先指定的分类学习算法去评价各个特征或者特征子集的分类性能，从而进行合理的特征选择；第三类是嵌入式的方法（EmbeddedApproach），即将特征选择方法作为分类器训练的一个部分，通过分析所得学习模型的结果得到最终的特征选择子集。过滤型特征选择方法v过滤型方法的评价标准不依赖具体的分类器，而仅仅依赖于数据特征本身所附带的信息。一般而言，该方法假设每个特征都相互独立，通过某种搜索策略，选择合理的特征子集。过滤型方法也是最为简单的特征选择方法封装型特征选择方法v封装型

18、特征选择方法最早在 1994 年，由 John 等人提出，其特征性能的评价依赖于具体的分类器，所以该类方法的分类精度得到了大幅度的提高。封装型方法由于受到所选分类器的限制，算法效率很低，不适合针对大规模数据集或高维数据进行运算。此外，封装型方法还有一个明显的缺陷，就是对小样本数据集进行特征选择时，容易出现过拟合的情况。Automated Variable Weighting in k-Means Type Clustering(自动给变量加权的k-means聚类算法)v引言vk-Means 算法vW-k-Means 算法v实验v结论引言v在高维数据中有意义的聚类结构通常出现在子空间中v为了找到

19、这些聚类结构，识别变量的子集非常重要vK-means算法不能自动地选择变量，它在聚类过程中平等地对待所有变量v本文提出了一种新的k-means算法，即W-k-means，能够根据变量在聚类过程中的重要性自动地给变量加权K-means算法vK-means算法是很典型的基于距离的聚类算法，采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。该算法认为簇是由距离靠近的对象组成的，因此把得到紧凑且独立的簇作为最终目标vk个初始类聚类中心点的选取对聚类结果具有较大的影响，因为在该算法第一步中是随机的选取任意k个对象作为初始聚类的中心，初始地代表一个簇。该算法在每次迭代中对数据集中剩余

20、的每个对象，根据其与各个簇中心的距离将每个对象重新赋给最近的簇。当考察完所有数据对象后，一次迭代运算完成，新的聚类中心被计算出来。如果在一次迭代前后，J的值没有发生变化，说明算法已经收敛。v算法过程如下：1）从N个文档随机选取K个文档作为质心2）对剩余的每个文档测量其到每个质心的距离，并把它归到最近的质心的类3）重新计算已经得到的各个类的质心4）迭代23步直至新的质心与原质心相等或小于指定阈值，算法结束K-means算法v设 是具有n个对象的集合。对象 具有m个变量（属性）。vK-means算法通过最小化下列目标函数将X划分成k个簇。,111(,)(,)knmi li jl jlijP U Z

21、u d xz,11,1ki lluin U是一个 的划分矩阵，是一个二元变量，表示对象i被分配到簇l。n k,i lu,1i lu是一个具有k个向量的集合，表示k个簇的中心。12,kZZ ZZ,(,)i jl jd xz是对象i和簇l的中心在第j个变量上的距离。010001100100010O1O2O3O4O5C1 C2 C3如果变量是数值型的，则 。2,(,)()i jl ji jl jd xzxz如果变量是分类型的，则,0()(,)1()i jl ji jl ji jl jxzd xzxz12,nXXXX,1,2,(,)iiii mXxxxK-means算法v上面的优化问题可以通过迭代地求

22、解以下两个最小化问题解决：v ：假定 求解 ；v ：假定 求解 ；1PZZ(,)P U Z2PUU(,)P U Z,11,1(,)(,)10mmi li jl ji jt jjji tuifd xzd xzfortkufortl 求解 ：1P求解 ：2P对于数值型变量,1,11ni li jil jni liu xzforlkandjmu 对于分类型变量,rl jjza其中，是簇l中变量值的模。rjaK-means算法v假设X是用分类型属性 描述的对象的集合。v 的一个模是一个向量 。v设 是第k类中属性 的对象数，是 在X中相关的频度v函数 被最小化当且仅当12,mA AA12,nXXXX1

23、2,mAa aa得到通过最小化,(,)(,)(,)nnmii jjiijD X Ad XAxa,0()(,)1()i jji jji jjxaxyxa,kcjn(,)D X A,(|)(|),1,rjjrjk jjk jfAaXfAcXacjm,jk jAc,(|)kcjrjk jnfAcXn,k jcK-means算法vStep1 选择一个初始的 ，求解 得到 。设置t=0 vStep2 使 ，求解 得到 。如果 ，输出 ，算法结束；否则，转到Step3vStep3 使 ，求解 得到 。如果 ，输出 ，算法结束；否则，设置t=t+1，转到Step20Z0(,)P U Z0UtUU(,)P U

24、 Z1tZ1(,)(,)ttP U ZP U Z,tU Z1tZZ(,)P U Z1tU1(,)(,)ttP UZP UZ,tUZW-k-means算法v设 是m个变量的权值，是属性权值 的参数。修改目标函数为：12,mWw wwjw,111(,)(,)knmi lji jl jlijP U Z Wu w d xz,1,11,10,1,1,11,01ki lli lmjjjuinuinlkww 最小化上述目标函数通过迭代地求解下面三个最小化问题：假定 ，求解 ；1P,ZZ WW(,)P U Z W：假定 ，求解 ；：假定 ，求解 ；2P3P,UU WW(,)P U Z W,UU ZZ(,)P

25、U Z WW-k-means算法v求解 ：v求解 ：同上v求解 ：1P,11,1(,)(,)10mmi lji jl jji jt jjji tuifw d xzw d xzfortkufortl 2P3P当 或 时，被最小化当且仅当 10(,)P U Z W1110010jjjhjttifDifDwDD,11(,)kni lji jl jliDud xz其中 ，h是 的变量的数量。0jD 当 时，被最小化当且仅当1(,)P U Z W1,0,jjwwjj其中，对于所有的j，jjDDW-k-means算法vStep1 随机选择一个初始的 并随机生成一个初始权值集合 ()。通过最小化 确定 。设

26、置t=0；vStep2 使 ，求解 ，得到 。如果 ，输出 ，算法结束；否则，转到Step3；vStep3 使 ，求解 ，得到 。如果 ，输出 ，算法结束；否则，转到Step4；vStep4 使 ，求解 ，得到 。如果 ，输出 ，算法结束；否则，设置t=t+1，转到Step2；012,kZZ ZZ000012,mWw ww11mjjw000(,)P UZ W0U,ttUU WW(,)P U Z W1tZ1(,)(,)ttP U Z WP U ZW,tU Z W1,ttUUZZ(,)P U Z W1tW1(,)(,)ttP U Z WP U Z W,tU Z W11,ttZZWW(,)P U Z

27、 W1tU1(,)(,)ttP UZ WP UZ W,tUZ W在人工数据集上的实验确定初始的簇中心，随机生成权值人工数据集包含5个变量，300个记录。在前三个变量上被分成3个簇，每个簇中有100个点；后两个变量是噪声。设 是3个簇的集合，是用聚类算法生成的三个簇的集合。123,CC C C123,CC C C给定数据集上的一对点 ，称其为(,)ijXXSS：如果两个点在C中属于相同的簇，在 中属于相同的簇DD：如果两个点在C中属于不同的簇，在 中属于不同的簇SD：如果两个点在C中属于相同的簇，在 中属于不同的簇DS：如果两个点在C中属于不同的簇，在 中属于相同的簇CCCC设a,b,c,d是S

28、S,SD,DS,DD的数量，则a+b+c+d=M，是可能的点对的总数，N是点数。(1)2MN NadRandIndexRM1kiiaClusteringAccuracyrN其中，是 中包含的 中的点数，N是数据集中的点数。iaiCiCK-meansW-k-means在人工数据集上的实验在人工数据集上的实验确定权值，随机生成初始的簇中心(Clustering Accuracy,Rand Index)在实际数据集上的实验澳大利亚信用卡数据集由690个实例组成，每个实例包含6个数值型属性和9个分类型属性，其中663个可用。心脏病数据集由200个实例组成，每个实例包含5个数值型属性和8个分类型属性。随

29、机重排原数据记录，并为每个实际数据集创建100个测试数据集。信用卡数据集心脏病数据集结论v实验结果表明：v在恢复数据集中的簇时，w-k-means算法比k-means算法做的好。v权值可以有效地区分噪声变量和正常变量。v在聚类的过程中，选择变量的能力是很有用的。An Entropy Weighting k-Means Algorithm for Subspace Clustering of High-Dimensional Sparse Data一种在高维稀疏数据上进行子空间聚类的熵加权的k-means算法v引言vEntropy Weighting k-Meansv实验v结论引言v高维稀疏数据

30、的聚类需要使用子空间聚类方法v根据确定子空间的方式，子空间聚类分为硬子空间聚类和软子空间聚类v本文提出了一种在高维稀疏数据上进行软子空间聚类的新的k-means算法EWKMv提出EWKM算法的动机是为了在高维稀疏数据上进行聚类Entropy Weighting k-Meansv目标函数：21111(,)()logknmmljlilijilililjiiF W Zwzxr 111,1,1,0,11,1,1,01kljljlmliliiwjnlkwlkim 第1项是簇内分散度的和，第2项是负的加权熵。正参数r控制着激励在更多的维上进行聚类的强度。EWKM Algorithmv假设矩阵W和Z已确定，

31、F被最小化，如果 ，其中 （1）v假设Z和 已确定，W被更新 （2）v假设W和 已确定，Z被更新 （3）1expexpltltmliiDrDr21()nltljltjtjDwzx22111,()()10,mmljlilijiririjiiiljwifzxzxforrkwotherwise 1111nljjijlinljjw xzforlkandimw r0时，与 成反比。越小，越大，表示相应的维越重要。liliDliDliEWKM Algorithmv输入：簇数k和参数r，随机选择k个簇中心并设置所有的初始权值为v重复v 更新划分矩阵W通过（2）v 更新簇中心Z通过（3）v 更新维的权值 通过（1）v直到目标函数得到局部最小值1 m在人工数据集上的实验EWKM和PROCLUS在100个人工数据集上的聚类精度不同算法的聚类精度这些结果表明在对复杂的高维稀疏数据聚类时，EWKM是很好的。结论vEWKM在聚类过程中同时最小化簇内分散度和最大化负加权熵v由于激励更多的维在识别簇时起作用，避免了在很少的稀疏维上识别簇，解决了高维数据的稀疏性问题v实验结果表明，EWKM的聚类结果的精度非常高。vEWKM还可以扩展到大的高维数据集，由于输入参数r不敏感算法容易使用