当前位置:文档之家› 采用属性聚类的高维子空间聚类算法

采用属性聚类的高维子空间聚类算法

采用属性聚类的高维子空间聚类算法
采用属性聚类的高维子空间聚类算法

空间聚类的研究现状及其应用_戴晓燕

空间聚类的研究现状及其应用* 戴晓燕1 过仲阳1 李勤奋2 吴健平1 (1华东师范大学教育部地球信息科学实验室 上海 200062) (2上海市地质调查研究院 上海 200072) 摘 要 作为空间数据挖掘的一种重要手段,空间聚类目前已在许多领域得到了应用。文章在对已有空间聚类分析方法概括和总结的基础上,结合国家卫星气象中心高分辨率有限区域分析预报系统产品中的数值格点预报(HLAFS)值,运用K-均值法对影响青藏高原上中尺度对流系统(MCS)移动的散度场进行了研究,得到了一些有意义的结论。 关键词 空间聚类 K-均值法 散度 1 前言 随着GPS、GI S和遥感技术的应用和发展,大量的与空间有关的数据正在快速增长。然而,尽管数据库技术可以实现对空间数据的输入、编辑、统计分析以及查询处理,但是无法发现隐藏在这些大型数据库中有价值的模式和模型。而空间数据挖掘可以提取空间数据库中隐含的知识、空间关系或其他有意义的模式等[1]。这些模式的挖掘主要包括特征规则、差异规则、关联规则、分类规则及聚类规则等,特别是聚类规则,在空间数据的特征提取中起到了极其重要的作用。 空间聚类是指将数据对象集分组成为由类似的对象组成的簇,这样在同一簇中的对象之间具有较高的相似度,而不同簇中的对象差别较大,即相异度较大。作为一种非监督学习方法,空间聚类不依赖于预先定义的类和带类标号的训练实例。由于空间数据库中包含了大量与空间有关的数据,这些数据来自不同的应用领域。例如,土地利用、居住类型的空间分布、商业区位分布等。因此,根据数据库中的数据,运用空间聚类来提取不同领域的分布特征,是空间数据挖掘的一个重要部分。 空间聚类方法通常可以分为四大类:划分法、层次法、基于密度的方法和基于网格的方法。算法的选择取决于应用目的,例如商业区位分析要求距离总和最小,通常用K-均值法或K-中心点法;而对于栅格数据分析和图像识别,基于密度的算法更合适。此外,算法的速度、聚类质量以及数据的特征,包括数据的维数、噪声的数量等因素都影响到算法的选择[2]。 本文在对已有空间聚类分析方法概括和总结的基础上,结合国家卫星气象中心高分辨率有限区域分析预报系统产品中的数值格点预报(HLAFS)值,运用K-均值法对影响青藏高原上中尺度对流系统(MCS)移动的散度场进行了研究,得到了一些有意义的结论。 2 划分法 设在d维空间中,给定n个数据对象的集合D 和参数K,运用划分法进行聚类时,首先将数据对象分成K个簇,使得每个对象对于簇中心或簇分布的偏离总和最小[2]。聚类过程中,通常用相似度函数来计算某个点的偏离。常用的划分方法有K-均值(K-means)法和K-中心(K-medoids)法,但它们仅适合中、小型数据库的情形。为了获取大型数据库中数据的聚类体,人们对上述方法进行了改进,提出了K-原型法(K-prototypes method)、期望最大法EM(Expectation Maximization)、基于随机搜索的方法(ClAR ANS)等。 K-均值法[3]根据簇中数据对象的平均值来计算 ——————————————— *基金项目:国家自然科学基金资助。(资助号: 40371080) 收稿日期:2003-7-11 第一作者简介:戴晓燕,女,1979年生,华东师范大学 地理系硕士研究生,主要从事空间数 据挖掘的研究。 · 41 · 2003年第4期 上海地质 Shanghai Geology

子空间聚类Sparse Subspace Clustering SSC

【子空间聚类】Sparse Subspace Clustering(SSC) Algorithm Symbol definition: is n linear subspace of . is the dimentsion of . is N noise-free data points. is a rank- matrix, represent (>) points that lie in . is a unknown permutation matrix. SSC Algorithm: Step 1: Solve the sparse optimization program ①Uncorrupted data ②Corrupted data ps: E corresponds to a matrix of sparse outlying entries, and Z is a noise matrix. Step 2: Normalize the columns of C as . ps: max norm : .

