子空间聚类算法解析课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,研究背景和意义,在过去的几十年里，随着科学技术的进步，数据采集及存贮能力得到了快速发展，很多学科都出现了信息爆炸的现象，研究人员需要面对越来越庞大的观测数据。因此，数据挖掘技术受到大家的广泛关注。,数据挖掘（Data Mining，DM）一般是指从数据库的大量数据中，自动搜索隐藏于其中有着特定价值和规律的信息的过程。此外，数据挖掘也是一种决策支持过程，基于人工智能、机器学习、模式识别、统计学、可视化等技术，分析各种类型的数据，做出归纳性的推理，从中挖掘出潜在模式，帮助各个领域的专家及研究人员做出正确的决策和判断,数据挖掘的主要过程包括数据准备、信息挖掘、结果表达和解释三个处理阶段,数据准备是指从相关的数据源中选取所需的数据样本，将其整合成用于数据分析的样本集；,信息挖掘是指利用各种数据挖掘算法将所得的样本集中包含的规律信息或潜在模式挖掘出来；,结果表达和解释是指尽可能以用户可理解的方式将找出的规律或模式表示出来,新的问题和挑战,首先，数据的规模越来越大的，也就是所谓的大规模数据（Large-Scale Data）的问题,其次，数据的特征不断增加，导致数据维数的增加，出现了数据密度稀疏和“维数灾难”等现象，导致出现如下的问题,1)很难定义准确的距离度量函数。,2)算法的空间复杂度和时间复杂度急剧上升。随着数据维数的渐增，导致各种数据挖掘算法的性能出现明显下降，难以解决实际问题中的实时性问题；,3)数据簇之间或数据类之间的差异无法判断。由于高维空间中存在大量冗余的特征，使得在整个特征空间中，各个样本点之间的距离几乎是相等的。,最后，数据挖掘越来越强调多学科的交叉，不仅需要灵活运用统计学、计算机、数学等建模技术，还需要具有生物学、脑科学、证券金融等学科的知识背景,针对于这些问题，人们提出了大规模数据的数据流（Data Stream）分析方法；针对高维数据的特征加权（Feature Weighting）和特征选择（Feature Selection）方法；同时，生物信息学（Bioinformatics）等交叉学科也成为目前数据挖掘领域的研究重点,子空间聚类算法,一般来说，样本之间的差异往往是由若干个关键的特征所引起的，如果能恰当的找出这些重要特征，对建立合理的聚类或分类模型将起到积极的作用。这样不仅可以减少模型的建立时间，提高模型预测的准确率，还能有效地提高数据挖掘算法的鲁棒性和适应性。因此，我们希望可以针对数据的高维特征，对其各个特征的重要性进行加权，或者挑选出最重要的特征子集，减少或消除冗余特征以及不相关特征的影响，最大限度地保留和利用原始数据中的关键特征，在这个想法的基础上我们提出了子空间聚类。,子空间聚类算法是指把数据的原始特征空间分割为不同的,特征子集,，从不同的子空间角度考察各个数据簇聚类划分的意义，同时在聚类过程中为每个数据簇寻找到相应的特征子空间。,子空间聚类算法,子空间聚类算法实际上是将传统的特征选择技术和聚类算法进行结合，在对数据样本聚类划分的过程中，得到各个数据簇对应的特征子集或者特征权重。,根据目前的研究结果，子空间聚类可以分为硬子空间聚类和软子空间聚类两种形式。,更具体而言，根据搜索方式的不同，硬子空间聚类方法又可分为自底向上的子空间搜索算法和自顶向下的子空间搜索算法两种；对于软子空间聚类方法而言，根据特征加权不确定性表示方式的不同，可以分为模糊加权软子空间聚类和熵加权软子空间聚类两种,自底向上子空间聚类算法,自底向上子空间聚类算法一般是基于网格密度，采用自底向上搜索策略进行的子空间聚类算法。它先将原始特征空间分成若干个网格，再以落到某网格中样本点的概率表示该子空间的密度情况。对于密度超过一定阈值的子空间作为密集单元进行保留，而对非密集的子空间进行舍弃。,经典的自底向上子空间聚类方法有最早的静态网格聚类算法,CLIQUE,、利用熵理论作为密度度量的,ENCLUS,方法，以及后来提出的通过动态查找策略，得到更加稳定划分结果的子空间聚类算法：,MAFIA,和,DOC,等,CLIQUE算法,在高维（多属性）空间中进行聚类，一般的聚类算法要求有一个降维的预处理过程，典型的做法是：（1）由用户指定其中的若干重要属性，从而达到维度的降低；（2）通过属性约简，将一些不重要的属性去掉，经常采用的方法有主成分分析法和粗糙集方法；（3）将数据空间通过不同维度的线性组合变换到一个低维空间中，使得不同点间的间隔在两个空间中近似相同。但是这些方法都存在一定的缺陷，对于前两种方法有丢失有趣的结构或模式的可能。对于第三种方法因为进行了属性的组合，打乱了与原空间的对应关系，使得产生的聚类结果很难解释。,CLIQUE算法采用了基于网格和密度的方法。首先对每个属性进行等分，整个数据空间就被分成一个超长方体集合，对每个单元进行数据点计数，大于某个阈值的单元称这稠密单元，然后对稠密单元进行连接就构成类。不同于其它方法，它可以自动地识别嵌入在数据子空间中的类。,右图是识别子空间聚类的示意图在由年龄和工资两维构成的原始空间中没有密集区域，但是在其由工资一维构成的子空间中，存在两个密集区域，形成两个类（,1000,工资,3000,和,5000,工资,6000,）而在由年龄一维构成的子空间中没有密集区域，不形成任何聚类。,算法框架,CLIQUE,聚类算法包含下列步骤：,找出包含密集的子空间：,对,n,维数据空间进行划分，划分为互不相交的矩形单元，同时识别其中的密集单元。,识别聚类：,可运用深度优先算法来发现空间中的聚类。,为每个簇生成最小化的描述：,对于每个簇来说，它确定覆盖相连的密集单元的最大区域，然后确定最小的覆盖区域。,Clique,算法的优缺点,优点：,CLIQUE,可自动发现最高维的子空间，高密度聚类存在与这些子空间中。,CLIQUE,对元组的输入顺序不敏感，无需假设任何规范的数据分布。它随输入数据的大小线性地扩展。当数据维数增加时具有良好的可伸缩性。,缺点：,1,、子空间剪枝：,CLIQUE,算法应用了一种剪枝技术来减少密集单元候选集的数目，但可能遗失一些密集。如果一个密集存在于,k,维空间中，那么它的所有子空间映射都是密集的。在自底向上的算法中，为了发现一个,k,维的密集所有的子空间都应该被考虑，但如果这些子空间在被剪掉的空间中，那么这个密集就永远不可能发现了。,2,、由于算法中的很多步骤都大大简化，以及很多步骤用的是近似算法，所以聚类结果的精确性可能会降低。,自顶向下子空间聚类算法,自顶向下子空间聚类算法主要是基于数据投影技术，运用迭代搜索策略进行的子空间聚类方法。具体而言，,首先将整个样本集划分为 C 个数据簇,，对于每个数据簇赋予相同的权值，并为每一类的各个特征赋予不同权重。然后利用迭代策略对这些,初始划分不断进行改进和更新,，产生新的权重和聚类划分。由于在大规模数据集中，多次迭代所需的计算复杂度相当高，因此，这类算法通常利用采样技术提高其算法的性能。,PROCLUS 是最早且最经典的自顶向下子空间聚类算法。,PROCLUS,算法（,PROjected CLUString,）首先选取整个样本集的小部分数据作为初始样本，再从中选取,C,个聚类中心通过迭代策略对数据簇的质量进行改进。其执行过程分为三个阶段：,初始化阶段：对整个数据集进行随机抽样，利用贪心策略得到一个潜在中心点集合的超集,M,，并且保证每个数据簇至少包含一个样本点在这个超集中；,迭代阶段：从超集,M,中随机选择,C,个聚类中心，将随机抽取到的新中心替代当前集合中不好的样本点，直到获得更优的中心点集。然后按照上述过程反复迭代，直到所得的聚类中心点的集合达到稳定。同时，以各个子空间包含的样本点到其对应聚类中心的平均距离作为该数据簇的半径，找到各个数据簇对应的特征子集；,改进阶段：对每个数据簇的聚类中心再次进行扫描以确定其对应的特征子集，并在该特征子集上计算样本点到聚类中心的曼哈顿距离，进行新的划分，同时去除孤立点。,实验结果表明，,PROCLUS,算法适合发现超球面形状的数据簇。但,PROCLUS,算法在聚类过程中，需要确定三个参数：簇的数量、簇的平均维数、最小偏差；所以,PROCLUS,算法对数据集的参数设置比较敏感。但由于,PROCLUS,算法使用了采样技术，在聚类速度方面要明显优于,CLIQUE,算法,模糊加权软子空间聚类算法,上述两类硬子空间聚类方法都是利用自底向上或者自顶向下的策略，从全部特征集合中选取某些特征子集组成其相应的子空间；而软子空间聚类算法则是指在聚类过程中，对每个数据簇的各个特征赋予相应的特征加权系数，在聚类过程中得到各个特征在对应数据簇的重要性。与硬子空间聚类方法对比，软子空间聚类算法对数据集的处理具有更好的适应性与灵活性。因此，软子空间聚类算法也受到人们越来越多的关注,具体而言，对于给定的数据集 ，人们希望利用软子空间聚类算法得到 C 个聚类中心 定义 表示第 j 个样本 属于第 i 个聚类中心 的模糊隶属度，则 U 表示整个数据集的模糊隶属度矩阵 。同时，为了更好地发现各个数据簇相应的子空间结构，软子空间聚类算法在聚类过程中对每个数据簇的全部特征都赋予一个特征加权系数。,模糊加权软子空间聚类算法,由此，定义 表示第 k 个特征对于 第 i 个 数 据 簇 的 重 要 性，则 W 表 示 整 个 数 据 集 的 特 征 加 权 系 数 矩 阵 。根据现有的研究结果，软子空间聚类算法按照其特征加权系数不确定性表示方式的不同，可以分为模糊加权软子空间聚类方法，如 AWA、FWKM、FSC；以及熵加权软子空间聚类算法，如 EWKM、LAC、ESSC等,通过引入特征加权系数 和模糊加权指数 ，模糊加权软子空间聚类算法（Fuzzy Weighting Subspace Clustering，FWSC）的目标函数可以表示成：,熵加权软子空间聚类算法,同样，,Jing,等人将信息熵引入软子空间聚类方法中，利用熵表示第,k,个数据特征对于第,i,个数据簇的不确定程度，提出了熵加权软子空间聚类算法（,Entropy WeightingSubspace Clustering,，,EWSC,）。定义一般化的,EWSC,目标函数：,特征选择算法研究,随着大规模数据和高维特征数据的涌现，原有的特征选择算法已难以满足实际的需求，对特征选择的研究呈现出综合性和多样化的趋势。一方面，特征选择技术开始向机器学习领域拓展，利用不同的学习算法对训练样本的特征进行挑选，选出合理的特征子集。另一方面，特征选择技术呈现出系统化、结构化的态势。Dash和 Liu 在对大量特征选择方法进行分析后给出了一个通用的特征选择技术的框架,一个特征选择算法主要由生成策略、评价准则、停止条件和结论验证四个部分组成:,1.生成策略是指从原始特征集合中生成某些特征子集；,2.评价准则是指评价特征子集的相关性，判断生成的特征子集的合理性；,3.停止条件是指判断生成的特征子集是否符合起始定义的要求；,4.结论验证是指验证所生成的特征子集的有效性,特征选择算法类型,根据训练数据集的,标记,使用情况，特征选择算法可以分为有监督、无监督和半监督三种类型。,有监督特征选择算法利用特征和各个数据类标的相关性，决定特征子集的重要性；,无监督特征选择算法利用数据的方差或分离性对各个特征的重要性进行判断；,半监督特征选择算法则利用少数已标记的数据样本作为附加信息，去提高未标记样本特征选择算法的性能。,根据特征选择算法,评估方法,的不同，特征选择可以大致分为以下三类：,第一类是将特征选择和分类验证过程分离，特征选择的过程和具体的分类器无关，这类算法被称为过滤型方法（Filter Approach）；,第二类是封装型方法（WrapperApproach），将特征选择和分类器的设计结合在一起，利用预先指定的分类学习算法去评价各个特征或者特征子集的分类性能，从而进行合理的特征选择；,第三类是嵌入式的方法（EmbeddedApproach）