（计算机应用技术专业论文）基于领域知识的半监督聚类算法研究.pdf

摘要 基于领域知识的半监督聚类算法研究 摘要 聚类分析是数据挖掘领域的基本方法之一，它根据数据对象之间的相 似性，把数据对象分割成簇。从机器学习的角度，聚类分析被看作是一种 无监督的学习方法，对数据的分析不需要知道数据相关的类别信息。然而， 在现实生活中，人们对所要分析数据的相关领域知识并非完全一无所知， 通过这种知识能够发现数据对象标识或相互之间的约束信息。半监督聚类 就是在聚类过程中引入先验知识来指导聚类过程，从而改进聚类结果。目 前，半监督聚类方法己成为人们研究聚类方法的新热点。 本文从约束的角度、属性的角度、规则的角度和实际应用的角度来研 究半监督聚类的实现方法及实际应用效果。本文的主要工作及创新点包 括： 1 、通过分析c o p k m e a n s 算法，指出了其中的不足，引入按约束集 分配的方法及辅助质心的概念，提出了改进的m l c k m e a n s 半监督聚类 算法，并通过实验证明了改进算法的有效性； 2 、针对属性和类标识及属性和约束的相互关系，一方面采取属性约 简方法，通过分析己知的标识数据对象，来消除冗余的属性，在新的属性 集上进行聚类；另一方面，通过对约束对象属性范围进行限制，找到新的 约束集合，来指导聚类过程。通过应用两种方法，达到了较好的聚类效果； 3 、利用关联规则方法，通过分析数据集中的部分标识数据，发现数 据属性子集和类标识之间的关联关系，并把此规则作为先验知识，引入到 北京化工大学硕士学位论文 聚类过程，来改进聚类效果。基于关联规则的半监督聚类方法有效地利用 了规则信息，展现了利用数据挖掘方法发现的先验知识和属性子集的关联 约束关系在半监督聚类中的应用； 4 、通过把半监督聚类的方法应用到w e b 用户的聚类分析之中，来检 验半监督聚类的实际应用效果。本文详细描述了从w e b 日志获取到聚类 分析的过程。 关键词：数据挖掘，领域知识，半监督聚类，m i c - k m e a n s 算法，属性 约简 摘要 a s t u d yo ns e m i - s u p e r v i s e dc l u s t e r i n ga l g o r i t h mb a s e do n d o m a i nk n o w l e d g e a b s t r a c t c l u s t e r i n ga n a l y s i s i so n eo ft h eb a si ct a s k si nd a t am i n h a gi nw h i c ht h e d a t a o b j e c t s a l e p a r t i t i o n e d i n t oc l u s t e r sb a s e do nc e r t i n t a i n s i m i l a r i t y c l u s t e r i n ga n a l y si sc a nb es e e na sa nt m s u p e r v i s e dl e a r n i n gp r o c e s s f r o mt h ep e r s p e c t i v eo fm a c h i n el e a r n i n g i ng e n e r a l , t h eu n s u p e r v i s e d l e a r n i n gd o e sn o tr e q u i r et h ecl a s sl a b e li n f o r m a t i o nb e f o r ea n a l y s i s h o w e v e r ， i nr e a lw o r l d ，p e o p l eh a v es o m ek n o w l e d g ea b o u tt h ed a t at ob ea n a l y z e d i n m o s tc a s e s ，t h eu s e f u li n f o r m a t i o ni s g e n e r a l l yi g n o r e d i nm o s tt r a d i t i o n a l s c e n a r i o s s e m i - s u p e r v i s e dc l u s t e r i n gi sp r o p o s e dt ou t i l i t i z et h ek n o w l e d g et o g u i d et h ec l u s t e r i n gp r o c e s sa n di m p r o v et h ec l u s t e r i n gr e s u l t i t h a sb e e n a s s u r e dt h a ts e m i - s u p e r v i s e dc l u s t e r i n gc a na c h i e v eb e t t e rc l u s t e r i n gr e s u l t r e c e n t l y , s e m i - s u p e r v i s e dc l u s t e r i n gh a sb e c o m eo n eo ft h eh o tr e s e a r c h t o p i c si nt h ea r e ao fc l u s t e r i n g t h i s p a p e rh a ss t u d y o ns e m i - s u p e r v i s e d a l g o r i t h mm e t h o da n d a p p l i c a t i o nr e s u l tf r o mt h ep e r s p e c t i v eo fc o n s t r a i n t s ：a t t r i b u t e s ，r u l e sa n d r e a l - w o r l d a p p l i c a t i o n t h i sp a p e r sm a i nc o n t r i b u t i o n sa n di n n o v a t i o n s i n c l u d e ： i l l 北京化工大学硕士学位论义 1 ) t h i sp a p e ra n a l y s e sc o p - w e a n sc l u s t e r i n ga l g o r i t h ma n dp o i n t so m i t sd i s a d v a n t a g e s ，i n d u c e st h ed i s p a t c h i n gm e t h o db a s e do nc o n s t r a i n ts e ta n d t h ec o n c e p to fa s s i s t a n tc e n t r o i d ，b r i n g sf o r w a r dt h ei m p r o v e dv e r si o nc a l l e d 匝c k l e a n sa n dc o n f n m si t se f f i c i e n c yw i t he x p e r i m e n t so no ns e v e r a lu c i d a t as e t s ； 2 ) t h i sp a p e rt r i e st od i s c o v e rt h er e l a t i o nn o to n l yb e t w e e na t t r i b u t ea n d c l a s sl a b e l , b u ta l s ob e t w e e na t t r i b u t ea n dc o n s t r a i n t s o no n eh a n d ，i ta d o p t s t h ea t t r i b u t er e d u c t i o nm e t h o d s ，d e c r e a s e st h ea t t r i b u t en u m b e rt h r o u g h a 1 1 a 舾i so fl a b e l e dd a t ao b j e c t sa n dp r o c e s sc l u s t e r i n go nn e wa t t r i b u t es e t o n t h eo t h e rh a n d ，i tf i n d sn e wc o n s t r a i n t sb yr e s t r i c t i n ga t t r i b u t es c o p eo fo l d c o n s t r a i n t s ，a n dt h e nu s e st h a tt od i r e c tc l u s t e r i n g b o t ho ft w om e t h o d s a c h i e v eg o o dr e s u l t ； 3 ) t h i sp a p e ra l s ou s e st h ea s s o c i a t er u l et od i s c o v e rr e l a t i o no fa t m b u t e s u b - s e ta n dc l a s sl a b e lb ya n a l y z i n gp a r t i a ll a b e l e dd a t ai nd a t as e t , a n dr i s e s t h er u l ea sp r e v i o u sd o m a i nk n o w l e d g e ，a d d si tt oc l u s t e r i n gp r o c e s st o i m p r o v ec l u s t e r i n gr e s u l t s e m i - s u p e r v i s e dc l u s t e r i n gm e t h o db a s e do n a s s o c i a t er u l e sm a k e sg o o du s eo fr u l ei n f o r m a t i o na n dd e m o n s t r a t e st h e a p p l i c a t i o ni ns e m i - s u p e r v i s e dc l u s t e r i n go f p r e v i o u sk n o w l e d g ed e r i v e df r o m d a t am i n i n gm e t h o da n dc o n s t r a i n tr e l a t i o na m o n ga t t r i b u t es u b s e t ； 4 ) l a s tb u tn o tl e a s t ，t h es e m i - s u p e r v i s e dc l u s t e r i n gt e c h n i q u ep r o p o s e d i nt h i sp a p e ri su s e di nr e a l - w o r l da p p l i c a t i o nb yu s i n gi tt ot h ec l u s t e ro fw e b u s e r s t h i sp a p e rg i v e sad e t a i ld e s c r i p t i o no ft h ep r o c e s sf r o md e r i v i n go f i v 摘要 w e bl o gt oc l u s t e r i n ga n a l y si s k e yw o r d s ：d a t am i n i n g ，s e m i - s u p e r v i s e dc l u s t e r i n g ，d o m a i nk n o w l e d g e ， m l c k _ m e a n s ，a t t r 南u t er e d u c t i o n v 符号说明 a 卜沁i a c m c c a n n o t - l i n k c m s c o n = c o n 壬 c n w d g p s i e e e i g g r k k d d 三 m m u s t - l i n k m n e w p c a u z 西 符号说明 人工神经网络 a s s o c i a t i o nf o rc o m p u t i n gm a c h i n e r y 国际计算机组织 同c a n r d t o l i n k 两个数据实例间的负相关关系，如果两个实例存在c a n n o t - l i n k 关系，则最终不能分配到相同的簇中 卡方检测 具有m u s t - l i n k 关系的实例对的集合 具有c a n n o t - l i n k 关系的实例对的集合 新产生的c 集合 d a t a 数据集合 g b b a l p o s i t i o n i n gs y s t e m 通用定位卫星系统 i n s t i t u t eo fe l e c t r i c a la n de l e c t r o n i c se n g i n e e r s 美国电气和 电子工程师协会 i n f o r m a t i o ng a i n 信息增益 g a i nr a t i o 增益率 k m w l e d g e 知识 k n o w n l e d g ed i s c o v e r yf r o md a t a b a s e 数据库知识发现； k n o w l e d g ed i s c o v e r ya n dd a t am i n i n gc o n f e r e n c e 知识发现与 数据挖掘会议 l a b e l e dd a t a 标识数据集 同m u s t - l i n k 两个数据实例间的正相关关系，如果两个实例存在m u s t - l i n k 关系，则最终不能分配到相同的簇中 新产生的m 集合 主成分分析 u n - l a b e l e dd a t a 未标识数据集 专家系统 空集合 x 1 1 1 北京化工大学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立 进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含 任何其他个人或集体己经发表或撰写过的作品成果。对本文的研究做出重 要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声 明的法律结果由本人承担。 作者签名：盔鱼絮- 一一 日期： 关于论文使用授权的说明 学位论文作者完全了解北京化工大学有关保留和使用学位论文的规 定，即：研究生在校攻读学位期间论文工作的知识产权单位属北京化工大 学。学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可 以允许采用影印、缩印或其它复制手段保存、汇编学位论文。 保密论文注释：本学位论文属于保密范围，姐年解密后适用本授 权书。非保密论文注释：本学位论文不属于保密范围，适用本授权书。 作者签名：垄。莓起日期：幽臣篁垒! 导师签名： 坌。酶莲 日期： 丝享二墨二! 一 第一章绪论 第一章绪论 数据挖掘( 又称知识发现) 是近年来人工智能领域研究中的一个热点课题。它指从 大量收集的数据中挖掘出未知的、非平凡的、有潜在决策价值的模式或知识的复杂过 程【l 捌。它是在现实生活中各种数据量呈指数级不断增长，以及以数据库技术为核心 的信息技术逐渐成熟的背景下产生的。聚类分析是数据挖掘的一个基本问题。其目的 是将数据集中的数据对象“自然地”划分为若干个组( g r o u p ) 或簇( cl u s t e r ) ，使得处 于同一组或簇内的数据对象尽可能地相似，而处于不同组或簇之间的数据对象尽可能 不相似。数据对象的相似性描述通常是基于距离来计算的。如在欧式空间中，常用的 距离计算方式有欧氏距离、曼哈顿距离和闵可夫斯基距离等。距离值越大，相似程度 就越小，数据对象就越不可能处于同一组或簇，反之亦然。根据聚类分析过程中算法 思想的不同，大致可以将聚类分析分为五类，即划分聚类、层次聚类、密度聚类、网 格聚类和模型聚类方法。这些方法都有各自的优势和适用领域。在商业、气象、军事、 生物等众多领域中，聚类分析具有极为广泛的应用。 从机器学习的角度来看，聚类分析是一个无监督的学习过程。然而在现实应用中， 人们对待聚类数据集的相关领域知识并非一无所知。如何利用领域中先验知识或己知 约束来改进聚类质量是半监督聚类分析的重要研究内容。具体来说，一方面，半监督 聚类研究如何更好地利用和挖掘领域知识，以获得更多对数据挖掘任务有益的信息； 另一方面，半监督聚类研究如何把获得的领域知识引入聚类，改进原有聚类算法。如 通过一些常识性知识可以判断两个数据对象是否属于同一聚类中，以此作为约束条 件，对聚类过程和聚类结果加以限制，就可以提高整个聚类结果的可理解性。 1 1 课题研究的背景和意义 在数据挖掘任务中，实际数据往往由大量无标识数据和少量标识数据组成。由于 标记数据的获取需要花费昂贵的代价，而且我们可以通过某种手段获得数据相关的领 域知识，通过这种领域知识能够达到对数据更好的识别效果。本文所指的领域知识不 但包括部分标识的数据对象，还包括利用专家系统、数据挖掘等方法得出的相关数据 的知识。半监督学习是处理此类数据的一种学习方法，近年来受到众多研究者的关注。 目前，研究者们已提出多种半监督学习方法。一般来说，半监督的学习问题可分为两 个方面：半监督的分类问题和半监督的聚类问题。前者是在有监督分类的基础上，通 过无标识数据指导分类过程，以提高分类的准确性；后者则是在无监督聚类的基础上， 通过标识数据指导聚类过程，以提高聚类质量。 传统的聚类过程是一种无监督的学习过程。它主要存在以下不足： 首先，它只考虑到数据本身的一些特性，忽略了先验知识的作用。这样导致了一 北京化工大学硕士学位论文 些聚类的盲目性，所得的分类结果并不能真正满足用户需要。其次，传统的聚类方法 都有一定的适用范围。如果想达到好的聚类效果，对性质不同的数据就要尝试不同的 聚类方法。特别是当数据分布复杂的时候，处理起来就非常的费时费力，而且只有在 聚类结果出来后才能对聚类效果进行评价。 通过加入相关的领域知识，就会使得聚类过程带有一定的方向性和目的性，不但 能够对聚类过程有所指导，同时还充分考虑到人的主观因素。首先，如果在聚类过程 中加入约束信息，就可以避免错误的聚类倾向，从而使聚类过程向好的方向收敛。另 外，主观因素对聚类结果的重要性逐渐为人们所认识。对于不同的应用，其相应的聚 类结果应该不同。“如对金枪鱼、鲸和大象进行聚类，根据它们的相似性，鲸和大象 也许会因为都是哺乳动物而分入一类，可是若用户的兴趣是基于是否生活在水中 这一特征，则鲸和金枪鱼应分入一类 。如何把用户的倾向结合入聚类过程成为一个 具有挑战性的问题【3 1 。 一般来说，半监督聚类主要包括几下几个方面的优点： ( 1 ) 有效利用领域特殊知识； ( 2 ) 提高聚类效果； ( 3 ) 标示特殊形状的聚类： ( 4 ) 用户可以指导聚类过程，更好地反映用户需求。 可见，半监督聚类能够充分利用已知的知识，提高传统聚类的适应能力和聚类效 果，是对聚类从研究方式上的重要改进。这种改进更符合现实情况，具有非常重大的 意义。自从2 0 0 0 年w a 擎t a f f 提出利用两种约束关系来研究半监督聚类以来【4 1 ，国内外 在此方面的研究已蓬勃开展起来。 虽然对半监督聚类的研究已经取得了部分的成果，但在领域知识的利用、聚类算 法的改进、统一模型的构建及实际应用方面都存在许多问题和分歧。目前，国内对半 监督聚类的研究也处于刚刚发展阶段，对相关知识的积累比较薄弱。本文从此出发， 较为详细论述了数据挖掘及半监督学习的方法，研究了如何利用领域知识进行半监督 聚类分析，以及用实际例子展示了半监督聚类的应用方法及效果。本文的研究对于从 事半监督聚类算法的研究分析，综合利用、挖掘领域知识及互联网用户行为分析等方 面有积极的指导意义。 1 2 国内外研究现状 1 2 1 半监督聚类算法分类及目前主要方法 1 2 1 1 半监督聚类算法分类 在聚类分析时，人们通过已有的领域知识，很容易做出以下判断：某两个数据对 2 第一章绪论 象应该分入同一个簇，或某两个数据对象不应分入同一个簇。为描述数据对象间的这 类关系，w a g s t a f t 在2 0 0 0 年引入了m u s t - l i n k ( 正关联) 和c a n n o t - l i n k ( 负关联) 两种约束 来描述这种背景知识【4 1 。他提出的基于软关联的s c o p - k m e a n s 算法被成功用于分析火 星遥感数据。由于数据对象间的关联约束在实际问题中经常会遇到，如何有效地利用 它们引起了极大的关注。 其它直接利用的领域知识的形式是部分标识的数据。所谓标识即为数据对象最终 的类别。对于聚类任务来说，标识反映了数据最终正确的簇划分。 目前，半监督的聚类方法大致分为以下三类： ( 1 ) 基于标识数据和约束的方法。该类算法在聚类过程中，利用用户给出的标识 数据或约束条件来引导聚类过程，目的是得到优化的聚类结果。主要的方法包括：利 用部分标识的数据初始化聚类参数并通过标识数据的空间分布在聚类过程中约束数 据的划分【5 】；修改聚类的目标函数，使聚类结果满足给定的限制条件【6 】；加入约束的 作用，使得聚类过程在一定条件下进行【7 】等。 ( 2 ) 基于距离函数学习的方法。该类聚类算法的目标是对满足特定条件的距离函 数进行聚类。该距离函数是通过对标识数据和未标识数据学习所得到的数据对象距离 测度。其主要的方法有：利用标识数据基于凸的优化方法而得到的马氏距离【8 1 ；利用 标识数据基于图的最短路方法而得到的欧氏距离【9 】；基于特征向量空间映射及矩阵因 数分解【l o 】等： ( 3 ) 集成上述两种思想的半监督聚类方法。b i l e n k o 等人通过把距离约束转化为距 离度量，改进k m e a n s 算法，将上述两种思想集成于一个框架之下【l l 】。s u g a t o 等人提 出了一种统一的半监督聚类概率模型，利用改进后的隐式空间数据间的距离反映约束 关系【1 2 1 。 1 2 1 2 主要半监督聚类算法概述 对于如何结合并利用领域知识来改进聚类算法，学者们已经进行了比较深入的研 究。下面是目前半监督聚类的主要算法： ( 1 ) c o p - k m e a n s 。c o p k m e a n s 是对k m e a m 算法的改进，利用给定的约束信息， 通过强制性地将一些数据对象归入( 或不归入) 同一组，来提高聚类准确率。同时，一 些数据对象分类的改变会影响聚类中心的位置，进而影响其它数据对象的分类，以提 升整体的准确率嘿 ( 2 ) c c l 。c c l 是对c o m p l e t e l i n k 层次聚类算法的改进。算法先算出数据对象之 间的距离后，再依据约束信息来调整距离矩阵。具体方法是：先将正关联的数据对象 之间距离置0 。接下来，对于数据对驰、b 、c ，若d i s ( a ，动十d i s 似，c ) d i s ( b , c ) ，则 甑 o 的值为d i s 似，计d i s0 ，o ，d i s 函数为两个数据对象间的距离。通过对距 离矩阵的修改，可扩大正关联的影响，把约束从实例级扩展到空间级。最后将负关联 的数据对象间的距离设为无穷大。距离矩阵经调整后，在其后的聚类过程可基本满足 北京化工大学硕士学位论文 关联约束。通过把约束扩展到对空间内数据对象的引导，来达到优化聚类的目的【1 0 】。 ( 3 ) s e e d e d k m e a n s 。约束播种半监督聚类算法，是b a s u 币l c o l l a b o r a t o r s 等2 0 0 2 年提 出的利用部分标识数据来初始化簇质心的k 均值聚类算法的改进算法。核心思想是利 用离散的标记点计算聚类质心的近似值。这种思想能被扩展到计算m u s t - l i n k 点的闭包， 然后用每个闭包的平均值来播种聚类质心【5 1 。 ( 4 ) 从约束学习距离函数然后聚类，是x i n g 在2 0 0 3 年提出的。算法利用用户给出 的相似约束信息，在r n 维空间学习距离度量标准来反映这种约束关系，聚类算法被转 化到球形优化问题，从而避免局部最优【8 】8 。 ( 5 ) s u g a t ob a s u 等人提出了一个主动半监督聚类算法。算法设计了一个代价函数 用来配置隐马尔柯夫随机域( h i d d e n m a r k o v r a n d o m f i e l d ，h m r f ) 的能量。聚类过程 即等价于寻找能量最小的隐马尔柯夫随机域配置。算法为了充分利用有限的先验约束 知识，采取了主动选择策略，挑选含有信息最多的约束来改进聚类质量，不仅减少了 对先验知识的依赖性，而且使得算法与数据集规模呈线性关系，因此具有较好的可扩 展性【1 3 1 。 ( 6 ) 何振峰、熊范纶定义了数据对象和集合间的两类关联，以及集合间的三类关 联。并在此基础上给出了结合限制的分隔模型，提出了c k s 算法( c o m t r a i n e d k m e a m w i t hs u b s e t s ) 。在u c i 的部分数据集上，c k s 在准确率及健壮性上优于c o p k m e a n s 算法，c k s 算法在时间效率上也有一定优势【1 4 】。 ( 7 ) l a bd a v i d s o n 等引入了两类新的约束：即约束和6 约束。约束强调属 于同一聚类中的任意两个数据对象的距离至多为，而6 约束限制分属于不同聚类 的任意两个数据对象的距离至少6 。通过约束和6 约束可以利用背景知识指导 搜索过程来发现期望的聚类。实际上，在很多情况下寻找一个满足所有约束的聚类解 决方案往往是一个n p 完全问题【1 5 】。 ( 8 ) 高滢等提出了一种处理多关系数据的改进的k 均值半聚类算法。该算法在k 均 值聚类算法的基础上扩展了其初始类簇的选择方法和对象相似性度量方法，以用于多 关系数据的半监督学习。为了获高性能，该算法在聚类过程中充分利用了标记数据， 对象属性及各种关系信息【1 6 】。 其它一些半监督聚类算法有：s s r d 1 7 1 ，s c r e e n 墙】，引入遗传算法来研究半监督聚 类【6 1 ，或是把半监督聚类应用于图像处理【19 1 ，或是研究用户反馈【2 0 】等，这些方法都取 得不错的效果。 1 2 2 半监督聚类的实际应用 半监督聚类方法作为传统聚类方法的改进，很好地融入了相关领域的知识，提高 了聚类的效果。它在不同的领域中有着更加广泛的应用。 4 第一章绪论 w a 擎t a l j f 已经成功地把半监督聚类方法应用f f ：g p s 车道发现( 1 a n ef i n d i n g ) 。l a n e 看作是行车密集区域。与此相对，l a n e 边界是行车相对较少区域。对汽车的位置进行 聚类分析，就是发现l a n e 区域。通过对行车密集区域的发现和参考当前行车位置，对 司机提供个性化的行车线路服务。聚类过程中采用两类启发式先验知识：踪迹连续 ( t r a c ec o n t i g u i t y ) 和最大划分( m a xs e p a r a t i o n ) 。l a n et r a c e 表示同一路段上的点应该划 分到同一l a 。m a x s e p a m t i o n 表示不把两个点划分到相同簇的距离。通过实验比较， 证明利用领域知识的半监督聚类的方法具有很高的聚类精度，改进后的方法提高了传 统聚类方法的聚类效果【7 1 。 王晓峰、姜建国用半监督聚类方法建立入侵检测模型，用来分析计算机网络或系 统中的审计数据，从中发现网络或系统中是否存在攻击或异常行为。根据部分标识的 数据，结合进化策略，提出进化半监督模糊聚类算法( e s s f c ) 。在该算法中，用少量 的标识数据提供的类标识信息，来引导未知标识数据模糊划分的发展方向。未知标识 数据担任染色体的角色，每条染色体的适应度用未标识数据的模糊聚类差异和标识数 据的错分误差联合评估。基于e s s f c 建立入侵检测系统，对k d d c u p 9 9 2 i 】入侵数据进 行实验仿真，取得了较好的分类效果【2 2 1 。 李嵬、王新伟等把半监督聚类应用到集装箱港口出口箱量短期预测。基于隐式马 尔可夫模型，提出了基于度的半监督聚类算法( s c u d ) 。s c u d 利用约束先计算每个数 据点的度，然后根据约束度来初始化聚类中心，最后利用e m 算法进行聚类。对集装箱 港口出口量预测，采取两步骤：运用s c u d 先进行数据分组，然后再建立a r m a 模型 进行预测。该方法运用下一港口、船最大载重、到达和离开时间、所处月份以及关联 约束等背景知识来有效地提高预测精度。使得集装箱码头能保证集装箱快速地进场、 堆放和装船，有效缩短了船舶靠港时间，保证码头运行的安全稳定性，实现码头市场 运营费用最小瞄】。 半监督聚类的其它应用研究包括：半监督的彩色图像分害4 1 2 4 j ，基于半监督聚类的 三维肢体分n t 2 5 1 ，w e b 流量半监督聚类【2 6 】等。 1 3 本文的主要工作及组织结构 利用领域知识和改进聚类算法是半监督聚类的关注点。如何能更好地结合两者， 以达到优化的聚类结果，成为人们研究的焦点。本文围绕领域知识的获取及表达形式、 聚类算法的改进方法以及半监督聚类的实际应用展开研究、分析和讨论。 本文主要完成的工作包括： ( 1 ) 本文首先介绍了半监督聚类研究的最新动态，接下来综合阐述了数据挖掘和 聚类分析的主要方法及领域知识的获取、表达形式。 ( 2 ) 从三个不同角度来分析、研究领域知识在半监督聚类算法中的应用情况。体 5 北京化工大学硕士学位论文 现在：a ) 利用约束的方法完成了对c o p k m e a n s 算法的改进及对基于约束实例属性 扩展半监督聚类的分析：b ) 利用部分标识的数据来完成属性的约简及实现半监督的 聚类；c ) 把利用关联规则的方法获得的规则信息加入到聚类算法中，实现对聚类过 程的指导。几种方法都通过详尽的试验来验证新算法的可行性。 ( 3 ) 在半监督聚类算法实际应用的研究方面，本文对w e b 用户进行半监督条件下 的聚类分析。对w e b 数据从获取、预处理、转换及最终的聚类及半监督聚类方法做了 详尽的描述，综合比较了几种半监督聚类算法的实际效果。 本文的组织结构如下： 第一章介绍了论文研究的背景和意义，国内外研究现状，本文的主要工作及组 织结构。 第二章综合阐述了数据挖掘和聚类分析技术的定义和主要方法。其次介绍了半 监督学习及领域知识的概念、来源及表示形式。 第三章分析了c o p k l e a l l $ 半监督聚类算法，然后对改进的m l c k m e a n s 算法 进行详细论述和实验证明。 第四章从属性的角度，分别利用属性约简方法和基于约束的属性范围扩展方法， 研究领域知识指导下的半监督聚类方法。 第五章论述了利用关联规则方法从领域知识中获得规则信息及把这种信息应用 于聚类算法的方法及实验效果。 第六章论述了w e b 挖掘的基本知识及利用半监督聚类的方法对凤凰网注册用户 进行聚类分析的步骤及效果。 第七章对全文的工作进行总结，并给出今后进一步的研究方向 6 第二章数据挖掘及聚类分沂技术 第二章数据挖掘及聚类分析技术 数据挖掘作为新兴的技术，经过二十来年的发展，已经吸引了众多研究者的目光。 世界各地的学者们为数据挖掘算法的研究和应用做出了积极的探索，取得了令人瞩目 的成就。本章详细论述了数据挖掘的定义、历史、发展和主要方法，聚类分析的定义 及主要方法以及基于领域知识半监督聚类的基础知识，包括半监督学习的方法和领域 知识来源、表示等。 2 1 数据挖掘技术简介 2 1 1 数据挖掘的定义、历史和发展 随着计算机技术的发展，各个行业积累了大量的数据。数据库技术的成熟为数据 挖掘提供了条件。数据挖掘，是之指从大量的、不完全的、有噪声的、模糊的、随机 的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息 和知识的过程。数据挖掘技术使得人们能够从历史数据中获得决策支持，为数据的有 效利用提供了方法。 数据挖掘是一个萃取和展现新知识的过程，具体过程如图2 - 1 所示。数据挖掘是 一门交叉性学科，主要用到的技术涉及了机器学习、模式识别、统计学、智能数据库、 知识获取、数据可视化、高性能计算、专家系统等多个领域。数据挖掘是从不同的角 度，利用不同的方法，来发现有趣的模式和信息，并把此转化为决策者可理解的模式 展现出来。 数据源 信 息 图2 - 1 数据挖掘基本过程 f i g 2 - 1b a s i cp r o c e $ $ o fd a t am h n m g 数据挖掘技术出现于2 0 世纪8 0 年代后期，9 0 年代有了突飞猛进得发展，是当今 计算机技术最活跃的研究领域之一。数据挖掘最初就是从数据库中发现知识。k d d 一词首次出现于1 9 8 9 年8 月在美国底特律召开的第l l 届国际人工智能联合会议的专 题讨论会上。随后在1 9 9 1 年、1 9 9 3 年和1 9 9 4 年都举行过k d d 和d m 专题讨论会，汇 集来自各个领域的研究人员和应用开发者，集中讨论数据统计、海量数据分析算法、 知识表示及运用等问题。国际k d d 组委会于1 9 9 5 年把专题讨论会提升为国际会议， 7 北京化工大学硕士学位论文 在加拿大蒙特利尔召开的第一届知识发现( k d d ) 和数据挖掘( d a t am i n i n g ) 国际学术 会议。随着参与人员的不断增多，k d d 的研究已经扩展到人工智能、机器学习等众 多领域，从研究的深度和广度都有极大的扩展。在实际生活中，数据挖掘的研究和应 用都取得了卓有成效的成果。 在学术研究方面，数据库、人工智能、信息处理和知识工程等领域的国际学术刊 物也纷纷开辟了k d d 专题或专刊，包括 i e e e 知识与数据工程汇刊， a c m 数 据库系统汇刊，数据与知识工程等。在网络上也有不少k d d 电子出版物，如 k n o w l e d g ed i s c o v e l t n u g g e t ( 1 帅：w w w k d n u g g e t s c o m s u b s c d o e h t n a ) 。在网上还有很 多自由论坛，如d me m a i lc l u b ，中文的数据挖掘研究院( h t t p d w w w d n n e s e a r c k n e 0 。 其它和计算机技术、决策支持相关的国际会议和学术期刊也把数据挖掘和知识发现列 为专题和专刊讨论，如并行计算、计算机网络和运筹与优化等领域的学术会议和期刊。 国内方面，1 9 9 8 年复旦大学联合m m 举办了一次数据挖掘和数据仓库讲习班，对中 国数据挖掘的研究起到了极大的推动作用。 目前，国外数据挖掘的发展趋势及研究方向主要有：对知识发现方法的研究和进 一步发展：k d d 与数据库的紧密结合；智能技术应用于数据挖掘方面的研究。应用 方面主要表现在：数据挖掘商业软件工具不断产生和完善，注重建立解决问题的整体 系统，而不是孤立的过程。用户主要集中在大型银行、保险公司、电信公司和销售业 等产生大量数据和有巨大利润空间的行业。 国外很多计算机公司非常重视数据挖掘的开发应用，许多著名的计算机公司开始 尝试数据挖掘软件的开发。比较优秀的如s a s 公司的e n t e r p r s em i n e r , i b m 公司的 i n t e l l i g e n tm i n e r , s p s s 公司的c l e m e n t i n e s g i 公司和美国斯坦福大学联合开发的 m i n e s e t ，以及由韩家玮教授的研发组开发的d b m i n e r ，由h o s c h k a 和k l o s g e n 开发 的e x p l o r a ，其他还有d a r w i n ，q u e s t ，w c k a ，a c 2 ，k d w 等等，这些软件都有自己 的特长，可以应用于不同的领域。 数据挖掘技术短短十几年时间的发展，已经取得了令人瞩目的成就。国内外许多 学者进行了辛勤的努力和探索，对数据挖掘技术从产生到应用做出了巨大的贡献。随 着科学技术的进一步发展，对智能技术的需求进一步增加，数据挖掘的领域将会更加 深入，更加贴近人们的实际生活。数据挖掘将为人类社会进步做出更大贡献。 2 1 2 数据挖掘的主要方法 数据挖掘融合了人工智能、数理统计及机器学习等多学科的理论、方法和技术， 这些学科中的多种技术和方法都可以应用到数据挖掘中。下面是数据挖掘的一些主要 技术和方法。 ( 1 ) 决策树方法 第二章数据挖掘及聚类分析技术 在分类方法中，决策树是一种常用的、直观的快速分类方法。决策树也称为判定 树，是模式识别中进行分类的一种有效方法。它通过分而治之的方法，把一个复杂的 分类别分类问题转化成若干个简单的分类问题来解决。决策树在形式上是一棵树结 构，由中间结点、叶结点和分支构成。决策树是数据挖掘中用于分类和预测的主要方 法之一。 决策树的构造通常分两个步骤：利用训练集生成决策树；再对决策树进行剪枝。 决策树的生成是一个从根节点开始、自上而下的递归过程，一般采取分而治之的方法， 通过不断地将训练集分割成子集来构造决策树。决策树的剪枝是对树结构进行修剪， 删除多余分支的过程。剪枝的目的是为了防止过拟合。构建决策树的算法很多，其中 最具代表性的有i d 3 2 7 1 、c 4 5 t 2 8 算法。 决策树方法在许多应用领域被广泛地应用，主要优点有： a ) 决策树的构造不需要其它的领域知识，学习过程中需要的参数也较少，对训 练集没有任何要求，能处理离散型和连续型的数据，分类的准确度较高。 b ) 决策树的构造过程是可监控的，进行分类时所需的计算量不大。 c ) 决策树的输出包含属性的排序，决策树能够清楚地指出哪一个属性对决策是 最重要的。每个叶结点对应一条分类规则，清晰的层次结构易于理解。 决策树方法也存在着一定的不足。如：训练一棵决策树的耗费很大，对具有连续 值的属性预测比较困难，在类过多的情况下分类容易出错等。 ( 2 ) 人工神经网络 人工神经网络( a n n ) 是模拟人脑神经元的数学模型为基础建立的，是由大量的简 单神经元按一定规则连接构成的网络系统。从信息处理的角度来看，神经元可以看作 是一个多输入单输出的信息处理单元。网络能够模拟人类大脑的结构和功能，采用适 当的学习算法从训练样本中学习，并将获取的知识存储在网络各单元之间的连接权值 中。人工神经网络具有自学习、自组织、自适应等方面的能力。 神将网络有三个要素：拓扑结构、连接方法和学习规则。神经网络的单元通常按 层次排列。依据层次数，神经网络被分成单层、两层和多层结构。一般情况下，问题 越复杂，所需的层次数越多。神经网络的连接包含层次内部连接和层次间连接，依据 连接形式，可以分成前馈式网络、反馈式网络、全相连神经网络和部分相连神经网络。 从学习方法看，神经网络分成感知器和认知器；从学习规则来说，分为相关学习网络、 纠错学习网络和自组织学习网络。 神经网络具有非线性学习和联想记忆的优点。目前已经出现了多种网络模型和学 习算法，主要用于分类、优化、模式识别、预测和控制等领域。神经网络对于从复杂 和不确定数据导出概念和确定走向也有比较突出的优势。缺点在于训练过程时间长， 输出结果较难解释。 ( 3 ) 基于遗传算法的方法 9 北京化工大学硕士学位论文 遗传算法( g a ) 1 2 9 】是由美国科学家j h h o l l a n d 于2 0 世纪6 0 年代提出的一种模拟 生物自然选择和遗传机制的随机搜索算法。算法具有隐含的并行性、非线性求解及易 于和其它模型结合等特点。遗传算法是一种全局优化算法，适合具有很大搜索空间的 优化问题。 遗传算法包括选择、交叉和变异三个基本算子： a ) 选择：从上一迭代过程产生的旧种群中选择个体，作为新种群； b ) 交叉：交换两个个体的部分基因，形成新个体； c ) 变异：用来改变个体的某些基因。 在应用遗传算法进行数据挖掘时，需要把数据挖掘任务表达为一种搜索的问题， 以便发挥遗传算法的搜索能力。它是基于群体的、具有随机和定向搜索特征的迭代过 程。 ( 4 ) 粗糙集的方法 粗糙集是一种处理模糊和不确定知识的数学方法，由波兰科学家z p a w l a k 于1 9 8 2 年提出【川。粗糙集主要用于分类和特征描述。作为一种软计算方法，粗糙集可以不需 任何辅助信息，仅依据数据本身提供的信息就能对数据进行化简并求得知识的最小表 达。粗糙集方法可以克服传统的不确定信息的处理方法的不足，并且能和它们有机结 合，进一步增强对不确定