Step 3: Form a similarity grahp with N nodes wegiths on the edges between the nodes by . ps: Step: Use spectral clustering to the similarity graph. Output: . Subspace-Sparse Recovery Theory Definition: ① ps: is said to be independent. ② ③Principle angle between and

【子空间聚类】Sparse Subspace Clustering(SSC) Algorithm=

Sparse subspace clustering:Algorithm,theory,and Application 稀疏子空间聚类(SSC)的算法,理论和应用 参考文献: 1、E. Elhamifar and R. Vidal. Sparse subspace clustering: Algorithm,theory,and Application. IEEE Transactions on Pattern Analysis and Machine Intelligence,2013 2、E. Elhamifar and R. Vidal. Sparse subspace clustering. In CVPR, 2009 2013年的这篇论文写得比09年那篇容易懂一些,讨论和实验也更详细。2013年的这篇可以看成是09那篇会议的扩展版。 一、算法 数据没有损坏,求解模型(5)获得矩阵C:

数据有损坏(noise and sparse outlying entries),求解模型(13)获得矩阵C: 仿射子空间模型: 二、理论 1、independent子空间 设rank(Yi)=di,Yi表示从第i个子空间Si抽取的Ni个样本构成的矩阵,di 表示Si的维数。论文的定理1表明,模型(5)的解C*是一个块对角矩阵,属于同一个子空间的数据间的cij可能非零,不属于同一个子空间的数据间的cij=0.

2、disjoint子空间 对于disjoint子空间,除了满足条件rank(Yi)=di外,还需要满足公式(21): 则可获得与independent子空间下类似的结论:

稀疏子空间聚类算法

