（应用数学专业论文）相似性度量的研究及其在数据挖掘中的应用.pdf

中文摘要 中文摘要 相似性度量是人工智能的基础问题之一，它涉及数据挖掘、机器学习、自然语 言处理和信息检索等多个领域。传统的许多分类，聚类，特征选择算法的性能在很 大程度上依赖于一个好的相似性度量。一些常见的相似性度量方法如m i n k o w s k i 距离，e u c l i d e a n 距离，m a h a l a n o b i s 距离，m a n h a t t a n 距离和c o s i n ea n g l e 距离1 1 】等已被 广泛使用，这些相似性度量方法往往存在这样或那样的缺陷，如为了计算的统一性 需要转换不同类型的属性，从而可能改变数据的原意或是丢失一些信息。但是实际 应用中的许多数据集往往包含多种类型的数据，因此，设计一种好的相似性度量显 得至关重要。 本文将相似性度量的概念加以推广和扩充。从数据空间覆盖关系的角度提出一 种新的相似性度量方法，并在此基础上设计和实现了相应的两种算法：( 1 ) 基于数 据空间部分覆盖的分类算法( p c c ) ( 2 ) 基于动态部分覆盖的特征选择算法( d p c ) 。 在u c i 机器学习公共数据集和来自于实际应用中的化工产品的毒性预测数据集上的 实验结果说明这两种新算法的有效性和与传统的的数据挖掘算法的可比性；我们也 结合邻近集计算的相似性度量思想提出了一种基于时间权重邻近集计算的算法，在 基于历史数据经济数据分析领域中的股票市场预测上取得了良好的效果；采用有序 树匹配的思想，提出了基于页面结构相似性度量的w e b 页面聚类方法，并应用于 w e b 信息抽取中。 实验结果体现了这些新的相似性度量方法是对现有的相似性度方法的有效补 充，具有广泛的应用基础。 关键词：空间覆盖，相似性度量，分类算法，特征选择算法，时间序列，信息抽取 中文文摘 中文文摘 相似性度量涉及到人工智能的各个领域，如何选取一个适当的相似性度量方法 影响到许多分类、聚类、特征选择算法的性能。相似度是两类模式之间的相似程度， 它有多种的定义方式。在数据挖掘研究中，常用距离和相关系数来衡量对象之间的 相似度。 现在广泛应用的各种相似性度量方式都有其优点也有其缺陷，在时间效率、鲁 棒性和精确性方面各存在不同程度的问题，这制约了其在各种算法中的使用范围。 对于大多数经典的距离度量公式而言，有的只能处理数值型属性或只能处理离散类 型的属性，而能够处理多种属性的公式也往往需要进行相应的类型转换或者归一化 处理，这就可能改变数据的原意或是丢失一些信息。 因此，在本文中我们提出一种基于空间覆盖的相似性度量方法，它能够灵活处 理各种不同的数据类型，具有更好的通用性。并将其应用于分类、特征选择和时间 序列分析的领域，取得了良好效果。 论文的主要研究成果以及文章组织如下： 第一章对相似性度量的理论基础进行了系统的研究，对现有的各种相似性度量 方法进行了较全面的评述，分析了传统数值型数据之间的距离度量、离散型变量之 间的距离度量、混合型变量间的距离度量和一些新的距离度量方式，并对其优缺点 进行了分析。 第二章提出一种了在多维空间下基于部分覆盖关系的元组相似性度量方法，并 用它创造了p c c 分类算法。我们采用几个u c i 上的公共数据集对该方法进行了测 试。实验结果表明，p c c 的分类性能可以与经典的分类方法相媲美。之后将p c c 算法应用于毒性物质预测的研究也取得良好效果。 第三章将空间覆盖的思想引入特征选择领域，提出d p c 特征选择算法。这种方 法不需要搜索全部的特征子集空间，并且它不需要对搜索方法采用评估函数和设置 停止标准。做为种懒惰类型的特征过滤算法，实验结果显示d p c 的效率与经典的 特征选择算法具有可比性，在某些数据集上可以达到最好效果。 第四章结合类似空间覆盖理念的邻近集计算思想，提出一种新的基于时间权重 的相似性度量方法- t w n c m ( t i m ew 色i g l l t e dn c m ) 。我们通过计算多维时间序列中 i i i 中文文摘 的时间和空间关联来定义其邻近关系，并采用邻近集计算来衡量时间序列的相似性。 同时采用经济数据预测的方法来对其进行评估，在使用的股票价格数据集上进行了 测试，取得良好效果。 第五章采用有序树匹配的相似性度量，提出了一种基于页面结构聚类的w e b 信 息抽取方法。该方法能有效地根据页面结构对页面进行相似性度量，从而实现w e b 页面结构的聚类，进而提取出相同结构w e b 页面中的不同信息。该方法实现了页面 中的有用数据从半结构化向结构化的转化。 最后在第六章对本文的主要工作进行总结并提出了今后的展望。这些新的相似 性度量方法扩展了许多传统的不同领域的算法，实验表明它们与其它相似性度量方 法相比具有其特有的优势和价值。 i v a b s t r a c t a b s t r a c t s i m i l a r i t ym e t h o di so n eo ft h ep r o b l e mt h a tu n d e r l i e sm a n ya r t i f i c i a li n t e l l i g e n c e t a s k s ，i n c l u d i n gd a t am i n i n g ，m a c h i n el e a r n i n g ，n a t u r a ll a n g u a g eu n d e r s t a n d i n g ，a n d i n f o r m a t i o nr e t r i e v a l al o to ft r a d i t i o n a la l g o r i t h m so fc l a s s i f i c a t i o n m ，c l u s t e r i n ga n d f e a t u r es e l e c t i o na r eb a s e do nas u i t a b l es i m i l a r i t ym e a s u r e an u m b e ro fs i m i l a r i t y m e a s u r e s h a v e b e e np r o p o s e da n da r ew i d e l yu s e ds u c ha sm i n k o w s k id i s t a n c e ， e u c l i d e a nd i s t a n c e ，m a h a l a n o b i sd i s t a n c e ，m a n h a t t a nd i s t a n c ea n dc o s i n ea n g l e d i s t a n c e t h e s es i m i l a r i t ym e a s u r e sw h i c hn e e dt oc o n v e r t t r a n s f o r md i f f e r e n tt y p e so f d a t at oau n i f o r mf o r m a tm a y b r i n gs o m ed i s t o r t i o n so rc a u s ei n f o r m a t i o nl o s e ，b u tt h e c o m p l e xr e a l - w o r l da p p l i c a t i o n sm a yc o n t a i nd i f f e r e n tt y p e so fd a t a s oag o o ds u i t a b l e s i m i l a r i t ym e t h o di sn e e d e d w ee x t e n dt h ec o n c e p to fs i m i l a r i t y an o v e ls i m i l a r i t ym e t h o db a s e do ns p a t i a l c o v e r a g er e l a t i o n s h i p i sp r o p o s e di n t h i s p a p e rt o g e t h e rw i t ht w on e wd e v e l o p e d a l g o r i t h m s o n ei sc a l l e dp c c - p a r t i a lc o v e r a g eb a s e da p p r o a c ht oc l a s s i f i c a t i o na n d t h ea n o t h e ri sc a l l e dd p c - d y n a m i cp a r t i a lc o v e r a g eb a s e df e a t u r es e l e c t i o nm e t h o d ( d p c ) e x p e r i m e n t sw e r ec a r r i e do u to ns o m ep u b l i cd a t a s e t s f r o mu c im a c h i n e l e a r n i n gr e p o s i t o r ya n ds o m et o x i c i t yd a t as e t sf r o mp r e d i c t i v et o x i c o l o g yd o m a i n t h e e x p e r i m e n t a lr e s u l t ss h o wt h a tt h ed e s i g n e da n dd e v e l o p e dt w oa l g o r i t h m sc o m p a r e w e l l w i t hs o m ec l a s s i c a lm e t h o d si nd a t am i n i n g w ea l s op r o p o s ean e wm e t h o df o rt i m e s e r i e sf o r e c a s t i n gw h i c hi sc a l l e dt w n c m 伍m ew e i g h t e dn e i g h b o r h o o dc o u n t i n g m e t h o d ) ，a n du s ei ti nt h es t o c kp r i c ef o r e c a s t i n gb a s e do nh i s t o r i c a ld a t ai nt h ec o n t e x t o ff i n a n c i a lt i m es e r i e sf o r e c a s ta n da n a l y s i s a n dw ed e v e l o pan e w w e bi n f o r m a t i o n e x t r a c t i o nm e t h o db a s e do np a g es t r u c t u r ec l u s t e rw i t ht h eo r d e r e dt r e ec o m p a r ei d e a t h ee x p e r i m e n t a lr e s u l t ss h o wt h ea d v a n t a g eo ft h ep r o p o s e ds i m i l a r i t ym e t h o d s t h e ya r et h es u p p l e m e n t st ot h es y s t e m so fs i m i l a r i t ym e a s u r e sa n d r e s t so n ab r o a db a s e k e y w o r d s ：s p a t i a lc o v e r a g e ；s i m i l a r i t ym e t h o d ；c l a s s i f i c a t i o n ；f e a t h e rs e l e c t i o n ；t i m e s e r i e s ；i n f o r m a t i o ne x t r a c t i o n i l 福建师范大学硕士学位论文独创性和使用授权声明 福建师范大学硕士学位论文独创性和使用授权声明 本人( 姓名) 黄杰学号2 q q 鱼q 鱼璺5 专业座用数堂所呈 交的学位论文( 论文题目：相似性度量的研究及其在数据挖掘中的应用) 是本人在导师指导下，独立进行的研究工作及取得的研究成果。尽我所 知，除论文中已特别标明引用和致谢的内容外，本论文不包含任何其他 个人或集体已经发表或撰写过的研究成果。对本论文的研究工作做出贡 献的个人或集体，均已在论文中作了明确说明并表示谢意，由此产生的 一切法律结果均由本人承担。 本人完全了解福建师范大学有关保留、使用学位论文的规定，即： 福建师范大学有权保留学位论文( 含纸质版和电子版) ，并允许论文被 查阅和借阅；本人授权福建师范大学可以将本学位论文的全部或部分内 容采用影印、缩印或扫描等复制手段保存和汇编本学位论文，并按国家 有关规定，向有关部门或机构( 如国家图书馆、中国科学技术信息研究 所等) 送交学位论文( 含纸质版和电子版) 。 ( 保密的学位论文在解密后亦遵守本声明) 文作：铡 签钿期：1 年钿弓日 指导教师签名糯缇 辩醐：千幻厂日 第一章绪论 1 1 立题依据 第一章绪论 随着现代互联网信息技术的迅猛发展，人们面临着爆炸式增长的各种类型的数 据，例如图片、文本、音频、视频等等。所谓数据挖掘，就是帮助人们从这些海量 的数据中发掘出隐含的、有价值的信息和可理解的模式，从而帮助用户分析出其间 所蕴涵的有价值的知识。 数据挖掘的任务可以大致分为以下几类：数据分类或预测、数据总结、数据聚 类、关联规则发现、序列模式发现、依赖关系或依赖模型发现、异常和趋势发现等 等【2 】。而相似性度量是其中大多数算法的基础，针对具体问题，选择适当的相似性 度量是保证其挖掘结果质量的重要问题。 相似度是两类模式之间的相似程度，相似度有各种各样的定义方式，数据挖掘 研究中，常用距离和相关系数来衡量对象之间的相似度。现有的许多距离函数和相 似性度量方法以及被广泛应用来处理不同类型的数据。如e u c l i d e a n 距离可以处理数 值型数据，h a m m i n g 距离可以处理离散型数据，编辑距离可以用以处理序列，最大 子图度量可以用来处理图形数据等。 大多数数据挖掘的算法都需要一种与其相适应的相似性度量方法，而普通的相 似性度量方法在处理不同属性的数据时可能会存在诸多问题。已经存在的一些相似 性度量的方法有m i n k o w s l 【i 距离、e u c l i d e a n 距离、m a h a l a n o b i s 距离、m a n h a t t a n 距 离和c o s i n ea n g l e 距离【1 l 等，这些相似性度量的方法需要将不同的数据类型进行相 应的转换，进行归化后才能进行距离的度量，而这种转换工作可能导致一些信息 的丢失。而有些相似性度量方式在低维空间中表现优异，但是在高维空间中效率低 下。而且复杂的现实世界中的应用含有各种新类型的数据或者已存在数据的结合类 型。这就需要新的距离相似性度量函数来处理相应问题。而且现在越来越多人开始 关注源自自然语言文档采集的域知识模型，采用这种模型去推论词汇和文档之间的 语义相似性，并将其用于基于概念的信息检索1 3 1 。而这些工作的重点就是设计一种 适合的相似性度量。 福建师范大学黄或硕士学位论文 1 2 论文的主要内容与组织安排 本文的主要内容和特色是提出了一种基于空间覆盖关系的相似性度量方法，结 合分类、特征选择的相关内容，提出了两个新的算法：p c c 分类算法、d p c 特征选 择算法，并将其应用于毒性物质预测分析等领域。同时结合邻近集的思想，提出了 一个时间序列相似度的方法( t w n c m ) ，将其与经济数据预测分析相结合用于股票 市场预测，取得较好效果。采用有序树匹配的相似性度量，提出了一种w e b 页面 的聚类和信息抽取算法。 本文从基础理论、算法设计与实现、实际应用三个层面进行研究。共分为6 章， 结构如下： 第一章引言 1 立题依据、研究内容 2 相似性度量的基本概念 第二章基于空间覆盖的分类算法 1 新的相似性度量思想 2 提出新的分类算法p c c 3p c c 在毒性数据预测上的应用 第三章基于空间覆盖的特征选择算法 1 新的特征选择算法d p c 2 d p c 的比较分析 一一一一母一一一一一一 第四章邻近集相似性理论及其发展应用 1 引入邻近集计算的基本思想 2 提出新的算法t w n c m 3 将其应用于经济数据预测领域 = = 延；= = ：一一 第五章基于页面结构相似性度量的w e b 页面聚类 及其在信息抽取中的应用 1 有序树的匹配模型和相似性度量 2 页面结构的模糊聚类 3 w e b 页面的规约与抽取 2 第一章绪论 第一章提出本课题的立体依据和主要内容，对相似性度量的基本概念和发展现 状进行了探讨。 第二章提出了基于空间覆盖的相似性度量方法，并将其与分类思想相结合，提 出了新的分类算法，并将其应用于有毒性物质预测领域。 第三章将新的相似性度量方法与特征选择，提出了新的特征选择算法， 第四章结合邻近集计算的思想，提出一个新的时间序列预测算法，并将其应用 于经济数据的预测分析中。 第五章采用页面结构相似性概念，提出了一个w e b 页面的聚类和信息抽取的 算法。 第六章对本文的主要工作进行总结和对今后工作的展望。 1 3 相似性度量方法概述 1 3 1 相似度的定义 相似度是两类模式之间的相似程度，它有多种的定义方式。在数据挖掘研究中， 常用距离和相关系数来衡量对象之间的相似度，距离和相关系数统称为归类指数。 在度量特征空间中，向量五和x ，之间的距离定义d ( x ；，x ，) 多种多样，有许多距离 已经被广泛采用，例如曼哈顿( m a n h a t t a n ) 距离、欧氏( e u c l i d e a n ) 距离、马氏 ( m a h a l a n o b i s ) 距离等。d ( 五，x ，) 越大则表明两个对象相差越远，a ( x j ，x ，) 越小 则两个对象越近。 1 3 2 基本数据类型 我们讨论距离函数前，我们需要先讨论一下不同的数据属性类型。不同的数据 类型在计算中可用于描述不同类型的对象信息，这使得我们能够使得不同对象参与 相应的数学计算。 通常我们把数据类型分为以下几类： ( 1 ) n o m i n a l 类型 这种类型的变量用以描述特定领域内的一些名称或者类标签，它们只能参与“相 福建师范大学黄或硕士学位论文 同”或者“不相同”的运算 ( 2 ) o r d i n a l 类型 此类变量的值可用于表述具有顺序类型的数据，除了可用于“相同”或者“不相 同，的运算外，还可参与比较大小和先后的运算。 ( 3 ) i n t e r v a l 类型 此类变量含有所有o r d i n a l 类型的特性，可以描述一定的区间集合，可用于加 法和减法的运算。 ( 4 ) r a t i o 类型 此类变量含有所有i n t e r v a l 类型的特性，而且可使用乘法和除法运算。 n o m i n a l 类型的属性有时候被称为c a t e g o r i c a l ( 独立型或离散型) 属性，而r a t i o 型属性有时候在文献中被简化成n u m e r i c a l ( 数值型) 属性。在模式识别和机器学习 等领域，最常使用的就是n o m i n a l ，o r d i n a l 和r a t i o 类型的数据。在本文中，我们主 要考虑c a t e g o r i c a l 和n u m e r i c a l 两种类型的属性。前者的操作包括“相同”或者“不相 同”，而后者可以参与比较大小和加减乘除的运算。 1 3 3 常见的距离度量方式 已经有许多的距离度量方式被广泛应用，我们根据数据类型的不同将其做个简 要的划分。设置和x j 是数据集中的两个数据对象，则常见的距离度量公式可以归 纳如下： ( 一) 数值型数据之间的距离 ( 1 ) 曼哈顿( m a n h a t t a n ) 距离 曼哈顿距离公式为d ( 置，x ，) = 毫k - - x j k ，其中，置= “。，鼍：，) r ， x j o z 弦，z 扣) r 为万维曼哈顿空间r “中的两个对象。曼哈顿距离在有些文献中 也称绝对( 值) 距离。 ( 2 ) 明考夫斯基( m i n k o w s k i ) 距离 明考夫斯基距离公式为d ( x ；，x ，) = ( 砉i 一靠1 9 ) ；，其中，x ；= x i ：，) r ， 第一章绪论 x j = ( x j 。，x ：，b ) r 为甩维空间r “中的两个对象。 ( 3 ) 欧氏( e u c l i d e a n ) 距离 欧氏距离是较为常见的距离公式，可描述为d ( 五，x j ) ；砉k 一啄1 2 ，其中， 五一“。，五2 ，) r ，x j o ，。，菇，2 ，工加) r 为刀维欧式空间彤中的两个对象。 ( 4 ) 马氏( m a h a l 卸o b i s ) 距离 马氏距离公式为d ( 五，x ，) 2 一一x ，) r j ，- 1 ( 墨- x ，) ， 其中， 置一“。，t ：，黾) r ，x ，一o ，z ，2 ，z 加) r 为以维空间r “中的两个对象。 y 。丢一a l , a 2 , - , a m ) r ( 口- ，口z ，口。) 为对象五和x j 之间的协方差阵，为可逆矩阵， 口，。瓴一心，一以) r ，以。言荟，f _ 1 ，2 ，肌。 ( 5 ) 兰氏( l a n c ew i l l i a m s ) 距离 兰氏距离公式枷沪蠢鼎，其中五吨，耵r ， z ，。t ，_ ：，) r 为甩维空间掣中的两个对象。 ( 6 ) 切比雪夫( c h e b y s h e v ) 距离 切比雪夫距离公式为d ( 五，x f ) 。m a 】【k z 弦l ，其中，五= “。，而：，) r ， 1 n x ，一o 。，x ，2 ，靠) r 为，l 维空间r “中的两个对象。 ( 7 ) 相关系数 相关系数是指置和x 之间的关联程度，相关程度越大相似度越大。反之，相 关程度越小则相似度越小。其公式可以描述如下： ，；吾警鲁磐粤， 荟( 一而) 2 荟 业一x ，) 2 其中，x ；。瓴。，t ：，) r ，x = o ，。，工，：，) r 为，l 维欧式空间r “中的两 福建师范大学黄或硕十学位论文 ( 二) 离散型变量的距离 设对象五、x ，为离散型变量，x i = “，2 ，) ，x ；似j 。，x 2 ，) ，变 量的状态有 口l ，a 2 , - - - , a ) ，即，x 肚一a z , ze a 1 ，口2 ，k 1 ，2 ，l 】- 。若x i 和 x s 间不同状态的个数为m ，则它们之间的距离可描述为d ( 置，x ，) = i m 。而二进制 变量之间的距离也可以看作是一种特殊的离散型变量的距离，设对象置、z ；为二 进制变量，x i = “1 ，t 2 ，) ，x ，一o j l ，z ，2 ，) ，x i k ，x j k = 0 或1 ，k 1 ，2 ，以】。 若两个对象间不同状态的个数为优，则它们之间的距离可描述为d ( 置，x ，) 。竺。 ( 三) 混合型变量间的距离 设对象鼍、x ，为混合型变量为，置一“。，五：，) ，x 一o j 。，z j ：，) ， 则它们之间的距离公式可以描述为d c 置，z ，；羔量妻斧。其中，、有一 个为缺省值或一= o 时，峨一0 ，否则 v x i x ，= 1 。d 譬t 为置、x ，中第七个 变量对距离函数d ( 置，x ) 的影响情况。若k 为类别型数据变量，当一时 d 譬羔，一0 ，否贝i 一面( i t z ) j 一1 ；当七为数值型变量时， 噶，一d 甚 其中，m a x 。毛。为k 变量的最大取值，m i n 。为k 变量的最小取值， 1 3 4 距离度量方式的发展 在基本距离度量方式的基础上，人们根据需求的不同提出了一些新的距离度量 方式。 ( 1 ) h e o m 度量 混合欧几里德重叠度量( h e t e r o g e n e o u se u c l i d e a n o v e r l a pm e t r i c ) h e o m 4 噪用 第一章绪论 重叠覆盖或者h a m m i n g 距离来处理数值型和离散型数据，并且可以为e u c l i d e a n 距 离的数据进行归一化操作。它的公式可以描述如下： 其中当x 和y 未知时，属性a 中x 和y 之间的距离d a ( x ，y ) = 1 ；当属性a 是非数 值型时，d 。( x ，y ) = o v e r l a p ( x ，y ) ；当属性a 是数值型时，d a ( x ，y ) = d i f f a ( x ，y ) 。 其中，当x = y 时，o v e r l a p ( x ，y ) = 0 ； d i f f a ( x ，y ) 昌盂i x - i y l ， r a n g e , = m a x 口一m i n 4 ( 2 ) 值差度量( v d m ) 值差度量( v d m v a l u e d i f f e r e n c em e t r i c ) 【5 】也是一种有效的距离度量函数，并 且被广泛使用。经典的v d m ( 未使用权重) 中属性a 之间的距离可被定义如下： 砌俐= 荟ci 等一 = 艺f 7 阪c 一i 口 其中n 。，x 是训练集t 中实例x 的a 属性的数目，n 。，x ，c 是训练集中c 类的实例 x 的a 属性的数目；c 是类标签的数日，q 是一个定值，通常为1 或者2 ；p a , x ，c 是 一个条件概率，表示c 类中a 属性为x 的可能性。 采用以上的距离函数，x 和y 之间的距离可以被定义为： 一些改进的算法【6 ，7 ，8 】已经开始采用增加各种权重来得到更好的效果，而m v d m 算法【6 7 l 没有用到传统v d m 算法中属性的权重，而是采用了一种基于实例历史表现 情况的权重，可以达到更好效果。 ( 3 ) 混合值差度量( h v d m ) 由于e u c l i d e a n 距离不适合绝对属性，而v d m 不适合连续的属性，所以诞生了 一种混合两种方式的度量方法h v d m ( h e t e r o g e n e o u sv a l u ed i f f e r e n c em e t r i c ) 1 4 1 o 它 能够结构两种距离函数来处理不同类型的数据，它被定义如下： 福建师范大学黄或硕士学位论文 函数d 。( x ，y ) 给出x 与y 的a 属性之间的距离，其中当x 和y 未知时候，属性a 中x 和y 之间的距离d 。x ，y ) = 1 ；当属性a 是非数值型时，d 。x ，y ) = v d m 。x ，y ) ；当属性 a 是数值型时，d 。( x ，y ) = d i f f ( x ，y ) 。 ( 4 ) 插值值差度量( i v d m ) 7 插值值差度量( i v d m i n t e r p o l a t e dv a l u ed i f f e r e n c em e t r i c ) 【4 j 扩展了v d m 算 法的试用，使其可以处理连续型的数据。w d m 使用离散化的方法处理相应的数据， 使其可以参与v d m 的运算。连续型的数据将被离散为s 个等长的区间，属性a 上 的值x 将被离散化。i v d m 的计算复杂度和v d m 相当，它仅能被使用在分类算法 上。其公式为： 其中，当属性a 为绝对属性时i v d m 。( x ，y ) = v d m 。( x ，y ) ，否则 i v d m a ( x ，y ) = 三。陋，c ) 一，c ( y ) 1 2 ( 5 ) 最低的风险度量( m r m ) b i a n z i e r i 和r i c c i 9 】提出了最低风险度量( m r m m i n i m a lr i s km e t r i c ) ，它是 一种基于概率的距离度量方式，可视为一种降低误分类概率的函数。在类c i 中给定 一个数据点x 和一个近邻y ，x 被误分类的概率为p ( c ；i x ) ( 1 - p ( c ；l y ) ) ，则在全部类别中 两个数据点x 和y 之间的m r m 距离可被定义为： c m r m ( x ，y ) = ，x ，y ) = 善p ( c i i x ) ( 1 一p ( c i l y ) ) m r m 的关键就是p ( c ；i x ) 概率的计算，它可以采用任何可行的概率计算方式， 例如n a i v eb a y e s 和g a u s s i a nk e r n e l ，所以它的扩展性很大，但是也仅能使用在分类 算法中。 第一章绪论 1 3 5 小结 在数据挖掘中已经有许多的相似性度量方式得到广泛的应用。对于大多数经典 的距离度量公式而言，有的只能处理数值型属性或只能处理离散类型的属性，而能 够处理两种属性的公式也往往需要进行相应的类型转换或者归一化处理，这就可能 改变数据的原意或是丢失一些信息。 在一些改进的度量公式中，h e m o 简单易行，而h v d m 、i v d m 、和d v d m 的公式则具有实现的复杂性。实验【4 】表明，相对于h e o m 、h v d m 和d v d m 这三 种度量方式，i v d m 可以达到较高的精度，但是它鲁棒性不是很好。而m r m 的计 算复杂度则比较高【9 】，在使用n a i v eb a y e s 概率计算时它几乎要比h e o m 和d v d m 多花1 0 倍的时间。就应用领域而言，e u c l i d e a n 距离、h a m m i n g 距离和h e o m 能 够独立使用，而d v d m 、h v d m 、i v d m 和m r m 只能使用在分类算法中。 总而言之，每种度量方式都有其优点也有其缺陷，在时间效率、鲁棒性和精确 性方面各存在不同程度的问题，这制约了其在各种算法中的使用范围。我们将在下 文中提出一些新的相似性度量方法，并将其应用于分类、特征选择、时间序列预测 和w e b 页面聚类中。 第二章基于空间覆盖的相似性度量及其对应的分类算法 第二章基于空间覆盖的相似性度量及其对应的分类算 法 在本章中，我们提出空间覆盖相似性度量的基本思路，它采用数据对象之间的 空间覆盖关系作为一种相似性度量，不需要对不同的属性进行转换和归一化处理。 我们并将其应用于分类中，提出一种新的分类算法p c c ( p a r t i a lc o v e r a g eb a s e d c l a s s i f i c a i t o nm e t h o d ) ，并通过公共数据集和毒性物质数据集进行了测试。实验结果 表明，p c c 算法的分类精度可以与传统分类方法相媲美。 2 1 分类算法概述 数据挖掘中的分类就是分析用户输入的数据，然后根据已经掌握的每类若干样 本的数据信息总结出其中的规律性，为每一个类找到一种相对准确的描述或者模型， 然后以此预测新数据的所属的类别。近年来，各种文献中已经提出了大量的分类算 法，我们根据其采用的机制和应用领域，做一些简单的归纳： ( 一) 基于机器学习思路的分类算法 传统的机器学习算法有两大代表基于覆盖的a q 家族算法1 1 1 】和以信息熵为 基础的i d 3 决策树算法【1 0 , 1 1 】( 以及i d 3 算法的增量版本，包括i d 4 和i d 5 算法) 。而 后又出现了基于粗糙集理论的学习算法。这些学习算法比较适用于具有离散型数据 类型的数据集，而对于连续型的变量往往需要采用一些离散化的手段先把它们转化 成离散的数据类型再进行处理。 ( 二) 基于判别分析的分类算法 基于统计学的分类算法的主要思想是假设数据服从某种特定的分布或概率模 型，然后基于该分布模型对数据进行测试。常用的概率分布模型有正态分布、泊松 分布、二项分布、指数分布等等。这种基于概率分布模型的分类技术在统计分析领 域中被称为判别分析，比较常见的算法有距离函数法1 5 9 , 6 0 l 、b a y e s 判别法1 2 ，1 1 ，1 2 】和支 持向量机( s v m ) 1 3 , 1 4 , 1 5 】等。 这些基于统计的方法通常采用数据变异指标分析数据的散度情况。统计变异指 标的值越大表示变异越大、散布越广；而变异指标的值越小表示离差越小、越密集。 福建师范大学黄残硕士学位论文 通过统计变异指标，用户可以了解到数据集的总体特征及数据的分布情况，直观明 了地发现数据的分布规律。从而更好地辨别数据点的类分布和分离噪音数据，实现 对数据样本的分类。 ( - - ) 基于神经网络的方法 工神经网络( a r t i f i c i a ln e u r a ln e t w o r k s ，a n n ) ，一种模仿动物神经网络行为特 征，进行分布式并行信息处理的算法数学模型。它是在现代神经科学研究成果的基 础上提出的，由大量处理单元互联组成的非线性、自适应信息处理系统，试图通过 模拟大脑神经网络处理、记忆信息的方式进行信息处理。 1 9 4 3 年，w s m c c u l l o c h 和w p i t t s 首次建立了神经网络和数学模型，称为m p 模型。1 9 8 2 年和1 9 8 4 年，j j h o p f i e l d 先后提出了h o p f i e l d 神经网格模型和连续时 间h o p f i e l d 神经网络模型，为神经计算机的研究做了开拓性的工作，有力地推动了 神经网络的研究。1 9 8 5 年，又有学者提出了波耳兹曼模型，在学习中采用统计热力 学模拟退火技术，保证整个系统趋于全局稳定点。1 9 9 1 年，l x u 和e o j a 等人用并 行结构的神经元实现了学习子空间方法，使这项工作走向实用化。 人工神经网络模型主要考虑网络连接的拓扑结构、神经元的特征、学习规则等。 目前，已有大量的神经网络模型保被广泛应用，例如有反传网络、感知器、自组织 映射、h o p f i e l d 网络、波耳兹曼机等等。由于其具有高度并行性、容错性以及良好 的非线性影深能力的特点，因此相对于其它的分类算法，神经网络分类器不但能够 在模式空间内形成各种复杂的判决表面，同时还具有模式变换和模式特征提取的作 用。而且它对输入数据的不完备性或特征的缺损不太敏感，这些特性使得神经网络 在分类算法上具有其特有的优势。 2 2 基于部分覆盖的分类算法( p c c ) 2 2 1p c c 算法简介 大多数分类算法都需要一种与其相适应的相似性度量方法，而普通的相似性度 量方法在处理不同属性的数据时可能会存在诸多问题。已经存在的一些相似性度量 的方法有m i n k o w s k i 距离、e u c l i d e a n 距离、m a h a l a n o b i s 距离、m a n h a t t a n 距离和 c o s i n ea n g l e 距离f 1 j 等，这些相似性度量的方法需要将不同的数据类型进行相应的转 第二章基于空间覆盖的相似性度量及其对应的分类算法 换，进行归一化后才能进行距离的度量；而这种转换工作可能导致一些信息的丢失。 在某些情况下，将一些离散类型的属性转换成数值型属性将会发生误差，特别 是相互间不存在顺序关系的离散属性进行转换时会改变其本来的含义。另一方面， 虽然存在许多的分类方法，但是大多数方法只能处理有限的几种类型的数据。例如， 支持矢量机( s v m ) 不能直接处理离散类型的属性f 1 6 1 7 】；贝叶斯不能支持数值类型 的数据。所以需要一种能够支持所有数据类型并且不需要传统距离度量的新分类方 法。w a n g i s 】提出了一种基于网格( 1 a t t i c e s ) 与超元组关系( h y p e rr e l a t i o n s ) 的数 据约减方法d r 。 d r 算法能够处理融合同一类数据中的单元组( s i m p l et u p l e s ) 和超元组( h y p e r t u p l e s ) ，并生成相应的新超元组。合并操作的成功与否，取决于新的超元组是否能 由具有相同类标签的单元组合并操作而产生。如果一个新的超元组覆盖了一个具有 不同类标签的单元组，该操作将被取消。该合并操作不断递归执行，直到所有具有 相同类标签的超元组和单元组不再合并为止。但是现实中的许多数据集仍然含有许 多不相干的或者无用的属性，并且许多噪音数据仍然会直接影响到d r 算法的性能。 在这种情况下，完全覆盖的方法，例如d rl l s l p & c 1 9 1 就不能有效地处理和发现多 维数据空间中的元组关系。尽管如此，d r 算法的主要思想仍然启发我们创造了一 种在多维数据空间中基于不同类标签和类分布的部分属性覆盖关系的新方法，该方 法不需要采用统一的公制距离度量，也不需要进行不同类属性之间的数据转换工作， 从而避免了许多弊端。 这个新的分类算法称为p c c ( p a r t i a lc o v e r a g eb a s e dc l a s s i f i c a i t o nm e t h o d ) ，它 能够用一种统一的方式处理不同的数据类型。它提出一种了在多维空间下基于部分 覆盖关系的元组相似性度量方法，而且它的算法实现方式相对简洁。我们采用几个 u c i 上的公共数据集对该方法进行了测试。实验结果表明，p c c 的分类性能可以与 经典的分类方法相媲美，在某些数据集上可以达到最好的分类精度。 2 2 2 定义及符号 设d 是一个有限集，符号定义为d = d l ，d 2 ，磊 ，其中西是一个拥m 维属 性的单元组，符号定义为盔= ( 口“，a 眩，口拥) 。每个属性的类型可以是离散型、数值 型或者布朗型等。 例如( 3 2 ，1 0 0 ，t r u e ，“h i g h ”，y e s ) 是一个合法的单元组。 福建师范大学黄或硕士学位论文 【定义1 】超元组( h y p e rt u p l e ) 当一个元组的每个属性条目是离散型集合或者数值型区间而不是一个单独值的 时候，该元组被称为超元组( h y p e rt u p l e 7 1 ) 。例如，元组( a ，b ，c ，【1 3 2 1 3 5 1 ) 是- 个超元组。 【定义2 】单元组( s i m p l et u p l e ) 当一个元组的每个属性条目的集的势为1 ，既只含有一个单独值的时候，该元 组被称为单元组( s i m p l et u p l e ) 。例如，元组( a ) ，| 【1 2 1 ) 是一个单元组。简单的 说，元组( a ， 1 2 1 ) 能被表示为( a ，1 2 1 ) 。显然，一个单元组是一个超元组的特殊情 况。 【定义3 】合并操作+ 合并操作+ 被定义为离散型数据的集合合并操作和数值型数值的区间合并操 作。例如，给予两个超元组：t x = ( 【1 35 6 1 ， a ，b ) ，t 2 = ( 【2 48 1 1 ，【c ，a ) ) ， t i + t 2 = ( 【1 3 81 】， a ，b ，c ) ) 。 【定义4 】覆盖操作 设y 是一个单元组，表示为l ，y 2 ，y m ) ，z 是一个超元组，表示为( z 1 ，z 2 ， 碥，如果z i 是一个区间，它被表示为盔l 。z i 2 】，否则它被表示为一个集合。w 是一 个权重的集合，表示为( w l ，w 2 ，w m ) ，w i 是第i 个属性的权重，并且w i 【0 。1 1 。 九是一个预先确定的用来控制属性覆盖的阈值。g 是个一个如下定义的函数： g ( y , z ，f ) 一 1 ye z , ，枚举型属性时 z ；。sy s z i 2 ，数值型属性时 0y 譬z i ，枚举型属性时 x 乙，数值型属性时 y 是缺失值 = ( y 剧z ) 咝) y _ z 称为y 被z 覆盖，当且仅当a = l 时。 【定义5 】噪声元组( n o i s et u p l e ) 给定三个单元组： t 1 ，t 2 ，t 3 ，其中t 1 ，t 2 有相同的类标签，z = t 1 + t 2 是一个超 元组。当t 3 s c a l e ( d ，：) ，则d 的类标签为。 如果我们将0 的值设置为o 7 ，我们能计算出s c a l e ( d ，：) = 5 6 = 0 8 3 并且 s c a l e ( d ，) = 4 5 = 0 8 。则s c a l e ( d ，) s c a l e ( d ，：) ，d 的类标签将被分为：。 2 2 5p c c 算法的优势 通过对p c c 算法的描述，与其他分类算法相比较p c c 具有如下优点： ( 1 ) 具有一个统一的可处理数值型和离散型方法； ( 2 ) 容易处理缺失值； ( 3 ) 给定一个数据元组，它能提供其对于每一个类的元组之间的相似性度量值。 2 3 实验及