（计算机软件与理论专业论文）噪声鲁棒的自适应降维聚类.pdf

噪声鲁棒的自适应降维聚类 论文题目 专业 硕士生 指导教师 噪声鲁棒的自适应降维聚类 计算机软件与理论 薛少锷 印鉴教授 摘要 聚类是用于数据分析的一种有着广泛应用的统计方法。随着数据收集技术 的不断发展进步，数据集的维度越来越高，在高维数据集上进行聚类成为一个具 有挑战性的课题自适应降维聚类法( a d r c ，a d a p t i v ed i m e n s i o nr e d u c t i o n c l u s t e r i n g ) 是近年来提出的一类具有较好应用前景的高维聚类算法，它以距离 作为相似性度量，同时地考虑“自适应降维”和“子空间聚类”两个方面，使所 抽取出来的子空间具有最佳判别能力，从而聚类的结果比起传统的算法，如群 m e a n s ( k m ) 更容易跳出局部最优。然而，这类算法在建模的时候没有考虑到离 群点可能带来的影响，对数据集中同时存在明显同方差簇和离群点的情况表现得 不鲁棒。而离群点在现实数据集中是经常出现的 为处理这个问题，本文提出了噪声鲁棒的a d r c 算法思想( n r a d r c ，n o i s e r o b u s ta d r c ) 它尝试在自适应降维聚类算法的两个主要步骤“自适应降维”和 “子空间聚类”中引进密度因素，降低这两个过程被噪声污染的可能性。本文选择 最近提出的l d a k m 算法作为特例，在其两个子过程l d a 和k m e a n s 过程中考虑 密度因素，得到n r l d a ( n o i s er o b u s tl d a ) 和n r k m ( n o i s er o b u s tk m e a n s ) 然后从理论上证明了如果使用同一种有效的密度估计方法，n r l d a 和n r k m 可 以集成为一个统一的噪声鲁棒的自适应降维聚类框架。最后，采用一定的密度估 计策略在实际数据集和合成数据集上进行实验，结果表明了n r a d r c 的有效性。 关键词：聚类、k m e a n s 聚类、自适应降维、高维数据、密度估计 第1 页 噪声鲁棒的自适应降维聚类 t i t l en o i s er o b u s ta d a p t i v ed i m e n s i o nr e d u c t i o nc l u s t e r i n g n a m es h a o ex u e m a j o rc o m p u t e rs o f t w a r ea n dt h e o r y s u p e r v i s o rp r o f e s s o rj i a ny i n a b s t r a c t c l u s t e r i n gi so n eo ft h em o s tw i d e l yu s e ds t a t i s t i c a lm e t h o d si nd a t aa n a l y - s i s w i t ht h ed e v e l o p m e n to fd a t ac o l l e c t i o nt e c h n i q u e s t h en u m b e ro fd i m e n s i o n s i n c r e a s e s ，w h i c hm a k e si t ac h a l l e n g i n gw o r kt op e r f o r mc l u s t e r i n gi nah i g hd i - m e n s i o n a ld a t a s e t a d a p t i v ed i m e n s i o nr e d u c t i o nc l u s t e r i n g ( a d r c ) m e t h o d s a r eac l a s so fp r o m i s i n gc l u s t e r i n gt e c h n i q u e sp r o p o s e di nr e c e n ty e a r s b a s e do n d i s t a n c es i m i l a r i t yg e n e r a l l y , t h e ys i m u l t a n e o u s l yc o n s i d e r “a d a p t i v e l yr e d u c i n g t h ed i m e u s i o n a l i t y 。a n d “c l u s t e r i n gi nt h el o wd i m e n s i o n a ls u b s p a c e ”s u c ht h a t t h es u b s p a c ee x t r a c t e dc o n t a i n st h em o s td i s c r i m i n a t i v ei n f o r m a t i o n ，a n dt h a t c l u s t e r i n gr e s u l t st e n dt oe s c a p ef r o ml o c a lm i n i m aw h i c hi so f t e ne n c o u n t e r e d i nc o n v e n t i o n a la p p r o a c h e sl i k ek m e a n s ( h e n c e f o r t hk m ) h o w e v e r ，t h ea d r c m e t h o d sd on o tp a ya t t e n t i o nt on o i s ed a t ai n f l u e n c ei nt h e i rm o d e l s ，a n dg e t s t u c ki nt h es i t u a t i o nw h e r et h e r ea r eh o m o s c e d a s t i cc l u s t e r s ，w h e r e a so u t l i e r sa t t h es a m et i m e t oa d d r e s st h i sp r o b l e m ，a ni d e an a m e dn o i s er o b u s ta d a p t i v ed i m e n s i o n r e d u c t i o nc l u s t e r i n g ( n r a d r c ) i sp r o p o s e d n r a d r ci n t r o d u c e st h ed e n s i t y f a c t o ri n t ot h et w os u b p r o c e s s e so fa d r ct om a k et h e ml e s ss e n s i t i v et oo u t l i e r s t h i sp a p e rt a k e st h er e c e n t l yp r o p o s e dl d a k m a l g o r i t h ma sas p e c i f i ci n s t a n c e d e n s i t yi sc o n s i d e r e di nl d aa n dk - m e a n s ，r e s u l t i n gi nn r l d a ( n o i s er o b u s t l d a ) a n dn r k m ( n o i s er o b u s tk m e a n s ) ，w h i c ha r el a t e rt h e o r e t i c a l l yp r o v e d 乞ob ec o m b i n e di n t oau n i f i e dn r a d r cf r a m e w o r ki ft h es a m ed e n s i t ye s t i m a t i o n s c h e m ei sa p p l i e di nb o t hn r l d aa n dn r k m f i n a l l y , e x p e r i m e n t su s i n gc e r - t a i nd e n s i t ye s t i m a t i o ns t r a t e g i e so nr e a lw o r l da n ds y n t h e t i cd a t a s e t ss h o wt h e e f f e c t i v e n e s so ft h ea l g o r i t h mp r o p o s e d k e yw o r d s ：c l u s t e r i n g ，k - m e a n sc l u s t e r i n g ，a d a p t i v ed i m e n s i o nr e - - d u c t i o n ，h i g h - d i m e n s i o n a ld a t a ，d e n s i t ye s t i m a t i o n 第1 i 页 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立 进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全 意识到本声明的法律结果由本人承担。 学位论文作者签名： 日期： 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并向国家主管部门或其指定机构送交论文的电子版 和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论文进 入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入有关数 据库进行检索，可以采用复印、缩印或其他方法保存学位论文。 学位论文作者签名前少铭 醐一7 年硼堋 导师签名： 醐：7 砩卿 噪声鲁棒的自适应降维聚类 1 1 研究背景 第1 章绪论 随着人类的不断发展进步，信息社会的到来给我们带来了极大的冲击。信息 这个概念对人们来讲不再陌生。为了获取更多的信息，人们不断提高收集数据的 能力和速度，不断地进行技术创新。然而，数据并不等同于信息，人们往往并不 缺少数据，而是缺乏将数据中所蕴含的人们感兴趣的丰富信息提取出来的方法和 技术。数据是信息的载体，如何透过这个载体获取人们感兴趣的信息，是一项重 要的有意义的工作。数据库的检索查询工具已不能满足人们的需要，数据仓库的 联机分析处理( o n - l i n ea n a l y t i c a lp r o c e s s i n g ，o l a p ) 虽然有了总结、概化和聚 集的功能，可以多角度观察数据，对决策支持有一定帮助，但它也不能进行更深 层次的分析，发现大量数据背后所承载的有用的知识。 数据挖掘( d a t am i n i n g ) 正是用于从数据中挖掘有用信息的一个概念和技 术。有时，它也被称为数据库中的知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ) ， 是数据库研究、开发和应用最活跃的分支之一。它是一个交叉的学科，用到很多 领域中的知识。比如，统计学、模式识别、机器学习、信息检索、人工智能、神经 网络等等。这些领域的知识的交叉、融合，使得数据挖掘具有非常广泛的应用。它 于2 0 世纪8 0 年代逐渐兴起，9 0 年代有较大发展，并且，在新世纪里，继续备受关 注。 聚类( c l u s t e r i n g ) 技术是一种经典的数据挖掘技术，它将物理的或抽象的对 象划分成若干小组，使得同一小组内部的对象相似度高，不同小组间相似度低。 聚类分析可应用于许多领域，比如市场研究( m a r k e t i n gr e s e a r c h ) 、模式识别 ( p a t t e r nr e c o g n i t i o n ) 、图像处理( i m a g ep r o c e s s i n g ) 等。在这些应用中，人们遇 到了一类问题：数据的维度( 也可以理解为事物的属性、特征、方面) 过高，引发 了所谓的“维度灾难 问题 1 】，使得与聚类任务相关的维信息被其他无关的维信 息所淹没，从而难以在高维空间上取得良好的聚类效果。 为处理这个问题，人们通常会采用降维技术对数据集进行处理，然后再在低 维子空间上执行聚类。一般地，降维处理与聚类操作是两个分离的过程，降维 被看作是聚类操作的一项前处理工作，两者之间并没有必然的联系。比如，先 第1 页 噪声鲁棒的自适应降维聚类 数据 挖掘 分类 f ，一般 聚类一 l l 高维 其他 图1 1研究背景：a d r c 算法在数据挖掘中的粗略位置 用p c a 2 1 方法对数据集进行降维处理，再把原数据集投影至u p c a 子空间上，最 后再用普通的聚类算法，如k m e a n s ( 下文简称k m ) 对经过降维处理的数据集 进行聚类；类似的降维技术还包括有随机投影( r a n d o mp r o j e c t i o n s ) 【3 】3 ，拉普 拉斯特征映射( l a p l a c i a ne i g e n m a p s ) 【4 】，保留局部性投影( l o c a l i t yp r e s e r v i n g p r o j e c t i o n s ，l p p ) 5 1 ，l a p l a c i a np c a 6 等。 这些方法的特点是降维操作只进行一次，一旦聚类子空间确定，则其在后继 的聚类过程中是保持不变的。近年来，有一类称为“自适应降维聚类 ( a d a p t i v e d i m e n s i o nr e d u c t i o nc l u s t e r i n g ，下简称a d r c ) 的方法认为，企图一次降维就找 到适合于聚类的子空间可能是不妥的，因为此时抽取得到的子空间还很可能保存 了一些与聚类无关的噪声维，继续影响着聚类任务的顺利进行。所以，a d r c 算 法同时地考虑“自适应降维”和“子空间聚类”两个方面，把子空间上聚类的结果 反馈给降维过程，以期继续剔除与聚类任务无关的维度，改进此前找到的子空间， 最终自动求得最具判别能力的子空间( d i s c r i m i n a t i v es u b s p a c e ) 。 a d r c 算法正是本文的研究重点。图1 1 给出了此类算法在数据挖掘中的粗略 位置图。 1 2自适应降维法聚类算法的研究现状 自适应降维聚类算法目前主要有如下几类，分别是a d r e m ( a d a p t i v ed i m e n s i o nr e d u c t i o nf o re m ) 7 1 ，a d r k m ( a d a p t i v ed i m e n s i o nr e d u c t i o nf o r k m ) f 7 1 ，a s i ( a d a p t i v es u b s p a c ei t e r a t i o n ) 8 】，d c a ( d i s c r i m i n a n tc l u s t e r a n a l y s i s ) 【9 】，l d a k m ( l i n e a rd i s c r i m i n a n ta n a l y s i sk m ) 1 0 。其中，a d r k m 是 可看作a d r e m 的一种特例，因此在后面的行文中，将这两种算法简记为a d m ，并 且在没有特别说明的情况下，a d m 指的是a d r k m 。 第2 页 隹圭一 隹 争 皇_ i f 降 应 次 适 一 自 ，、【 噪声鲁棒的自适应降维聚类 2 0 0 2 年，c h r i s td i n g 等人在i c d m 0 2 上发表了用于高维数据聚类的自适应降 维法a d m ，旨在解决像e m 1 1 或k m 这类算法易陷入局部最优的问题。算法在合 成的高度重合的g a u s s i a n s 数据，d n a 微序列基因表达数据都表现了不错的性能。 2 0 0 4 年，t a ol i 等人提出了a s i 算法，用于文档聚类。a s i 基于模型，假定数据 中的每一个簇都有其对应的子空间结构，这个子空间是原空间中的特征的线性组 合。a s i 显式地描述这些子空间结构，并推出了一个自适应子空间迭代( a d a p t i v e s u b s p a c ei t e r a t i v e ) 的框架，用在文本聚类上聚得了不错的效果。 2 0 0 6 年，t o r t e 等人又提出了一种a d r c 算法d c a 。它实际上可以看作是一种 “软划分”聚类。这一点a d r e m 接近，但与a d r k m 和a s i 贝u 不同。这种办法在人 脸数据集上表现了良好的聚类结果。 2 0 0 7 年，c h r i s t d i n g 等人提出了l d a k m 算法。他们认为，l d a 与k m 的目 标都是使得类内方差最小化，而类间方差最大化，依此，他们将有监督的l d a 嵌 入到无监督的k m 算法中，得到了一种新颖的a d r c 算法。这种算法设计和实现都 较简单，在实际数据集上也表现出了一定的优越性。 然而，上述的几种a d r c 算法均只考虑用距离作为相似性度量，且都对数据 的分布形态作了一定的假设，一般都要求出现在子空间上的簇是可以使用k m 得 到最佳划分的。这样的假设使得它们在遇到实际数据集时，表现随着数据集形态 的不同而产生不同的效果。而离群噪声点，对于数据的形态有着较显著的影响。 即使数据集中的主要簇是满足假设的，但只要有小部分的噪声点，数据的形态将 会被改变。从而，从子空间聚类过程反馈给降维过程的信息就很可能不能抓住数 据集中最重要的部分的信息，使得降维过程不能有效地完全剔除与聚类任务无关 的维度，最终导致上述的算法失效，因此很有必要设计更有效的a d r c 算法来应 对这种情形。 1 3本文研究内容及意义 针对现有a d r c 算法的在数据模型假设上的缺点，本文着重地研究了这种情 况：当数据集中的主要明显簇满足同方差高斯分布，但同时存在着一些噪声点时， 应当如何恰当地使用a d r c 算法，使其对于噪声的敏感度最大程度地降低，最终 发现最佳判别子空间以及子空间上的明显簇。 本文所提出的算法的基本思路是将密度因素引进了a d r c 框架中的两个主要 第3 页 噪声鲁棒的自适应降维聚类 步骤，同时考虑距离因素和密度因素，以降低噪声数据在这两个子过程中的影 响，从而得到噪声鲁棒的a d r c 算法( n o i s er o b u s ta d a p t i v ed i m e n s i o nr e d u c - t i o nc l u s t e r i n g ，下简称n r a d r c ) 。这种思想可以用于已有的几个a d r c 算法， 本文以最近提出的l d a k m 为特例，借鉴了谱聚类( s p e c t r a lc l u s t e r i n g ) f 1 2 】中 的图模型进行密度估计，实现了一种n r a d r c 。在下文中，对n r a d r c 和本文 以l d a k m 为例所实现的n r a d r c 的特例在不作说明的情况下将不再区分，根据 具体语境而定。 现实的数据集中，由于数据收集、预处理等过程的复杂性，出现离群点或噪声 点的可能性是很大的，这种情况下，如果采用只适合于完美假设的模型来处理 实际的数据集，那么聚类的效果将很大程度上地被噪声点所左右。而n r a d r c 算 法考虑了噪声影响，在聚类效果方面表现出比现有的a d r c 更优越的一面。而且， 事实上它并没有增加本质的计算复杂度。复杂度的增加主要是在前期密度估计上， 如果有办法采用计算复杂度较低的密度估计办法，那么本文所提出的n r a d r c 算 法将明显优于现有的其他算法，因而具备良好的实用价值。 1 4术语和符号约定 为了统一语意，在本文中，对于术语和符号将作如下约定。 1 4 1 基本术语 属性空间s 设a = a 1 ，a 2 ，a d ) 是一个属性的集合，则s = a 1 a 2 a d 为一 个d 维的属性空间，其中a 1 ，a 2 ，a d 是s 的维( 同义词：特征、方面、变量) ，d 称 为s 的维数。 5 空间上一个大小为死的数据集疋= z 1 ，z 疗) 是由a 上的n 个数据点( 同义 词：对象、无组、实例、记录) 兢= ( z 5 ，z ：，z 尸) t ，z = 1 ，佗组成。这 里z i 是列向量形式，z y a j ，j = 1 ，d ，表示数据点甄的第j 个分量。x = 陋1 ，z n 】则表示彤对应的d n 矩阵。后面的行文中，一般地，除非有特别说明， 否则，对矩阵所表达的点集和点集本身不作严格区分，即x 就表示点集彤。 狭义子空间 d 维属性空间5 的d 维子空间一般是指属性集合a 的大小为d 的子集所组成的属 第4 页 噪声鲁棒的自适应降维聚类 性空间，即s 7 = a t 。xa t 。x xa t d ，其中，d d ，且如果i j ，则如 t j 。 广义子空间 如果构成对子空间每一个特征稍作放宽，可以得到d 维属性空间s 的d 维广义子空 间。构成s 上的每一个属性均看作是是属性集合a 中的属性的线性组合，即s = 墨。u p a t 圣。u ax 墨。d n a t ，其中，嘶= ( 母，q d ) t ，j = 1 ，d 是每一个广义特征的线性系数向量。如果限制u f 的元素只允许有且仅有一 个为l ，而其余元素为0 ，并且对任意i j ，u i 嘶，那么此时的广义子空间就等 价于一般的子空间了。 记u = 【2 5 1 ，u 2 ，牡d 】，则u 事实上是一个对应于子空间y 的d d 投影矩 阵，它能将s 上的数据集x 投影到上，得到x 在y 上的表达y = u t x 。y 就是 一个dx 扎矩阵，对应于n 个d 维的数据点组成的点集y = 可1 ，耽，玑) 。 1 4 2 符号约定 如果没有特殊说明，一般使用小写的字母表示标量，用粗斜体小写字母表示 向量，用粗体大写字母表示矩阵，用花体字母表示属性空间，或对应空间上的点 集合。实数集合为r ，非负实数集为r + ，r d 表示一个d 维的实数空间。符号约定 参见表l 一1 。 1 5本文组织结构 本文分成六章，第1 章为绪论；第2 章简章介绍聚类，特别是高维数据聚类的 基本概念及其发展的基本情况；第3 章着重介绍自适应降维聚类法，详细介绍对这 类算法的现有几种重要类型，并指出其不足；第4 章针对第3 章指出的现有自适应 降维聚类算法缺点，提出更准确反映数据集的假设，设计了n r a d r c 算法，并从 理论上证明其有效性；第5 章是实验。通过实际数据集和合成数据集上的实验证 明n r a d r c 算法的有效性；第6 章是本文的总结和展望。 第5 页 噪声鲁棒的自适应降维聚类 表1 - 1符号约定 r ，r + ，r d 实数集合，非负实数集合，d 维实数集 s = a 1 a 2 a d d 维属性空间 e n 亍龠) t 包含n 个1 的全1 向量 名= 戤悻= 1 ，2 ，n 属性空间5 上的一个样本大小为几数据集 x = x l ，z n 】 数据集z 所对应的矩阵表示1 x k = 陋，z 】 第尼个簇中的所有砜个点的矩阵表示 z ， 点兢的第f 维元素，f = l ，d w i ，i = 1 ，2 ，佗点戤，i = 1 ，2 ，礼的密度、影响力、权重 w = d i a g ( w l ，w 2 ，) 对象线上为x 中的点的对应影响力的对角矩阵 w k = d i a g ( w k l ，w k 2 ，砌k k ) 对角线上为x 七中的点的对应影响力的对角矩阵 z r x t向量z 的转置，矩阵x 的转置 面= 警或融 x 的几何中心或加权中心 n 。e 二w 瓦= 警或糍 x 七的几何中心或加权中心 u = f u l ，t d 】 投影矩阵，d 维子空间，d d 鼽= u t 翰戤，i = 1 ，n 在子空间u 上的投影 m = ( 面1 ，瓦) x 的k 个簇的几何中心或加权中心 c = 可1 ，可k ) y = u t x 的k 个簇的几何中心或加权中心 h 点簇关系矩阵 i i 绝对值 i | 0 l 2 范数；e u c l i d e a n 距离 t r ( x ) 矩阵x 的迹 d e t ( x ) 矩阵x 的行列式 d i a g ( a l ，a 2 ，a n ) 生成一个对角线上为n 。，a 2 ，q n 的对角矩阵 1 没有特别说明时，认为x 既表示数据集石也表示其对应矩阵 第6 页 噪声鲁棒的自适应降维聚类 第2 章聚类 本章分成三个部分。第一部分介绍数据挖掘，阐述数据挖掘领域的重要技术 “聚类”。第二部分，简单综述高维空间上的聚类的特点和基本方法。第三部 分，详细介绍了经典聚类算法k m 聚类的基本思想、算法描述及其优缺点。 2 1数据挖掘与聚类 这一部分包括了两个子部分，第一个子部分介绍数据挖掘的概念、产生背景 和应用领域等。第二个子部分介绍聚类的概念、应用背景、以及主要算法概览。 2 1 1 数据挖掘 今天，人们不可避免地生活在一个充满数据的世界里。一个人从出生的那一 天起，几乎就注定了与数据相伴，不管是否愿意。每一天，人们几乎都在遇到各种 各样的数据，包括图片，数字，声音，现象等。在这其中，有一些数据可以数字化 表示，以数据形式存放在媒介上，如电脑磁盘。信息技术的发展，一方面给人们带 来数据处理能力的提升和无比丰富的资讯，另一方面，也使得人们在数据的海洋 中多少显得有些无所适从。要理解数据挖掘，可以从数据管理的演化过程找到一 些轨迹。 2 0 世纪5 0 年代中期以前，数据管理处于人工管理阶段，数据不保存；2 0 世 纪5 0 年代后期n 6 0 年代中期，数据管理进入了文件系统阶段，由于有了磁盘等直 接存取存储设备，数据可以长期地保存；2 0 世纪6 0 年代后期以来，数据管理进入了 数据库系统阶段，大量的数据可以被长期保存在数据库中。2 0 世纪7 0 年代以后，关 系数据库系统、数据建模工具等逐渐得到应用，联机事务处理( o l t p ) 对于数据 库技术的发展也作出重要贡献。2 0 世纪8 0 年代以后，各种先进的数据模型被引入 了数据库系统，如扩充关系模型、面向对象模型等。异质数据库和基于i n t e r n e t 的 全球信息系统也出现，并成为信息产业的主力军。数据仓库正是在这样的环境下 诞生的，它可以以统一的模式组织存储异质数据源，对帮助人们处理数据，支持 决策有发挥着重要作用。数据仓库技术包括了数据清理、数据集成、和联机分析 ( o l a p ) 。然而，尽管数据仓库可以支持汇总、聚集、多角度观察数据等功能，但 是对于深层次的分析，如，数据的分类、聚类、数据随时间变化的特征，仍然需要 第7 页 噪声鲁棒的自适应降维聚类 有其他工具的帮助。 “需要是发明之母”。数据丰富而提取有用信息的技术缺乏，使得存在着大 量数据的大型数据库变成了长埋地下无人可及的宝藏。于是，重要的决定往往不 是基于数据库中信息丰富的数据，而只能靠决策者的直觉，因为决策者缺少有力 的工具以提取有价值知识。当然，目前也有人提出了“专家系统”的概念和技术， 这种系统需要用户和领域专家人工地将知识输入到知识库中。然而，不可避免地 会有所偏差，且耗时、成本高。数据挖掘工具可以发现数据中人们感兴趣的信息、 知识。“信息匮乏”而“数据泛滥”之间的矛盾，促使人们系统地进行数据挖掘方 法和工具的研发，以锻造开采数据宝藏的利器。 关于数据挖掘的概念，并没有一个统一的定义。比较认同的一个定义是：数 据挖掘( d a t am i n i n g ) 是指从大量的、不完全的、有噪声的、模糊的、随机的数 据中，提取隐含在其中的，人们事先不知道的、但是又潜在有用的信息和知识的 过程f 1 3 1 。此外，数据挖掘还有不少近似的叫法，如知识发现( k d d ) ，知识提取， 数据捕捞等。数据挖掘是一门交叉学科，其研究者包括了数据库、人工智能、模 式识别、统计分析、可视化等等。各行各业中，数据挖掘技术也得到越来越广泛 的应用。如，在商务界市场研究中，利用数据挖掘，可以挖掘出市场主要消费群体 的特征，从而对其实施个性化的营销策略；在计算机图像设计中，利用数据挖掘， 可以帮助设计人员对多媒体进行快速有效的处理；在社会建设中，得用数据挖掘， 可以发现社区运作过程的某些规律，从而更好地节约能源，创建文明社会。 数据挖掘可以看作是各种技术的混合使用，在大量的数据中发现模型和数据 间的关系，并利用这些模型或者关系来描述或者预测事物。它一般包括了以下几 个步骤： 1 数据清理：清除噪声及不一致数据 2 数据集成：组合不同的数据源 3 数据选择：从数据库中检索、分析与挖掘任务相关的数据 4 数据变换：将原始的数据变换到适合采用数据挖掘技术的形式 5 知识提取：核心基本步骤，采用各种办法提取有趣的模式或者信息 6 模式评估：根据某些兴趣度评价准则，对提取出来的模式进行评价 7 知识表达：使用可视化等技术，向用户展示挖掘的模式、知识、信息 当然，必须指出的是，数据挖掘技术并非万能，它仍然离不开人，需要使用者 了解业务，理解数据，清楚分析方法。一个数据挖掘得到的模式无法保证其在实 第8 页 噪声鲁棒的自适应降维聚类 际领域中的实用价值，只能对特定的领域有所作用，必须在实际中得到检验。 数据挖掘的研究方向有不少，如分类、聚类、时间序列频繁模式挖掘、图挖 掘等等，这些方法在不同的应用中发挥着重要作用。下一部分，会着重地介绍聚 类技术。 2 1 2 聚类技术 聚类( c l u s t e r i n g ) 技术是数据挖掘中的一个重要方向。现实中，我们也会经 常碰到聚类问题。比如，即使没有人教我们，我们也能很容易地能对猫和狗进行 区分，对动物和植物进行区别。又比如：操场上有一群小孩，如何将这群小孩按 照某一定的规则( 如按性别) 划分成到几个小组里面，使得同一个小组里面的小 孩具有高度的某种相似性，而不同小组之间的小孩的这种相似性差别是较大的， 这也是聚类问题。再如，我们为了使个人物件更方便存取，会将用途较为接近的 物件放到一起，而将差异较大的分开放，事实上我们也是进行了聚类分析的过程。 聚类分析过程可以看作是人们认识学习新事物的众多方法之一。对于新的事物或 现象，人们总会有意识无意识地寻找一些本质的特征来描述它，然后，使用一定 的准则，将不同事物或现象之间的特征进行比较，以此来判断事物之间的相似性。 这里，所找到的描述事物或者现象本质的特征以及事物之间的相似性就可以看作 是学习到的事物内在的信息。如果在寻找本质特征或者比较事物之间相似度的过 程中是有指引的( s u p e r v i s e d ) ，那么就将这种方法称为有监督的( s u p e r v i s e d ) ， 反之，则称为无监督的( u n s u p e r v i s e d ) 。比如，给一个刚会识人的小孩看一群人， 告诉他哪些人是男的，哪些人是女的，以便让该小孩获取到男人和女人的特征， 这个过程就是有监督的。如果只给这个小孩子看一群人，但不告诉他哪些是男人， 哪些是女人，那么，看多了，他可能就知道这些他看到的人中大概可以分成两个 组，尽管他不知道这些人叫做男人和女人，但他可以知道这些人在某些本质的特 征上是存在着不同的。这个过程就是无监督的。 聚类分析就是一种无监督的学习过程。下面先给出聚类分析中的重要定义： 定义2 1 1 聚类( c l u s t e r i n g ) p s i 将物理或抽象对象的集合分成相似的对象类的 过程称为聚类。 定义2 1 2 簇( c l u s t e r ) p s i 是数据对象的集合，这些对象与同一个簇中的对象 彼此相似，而与其他簇中的对象相异 聚类分析的任务，就是根据数据之间的某种的相似性度量把数据集合划分到 第9 页 噪声鲁棒的自适应降维聚类 不同的组中，使得组内数据相似性最大化，组间数据相似性最小化。相似性度量 的可定义如下： 定义2 1 3 相似性度量( s i m i l a r i t ym e a s u r e 土两个对象z t 和奶之间的相似性度量 是一个如下形式的函数： 8 = 5 ( x i ，) ，s r +( 2 1 ) 其中，她，均是实际对象的描述，通常使用向量表示。即z ；= ( z ：，z 尸) 。相 似性度量函数有两大类，一类是差异函数形式的，函数值越小就意味着两个对象 之间越相似；另一类是相似函数形式的，函数值越大就表明两个对象之间越相似。 以差异函数形式出现的相似性度量例子有几何问题中的标准度量m i n k o w s k i 距离 n l p ( x t ，吻) = ( 印一z y 附 1 = 1 ( 2 - 2 ) 其中z 表示z i 的第2 维的值。令p = 2 就得到最常见的e u c l i d e a n 距离，令p = 1 就得 至 j m a n h a t t a n 距离。以相似函数形式出现的有c o s i n e 度量，p e a r s o n 相关系数f 1 3 等。 相似性度量形式的多种选择，使得聚类算法种类繁多，同时，也有许多不同 很多场合。在市场营销中，人们可根据客户的消费数据将客户聚类，然后在聚类 的基础上进行有针对性的个性营销；在互联网应用中，可以根据内容对w e b 文档 进行聚类，进而结合分类( c l a s s i f i c a t i o n ) 技术，发信隐藏于其中的信息。聚类分 析应用从工程领域( 机器学习，人工智能，模式识别，电子工程) ，计算机科学领 域( w r e b 挖掘，空间数据库分析，图像分割) ，生命与医学科学领域( 遗传学，生物 学，微生物学，心理学) ，到地球科学( 地理学，地形学，遥感) ，社会科学领域( 社 会学，教育) ，以及经济领域( 市场营销，商务) 1 4 1 。但是，从另一个角度看相似 性度量形式的多样性，它使得聚类结果是没有统一的最优标准的。所以，正如【1 5 】 中所提到的“不可能性定理”所叙述的那样：“开发出一个统一的框架来从技术层 次上理解聚类是很难的( i th a sb e e nv e r yd i f f i c u l tt od e v e l o pau n i f i e df r a m e w o r k f o rr e a s o n i n ga b o u ti t ( c l u s t e r i n 9 1a tat e c h n i c a ll e v e l ) ”。聚类是与具体领域知识 密切相关的，人们需要研究手头的数据的具体特点，按需要选择不同的相似性度 量。 聚类的方法有不少，如划分方法( p a r t i t i o n i n gm e t h o d s ) ，层次方法( h i e r a r c h i c a l m e t h o d s ) ，基于密度方法( d e n s i t y - b a s e dm e t h o d s ) ，基于网格方法( g r i d - b a s e d m e t h o d s ) ，基于模型方法( m o d e l - b a s e dm e t h o d s ) 1 3 】。 第1 0 页 噪声鲁棒的自适应降维聚类 划分方法要求将给出的对象集分配到若干个组中，使得结果满足：1 ) 每一个 组里至少有一个对象；2 ) 每个对象必须只属于一组。如果两个条件同时满足，一 般就称作硬划分( h a r dp a r t i t i o n i n gc l u s t e r i n g ；如果第2 个条件适当放宽，就 可以看作软划分( s o f tp a r t i t i o n i n gc l u s t e r i n g ) ，即一个对象就可以一定的概 率属于多个组。 层次方法对给定的数据对象集进行层次分解。一般来讲，有两大类，一类是 凝聚法，一类是分裂法。凝聚法自底向上地，开始时将每个对象视为单独的组，然 后逐次合并相近的对象或组，直到满足限制条件为止。分裂法刚好相反，它自顶 向下地，先将所有对象看作是一个组，然后，每一次把簇都分成更小的簇，直到满 足限制条件。 大部分的划分方法都是基于对象之间的距离进行聚类的，这些方法一般只能 发现球类的簇。不过，基于密度的方法就不同了，它可以发现任意开状的簇。其主 要思想是：只要“邻域”的密度( 数据点的数目) 超过某个阈值，则继续聚类。 基于网格的方法把对象空间量化为有限数目的单元，形成一个网格结构。然 后聚类操作就在这个网格结构，即量化的空间上进行。 基于模型的方法则是先为每一个簇假定一个模型，然后试图寻找数据对给定 模型的最佳拟合。 聚类方法众多，没有哪一种方法对于所有类型的数据集都全部适应的。通常， ：。 人们根据所感兴趣的应用作出假设，这种假设偏置不可避免地使得某一种聚类算 法在不符合假设的数据集上表现不如人意。这些方法中，有一种称为k m 聚类的 算法，是聚类算法中的经典算法，它是一种硬划分方法( 即每个对象必须只属于 某一组) ，原理简单，实现简便，所以声名远扬。本章的最后一部分将对这种方法 进行一个详细的介绍。 聚类分析有多年的研究历史，并且蓬勃发展，在这个信息高速膨胀的社会里 扮演着越来越重要的作用。研究的较多的主题是：聚类方法的可伸缩性、不同形 状的数据上聚类方法的有效性，高维数据的聚类等。 2 2高维数据聚类 在聚类算法的诸多研究方向中，有一个重要的研究方向是关于高维数据聚类 的。高维数据具有其自身的特点，在低维空间上表现良好的聚类算法，很可能因 第1 1 页 噪声鲁棒的自适应降维聚类 为没有充分考虑到高维数据集的特点，而在高维数据集上表现失常。高维数据在 许多应用领域中，如图像处理( i m a g ep r o c e s s i n g ) 、计算生物学( c o m p u t a t i o n a l b i o l o g y ) 等，经常遇到。例如，一幅3 0 3 0 象素的图片，用一个向量表示就是9 0 0 1 。 这相当于人们考虑理解一个事物时需要考虑的方面太多了，反而导致难以下结论， 被数据淹没。所以，有必要对高维数据设计专门的聚类算法来应对。 2 2 1高维数据聚类与降维技术 数据维度的增高，导致了所谓的“维度灾难”问题。“维度灾难”1 一词是 由b e l l m a n 第一次提出来的【1 1 0 最初是指不可能在一个多维网格上用穷举的办法 来优化一个多变量函数，因为网格的数量随变量数呈指数级增长。后来，“维度灾 难”用来泛指由于遇到变量( 属性) 过多而引起的问题。 比如，传统的聚类算法在高维空间上失效就可以看作是由于“维度灾难问 题引起的。这是因为，传统聚类算法把数据集中的点的所有维所存储的信息都考 虑在内，而很多维度跟聚类任务可能是无关的，这些维度上的信息将会把有意义 的簇隐藏起来。在维度特别高的空间上，对于大部分的数据分布和距离函数，每 两个点之间的距离( 即边长) 几乎是一样的 1 6 】，此时高维空间上的簇将会几乎完 全被隐藏起来。 通常，当人们遇到的问题涉及到太多方面的时候，人们往往倾向于根据正在 进行的活动，把问题化简，从而把握事物的本质、特征，以便更快速且准确地解决 问题。当聚类算法遇到高维度数据的时候，一般地也会根据“聚类”这个目的，某 种程度上排除到那些与聚类任务无关的，或者关系很小的维度，进而把握能够区 分数据集中的簇的那些本质特征。虽然，这样做很可能会丢失原有数据集中所蕴 藏的信息，但是，只要所丢失的这些信息与聚类任务无关的或者关系小到几乎可 以忽略的，我们就有理由认为这么做是合理的、成功的，因为它既尽可能地保留 了数据中的那些对我们的活动有用的信息，又排除了那些干扰的信息，提高了人 们思考的准确性和有效性。 降维技术是解决高维数据中出现的问题的一种重要手段，是一种学习过程。一 般有特征选择( f e a t u r es e l e t i o n ) 和特征抽取( f e a t u r ee x t r a c t i o n ) 之分。前者指的 1 关于“高维”一词的定义并没有统一标准，视问题本身有关，同时与维之间的相关程度也 有关系，不可一概而论。比如，在研究相似性搜索问题时，如果数据独立维超过1 0 维就属于高 维，而在图像处理中，几百维有时也可以看作是正常的。 第1 2 页 噪声鲁棒的自适应降维聚类 是从原有的维度( 特征) 中选出被认为与挖掘任务相关的维度( 特征) ，借此删除掉 那些不相关或冗余的维度。而后者有时也称为特征变换( f e a t u r et r a n s f o r m a t i o n ) ， 它不删除掉原有任何维度，而是用原有的维度的线性组合构造新的特征。如果限 制抽取的每一个特征的线性系数里有且仅有一个1 ，其余为0 ，则特征抽取就退化 成特征选择了。将选择或者抽取出来的特征组成一个属性空间，就称为特征子空 间。特征选择和特征抽取得到的特征子空间，分别对应于1 4 1 中的狭义子空间和 广义子空间。 特征选择或特征抽取可看作是维度压缩办法，采取适当的特征选择或抽取办 法，可以有效地描述数据集的本质特征，降低工作量，提高效率。 依据数据集中是否提供指导特征选择或特征抽取的数据，这两种降维技术基