稀疏子空间聚类算法与模型建立 稀疏子空间聚类是一种基于谱聚类的子空间聚类方法, 基本思想:假设高位空间中的数据本质上属于低维子空间,能够在低维子空间中进行线性表示,能够揭示数据所在的本质子空间, 有利于数据聚类. 基 本方法是, 对给定的一组数据建立子空间表示模型,寻找数据在低维子空间中的表示系数, 然后根据表示系数矩阵构造相似度矩阵, 最后利用谱聚类方法如规范化割(Normalized cut, Ncut)[22] 获得数据的聚类结果。 基本原理 稀疏子空间聚类[32] 的基本思想是: 将数据 αS x i ∈表示为所有其他数据的线性组合, j i j ij i x Z x ∑≠= (1) 并对表示系数施加一定的约束使得在一定条件下对所有的αS x j ?, 对应的0=ij Z 。将所有数据及其表示系数按一定方式排成矩阵 ,则式(1)等价于 XZ X = (2) 且系数矩阵N N R Z ?∈ 满足: 当i x 和j x 属于不同的子空间时, 有0=ij Z . 不同于用一组基或字典表示数据, 式(2)用数据集本身表示数据, 称为数据的自表示. 若已知数据的子空间结构, 并将数据按类别逐列排放, 则在一定条件下可使系数矩阵Z 具有块对角结构, 即 ????? ???????=k Z Z Z Z 00000021 (3) 这里),,1(k Z =αα 表示子空间αS 中数据的表示系数矩阵; 反之, 若Z 具有块对角结构, 这种结构揭示了数据的子空间结构. 稀疏子空间聚类就是通过对系数矩阵Z 采用不同的稀疏约束, 使其尽可能具有理想结构, 从而实现子空间聚类. Elhamifar 等[32] 基于一维稀疏性提出了稀疏子空间聚类(Sparse subspace clustering,SSC) 方法, 其子空间表示模型为 1min Z Z 0,..==ii Z XZ X t s (4)

基于分布式低秩表示的子空间聚类算法

计算机研究与发展DOI:10.7544桙issn1000‐1239.2016.20148362JournalofComputerResearchandDevelopment53(7):16051611,2016 收稿日期:2014-12-09;修回日期:2015-06-09  基金项目:国家自然科学基金项目(61373055);江苏省自然科学基金项目(BK20140419);江苏省高校自然科学研究计划重大项目 (14KJB520001) ThisworkwassupportedbytheNationalNaturalScienceFoundationofChina(61373055),theNaturalScienceFoundationofJiangsuProvinceofChina(BK20140419),andtheMajorProgramofResearchPlanoftheNaturalScienceinHigherEducationofJiangsuProvinceofChina(14KJB520001). 通信作者:吴小俊(wu_xiaojun@jiangnan.edu.cn)基于分布式低秩表示的子空间聚类算法 许 凯 吴小俊 尹贺峰 (江南大学物联网工程学院 江苏无锡 214122) (xukai347@sina.com) DistributedLowRankRepresentation‐BasedSubspaceClusteringAlgorithmXuKai,WuXiaojun,andYinHefeng(SchoolofInternetofThingsEngineering,JiangnanUniversity,Wuxi,Jiangsu214122) Abstract Visionproblemrangingfromimageclusteringtomotionsegmentationcannaturallybeframedassubspacesegmentationproblem,inwhichoneaimstorecovermultiplelowdimensionalsubspacesfromnoisyandcorruptedinputdata.Lowrankrepresentation‐basedsubspacesegmentationalgorithm(LRR)formulatestheproblemasaconvexoptimizationandachievesimpressiveresults.However,itneedstotakealongtimetosolvetheconvexproblem,andtheclusteringaccuracyisnothighenough.Therefore,thispaperproposesadistributedlowrankrepresentation‐basedsparsesubspaceclusteringalgorithm(DLRRS).DLRRSadoptsthedistributedparallelcomputingtogetthecoefficientmatrix,thentaketheabsolutevalueofeachelementofthecoefficientmatrix,andretaintheklargestcoefficientspercolumnandsettheotherelementsto0togetanewcoefficientmatrix.Finally,DLRRSperformsspectralclusteringoverthenewcoefficientmatrix.Butitdoesn摧thaveincrementallearningfunction,sothereisascalabledistributedlowrankrepresentation‐basedsparsesubspaceclusteringalgorithm(SDLRRS)here.Ifnewsamplesarebroughtin,SDLRRScanusetheformerclusteringresulttoclassifythenewsamplestogetthefinalresult.ExperimentalresultsonARandExtendedYaleBdatasetsshowthattheimprovedalgorithmscannotonlyobviouslyreducetherunningtime,butalsoachievehigheraccuracy,whichverifiesthattheproposedalgorithmsareefficientandfeasible.Keywords lowrankrepresentation;subspaceclustering;parallelcomputing;incrementallearning;coefficientsreconstruction 摘 要 针对基于低秩表示的子空间分割算法运算时间较长、 聚类的准确率也不够高,提出一种基于分布式低秩表示的稀疏子空间聚类算法(distributedlowrankrepresentation‐basedsparsesubspaceclusteringalgorithm,DLRRS),该算法采用分布式并行计算来得到低秩表示的系数矩阵,然后保留系数矩阵每列的前k个绝对值最大系数,其他系数置为0,用此系数矩阵构造一个稀疏的样本关系更突出的相似度矩阵,接着用谱聚类得到聚类结果.但是其不具备增量学习功能,为此再提出一种基于分布式低秩表示的增量式稀疏子空间聚类算法(scalabledistributedlowrankrepresentationbasedsparsesubspaceclusteringalgorithm,SDLRRS),如果有新增样本,可以利用前面的聚类结果对新增样本进行

聚类分析中几种算法的比较

聚类分析中几种算法的比较 2009-04-13 23:12 将数据库中的对象进行聚类是聚类分析的基本操作,其准则是使属于同一类的个体间距离尽可能小,而不同类个体间距离尽可能大,为了找到效率高、通用性强的聚类方法人们从不同角度提出了近百种聚类方法,典型的有K-means 方法、K-medoids方法、CLARANS方法,BIRCH方法等,这些算法适用于特定的问题及用户。本文综合提出了评价聚类算法好坏的5个标准,基于这5个标准,对数据挖掘中常用聚类方法作了比较分析,以便于人们更容易、更快捷地找到一种适用于特定问题及用户的聚类算法。 聚类算法研究及比较框架 聚类算法一般有五种方法,最主要的是划分方法和层次方法两种。划分聚类算法通过优化评价函数把数据集分割为K个部分,它需要K作为输人参数。典型的分割聚类算法有K-means算法, K-medoids算法、CLARANS算法。层次聚类由不同层次的分割聚类组成,层次之间的分割具有嵌套的关系。它不需要输入参数,这是它优于分割聚类算法的一个明显的优点,其缺点是终止条件必须具体指定。典型的分层聚类算法有BIRCH算法、DBSCAN算法和CURE算法等。 对各聚类算法的比较研究基于以下5个标准: ①是否适用于大数据量,算法的效率是否满足大数据量高复杂性的要求; ②是否能应付不同的数据类型,能否处理符号属性; ③是否能发现不同类型的聚类; ④是否能应付脏数据或异常数据; ⑤是否对数据的输入顺序不敏感。 下面将在该框架下对各聚类算法作分析比较。 数据挖掘常用聚类算法比较分析 3.1 K-pototypes算法 K-pototypes算法结合了K-means方法和根据K-means方法改进的能够处理符号属性的K-modes方法,同K-means 方法相比,K-pototypes 算法能够处理符号属性。 3.2 CLARANS算法(划分方法) CLARANS算法即随机搜索聚类算法,是一种分割聚类方法。它首先随机选择一个点作为当前点,然后随机检查它周围不超过参数Maxneighbor个的一些邻接点,假如找到一个比它更好的邻接点,则把它移人该邻接点,否则把该点作为局部最小量。然后再随机选择一个点来寻找另一个局部最小量,直至所找到的局部最小量数目达到用户要求为止。该算法要求聚类的对象必须都预先调人内存,并且需多次扫描数据集,这对大数据量而言,无论时间复杂度还是空间复杂度都相当大。虽通过引人R-树结构对其性能进行改善,使之能够处理基于磁盘的大型数据库,但R*-树的构造和维护代价太大。该算法对脏数据和异常数据不敏感,但对数据物人顺序异常敏感,且只能处理凸形或球形边界聚类。 3.3 BIRCH算法(层次方法) BIRCH算法即平衡迭代削减聚类法,其核心是用一个聚类特征3元组表示一个簇的有关信息,从而使一簇点的表示可用对应的聚类特征,而不必用具体的一组点来表示。它通过构造满足分支因子和簇直径限制的聚类特征树来求聚类。BIRCH算法通过聚类特征可以方便地进行中心、半径、直径及类内、类间距离的运算。算法的聚类特征树是一个具有两个参数分枝因子B和类直径T的高度平衡树。分枝因子规定了树的每个节点子女的最多个数,而类直径体现了对一类点的直径大小的限制即这些点在多大范围内可以聚为一类,非叶子结点为它的子女的最大关键字,可以根据这些关键字进行插人索引,它总结了其子女的信息。 聚类特征树可以动态构造,因此不要求所有数据读人内存,而可以在外存上逐个读人。新的数据项总是插人到树中与该数据距离最近的叶子中。如果插人后使得该叶子的直径大于类直径T,则把该叶子节点分裂。其它叶子结点也需要检查是否超过分枝因子来判断其分裂与否,直至该数据插入到叶子中,并且满足不超过类直径,而每个非叶子节点的子女个数不大于分枝因子。算法还可以通过改变类直径修改特征树大小,控制其占内存容量。 BIRCH算法通过一次扫描就可以进行较好的聚类,由此可见,该算法适合于大数据量。对于给定的M兆内存空间,其空间复杂度为O(M),时间间复杂度为O(dNBlnB(M/P)).其中d为维数,N为节点数,P为内存页的大小,B为由P决定的分枝因子。I/O花费与数据量成线性关系。BIRCH算法只适用于类的分布呈凸形及球形的情况,并且由于BIRCH算法需提供正确的聚类个数和簇直径限制,对不可视的高维数据不可行。 3.4 CURE算法(层次方法) CURE算法即使用代表点的聚类方法。该算法先把每个数据点看成一类,然后合并距离最近的类直至类个数为所要求的个数为止。CURE算法将传统对类的表示方法进行了改进,回避了用所有点或用中心和半径来表示一个类,而

相关主题
相关文档 最新文档