（计算机应用技术专业论文）基于空间约束的半监督子空间聚类算法.pdf

大连理工大学硕士学位论文 摘要 聚类分析作为数据挖掘中的重要技术，具有广泛的应用领域。根据应用领域的不同， 聚类算法被分为了四大类，其中包括划分方法、层次方法、基于网格的方法、基于密度 的方法等。目前，如何处理大规模的高维数据集是聚类分析领域的热点和难点之一。由 于高维数据具有稀疏性，传统的聚类算法在处理这类数据时往往不能获得理想的效果。 子空间聚类算法正是针对高维数据集提出的一种新的聚类算法。它是传统聚类在高 维数据空间中的一种扩展，其主要思想是将搜索局部化，在相关维中进行簇的搜索。代 表性算法包括c l i q u e 、p r o c l u s 、o r c l u s 等。然而，随着真实数据集的维数发生 变化，子空间的维选择也越来越困难，这也导致了上述的子空间聚类算法在分析真实高 维数据集时效果往往不令人满意。 为了更好的解决高维数据集引发的问题，本文引入半监督学习的方法，通过利用以 往被其他子空间算法忽略的先验知识信息，提出了一种新的半监督子空间算法，该算法 关注于表现形式为成对约束的先验知识，一方面利用成对约束在全维数据下的不一致性 来确定子空间的搜索方向，来进行维的选择，大大降低了子空间维选择时的难度，同时 也提高了子空间维选择的准确率；另一方面利用成对约束形成簇的中心点，很大程度上 提高了聚类结果的准确度。另外，由于本算法利用了成对约束信息进行维选择，这在保 持了子空间聚类算法优点的同时，也避免了其他算法主观地给定参数所具有的缺陷。 本文将该算法同其他算法在人工数据集和真实数据集上进行了实验比较，由实验结 果可以看出该算法比其他算法具有更高的准确度，对高维数据集的效果更为明显，说明 该算法在处理高维数据集时的有效性和可行性。 关键词：半监督学 - - j ，聚类，子空间聚类，不一致性约束，高维数据 基于空间约束的半监督子空间聚类算法 s e m i - - s u p e r v i s e ds u b s p a c ec l u s t e r i n gb a s e d o ns p a c e - l e v e lc o n s t r a i n t a b s t r a c t c l u s t e ra n a l y s i s 硒t l la 嘶d er a n g eo fa p p l i c a t i o n si sv e r yi m p o r t a n tf o rd a t am i n i n g a c c o r d i n gt ot h el a r g en u m b e ro fd i f f e r e n ta p p l i c a t i o n s ，c l u s t e r i n ga l g o r i t h m sa r ed i v i d e di n t o f o u rb r o a d c a t e g o r i e s ：p a r t i t i o nm e t h o d ，h i e r a r c h i c a lm e t h o d s ，g r i d - b a s e dm e t h o d s ， d e n s i t y b a s e dm e t h o d s a tp r e s e n t ，h o wt od e a lw i t hl a r g e s c a l eh i g h d i m e n s i o n a ld a t as e ti s o n eo ft h eh o ta n dd i f f i c u l ti s s u e si nd a t am i n i n g d u et ot h eh i g h - d i m e n s i o n a ld a t aa r es p a r s e ， t h et r a d i t i o n a lc l u s t e r i n ga l g o r i t h mi so f t e nu n a b l et oo b t a i nt h ed e s i r e dr e s u l t si nd e a l i n g 、析t l l s u c hd a t a s u b s p a c ec l u s t e r i n ga l g o r i t h mi s an e wc l u s t e r i n gt e c h n i q u e ，w h i c hi s p r o p o s e df o r l l i g h - d i m e n s i o n a ld a t as e t s i ti sa l le x t e n s i o no f t h et r a d i t i o n a lc l u s t e r i n gi nh i g hd i m e n s i o n a l d a t a s e t i t sm a i ni d e ai st ol o c a l i z et h es e a r c hi nt h er e l e v a n td i m e n s i o nt oc l u s t e rs e a r c h r e p r e s e n t a t i v ea l g o r i t h m si n c l u d ec l i q u e ，p r o c l u sa n d o r c l u se t c h o w e v e r , ab e t t e r s o l u t i o no fd i m e n s i o ns e l e c t i o ni ss t i l ln o ta v a i l a b l ew h i c hc a no b t a i ns a t i s f y i n gr e s u l t s i no r d e rt od e a lw i t hs u c hp r o b l e mc a u s e db yh i g hd i m e n s i o n a ld a t a s e t , w eu s e s e m i s u p e r v i s e dl e a r n i n gm e t h o dt os o l v ep r o b l e m w ep r o p o s e dan e ws e m i s u p e r v i s e d s u b s p a c ec l u s t e r i n gb yu s i n gd o m a i nk n o w l e d g e ，w h i c hi si g n o r e db yt r a d i t i o n a ls u b s p a c e c l u s t e r i n g o u ra l g o r i t h mf o c u s e s o nt h ef o r mo fc o n s t r a i n t s i no n eh a n d ，o u ra l g o r i t h mu s e s i n c o n s i s t e n tc o n s t r a i n t st of r e dt h es u b s p a c es e a r c hd i r e c t i o n , s oi tc a l lr e d u c et h et i m eo f s e l e c t i n gt h er e l a t e dd i m e n s i o n sa n di m p r o v et h ea c c u r a c yo fs e l e c t i n g i no t h e rh a n d ，o u r a l g o r i t h mu s et h ec o n s t r a i n tp o i n t st of o r mt h ec l u s t e rc e n t r o i d s i tc a ni m p r o v et h ee f f i c i e n c y o fc l u s t e r i n g i na d d i t i o n ，a so u ra l g o r i t h mu s e st h ec o n s t r a i n tt os e l e c td i m e n s i o n s ，i tc a nn o t o n l ym a i n t a i nt h ea d v a n t a g e so fs u b s p a c ec l u s t e r i n ga l g o r i t h m s ，b u ta l s oa v o i dt ot h ew e a k p o i i l to fg i v e np a r a m e t e r s w et e s to u ra l g o r i t h mo nb o t hs y n t h e t i ca n dr e a ld a t a s e t s 1 1 1 ee x p e r i m e n t a lr e s u l t ss h o w t h a to u ra l g o r i t h mc a np e r f o r mw e l lo nh i g hd i m e n s i o n a ld a t a s e ta n di sm o r ee f f i c i e n tt h a n f i n d i t p r o c l u sa n do r c l u s k e yw o r d s ：s e m i - s u p e r v i s e dl e a r n i n g ，c t u s t e r i n g ，s u b s p a c ec t u s t e r i n g ， i n c o n s i s t e n tc o n s t r a i n t s ，h i g hd i m e n s i o n a ld a t a s e t 一i i 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：望i 丝囟垣差鱼! 整塑主叁国耋差簋竖 作者签名：塑叁 一 一日期： 星竺3 年l 月盟日 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目： 蕴垒望绉垒鱼垒垒丝堑塑! 受墨主鬈丝 作者签名： ，亟塑，一日期：翌竺刍年j 上月1 _ 日 导师签名：音啦魄丑年旦月卫日 大连理工大学硕士学位论文 1 绪论 1 1 研究背景及意义 随着二十一世纪社会生产力的发展和进步，人类步入了全新的信息化社会。计算机 技术的迅猛发展大幅度提高了人们产生和收集数据的能力，然而随着数据规模越来越 大，数据之间的关系也越来越复杂，因此这样的情形被人们描述为“数据丰富，但信息 贫乏”。面对快速增长的海量数据被收集和储存，如果没有强有力的工具，理解和分析 它们已经远远超出了人的一般能力。这就导致了人们对高效的数据分析工具的强烈需 求。因此，面对人们被数据淹没却苦于寻找于有用信息的挑战，数据挖掘技术应运而生， 并得以蓬勃发展，越来越显示出其远大的前景1 2 。 数据挖掘是一个从数据集中挖掘潜在的、有用的信息的过程【2 7 】。在很多领域都得到 了广泛的运用，诸如，基因序列表达、保险和股票管理等。 其主要过程可以分为以下几步： 数据清理：消除不一致数据或噪声：数据集成：组合多种数据源；数据选择：检索 数据库中与分析任务相关的数据；数据变换：将数据统一或变换成适合挖掘的形式；数 据挖掘：基本步骤，使用智能算法发现数据模式；模式评估：根据某种兴趣度识别度量 表示知识的有用模式；知识表示：使用可视化和知识表示技术向用户提供挖掘的知识。 数据挖掘的功能和任务有：概念描述，包括特征化和区分、关联分析、分类和预测、 聚类分析、孤立点分析、演变分析等。其中，聚类分析作为数据挖掘的一个重要方向， 已经被广泛研究与探讨。聚类就是将数据对象分组成为多个类或簇，在同一个簇中的对 象之间具有较高的相似度，而不同簇中的对象具有较大相异度。相异度是根据描述对象 的属性值来计算的。可见，聚类分析能作为一个独立的工具来获得数据分布的情况，观 察每个类的特点。因此，聚类分析可以应用于许多领域，例如在商务中，聚类可以帮助 市场分析人员从客户基本库中发现小同的客户群体，并用购买模式来刻画不同客户群的 特征；在生物学上，聚类能用于推导植物和动物的分类，对基因进行分类，获得对种群 固有结构的认识；聚类也能用于对w e b 上的文档进行分类以发现有用的信息。 目前，聚类分析的研究集中在聚类方法的可伸缩性、对复杂形状和类型的数据进行 聚类的有效性、高维聚类分析技术以及混合数据的聚类方法研究，其中，高维数据聚类 是聚类分析的难题，主要体现在两个方面：( 1 ) 由于高维数据中存在大量无关的属性， 这使得在所有维中存在簇的可能性几乎为零；( 2 ) 由于在高维空间中的数据比低维空 基于空间约束的半监督子空间聚类算法 间中的数据分布要更稀疏，所以数据间距离几乎相等是普遍现象，然而，传统的聚类方 法却是基于距离进行度量的，因此无法在高维空间中再使用距离来构建簇【2 引。 相关研究发现，在高维数据中聚类总是存在于由一部分属性构成的属性子集里，这 些属性子集或称维子集就是子空间。由于高维数据中，聚类可能分布在相同的子空间中， 也可能分布在不同的子空间中，子空间聚类【2 9 j 的主要任务就是挖掘存在于子空间中的聚 类和聚类所在的属性集。子空间聚类可以看成是传统聚类的一个扩展，但不同于传统的 聚类算法，子空间聚类算法一般具有的两个目标：寻找隐藏在子空间中的簇和其所在的 子空间。然而，子空间聚类中仍然存在很多的挑战，其中一个很重要的问题是如何选择 正确的维。原因在于数据点之间的距离会随着选择的维而改变。可见，在没有先验知识 支持的情况下，正确地选择维是一件很困难的事情。 如今，如何有效地利用先验知识是数据挖掘领域中的一个重要问题【i 】。在许多实际 的数据挖掘应用上，无标记的训练样本是很容易获得的，相反，获得标记样本的成本却 是很昂贵的，因此，半监督学习逐渐成为了热点话题。当前，半监督学习可以分为：半 监督分类，半监督回归，半监督聚类三种。其中，半监督聚类的主要思想是利用先验知 识去提高和改进无监督聚类结果【1 4 1 。半监督聚类是一种新近发展起来的学习机制。半监 督聚类算法研究无监督学习中如何利用少量的监督信息来提高聚类性能。少量的监督信 息可以是数据的类别标记或一对数据是否属于同一类的连接约束关系。 1 2 相关研究现状 聚类分析作为- i - 交叉学科，包含了统计学、机器学习和数据挖掘等领域的知识， 吸引了众多研究人员投身其中，使之成为数据挖掘领域的一个非常活跃的研究课题。到 目前为止国内外的研究者们提出了许多无监督聚类算法，主要可以分为如下几类聚类算 法 3 0 】： 层次方法：对给定数据对象集合进行层次分解。根据层次分解的方式不同，又可分 为两种层次聚类，一种是自底向上的凝聚的聚类，另一种是自顶向下的分裂的聚类。 划分方法：对给定数据集合，构建数据的k 个划分，每一个划分代表一个类；使 用迭代的重定位技术，通过数据对象在各个类之间的移动来改进划分。 密度方法：如果数据集中数据对象的临近区域密度( 对象或数据点的数目) 超过某 个阈值就将这个区域看成是一个簇。 网格方法：把对象空间量化为有限数目个单元，形成一个网格状的结构，所有的聚 类操作都在这个量化的空间上进行。 大连理工大学硕士学位论文 模型方法：为每个类假定一个模型，寻找数据对给定模型的最佳拟合【3 1 1 。 近年来，聚类分析技术向处理高维度的海量数据的方向发展，子空间聚类很好地解 决了高维数据聚类问题。根据搜索策略的不同，子空间聚类算法可以分为两种： 一种是自底向上的算法。该类算法使用a p r i o r i 方法，利用密度块的向下闭合属 性以减少搜索空间。密度块的向下闭合属性是指如果在k 维下存在密度块，那么在任意 的k - 1 维下同样也存在密度块。像c l i q u e 6 j 和m a f i a 7 】等，都属于这一类算法。 另一种算法是自顶向下的算法。该类算法通常在开始时给每维设置相同的权重，并 在全维下找到一个初始聚类结果的近似值。而后，根据每一个簇的情况，对维进行权重 的重分配。利用这些更新后的权重，可以再次产生新的聚类结果。这是一个需要多次迭 代的过程。为了降低迭代产生的时间消耗，许多这方面的算法都使用了抽样技术以提高 效用。p r o c l u s l l1 1 ，o r c l u s 1 2 1 ，f i n d i t 1 3 】等算法都属于这一类。 不同于无监督的聚类，半监督聚类是利用先验知识去提高和改进无监督聚类结果， 并且研究时间并不长，提出的半监督聚类算法也不多。这些已提出的算法主要是从两个 方面来利用先验知识： 一方面是改变搜索聚类结果的策略，这种算法改变原有的聚类算法，在搜索过程中 加入先验知识，像发现约束的传递闭包，利用闭包来初始化聚类算法【l 】；又像在代价函 数中加入关于先验知识的限制项1 3 1 ；或者像要求聚类的形成过程应该满足先验知识的规 剧4 】。 另一方面是调整原有算法的相似度，这种算法改变原有算法的相似度公式，使得新 的相似度公式能够满足先验知识的限制。像用梯度下降来训练j e n s e n - s h a r m o n 差异【3 刨； 又像用最短路径算法来修改欧氏距离【5 1 ；或者像用凸优化来调整马氏距离【8 】。两者的区 别在于前者假设数据点之间的相似度能够很好的反映关于数据点的分类信息【l5 1 ，后者却 假设相似度是需要改变的以便能够反映关于数据点的分类信息闭。 1 3 本文研究内容及组织 聚类分析是数据挖掘领域中一个相对比较困难的问题。其中，大规模、高维数据下 的聚类分析尤其如此。针对这一问题，子空间聚类算法得到了广泛的研究，然而，子空 间聚类中仍然存在很多的挑战，其中一个很重要的问题是如何选择正确的维。原因在于 数据点之间的距离会随着选择的维而改变。换句话说，在没有先验知识支持的情况下， 正确地选择维是一件困难的事情。因此，如何利用先验知识去发现子空间是非常具有重 要的理论价值，考虑到聚类技术拥有的广泛应用领域，这个研究也具有显著的现实意义。 本文正是利用了先验知识，提出了半监督子空间算法，通过实验与传统子空间聚类算法 基于空间约束的半监督子空间聚类算法 进行了比较，证明了该算法的有效性，能够通过利用先验知识更加有效地解决现有聚类 算法对处理高维分类属性数据集过程中存在的一些缺陷。 本文结构如下：第一章为绪论，主要介绍本文课题的研究背景以及研究现状；第二 章简要介绍了高维数据中聚类的问题，介绍了子空间聚类的基本原理和方法：第三章介 绍了半监督聚类算法的基本原理和方法；第四章介绍了利用不一致性约束发现子空间的 半监督子空间算法的原理和方法；第五章给出了传统子空间算法和本文算法的实验结果 和对比分析；最后将总结本课题工作并做出展望。 大连理工大学硕士学位论文 2 高维聚类问题 2 1 高维数据聚类 2 。1 1 高维数据的挑战 在面向数据挖掘的聚类研究中，所要处理的数据经常会有几十甚至上百个属性。如 果把这些数据对象看成高维属性空间中的点，那么数据对象则能表示成一个向量，这样 就可以把现实中的对象集合用高维空间中点的集合来表示。典型的高维数据包括零售交 易数据，空间数据，地理数据，多媒体数据，时间序列数据，基因数据等。与低维数据 相比，这些数据在许多方面表现出不同的特性，如稀疏性，空空间现象【3 i 】以及高维数据 处理过程中的“维度效应”现象p z l 。 ( 1 ) 高维数据的稀疏性 假设一个d 维数据集d 存在于一个超级立方体单元q = 0 ，1 】d 中，数据在空间中均 匀分布，并且各个维之间独立。对一个边长为s 的超级立方体范围，一个点在这个范围 内的概率为s d ，由于s 2 0 时，它们的性能就会降到顺序搜索的水平。 随着时间的推移，“维度效应”这一术语用来泛指在数据分析中遇到的由于变量( 属 性) 过多而引起的所有问题。在高维数据聚类中这些问题主要表现在两个方面i lo 】：一方 面距离函数难于定义。聚类操作的基础是数据对象之间相似性的度量，将相似度高的对 象归为一类。低维空间中经常使用欧氏距离等距离函数来度量相似性，但在高维情况下 相似性没有传递性，因此距离函数失效。必须重新考虑新的度量数据对象相似性的标准 或准则。另一方面基于距离的聚类方法经常需要计算簇的均值或近邻，但在高维情况下， 按距离计算的簇均值会很接近，聚类操作由于无法明确区分簇的中心而无法进行。在高 维空间中一个点到它的最近邻和最远邻在很多情况下几乎是等距离的，最近邻的概念常 常会失去意义。 2 1 2 高维数据对传统聚类的影响 多数传统聚类算法都是针对低维空间进行处理的。由于高维数据具有上述的特点， 稀疏性、空空间现象以及维度效应，这就导致数据在全维空间和稀疏，而传统的聚类算 法都是针对全维空间进行的，并且多数算法都运用了全维空间中距离的概念。因此在高 维数据空间中使用这些算法主要遇到以下问题： ( 1 ) 随着维数增长，聚类的时间和空间复杂度迅速上升从而导致算法的性能下降 p 引。相比低维数据，高维数据空间很难确定一个聚类的中心。在基于网格的聚类方法中， 一6 一 大连理工大学硕士学位论文 聚类往往被一些( d 1 ) 维的分隔平面所分割。不妨简单假设在每一维上只分割一次， 这样就有d 个( d 1 ) 超平面将整个数据空间分成2 d 个单元格，原有的数据之间的相邻 属性将消失。下面提供一种最坏情况。设所有数据在 0 ，1 d 中，每一维在0 5 的地方被 分割。数据分布在以( o 5 ，0 5 ，o 5 ) 为球心，半径为e ( o 1 ) 的超球体中。当 d 2 0 时，某个聚类中的绝大多数数据点将被分割到各个单元格中。因此为了发现这个 聚类，我们可能要搜索2 d 个相邻单元格，计算量将非常巨大； ( 2 ) 高维数据集中存在大量无关的属性，并且在这些不相关的维上十分稀疏【3 3 1 。 这就使得在所有维中存在簇的可能性几乎为零；所以传统的聚类算法不适合对高维数据 进行聚类。聚类的核心概念是相似度，而许多传统的聚类算法，如k - m e a n s ，b i r c h 等 都用到了距离来表示两个对象间的相似度。在高维数据空间的情况下，距离测度将是毫 无意义的由于数据量不可能随着维数的增加而指数级增加，因此在高维空间中，存在着 大量的稀疏部分。其结果是，最远的两个数据点之间的距离和最近的两个数据点间的距 离差别将很小，或者几乎没有； ( 3 ) 距离函数难于定义，聚类操作的基础是数据对象之间相似性的度量，相似度 高的对象归为一类。但在高维情况下距离函数失效，因此必须通过重新定义合适的距离 函数或相似性度量函数以避开“维度效应 的影响。 上述的研究结果揭示了高维数据聚类分析所面临的潜在问题。不过，实际应用的问 题并非总是如此严重，有时可以通过属性约简和子空间聚类来克服维度效应。 2 1 。3 特征约简技术 针对高维数据产生的问题，前人提出了降维方法来解决这一问题。降维一般分为两 种，一种是特征选择，另一种是特征变换 3 4 1 。特征选择就是从原始高维空间中选取若干 属性维组成新的坐标系，但保留的维没有旋转。不同地是，特征变换是指构造降维映射 将原数据集的维合并至k 个新维，保持基本特征不变使得维数减少从而使算法能在这k 个新维中进行有效聚类。 ( 1 ) 特征选择 特征选择【3 5 】就是从原始高维空间中选取若干属性维组成新的坐标系，但保留的维没 有旋转。例如，有时可以得到一些关于数据的先验知识，与问题相关的变量只是其中一 小部分。这时可以在聚类分析之前进行一个“特征选择 步骤，来消去与所需特征无关 的或与其他特征高度相关的属性维，以达到维度约简的目的。不过，在高维数据聚类过 程中，特征选择过程一般不依赖于聚类算法，它基于一个准则函数，以某种搜索策略对 属性或属性集进行评价，从而得到好的子集。常用的搜索策略包括随机搜索，前向搜索， 基于空间约束的半监督子空间聚类算法 后向搜索，组合方法以及加权方法等。近年来提出了一些新的特征选择方法，如顺序特 征选择算法、遗传算法、基于分形的特征选择算法等。与其它方法相比，基于分形的特 征选择算法可以估计需要保留的维数，它还可以发现维之间的非线性甚至非多项式相 关。 ( 2 ) 特征变换 特征变换【3 7 j 是指构造降维映射将原数据集的维合并至k 个新维，保持基本特征不变 使得维数减少从而使算法能在这k 个新维中进行有效聚类这种维度约简方法通常是利 用一些统计学或线性代数方法来实现的。其思想是：使数据得到相当程度的近似，即使只 保留其中很少的一些相关维，也基本上不丢失真实的信息。而且，这种技术在某些方面 还可以扩展数据分析性能，可以有效地去除数据中的噪音。 传统的特征变换技术包括线性方法和非线性方法。线性特征变换方法有主成分分析 方法( p r i n c i p l ec o m p o n e n ta n a l y s i s ，p c a ) 【3 引，投影寻踪方法( p r o j e c t i o np u r s u i t ，p p ) p 9 j 等，这类方法思想简单直观，适用于处理线性结构，但计算复杂。下面对一些常用的 特征变换方法进行分析。p c a 是一种统计分析方法。p c a 经常被采用来对数据降维它 首先计算原始数据的协方差矩阵和该矩阵的前k 个特征向量，然后把原始数据映射到这 k 个主特征方向上，映射后的数据维很低，最后可以应用传统聚类算法如k m e a n s ， a u t o c l a s s 等进行聚类。p c a 在确定k 值时有较大的难度，若设得太小，将使数据丢失 很多有用的信息；若设得太大，虽然可以保留较多的特征信息，但对传统聚类算法来说维 数仍然太高，无法有效地聚类。另外，p c a 的计算量大，内存需求高，均为o ( m 2 ) ， 其中m 是样本数，当m 值很大时，算法复杂度无法接受。矩阵的奇异值分解( s v d ) 是一种有效的代数特征抽取。设a 为一个m x n 阶矩阵，若存在各列两两正交的方阵u ， n 阶正交方阵v 与主对角元素全部非负的对角阵d = d i a g ( d 1 ，d 2 ，d n ) 使得： a - u d v t ( 2 1 ) 则称d l ，d 2 ，“为矩阵的奇异值。将a 化为上式右端的形式，称为对a 进行 奇异值分解。 目前，奇异值分解在数据压缩、信号处理和模式分析等方面获得了广泛的应用，其 主要的理论依据是奇异值分解得到的特征，具有奇异值的稳定性，奇异值特征向量的旋 转不变性、转置不变性、位移不变性等良好性质。潜在语义分析( l a t e n ts e m a n t i c i n d e x i n g ，l s i ) 4 0 】是与p c a 类似的一种属性约简方法。与p c a 使用协方差矩阵的特 征向量不同，l s i 直接使用原始数据的奇异值分解技术，由于它不再计算协方差矩阵， 对内存和c p u 的需求比p c a 较少。f a s t m a p l 4 1 也是一种快速有效的特征变换方法，它 一8 一 大连理工大学硕士学位论文 采用距离映射将数据集映射到一个k 维空间，在这个空间中，对象之间的距离近似得以 保持，但要找到一个距离保持映射是困难的通常也是耗时的过程。另一较著名的方法是 自组织映射网络s o f m ( t h ek o h o n e ns e l f - o r g a n i z i n gf e a t u r em a p ) 【4 引，它基于神经网 络把高维数据映射到低维特征空间，算法主要缺点是无法确定其完成的属性转换是否有 效，即无法对质量进行评价。另外，当数据的维数非常高时训练网络的收敛速度非常慢， 影响正常使用。 2 2 子空间聚类 通常属性约简都是作为聚类的一个预处理阶段，从而使聚类算法有较少的有用属 性。但是属性约简方法也存在很大的不足：首先约简后的噪音数据与正常数据之间的差别 缩小，聚类质量无法保障。另外，属性约简技术的使用虽然缩小了数据维度空间，但其 可解释性、可理解性较差，可能会丢失重要的聚类信息，其结果的表达和理解存在着一 定的难度。总之，基于属性约简的降维技术对极高维数据的处理有着很大的局限性，无 法满足当前高维聚类应用的发展1 16 】。 同时，特征变换仅适用于大部分数据的维与聚类相关，同时维于维之间存在很大的 线性相关性和冗余度的高维聚类问题，并不是所有由特征选择得到的维都与聚类有关， 不同的数据类别可能对应不同的子空间，而每个子空间的维数也可能不同，要在全空间 得到聚类结构往往是非常困难的，甚至很多数据在整个空间没有明确的分类。而子空间 聚类算法能找到类以及与之相关的子空间来很好地解决这个问题。 2 2 1 子空间聚类原理 子空间聚类是在数据集的不同子空间中搜索聚类簇的过程，同样的数据集在不同的 属性子集上形成的聚类不同，所以子空间聚类的结果包括搜索到的聚类簇及其所在的子 空间【1 8 】。与传统聚类算法一样，子空间聚类算法也是一个搜索的过程。但是子空间聚类 算法需要进行两个搜索过程，一个是搜索聚类簇所在的子空间，即相关属性的集合；另一 个则是要搜索存在于子空间中的簇集。在高维数据中，由于可能的子空间数目通常很大， 要求高效的搜索算法。对搜索策略的不同选择，将产生不同的聚类偏差，同时也将影响 聚类算法对数据分布的假设。因此，搜索策略是子空间聚类方法中的一个重要因素。根 据不同的子空间搜索策略，现有的子空间聚类算法可以分为自底向上子空间搜索算法和 自顶向下子空间搜索算法两种【4 3 j 。 基于空间约束的半监督子空间聚类算法 2 2 2 自底向上的搜索算法 自底向上的搜索方法利用了关联规则中的先验性质( a p r i o r ip r o p e r t y ) 。如果一个 k 维单元是密集的，那么它在k 1 维空间上的投影也是密集的( 空间的上闭合性) 。反 过来，如果给定的k 1 维的单元不密集，则其任意的k 维空间也是不密集的【1 9 1 。 根据这一策略，它将每一维划分为若干网格，并为各维的所有网格形成直方图，然 后只选择那些密度大于给定阈值的箱( b i n ) ，因为包含了非密集维的子空间肯定不是密 集子空间，并不断重组这些密集单元以形成2 ，3 ，k 维单元，最后合并邻近的密 集单元以形成簇。因此这类算法也被称为基于密度的子空间聚类算法。 根据分箱的策略，自底向上子空间聚类算法可以进一步划分为基于静态网格的算法 和基于自适应网格的算法。基于静态网格的算法没有考虑每一维的具体数据分布情况， 而直接将每一维划分为大小相同的间隔。最早的静态网格聚类算法是由a g r a w a l 等人提 出的c l i q u e 算法，e n c l u s 也是一种经典的静态网格聚类算法。基于自适应网格的 聚类算法，使用数据驱动策略决定每一维分箱的割点，考虑每一维各自的数据分布特点， 以形成较少分箱数目，进而加快聚类过程。因此，自适应网格的聚类算法可以看作是对 静态网格聚类算法的改进，c b f 算法是这类算法的一个经典代表。 ( 1 ) c l i q u e 算法 c l i q u e l 6 】算法是一种综合了基于密度和基于网格的聚类算法的思想，并试图在数 据子空间中查找聚类的算法。该算法使用了策略来查找和合并某度量大于给定阈值的网 格，产生候选子空间，并且将这些候选子空间按其规模即子空间中点的数量的大小排序， 随后根据m d l ( m i n i m u md e s c r i p t i o nl e n g t h ，最小描述长度) 准则将规模较低的子空 间剪枝。其中，最小描述长度是解释数据的最好理论，应该使得描述理论所需要的比特 长度与在此理论下对数据编码所需要的比特长度之和最小。该类算法理论上可以找到任 意数量的维中任意类型和形状的簇，该结果由一组不同子空间的簇组成，并可由一个 d n p ( d i s j u n c t i v en o r m a lf o r m ，析取范式) 表达式所表示，且事先不需确定维的数量。 一般来说，c l i q u e 算法需要两个参数：网格尺寸和密度阈值t ，它们对聚类结果 的质量有很大影响。如果参数不合适，在剪枝阶段有时会删去小而重要的聚类。但是对 一个指定的数据集来说，要确定这些参数非常困难。因此，随后有不少算法针对c l i q u e 的缺点提出改进，如e n c l u s l 2 2 1 ，m a f i a t l l 】等。 ( 2 ) c b f 算法 不同于c l i q u e 算法，c b f l 2 3 1 算法提出了一种新型的网格建立算法和网格插人算 法，将箱子记录在一个基于过滤的索引结构中，从而增强了检索性能。首先，算法根据 大连理工大学硕士学位论文 每维的密度计算出其相应的分裂指标( s p l i ti n d e x ) ，随后将维分成两个部分再次计算 其分裂指标，如果该值小于其分裂前的值，则重复这个过程直至该值大于分裂前的值， 这时在n 维空间上建立的就是1 1 一最优分割区间。随后，算法将其中密度大于给定闭值的 箱子存人某个簇信息文件中，以改善f o 性能。最后算法访问该信息文件以得到最终簇。 c b f 算法需要两个参数：项阈值和箱阈值。项阂值决定了每一维的箱子数量，检索 时间随着该值的增大而降低；而箱阂值决定每个箱子中的最小点数，点数大于该阑值的 箱子才作为簇的一部分而选人簇信息文件。 2 2 3 自顶向下的搜索算法 自项向下算法也被称为基于投影的子空间聚类算法，采用的是迭代搜索的办法，使 得不同聚类簇具有不同的权重。具体算法流程是，首先在全空间给出一个初始近似的聚 类划分的，并给各个聚类簇赋予相同的权重，而后通过迭代对权重进行更新，更新后的 权重将用于在下一次迭代时生成新的聚类。 通过算法流程，不难发现算法通常需要行多次迭代，并且每一次迭代都要在全维空 间中对数据集进行聚类，需要很大时开销。因此，这类算法通常会采用抽样技术以降低 算法的时空复杂性。而且，这类算法为数据的每个部分都建立簇，这意味着不会有重复 的簇产生，一个点只能赋给一个簇。这也导致必须产生一个集合来分析孤立点。 p r o c l u s 1 1 】算法是第一个自顶向下的子空间聚类算法。f i n d i t l l 3 】算法是另外一种 不同的自顶向下子空间聚类算法它采取不同的策略，利用面向维的聚类距离来度量维度 的差别，来决定该对象每一维的权重。自顶向下子空间聚类算法趋向于发现同一子空间 或相同大小子空间中的聚类。 ( 1 ) p r o c l u s p r o c l u s 是最早被提出的自顶向下算法。它选择实际数据的一小部分作为数据的 样本，然后从样本中选择k 中心点并且反复改进簇的质量。该算法执行分三个阶段：( 1 ) 初始化阶段：为了保证每个结果簇中都至少有一个点在这个点集中。该阶段用贪心算法 从样本中抽取一些离得尽可能远的点集m ：( 2 ) 迭代阶段：该阶段对m 中每个中心点 都只选取那些在维上的平均值小于期望值的维作为相应的子空间。而后计算各个子空间 中所有点到相应的中心点的曼哈坦距离的平均值作为簇的半径，从而形成聚类。为了得 到最好的中心点，该阶段从样本中随机抽取一个点代替原点集m 中的最坏的中心点， 作为新的中心点，并以较优的点集为结果，反复这个操作直至m 稳定。( 3 ) 改进阶段： 该阶段对每个形成的簇的中心点重新计算来确定维集，以维集中点到中心点的距离的平 均值形成新簇，并删去孤立点。 基于空间约束的半监督子空间聚类算法 p r o c l u s 更适合查找超球面形状的簇，这些簇的大小必须相近，因为该算法以结 果簇的维的平均数量为参数。由于使用了抽样技术，p r o c l u s 在大数据集上聚类的速 度比c l i q u e 快些。但是，这样仅用少量的有代表性的点会导致p r o c l u s 完全地丢失 一些簇。 ( 2 ) f i n d i t 与其它聚类算法不同，f 1 n d i t 算法不使用常规的欧几里得距离衡量对象间的距离， 它使用d o d ( d i m e n s i o no r i e n t e dd i s t a n c e ，面向维的距离) ，该度量不仅可以表达对象 值的差别，还可以表达维度的差别。和p r o c l u s 类似，f i n d i t 也分三个阶段执行：在 抽样阶段，使用一个随机抽样方法产生两个相异的样本，其中样本s 反映了给定数据集 的分布情况，而样本m 是选定的簇的中心点集。在簇形成阶段，算法提出了维投票策 略( d i m e n s i o nv o t i n gm e t h o d ) ，计算s 集中每个维距中心点的平均d o d 距离，选取距 离小于阈值的维作为相关维。随后计算所有中心点之间的d o d 距离并合并距离较近 的中心点，以形成中心点簇( m e d o i dc l u s t e r ) 。在最后阶段，s 集中所有点被赋给距其 最近的中心点簇，而没有被赋给任何簇的点则被归为孤立点。 f i n d i t 需要两个输人参数：m i n s i z e 指出结果簇所需的最小实例数量，m i n d i s t 确定 两个簇之间的最小d o d 距离。如果两个簇之间的距离小于该最小距离，则合并这两个 簇，而阈值则由算法使用某种策略重复叠代产生，因此大大增加了算法所需的时间，所 以在算法中使用抽样策略改善聚类的效率。 2 。3 本章小结 本章介绍了高维大规模数据聚类面临的挑战和问题，比较了两种降维技术的优劣， 从而论证了子空间聚类算法的优势，并确定了子空间聚类是高维大规模数据聚类的主要 解决方法。在第二节中分析了几种常见子空间聚类算法的基本思想及其优缺点，指出了 这些算法面临的问题。 大连理工大学硕士学位论文 3 半监督聚类算法的研究 3 1 半监督学习 3 1 。1 半监督学习的研究背景 在传统的监督学习中，学习器通过对大量已标记的数据进行学习，从而建立模型用 于预测未标记的数据。近几年随着机器学习理论在数据分析和数据挖掘的实际问题，例 如网页检索和文本分类，基于生物特征的身份识别，图像检索和视频检索，医学数据处 理等问题中的广泛应用，收集大量未标记数据已经相当容易，而获取大量已标记数据的 数据则相对较为困难，因为获得这些标记可能需要耗费大量的人力物力1 2 0 j 。 显然，如果只拥有少量的已标记数据，那么利用它们所训练出的学习系统往往很难 具有强泛化能力；另一方面，如果仅仅使用少量“昂贵的 已标记数据而不利用大量的 “廉价的 未标记数据，则是对资源的极大浪费。因此，如何利用少量已标记数据提高 大量未标记数据的学习性能已成为当前及其学习研究中最受关注的问题之一。 针对这一问题，提出了半监督学习技术。半监督学习【5 j ( s e m i s u p e r v i s e dl e a r n i n g ) 是模式识别和机器学习中的重要研究领域。近年来，半监督学习在理论和实际应用研究 中获得了长足的发展。半监督学习研究主要关注当训练数据的部分信息缺失的情况下， 如何获得具有良好性能和推广能力的学习机器，这里的信息缺失涵盖数据的类别标签缺 失或者存在噪声，数据的部分特征维缺失等多种情况。 自2 0 世纪九十年代以来国际机器学习界研究者在半监督学习研究领域展开了广泛 深入的探讨和研究。其涵盖的范围非常广泛，例如半监督回归问题；利用标签和特征维 都缺失的数据集进行学习；标签有噪声时的数据处理；利用少量已标记数据和大量未标 记数据进行学习以及对于大量未标注数据中已知只存在少量己标记的情况下对于正样 本进行检测；对各种监督学习算法进行修改，探讨如何融入非监督数据信息或者对于非 监督学习算法进行修改，探讨监督数据信息的引入；利用有限混合模型对于数据的概率 分布进行建模或者利用其他模型对于数据标签关于特征维的条件概率进行建模，利用 e m 算法学习模型参数的半监督学习的研究；引入合适的数学方法进行半监督学习，例 如基于核矩阵的谱的分析，高斯随机场的利用，利用图论中的方法来对于样本集进行聚 类分析；半监督数据的流形分析等。研究者同时开展了将半监督学习和传统模式识别和 机器学习中的一些问题相结合的研究，例如基于半监督学习的特征提取，半监督学习和 集分类器的设计等。国际研究者同时开展了与半监督学习有着密切关联的一些相关研 基于空间约束的半监督子空间聚类算法 究，具有代表性的是利用半监督数据和数据的不同特征维子集在数据的不同视图上同时 训练具有良好性能的学习机器。 3 1 ，2 半监督学习的原理 半监督学习的基本设置是给定一个来自某种未知分布的已标记数据集l = ( x l ，y 1 ) ， ( x 2 ，y 2 ) ，( x l l i ，y i l i ) 以及一个未标记数据集u = 葛，t ，x i i ，期望学得函数x y 可以准确地对示例x 预测其标记y 。这里x i ，x ? x 均为d 维向量，y i ey 为示例 x i 的标记，| l i 和i u l 分别为l 和u 的大小，即它们所包含的数据个数。 而后，从数据分布估计的角度进行直观的分析，假设所有数据服从某个由l 个高斯 分布混合而成的分