（管理科学与工程专业论文）基于神经网络等技术的数据与文本聚分类研究.pdf

天津太学博_ 学位论文 中文摘要 聚类和分类技术是数据挖掘中最有价值的技术之一，而软计算中的神经网络 是聚分类中的主要技术之一。自适应谐振神经网络( a d a p t iv er e s o n a n c et h e o r y ： a r t ) 不仅参考人脑神经元互连的物理模型，而且也借鉴人脑的学习机理，具备数 据聚类的良好特性，目前国内外研究尚较处于发展阶段。文本挖掘中文本向量集 往往表示为订三交的高维空间，因而带来计算瓶颈和与实际应用背景不吻合的情 况，研究特性良好的降维算法、现有空间的改进等都存在很大的发展余地。 本沦文提出了四种基于a r t 2 神经网络的用于数据聚类的改进算法，克服了 经典a r t 2 神经网络输出无层次结构的缺点，均可形成动态的层次聚类结果，同 时降低了警戒参数主观设置的要求。 基于模、相位、空间密度的改进a r t 2 算法1 还克服了经典a r t 2 算法警戒参 数全局化、聚类与模无关的缺点，其通过按模和相位的综合评价，依据先前循环 形成类别中的输入向量个数分类别修正警戒参数以实现按空间密度局部化警戒 参数，在借鉴以前神经网络训练结果的基础上进行聚类； 基于凝聚和迭代思想的改进a r t 2 算法2 通过迭代在人，七交互下达到合理聚 类结果，并计算出合理聚类结果所需的警戒参数范围值；迭代以及迭代中神经网 络的输出都体现出有序的自组织特征，网络训练时间代价也在迭代中迅速下降； 基于l t e b b 规则和泄漏竞争的改进a r t 2 算法3 借鉴了h e b b 规则和泄漏竞争 的思想，允许多个神经元获胜并计算获胜神经元之间的相关性； 基于h e b b 规则和冗余神经元思想的改进a r t 2 算法4 克服了过分依赖获胜神 经元信息等不足，通过在竞争过程中同时考虑获胜神经元和其它神经元的信息以 及h e b b 规则来实现通过单个a r t 神经网络的层次聚类结果。 本论文提出了一种基于随机映射的文本降维算法，在可控、低代价地充分逼 近原始空间相似度计算结果和分类结果的情况下降低文本向量空间维数。在此基 础上本论文还提出了一种基于随机映射的加速隐含语义索引算法，此加速算法将 随机映射和隐含语义索引相结合，既可有效可控地降低空间维数，又可凸现语义 联系，使得其用于分类算法在文本高维环境中具备实时性和高分类准确率。 此外本论文提出了一种基于模式聚合和各维不同权重的改进k n n 文本分类 算法，在数据分析的基础上提出优化的模式聚合方法，并利用神经网络计算空间 各维不同权重以克服v s m 空间各维权重相等的缺点，可以在降低时问和空间复杂 度的基础上，提高k n n 算法的文本分类准确度。 关键词： 聚类，分类，自适应谐振神经网络，文本挖掘，k n n ，随机映射 天津大学博士学位论文 a b s t r a c t c l u s t e r i n ga n dc l a s s i f i c a t i o na r eo n eo ft h em o s tv a l u a b l et e c h n o l o g i e si nd a t a m i n i n g ，a n dt h en e u r a ln e t w o r ki ns o f tc a l c u l a t i o ni so n e o ft h em a i nt e c h n o l o g i e so f c l u s t e r i n ga n dc l a s s i f i c a t i o n a d a p t i v er e s o n a n c et h e o r y ( a r 、) n e u r a ln e t w o r kn o t o n l yr e f e r st ot h ep h y s i c a lc o n n e c t i o nm o d e lo fh u m a nb r a i nn e u r o n ，a n da l s ot ot h e s t u d y i n gm e c h a n i s mo f h u m a nb r a i n ，t h e r e f o r eh a st h eg o o df e a t u r eo fd a t ac l u s t e r i n g t h er e s e a r c h e so fa r ta r en o ws t i l li nt h eb e g i n n i n gp h a s e i nt e x tm i n i n g ，t e x tv e c t o r s e ti su s u a l l ye x p r e s s e da st h eh i g hd i m e n s i o n a lo r t h o g o n a ls p a c e ，t h e r e f o r e ，i tb r i n g s t h ec a l c u l a t i o nb o t t l e n e c ka n di n c o n s i s t e n c ew i t l lt h ef a c t u a la p p l i c a t i o nb a c k g r o u n d s o ，t h er e s e a r c h e so fg o o dd i m e n s i o nd e c r e a s i n ga l g o r i t h ma n dt h ei m p r o v e m e n to f c u r r e n ts p a c eh a v eal o to fd e v e l o p i n gs p a c e t h i sd i s s e r t a t i o np r e s e n t s4k i n d so fi m p r o v e da l g o r i t h m sb a s e do na r t 2n e u r a l n e t w o r kf o rd a t ac l u s t e r i n g ，a l lt h e s ei m p r o v e da l g o r i t h m so v e r c o m et h ec l a s s i c a l a r t 2 ss h o r t c o m i n gs u c ha so u t p u tw i t h o u th i e r a r c h i c a ln e t w o r ka n df o r mt h e d y n a m i ch i e r a r c h i c a lc l u s t e r i n gr e s u l t s ，a n dm e a n w h i l ed e c r e a s et h er e q u i r e m e n t so f v i g i l a n c ep a r a m e t e r s u b j e c t i v ec o n f i g u m t i o n t h ei m p r o v e da l g o r i t h m1o fa r t 2 ，w h i c hi sb a s e do nt h ei n t e g r a t i o no fm o d u l ， p h a s ea n ds p a c ed e n s i t y , a l s oo v e r c o m e st h ec l a s s i c a la r t 2 ss h o r t c o m i n g si n c l u d i n g v i g i l a n c ep a r a m e t e rg l o b a l i z a t i o na n dc l u s t e r i n gi n d e p e n d e n c ew i t hm o d e ，a n d c l u s t e r sb yt h ec o m p r e h e n s i v ec o l r t m e n t so fm o d u la n dp h r a s ea n dt o g e t h e rw i t ht h e r e f e r e n c et ot h ep r e v i o u st r a i n i n gr e s u l to ft h en e u r a ln e t w o r k i ta d j u s t st h ev i g i l a n c e p a r a m e t e ra c c o r d i n gt ot h en u m b e ro ft h ei n p u tv e c t o r so ft h ec l a s s e sg e n e r a t e di n p r e v i o u sc y c l et o r e a l i z et h ev i g i l a n c ep a r a m e t e rl o c a l i z a t i o nb a s e do nt h es p a c e d e n s i t y t h ei m p r o v g da r i t h m e t i c2o fa r t 2b a s e do nt h ea g g l o m e r a t i o na n di t e r a t i o n a c h i e v e st h er e a s o n a b l ec l u s t e r i n gr e s u l tb yt h em a n u a li n t e r a c t i o nt h r o u g hi t e r a t i v e m e t h o d s ，a n dc a l c u l a t e st h er e q u i r e dv i g i l a n c ep a r a m e t e r sr a n g en e c e s s a r yt ot h e r e a s o n a b l ec l u s t e r i n gr e s u l t ；a l lt h ei t e r a t i v ep r o c e s sa n dt h eo u t p u to fn e u r a ln e t w o r k i nt h ei t e r a t i o np r o c e s se x h i b i to r d e r l ys e l f - o r g a n i z a t i o nf e a t u r e ，a n dt h en e t w o r k t r a i n i n gt i m ea l s or a p i d l yd e c r e a s e si nt h ei t e r a t i v ep r o c e s s t h ei m p r o v e da l g o r i t h m3o fa r t 2b a s e do nh e b br u l ea n dt h el e a k e d c o m p e t i t i o na l l o w st h em u l t i - n e u r o n st ob et h ew i n n e r sa n dc a l c u l a t e st h ec o r r e l a t i o n a m o n g 山ew i n n i n gn e u r o n s t h ei m p r o v e da l g o r i t h m4o fa r t 2b a s e do nh e b br u l ea n dr e d u n d a n tn e u r o n o v e r c o m e st h es h o r t c o m i n g si n c l u d i n gr e l y i n go nw i n n i n gn e u r o nt o om u c ha n ds oo n , a n di ti m p l e m e n t sh i e r a r c h i c a lc l u s t e r i n gr e s u l tu s i n gs i n g l ea r tn e u r a ln e t w o r kb y t h em e t h o do fc o n s i d e r i n gb o t ht h ew i n n i n gn e u r o na n do t h e rn e u r o s i n f o r m a t i o na n d t o g e t h e rw i mh e b b r u l e t h i sd i s s e r t a t i o na l s op r e s e n t sat e x td i m e n s i o n r e d u c t i o na l g o r i t h mb a s e do n r a n d o mm a p p i n g ( r m ) ，u n d e rt h ec o n d i t i o n s o fc o n t m u a b l ea n dl o wc o s t ，a n d a p p r o x i m a t i n gs u f f i c i e n t l yt ot h ec a l c u l a t i o na n dc l a s s i f i c a t i o nr e s u l t so ft h eo r i g i n a l s p a c e ，i tc a ng r e a t l yd e c r e a s et h ed i m e n s i o no ft h et e x tv e c t o rs p a c eo nt h eb a s i so f t h i sa l g o r i t h mt h i sd i s s e r t a t i o np r e s e n t sa na c c e l e r a t e dl a t e ms e m a n t i ci n d e x ( l s l ) a l g o r i t h mt h a ti sb a s e do nt h ec o m b i n a t i o no fr ma l g o r i t h ma n dl a t e n ts e m a n t i ci n d e x t h ea c c e l e r a t e dl s ia l g o r i t h mc a ne f f i c i e n t l yr e d u c et h ed i m e n s i o no ft h es p a c ea n d a l s oe m p h a s i z et h es e m a n t i cr e l a t i o n s h i p ，t h e r e f o r ei tm a k e st h ec l a s s i f i c a t i o n a l g o r i t h m sh a v er e a l - t i m ea n db e r e rc l a s s i f i c a t i o na c c u r a c yi nh i g h d i m e n s i o nt e x t e n v i r o n m e n t i na d d i t i o n ，t h i sd i s s e r t a t i o n c a r r i e so u tai m p r o v e dk n nt e x tc l a s s i f i c a t i o n a l g o r i t h mb a s e do np a r e r na g g r e g a t i o na n dd i f f e r e n tw e i g h t so fe a c hd i m e n s i o n o n t h eb a s i so fd a t aa n a l y s i st h ei m p r o v e dp a t t e r na g g r e g a t i o nm e t h o di s p r e s e n t e d a n d t h en e u r a ln e t w o r ki su s e dt oc a l c u l a t et h ew e i g h to fe a c hd i m e n s i o no fv s m m o d e l s t oo v e r c o m es u c has h o r t c o m i n go fv s m s p a c ea sp o s s e s s i n gt h es a n l ew e i g h tb y e a c hd i m e n s i o n t h e r e f o r ei tc a l li n c r e a s et h et e x tc l a s s i f i c a t i o n p r e c i s i o no ft h e i m p r o v e dk n na l g o r i t h mo nt h eb a s i so fd e c r e a s i n go ft h ec o m p l e x i t yo ft i m ea n d s p a c e k e y w o r d s ：c l u s t e r i n g ，c l a s s i f i c a t i o n ，a d a p t i v er e s o n a n c et h e o r yn e u r a l n e t w o r k ，t e x tm i n i n g ，k n n ，r a n d o mm a p p i n g 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得苤盗盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：钽咄东 签字日期：2 0 0 5 年0 6 月1 日 学位论文版权使用授权书 本学位论文作者完全了解苤盗盘鲎有关保留、使用学位论文的规定。 特授权苤鎏盘茎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：铯瞻东 签字日期：2 0 0 5 年0 6 月f 日 翮签名：瓶 欧 签字日期：2 0 0 5 年0 6 月f 日 天津大学博十学位论文 第一章 绪论 第一章绪论 本章首先介绍选题的研究背景和意义：对数据挖掘的重要概念、过程、技 术进行阐述，然后重点介绍了数据挖掘中的聚分类技术，尤其是基于神经网络的 聚分类技术，并作出分析和评价；同时对文本的聚分类技术研究情况进行介绍； 最后介绍了本论文的主要工作和未来研究方向。 1 1 选题的研究背景和意义 数据挖掘起源于2 0 世纪9 0 年代中期，是一个年轻又活跃的研究领域，是多 门学科和多门技术相结合的产物。推动数据挖掘诞生、发展、应用的众多原因中， 对数据集背后潜在知识的迫切需求和人类分析提取信息的有限能力之间日益增 加的矛盾是其根本动因，另一方面是作为数据挖掘计算平台的计算机技术和水平 也达到了足够的高度以支持数据挖掘的运算要求；两方面结合在一起再加上数学 的进展促进了数据挖掘的不断研究与运用。 传统的数据库系统可以高效地实现数据的录入、检索、维护并保证其安全性 和完整性，虽然其后的基于数据仓库技术的o l a p ( 联机分析处理) 能够从任意 角度观察数据及其切片，但无论是数据库系统还是o l a p 都不能发现数据库中的 关联和规则，都不能够根据现有数据预测未来趋势，都不能够进行数据的分类或 者聚类，都不能够进行特征辨识。因而能够对隐藏在数据集背后知识的发现和利 用的数据挖掘成为新兴的研究方向，成为知识发现过程中的核心和关键步骤1 1 ，2 l 。 数据挖掘技术中聚类和分类技术是数据挖掘中最有应用价值的技术之一，其 应用领域遍及社会各个领域，几乎凡是有数据的地方就有对数据进行分类或者聚 类的需求。比如：根据金融和商业交易记录对客户的按照各种规则的分类、网络 文本的自动聚类、医院挂号处根据病人看病记录以及其它数据对病人应当去的科 室进行自动选择等等。随着数学和计算机技术的不断发展，数据量日益增大，对 于数据聚类和分类技术的研究就越发显得必要。 从认识论角度，知识是对事物运动状态及其变化规律的概括性描述；但基于 人工智能和信息系统，这个定义需要更精确的表达，知识源于人类的分类( 广义) 能力1 3 - 5 ，关于环境的知识从生存观点就是感觉信号的复杂分类，更抽象层次上 的分类则是推理、学习、决策的关键，是一种基础知识。因而数据挖掘中的数据 分类和聚类技术可以认为是数据挖掘中的基础和核心技术，实际上在很多数据挖 第1 页 天津大学博士学位论文第一章绪论 掘技术中聚类和分类被广泛使用，比如关联规则挖掘和时间序列挖掘等。从这个 角度考虑，在数据挖掘技术的研究中，聚类和分类技术的研究应当处在首要和优 先的地位上。 数据分类和聚类技术大体可以分为基于传统技术和基于软计算技术两大类， 而基于软计算的又主要以神经网络技术和粗糙集技术为主。基于传统技术的分类 技术主要包括支持向量机( s v m ) ”、k 近邻( k n n ) 。、决策树“”和贝叶斯分 类算法“”1 等；而传统聚类方法则主要包括基于凝聚思想的单链接聚类算法和全 链接聚类算法、基于分区聚类的k 一平均法、增量聚类算法等1 ”。神经网络的模 型中用于数据聚类和分类的主要神经网络模型包括：前向多层神经网络( b p 神 经网络) “2 、反馈型h o p f i e l d 神经网络“”、r b f 神经网络“7 1 9 , 2 0 k o h o n e n 的 自组织特征映射( $ o f m ) 神经网络“6 ”2 2 、学习矢量化( l v q ) 神经网络“6 ”。2 。2 、 波尔兹曼机( b m ) 神经网络”“”。2 “、自适应谐振( a r t ) 神经网络”等。 由于数据集体现出越来越多的无标签性、不确定性、不完整性、非均匀性和 动态性，传统的数据挖掘算法往往对此无能为力，而软计算的神经网络、粗糙集、 模糊逻辑和遗传算法，通过协同工作提供一种灵活的处理此类数据的能力【3 2 j ”。 其中模糊逻辑用于处理与不完整不精确的数据、模式理解、演绎等有关情况：神 经网络则用于高非线形决策边界建模、泛化和学习( 自适应) 、自组织和模式发现； 遗传算法则用于在动态环境下的优化和复杂目标对象的自适应；粗糙集则根据其 “核”属性获得对象的近似描述并提供以逻辑规则的形式快速抽取领域知识的算 法。因此软计算的应用已经成为数据挖掘领域的研究趋势，本论文韵主要研究就 集中在软计算中的神经网络及其混合技术在数据和文本聚分类中的应用。 具体到聚类与分类技术，传统的分类与聚类技术一般是在给定的样本集上进 行统计学习或者机器学习，其性能和效果往往深受此预先给定的样本集的影响， 比如k n n 方法其性能受聚类中心数量、初始聚类选择、输入空间几何分布特征等 许多因素的影响“；因而初始样本集是否能反应整体空间的情况直接影响传统聚 分类技术的性能和效果，而当样本空间分布发生变化时，此类算法就难以适应。 而神经网络由于自适应、泛化、任意函数逼近等特点，可以更好地适应样本空间 的动态变化。基于神经网络的聚分类方法中，自组织映射神经网络、学习向量化 神经网络、自适应谐振神经网络由于不仅在物理结构上借鉴了人脑神经元互连的 模型，而且在学习算法上也借鉴了人脑的工作机理或生物特性，因而能够更好地 模拟人脑进行数据的聚类和分类操作。尤其是其中的自适应谐振神经网络作为优 秀的聚类算法，目前国内外研究尚较处于发展阶段，其在数据挖掘中的优化和改 进还有很大的研究空间。 文本的挖掘“5 圳作为特殊的数据挖掘，既充分利用数据挖掘本身的原理和技 第2 页 大泮人学博士学位论文第一章绪论 术又有其自身的特点。软计算相比传统聚分类技术更加适合于文本环境，因为 软计算更适应于文本本身具备的主观性、不精确性、不确定性等特点，基于软计 算的文本的聚类与分类具有很好的研究前景。另一方面，文本向量集往往表示为 】卜交的高维空间，文本的样本集一般又规模较大，因而带来计算瓶颈问题和与实 际应用背景不相吻合的情况，而研究特性良好的降维算法、现有空间理论的改进 等课题还处- j 起始研究阶段，无论在理论还是实践环节都存在巨大的发展余地。 1 2 数据挖掘概述、聚类和分类概述 1 2 。1 数据挖掘 1 2 1 1 数据挖掘概述 数据挖掘是2 0 世纪9 0 年代中期兴起的一项新技术，是知识发现过程中的关 键和核心步骤，其起源于商业、科学、工程领域中对隐藏在数据集背后知识的发 现和利用的需求上。数据挖掘是一门交叉学科，涉及机器学习、模式识别、统计 学、数据库、知识获取、知识表达、专家系统、神经网络、模糊数学、遗传算法 等多个领域，内涵和研究热点非常广泛；所谓数据挖掘就是从数据集中抽取或发 现并应用隐含的、以前未知的、具有潜在或者现实应用价值的信息和知识的过程。 数据挖掘的基本任务或者功能如下：( 1 ) 分类，将被分类数据映射到一组事 先指定的类中；( 2 ) 聚类，根据对象属性实现未知空间分布缒样本集的划分，同 一组中数据的相似性最大，组间的差异性最大；( 3 ) 关联规则挖掘，发现数据变 量之间或者数据集或者其一部分之间的特征值之间的重要相关性；( 4 ) 预测与趋 势性规则挖掘，发现数据集中普遍演变行为的规则，包括各类回归方法、时间序 列挖掘等：( 5 ) 特征与辨识规则挖掘，发现数据集的所有数据满足的一般性特征 和用于不同数据集区分的辨识特征；( 6 ) 偏差检测，应用所得到的模式发现异常 或者最重要的变化。当然这里列出的只是数据挖掘任务中最主要的一部分，本论 文研究的侧重点则集中在数据和文本的聚类与分类上。 数据挖掘的活动大体可以分为两类1 1 3 3 5 】，第一类侧重于应用已发现的模式和 规律，生成已知数据集所描述的系统模型，主要用于预测、分析评价、偏差检测 等；第二类侧重于在可用数据集上寻找隐藏、潜在的、未知的模式的过程。第一 类数据挖掘的方法主要包括最近邻方法、基于案例的推理方法等；第二类数据挖 掘的方法1 3 5 1 则包括( 1 ) 基于逻辑的方法，既可以处理数值型数据，也可以处理非 数值型数据，包括基于规则方法、决策树方法等，( 2 ) 十字表方法，只能处理非 数值型数据，包括概念网等，( 3 ) 方程方法，只能处理数值型数据，包括统计技 第3 页 人滓人学博十。 干市论文 第一章 绪论 术、神经刚络等。实际上更多方法属于两类方法之间或者不同的细类方法之间。 聚类任务属于第一i 类方法，而分类任务则介于二者之间，本论文侧重于运用神经 刚络及其混合技术的数据与文本的聚类与分类研究。 第一类方法从认识论的角度上届于演绎的方法，第二类方法则属于归纳的方 法。由 二数据挖掘目的侧重于寻找潜在和未知的模式或者知识，因而大多数的数 掘挖拥算法都属于归纳方法的范畴，或者和归纳方法相联系。属于归纳的数扼挖 掘算法义可以划分为有监督( 教师) 的学习方法和无监督( 教师) 的学习方法。 何监督学习从已知输入输出的样本中进行学习，分类、函数逼近等是这种归 纳学习方法的典型应用。在有监督的学) j 过程中，假定存在具备环境知识和输入 输出样本集知识的老师的存在，但环境及其特性、模型参数等都是未知的。有监 督学习根据期望响应和学习系统实际响应的差值来调整学习系统的参数，学习算 法以误差来衡量系统功能，学习过程可以表示为误差曲面上点的移动过程i i 刈( 误 差曲面上点的移动定义为有监督的学习过程) ，有监督学习要求误差曲面e 的点 必须连续地向误差曲面上的局部或者全局最小点移动。支持这类学习的技术各不 相同，比如对数回归【3 6 】、感知机神经网络、决策树等。 无监督学习没有外部老师来监视学习过程，其样本只有输入值而没有预期的 输出值，其要求学习算法自己建立并估计模型，自发地去发现在数据集中的潜在 结构。这种学习质量的衡量是独立于任务的，学习算法中的自由参数就根据这个 衡量的结果进行优化；一旦系统变得和输入相谐振，学习算法就建立输入样本的 内在表述。支持这类学习的技术包括神经网络中的白适应谐振神经网络等。 1 2 1 2 数据挖掘中主要归纳技术 l 、统计方法：典型的技术包括贝叶斯推理、对数回归、a n o v a 分析 3 ”、对数 线形模型等； 2 、聚类分析：传统的聚类技术包括分裂聚类算法、凝聚聚类算法、划分聚类算 法和增量聚类算法等方法； 3 、决策树和决策规则：典型的技术包括c l s 方法、i d 3 算法、c 4 5 算法等及其 剪枝算法； 4 、关联规则方法：包括购物篮分析、演绎算法和w w w 路径遍历模式等； 5 、人工神经网络：反向传播学习的b p 神经网络和k o h o n e n 的自组织映射神经 网络、多层感知机等神经网络： 6 、遗传算法：基于生物进化原理设计了一系列的基因组合、交叉、变异、自然 选择等过程，进行问题优化； 7 、模糊方法：基于模糊集合、模糊逻辑、模糊决策等： 第4 贝 天津大学博士学位论文 第一章绪论 8 、粗集方法：作为研究不确定性的数学工具，属于集合论的扩展，主要用于研 究不完全和不完整信息描述，可以用于聚分类、特征约简和最小属性子集约 简等； 9 、可视化方法：采用直观的图形方式将数据模式、关联、趋势呈现出来，可以 通过可视化的交互技术分析数据l 口j 的关系，其包括几何学、基于图形、象素 导向和分层等技术。 本论文侧重点之一在于基于神经网络等混合技术进行数据聚分类研究，并在 多种神经网络模型中选择最适合聚类分析的自适应谐振( a d a p t i v er e s o n a n c e t h e o r y ：a r n 神经网络进行多项优化和改进。 1 2 2 数据聚类研究( 非基于软计算) 1 2 2 i 数据聚类中相似函数的研究 聚类分析属于无监督的学习方式，其输入可以定义为一个二元组( x ，s ) ，其中 x 表示输入样本集，而s 表示样本蚓相似度或者相异度的判定函数，聚类分析的 输出是一组类的集合，要求类内样本尽可能相似，而类问差异尽可能显著，聚类 分析的结果是这些类的特征或者描述。 向量相似性判定函数可以根据向量特征可比性以及是否满足距离三角不等 式加以区分： 同质的且满足距离三角不等式的常见相似性判定函数有【3 8 】： ，、i 2 n 维空间欧氏距离：d ( x ，x ，) = i 窆g 。一“) 21 ( 1 一1 ) n 维空间l l 距离： d ( x , , x j ) = 窆k - - x k ( 1 2 ) i = 】 n 维空间明考斯基距离：d g ，) = ( 砉g 。一x ，p 帅 c ，司 不满足距离三角不等式的向量相似性判定函数有 互近邻距离：哪，x ，) = n n ( x i , x j ) + ，b ，一) ( 1 - 4 ) 其中k ，o ) 是x j 点对x 。点距离接近的程度的序号，例如x i 是离x j 最近的 点- 么n n ( x ，o j 等于1 ，如果是第二近的点，贝t n n ( x , , x j ) 等于2 ； 当向量特征是非同质的。也就是不可比的情况下，简单地使用上述相似性判 第5 页 天津大学博士学位论文第章 鳍论 8 、粗集方法：作为研究不确定性的数学工具，属于集合论的扩展，主要用于研 究不完全和不完整信息描述。可以用丁聚分类、特征约简和最小属性子集约 简等： 9 、可视化方法：采用直观的图形方式将数据模式、关联、趋势呈现出来，可以 通过可视化的交互技术分析数据酬的关系，其包括几何学、基于图形、象素 导向和分层等技术。 本论文侧重点之一存于基于神经网络等混合技术进行数据聚分类研究，并在 多种神经嘲络模型中选择最适合聚类分析的自适应谐振( a d a p t i v er e s o n a n c e t h e o r y ：a r t l 神经网络进行多项优化和改进。 1 2 2 数据聚类研究( 非基于软计算) 1 2 2 1 数据聚类中相似函数的研究 聚类分析属于无监督的学习方式，其输入可以定义为一个二元组( x ，s ) t 其中 x 表示输入样本集，而s 表示样本恻相似度或者相异度的判定函数，聚类分析的 输出是一组类的集合，要求类内样本尽可能相似，l 阿类问差异尽可能显著，聚类 分析的结果是这些类的特征或者描述。 向量相似性判定函数可以根据向量特征可比性以及是否满足距离三角不等 式加以区分： 同质的且满足距离三角不等式的常见相似性判定函数有i j ”： n 维空间欧氏距离：d g ，一) = f 主g 。一b r1 ( 1 - 1 ) n 维空闻l i 距离：d b ，x ，) = 主卜。一l ( 1 2 ) t = 】 n 维空间明考斯基距离：d g 。x ，) = ( 砉b 。一b p ) ” c ，一s ， 不满足距离三角不等式的向量相似性判定函数有： 互近邻距离：m n d i x ，_ j = b ，x ，) + ，扛，一) ( 卜4 ) 其中m y x , ，) 是x ，点对x 点距离接近的程度的序号，例如| x i 是离x ，最近的 点，那么m v k ，- ) 等于i ，如果是第二近的点，i n n i x , ，_ ) 等于2 ； 当向量特征是非同质的 当向量特征是非同质的， 也就是不可比的情况下 也就是不可比的情况下 篇5 页 简单地使用上述相似性判 简单地使用上述相似性判 天津大学博士学位论文 第一章绪论 定函数是不合适的：而对不同的特征使用不同的相似性判定函数也是困难的，首 先不同判定函数之间的综合判定是很困难的，其次某些向量特征是质的而不是量 的，其运用于相似性判定函数的方式有待于进一步研究，最后即使是量的特征， 离散值或者区间值用于相似性判定函数的方式也需要进一步研究。对于离散的向 量特征“。”删，提出了简单匹配系数、j a c c a r d 系数、r a o 系数等相似性判定函数， 但其实际使用存在很多限制，只适用于离散值数量较少的情况，对于半离散半连 续的情况时，其更加难以应用。非同质、离散、半连续半离散、质的特征情况下 相似性判定函数的研究成为进一步研究的热点。 以上各个公式和讨论限于在两个向量之间，但在实际聚类过程中，也会涉及 两个类别之间相似程度( 距离) 的计算，这种类别之间相似程度( 距离) 的计算 无论在聚类过程中还是评价聚类质量时都是必不可少的。实际聚类中广泛应用的 类别c 之间相似程度( 距离) 的计算函数有： d 。( c j ，c ，) = m i n l p ，一p ，f 其中p ，c ，和p ，c j ( 1 5 ) p e ，c ) = j m 。一m ，i 其中m 。和m 是c 和c ，的质心( 卜6 ) 见。( c i ，c ) _ 剿 ( j _ 7 ) 月胛， 其中p ，c ，和p ，c ，且n ，和n 。是c 。和c 。的样本数 d 。虹，c ，) = m a ) 【b p ，|其中p ，e c , 和p j c j ( 卜8 ) 1 2 2 2 数据聚类算法 聚类算法基本都是基于下述基本思想：层次聚类方法、迭代的非层次的分区 聚类方法、基于密度的聚类方法i ”2 1 、基于网格 4 0 , 4 3 的聚类方法。每种思想都 有若干种常见的聚类算法，层次聚类思想有单链接和全链接聚类算法，而迭代的 非层次分区聚类方法则有k 平均算法。下面对应用最广泛的层次聚类方法和分 区聚类方法分别给予介绍： ( 1 ) 层次聚类方法 层次聚类方法按类别嵌套规则组织数据，以形成层次的聚类结构，一般结果 可以树状结构来表示，根据聚类的方向可以进一步划分为凝聚算法和分裂算法。 凝聚算法首先把每个对象或者小集合作为一个初始类，然后把这些类别合并 到若干个更粗糙的类别中，如此反复合并直到所有的对象都处在一个大类中，这 是一个由底向上的过程，逐渐由从精细到粗糙：而分裂算法正好相反，其首先把 第6 丽 大泮人学博十学位论文 第一章绪论 整个样本集作为一个初始类别，然后把其分解为若干个小类别，然后把每介小类 别继续依次分解下去，因而这是一个由顶向下的过程，体现出从粗糙到精细。本 论文在基于a r t 2 的改进算法中，分别借鉴了这两种思想，其中第二章第二节和 第三节、第三章第五节和第六节体现了分裂思想与a r t 2 的结台，而第二章第四 节和第五节、第三章第三节和第四节则体现了凝聚思想与a r t 2 的融合。 由于聚类往往是在缺乏样本总体分布知识的情况下进行的，因而凝聚算法往 往比分裂算法更多地应用于实际应用中。基于凝聚算法的层次聚类方法主要是单 链接算法、全链按算法和c h a m e l e o n 、b i r c h 、c u r e 等改进算法。 单链接算法、全链接算法基本步骤相同，其不同之处只在于单链接算法采用 的类j 日j 相似度计算函数采用的是公式( 1 - 5 ) ，而全链接算法采用的类间相似度计算 函数采用的是公式( 1 8 ) 。 c u r c ( c l u s t e r i n gu s i n gr e p f c s e i n i v e s ) 算法【4 4 5 0 】利用代表点进行聚类，能够识别 非球形或者大小变化较大的簇，对孤立点的处理也更健壮，对大型数据集具备不 降低聚类质量的良好伸缩性，其缺点是不处理分类属性。 c h a m e l e o n 算法 4 7 , 4 8 1 是一种通过在合并两类时用更高的标准来提高聚类质 量的聚类算法，如果两个合并后的类之间的互连性和近似度与合并前的单个类的 互连性和近似度相似，则合并这两个类。c h a m e l e o n 能够自动适应于类的内部特 征，在发现密度不定的任意形状的聚类方面是有益的。但其向量处理的时间复杂 度为o ( n 2 ) ，n 为样本集中样本个数，因而其计算时问代价过高。 b i r c h ( b a l a n c e di t e r a t i v er e d u c i n ga n dc l u s t e r i n gu s i n gh i e r a r c h i e s ) 1 4 5 , 4 6 , 4 9 算法 引入聚类特征和聚类特征树两个概念来实现综合的利用层次方法的聚类，其优点 是具备可伸缩性，第一次扫描产生一个基本的聚类，第二次扫描改进聚类质量和 处理孤立点，时间代价为o ( n ) ，1 i 为样本集中样本个数，因而速度较快，缺点是 不能很好处理非球状的簇。 ( 2 ) 迭代的非层次的分区聚类方法 迭代的非层次分区方法试图在一个水平上实现类内相似而类问差异的聚类 结果，因而是非层次的 为了获得最优解，往往必须迭代检验n 个样本被聚为k 个类别的所有可能的分区组合，根据排列组合的计算方法，这个迭代过程在实际 计算上往往是不可行，因而研究了若干种启发算法来简少需要迭代检测的分区组 合数量，但目前研究并不能保证一定得到最优解。 对于大型样本集，由于构造层次的聚类模型非常困难，因而分区的算法占有 应用优势。分区算法利用定义在局部或者全局的误差函数来优化生成聚类结果， 产生每个类别的原型或者特征向量，然后可依据相似性原则将各个样本分配到各 个类别中。最常用的分区算法的误差函数是基于方差的方法，其目标是对于预先 第7 页 天津大学博士学位论文 第一章绪论 指定的类数产生总体方差最小的分区结果。设类别数目为m ，m k 为第k 类特征 向量，c k 为第k 类中样本个数，x i k 是第k 类的第i 个样本向量，则基于欧氏距 离的分区聚类误差函数e 为：( 当然也可以用其它相似度函数来进行计算，这里 用最常见的欧氏距离来进行说明) e ：兰兰。扩m 。) 2 ( 1 - 9 ) 则分区算法的核心就是对于给定的类别数目m ，使得误差函数e 的均值达 到最小值； 从广义上说无论k o h o n e n 的自组织映射( s e l fo r g a n i z a i t o nf e a t u r em a p p i n g ： s o f m ) 神经网络还是自适应谐振( a r t ) 神经网络都是属于这种非层次的分区聚 类算法，本身不能产生层次的聚类结果，尤其是k o h o n e n 的自组织映射神经网 络更加和此分区模型相像。只不过上述两种神经网络的学习模式是借鉴人脑机理 的机器学习，而不是上述基于统计学的分区聚类算法模型。 分区聚类算法中最常见的是k 一平均算法，k 平均算法很容易实现，其时间复 杂度是o ( n k l ) ，其中n 是样本集中样本数量，k 是类别数，l 是算法收敛时的迭 代次数。一般k 和l 都是事先指定的，因此算法时间复杂度和样本集规模成难比。 其空间复杂度为0 ( k + n ) ，因而空间效率很高，而且具备不依赖输入样本顺序的 优良特性。其缺点是对初始分区的选择较敏感，如果初始分区选择不当，会造成 误差函数的局部收敛，另外对异常点和噪音比较敏感。 k 中心点对异常点和噪音敏感这一缺点做了改进，类别的特征向量不是用该 类别所有向量的平均，而是类别中最接近类别中心的k 个向量来进行计算，因而 对异常点和噪音不敏感。 p a m ( p a r t i t i o