（计算机应用技术专业论文）多关系的约简及聚类研究.pdf

栾鸾：多关系的约简及聚类研究 摘要 由于现实世界的数据大多存放在关系数据库中，近年来多关系数据挖掘受到越 来越多研究人员的重视，而多关系分类和聚类都是多关系数据挖掘中的重要技术。 在进行多关系分类时，由于关系数据库结构的复杂性，所以对其中的表和属性进行 选择是有必要的，需要删除掉一些对最终分类并无太大影响的表和属性，这样可以 在保证一定分类准确度的同时，提高了分类效率。而在对多关系目标表中元素进行 聚类时，最主要是能较为精确的计算出目标表中任意两个对象之间的关系距离，这 样才能提高聚类的准确度。本文主要利用奇异值分解、典型相关分析等数学理论对 多关系中的数据进行分类和聚类。主要研究工作包括： 1 ) 基于协方差系数矩阵对关系数据库各表中的特征进行选择。构建每张表对应 的协方差系数矩阵，其中协方差系数矩阵中的元素代表这张表中任意两个属性之间 的相关性，对这样的协方差矩阵进行奇异值的分解，给定一个阈值名，将对应的奇 异值小于名的属性都删除，只利用奇异值大于五的属性对未知元组分类。 2 ) 研究基于表的关联度或贡献度的多关系分类，利用典型相关分析方法判断多 关系中的各个非目标表与目标表之间的关联度并得到一系列分类关键属性或定义关 系数据库中各表的贡献度，约简部分对最终分类影响不大的表，并在对各表进行查 找时按照其与目标表关联度从大到小的顺序或者按照贡献度从大到小的顺序依次遍 历其中的分类关键属性。 3 ) 研究如何计算多关系目标表中对象与对象之间的关系距离，从而对目标表中 的对象进行聚类。目标表中对象之问的关系距离不仅与本张表中的属性有关，也与 和目标表相关联的非目标表中属性有关。通过给每张非目标表设定不同的权值，较 为精确地得到目标表中任意对象之间的距离。 关键字：多关系；分类；聚类；准确度；奇异值分解；典型相关分析 栾鸾：多关系的约简及聚类研究i i i a bs t r a c t 1 1 1t h er e a l 。w o r l d ，m o s to ft h ed a t aa r es t o r e di nr e l a t i o n a ld a t a b a s e ，s oi nr e c e n t y e a r s ， m u l t i r e l a t i o nd a t am i n i n gg e t sa t t e n t i o nf r o mm o r ea n dm o r er e s e a r c h e r s c l a s s i f i c a t i o n a n dc l u s t e r i n ga r eb o t hi m p o r t a n tt e c h n i q u e si nm u l t i r e l a t i o nd a t am i n i n g d u et ot h e c o m p l e x i t yo ft h es t r u c t u r e ，i ti sn e c e s s a r yt oc h o o s ea m o n gt h et a b l e sa n da t t r i b u t e si nt h e p r o c e s so fc l a s s i f i c a t i o n s o m et a b l e sa n da t t r i b u t e sw h i c hh a v el i t t l ee f f e c to nt h ef i n a l r e s u l ts h o u l db ed e l e t e d i tc a l lb o t hg u a r a n t e et h ea c c u r a c ya n di m p r o v et h ee f f i c i e n c y w h e nc l u s t e r i n gt h ee l e m e n t si ns e v e r a lt a b l e s ，t h ep r i o r i t yc o n c e mi st oc a l c u l a t et h e d i s t a n c eb e t w e e nt w or a n d o mo b j e c t si nt h et a b l em o r e a c c u r a t e l y , i no r d e rt oi m p r o v et h e a c c u r a c y i nt h i sp a p e r , s i n g u l a rv a l u ed e c o m p o s i t i o n ，c a n o n i c a lc o r r e l a t i o na n a l y s i sa n d s o m eo t h e rm a t h e m a t i c a lt h e o r i e s 孤u s e dt od ot h ec l a s s i f i c a t i o na n dc l u s t e r i n go fd a t a i nm u l t i r e l a t i o n s t h em a i n w o r ki n c l u d e s ： 1 ) c o e f f i c i e n tc o v a r i a n c em a t r i xb a s e df e a t u r e s e l e c t i o no ft h e t a b l e si n m u l t i _ r e l a t i o nd a t a b a s e s c o n s t r u c tt h ec o v a r i a n c ec o e f f i c i e n tm a t r i xc o r r e s p o n d i n gt o e a c ht a b l e ，t h ee l e m e n t si nt h em a t r i xr e p r e s e n tt h ec o r r e l a t i o nb e t w e e nt w oa t t r i b u t e s s i n g u l a rv a l u ed e c o m p o s i n gt h em a t r i x ，d e l e t ea l lt h ea t t r i b u t e sw i mt h ev a l u el e s st h a na g i v e nt h r e s h o l d 五，u s eo n l yt h eo n e sw i t hv a l u eg r e a t e rt h a n2t oc l a s s i f yt h eu n k n o w n t u p l e 2 ) t h em u l t i - c l a s s i f i c a t i o nb a s e do nt h ec o n t r b u t i o no rt h ec o r r e l a t i o no ft h et a b l e s u s ec a n o n i c a lc o r r e l a t i o na n a l y s i st od e t e r m i n et h ec o r r e l a t i o nb e t w e e na l l n o n t a r g e t t a b l e sa n dt a r g e tt a b l e s ，o b t a i nan u m b e ro fc l a s s i f i c a t i o nk e ya t t r i b u t e s ，o rt od e f i n et h e c o n t r i b u t i o no ft h et a b l e s ，r e d u c et h et a b l e sw i t hl i t t l ee f f e c to nt h ef i n a lc l a s s i f i c a t i o n t r a v e r s et h ek e ya t t r i b u t e si nd e s c e n d i n gs e q u e n c eo ft h ec o r r e l a t i o no rt h ec o n t r i b u t i o n w h i l es e a r c h i n gt h et a b l e s i v 扬州人学硕+ 学位论文 3 ) h o wt oc a l c u l a t et h ed i s t a n c eb e t w e e no b j e c t si nt h em u l t i r e l a t i o nt a r g e tt a b l e ， t h e r e b yc l u s t e r i n gt h eo b j e c t si nt h et a r g e tt a b l e t h er e l a t i o n a ld i s t a n c eb e t w e e no b j e c t s r e l a t e dn o to n l yt ot h ea t t r i b u t e si nt h i st a b l e ，b u ta l s ot ot h ea t t r i b u t e si nt h en o n - t a r g e t t a b l e sa s s o c i a t e dt oi t b yg i v i n gd i f f e r e n tw e i g h tt oe a c hn o n - t a r g e tt a b l e ，m o r ep r e c i s e d i s t a n c eb e t w e e nt w or a n d o mo b j e c t si nt h et a r g e tt a b l ec a nb eo b t a i n e d k e y w o r d s ：m u l t i r e l a t i o n ；c l a s s i f i c a t i o n ；c l u s t e r i n g ；a c c u r a c y ；s i n g u l a r v a l u e d e c o m p o s i t i o n ；c a n o n i c a lc o r r e l a t i o na n a l y s i s 栾鸾：多关系的约简及聚类研究 6 3 扬州大学学位论文原创性声明和版权使用授权书 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下独立进行研究工作所取得的研究 成果。除文中已经标明引用的内容外，本论文不包含其他个人或集体已经发表的研 究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本声 明的法律结果由本人承担。 学位论文作者签名： 签字日期： 2 0 1 0 年岁月 学位论文版权使用授权书 本人完全了解学校有关保留、使用学位论文的规定，u p ：学校有权保留并向国 家有关部门或机构送交学位论文的复印件和电子文档，允许论文被查阅和借阅。本 人授权扬州大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以 采用影印、缩印或扫描等复制手段保存、汇编学位论文。同时授权中国科学技术信 息研究所将本学位论文收录到中国学位论文全文数据库，并通过网络向社会公 众提供信息服务。 靴敝储躲移 签字日期：加1 口年与月 争日 导师签名： 木 严乡 签字日期： p 年厂月( v 日 ( 本页为学位论文末页。如论文为密件可不授权，但论文原创必须声明 栾鸾：多关系的约简及聚类研究 1 引言 1 1 论文的研究背景和研究意义 计算机在信息社会的广泛应用，使得越来越多的数据积累在信息系统中。在这 些数据中隐藏着大量的不为人们所知的模式或知识，寻找有价值的数据模式或知识 是数据挖掘研究的主要内容。数据挖掘技术经历了近一二十年的发展，取得了较大 进展，在融合统计学、数据库、计算机图形学、人工智能和机器学习等学科内容的 基础上，形成了一套自己的理论、技术和方法。已经提出的数据挖掘技术包括关联 规则、分类、聚类、序列模式、预测、趋势分析、时间序列中的相似性搜索，等等。 然而，在现有的数据挖掘技术中所提出的数据挖掘算法基本上都是基于关系数 据库中的单个表上的数据实现的，而现实世界中的许多数据却是多关系的，即数据 由多种不同类型的实体组成，各类实体属性不尽相同，且实体间通过多种关系相互 关联【1 1 。多关系数据在生物信息学、w r e b 导航、社会网、知识获取与利用、地理信 息系统和自然语言理解等领域广泛存在【2 ，3 1 。 现有的多关系挖掘算法很多，有多关系关联规则的挖掘算法，多关系分类算法， 多关系聚类算法等。其中，多关系关联规则的挖掘算法很多，主要分为两类：一类 是解决统计偏斜问题的基于i l p 技术的研究，典型的算法有w 甜m 依【4 】、f a r m e r ； 另一类是解决性能问题的针对星型模式的数据库，主要算法有j s a 皿o r i 5 1 、m a s l 与 m a s h 。 多关系数据分类作为多关系数据挖掘【6 】中的重要任务，能够直接从多关系数据 表中寻找有效的分类或是聚类模式。按照多关系数据的表示形式及技术策略的不同， 主要可以分为以下三类：归纳逻辑程序设计( i n d u c t i v el o g i cp r o g r a m m i n g ，i l p ) 关系分类、图的关系分类、基于关系数据库的关系分类。其中i l p 关系分类是最为 经典的多关系分类技术。 2扬州大学硕士学位论文 i l p 关系分类是一种经典的多关系分类技术，主要可以分为关系决策树归纳分 类方法、基于距离的关系分类方法、i l p + 概率的关系分类方法。关系决策树的两个 主要的归纳算法是由两个最有名的命题决策树算法升级而来的，s c a r t r 7 ，8 】是 c a r t 的升级，t i l d e t g , o i 是c 4 5 的升级。t i l d e 和s c a r t 都能够完成离散和 连续值的预测任务，且分类准确度较高，但所耗时间较长，分类效率相对较为低下。 基于距离的关系分类方法是在多关系环境下给出对象之间恰当的距离定义来进 行分类学习的。在进行距离的定义时，要根据对象的描述信息的表达结构以及对象 之间的关系状态进行设计。因此，不仅要考虑对象本身的属性信息，还要考虑对象 由关系引起的扩展描述信息。主要有基于m b l 【1 1 , 1 2 】 的关系分类和基于核函数【1 3 ，1 4 1 的关系分类。基于距离的关系分类方法能够得到较高的准确度，但对于关系距离测 度的计算代价非常大，另外它要求在预测过程中必须加载所有实例使得系统的开销 急剧增加。 在实际数据集中难免因为测量失误出现噪声数据或者信息收集不完整现象， “ i l p + 概率”的解决思想就是向i l p 中引入一些应对不确定性内容的机制，来完善挖 掘任务的解决方案。目前，基于概率的多关系分类方法主要包括以下两类：i l p + b n 和i l p + s t o c h a s t i cg r a m m a r s 。i l p + b n 的思想是将贝叶斯网络( b a y e s i a nn e t w o r k s ， b n ) 1 5 1 - 与i l p 结合。将b n 拓展到多关系中的模型主要有贝叶斯逻辑推理( b a y e s d a n l o g i , cp r o g r a m s ，b l p ) 【1 6 】和概率关系模型( p r o b a b i l i s t i cr e l a t i o n a lm o d e l ，p r m ) 1 7 , 1 8 1 l 。i l p + s t , d c h a s t i cg r a i l l l a r s 的思想是是逻辑融合随机文法，其中最主要的方法 是随机逻辑推理( s t o c h a s t i cl o g i cp r o g r a m s ，s l p ) 1 9 1 。 图的关系学习( g r a p h b a s e ：dr e l a t i o n a ll e a r n i n g ，g b r l ) 【2 0 】是对图的数据挖掘 方法( g r a p h b a s e dd a t am i n i n g ，g b d m ) 的发展。它主要采用图来表示关系数据。 图的关系分类方法主要分为两类：基于图搜索的关系分类方法和基于图核的关系分 类方法。 栾鸾：多关系的约简及聚类研究3 而基于关系数据库的关系分类方法与关系数据库结合的较为紧密。基于选择图 的关系分类方法源于k n o b b e 等人提出的一个多关系数据挖掘框架 2 1 1 。这种方法摆 脱了i l p 方法的限制，把数据库中各个表和关联关系转换成直观的选择图来表示， 搜索空间是由选择图组成，选择图很容易通过算法转化为s q l 语句，也就是说仅有 s q l 语句组成的查询就可以实现了关系数据的分类。此外，还可以利用元组标志传 播进行关系分类，元组标识传播【2 2 】是指在关系数据库中从目标表向其他各表传播通 过传播类i d ，在此基础上主要提出了c r o s s m i n e 2 2 ，2 3 】和g r a p h - n b 【2 4 】算法。基于关 系数据库的关系分类方法在提高了分类效率的同时，保证了一定分类准确度。但现 有的算法都是对关系数据库中的每个表进行遍历，这样不仅浪费了大量的时间，且 对分类准确度的提高有限。 现有的多关系聚类算法也很多，其中最有代表性的有r d b c 2 5 1 和f o r c 2 6 】两 者。都是基于r i b l 2 所使用的关系距离测度方法，r d b c 方法完成凝聚的层次化 聚类，f o r c 完成基于k 均值的聚类 2 7 1 。另外，国内的刘大有，齐红提出的半监督 k 均值多关系数据聚类算法【2 8 1 ，定义了对象之问的距离公式。但这些方法在计算元 组之间的关系距离时，都未考虑不同的表对对象之间相似度影响的差异。这样，会 在一定程度上降低聚类的精确性。 所以，为提高效率，在对多关系中的数据进行分类前，应首先对关系数据库中 的表和属性进行约简。而在对关系数据库目标表中的元组进行聚类时，应考虑到不 同的非目标表在聚类中的不同作用。 1 2 论文的主要的研究内容 为了提高关系分类效率，可以约简掉与一些对分类结果影响不大的表和属性。 而对于多关系中的聚类问题，最主要是区分关系数据库中的各个表对元组之间相似 度影响的大小。 在此思想基础上，本文具有以下几个研究内容： 4 扬州大学硕士学位论文 1 ) 研究多关系分类中基于协方差系数矩阵的属性的约简，构建每张表对应的协 方差系数矩阵，其中协方差系数矩阵中的元素代表这张表中任意两个属性之间的相 关性，对这样的协方差矩阵进行奇异值的分解，给定一个阈值允，将对应的奇异值 小于t 的属性都删除，只利用奇异值大于五的属性对未知元组分类。 2 ) 研究基于表的关联度或贡献度的多关系分类，利用典型相关分析方法判断多 关系中的各个表与目标表之间的关联度并得到一系列分类关键属性，或利用单表的 特征属性占表全部属性的比例定义关系数据库中各表的贡献度。约简部分对分类影 响不大的非目标表，并在对非目标表进行查找时按照其关联度或贡献度从大到小的 顺序依次遍历其中的分类关键属性。 3 ) 研究如何计算多关系目标表中对象与对象之间的关系距离，从而对目标表中 的对象进行聚类。目标表中对象之间的关系距离不仅与本张表中的属性有关，也与 和目标表相关联的非目标表中属性有关。通过给每张非目标表设定不同的权值，可 以较为精确地得到目标表中任意对象之间的距离。 1 3 论文研究目的及创新点 本文针对关系数据库的结构，利用奇异值分解，典型相关分析等理论知识对多 关系数据库中的表和属性进行约简，从而进行多关系的分类和聚类。本文主要目标 是通过约简表和属性来提高分类的效率，并在进行多关系聚类时能较为准确地计算 出目标表中对象与对象之间的距离。本文主要的创新点如下： 1 ) 为关系数据库中的每个表构建协方差系数矩阵，其中协方差系数矩阵中的元 素即为这张表中任意两个属性之间的相关性。对这样的协方差系数矩阵进行奇异值 分解，删除掉部分奇异值较小的属性，降低了属性的维数。 2 ) 利用典型相关分析方法判断多关系中的各个非目标表与目标表之间的关联 度，或利用单表的特征属性占表全部属性的比例定义关系数据库中各表的贡献度。 选取对分类影响较大的表，并按照新的次序遍历语义关系图中的各个表，利用表中 栾鸾：多关系的约简及聚类研究 5 的分类关键属性对未知元组进行分类。从而在保证分类准确度的同时，提高了效率。 3 ) 提出了一种计算目标表中对象之间关系距离的方法。为每张非目标表设置了 一个权值，并用此权值标志其在计算目标表中关系距离时所起的作用。此外，在计 算两个相关组之间的距离时，首先找出了各个相关组的中心点，将计算相关组之间 的距离问题转化为计算中心点之间的问题。利用这种方法计算出的距离相对较为精 确，从而一定程度上提高了聚类的准确性。 1 4 论文的内容组织 本文共分为六章，各章节内容如下： 第一章主要介绍论文的研究背景、研究意义，以及论文的创新点和主要研究内 容。 第二章关于数据挖掘，多关系数据挖掘，特征选择的相关理论和技术。主要介 绍了数据挖掘和多关系数据挖掘的概念及其中的分类，聚类、特征选择的概念及常 用技术。 第三章基于协方差系数矩阵的多关系分类。为了提高分类效率，首先构建每张 表对应的协方差系数矩阵，并对这样的矩阵进行奇异值分解，约简掉一部分对应奇 异值较小的属性；其次，利用剩余的属性进行多关系分类。结果证明在保证了一定 精确度的同时提高了分类效率。 第四章基于表的关联度或贡献度的多关系分类。在进行多关系分类时，利用典 型相关分析判断关系数据库中的各个表与目标表之间的关联度，或利用单表的特征 属性占表全部属性的比例定义关系数据库中各表的贡献度，约简掉部分对最终分类 影响不大的表，并对剩余表按照关联度或贡献度从大到小的顺序依次遍历。结果证 明一定程度上提高了分类效率。 第五章基于关系距离的多关系聚类。在计算关系数据库的目标表中对象之间的 关系距离时，为每张非目标表设置了一个权值，并用此权值标志其在计算目标表中 6 扬州大学硕十学位论文 关系距离时所起的作用。此外，在计算两个相关组之间的距离时，首先找出了各个 相关组的中心点，将计算相关组之间的距离问题转化为计算中心点之间的问题。结 果证明利用这种方法计算出的距离相对较为精确，在一定程度上提高了聚类的准确 度。 第六章展望与结束语。 栾鸾：多关系的约简及聚类研究 7 2 数据挖掘相关理论及技术 知识发现是指从数据库中发现有用知识的整个过程，数据挖掘是知识发现过程 中的一个关键步骤，它利用特定的数据挖掘算法从数据中抽取模式，不包括数据的预 处理、领域知识结合及发现结果的评价等步骤。本章主要介绍数据挖掘、多关系数 据挖掘、属性约简的基本内容，以及涵盖于这些理论中的基本概念、方法等。 2 1 数据挖掘 近年来，数据挖掘引起了信息产业界和整个社会的极大关注，其主要原因是存 在可以广泛使用的大量数据，并且迫切需要将这些数据转换成有用的信息和知识。 获取的信息和知识可以广泛用于各种应用，包括市场分析、欺诈检测、顾客保险， 产品控制和科学探索等。 2 1 1k d d 的过程 k d d 是一个综合的过程，它包括数据录入、迭代求解、用户交互以及许多定制 要求和决策设计等，而d a t am i n i n g 只是k d d 中的一个具体却是关键的步骤。数据库 中的知识发现术语是在1 9 8 9 年的第一届k d d 专题讨论会上被首次采用，它强调了知 识是数据发现的最终产品。 在i d 9 6 国际会议上，f a y y a d ，p i a t e t s k y - s h a p i r o 和s m y t h 对k d d 作了如下描述： 指从数据库中获取正确、新颖、有潜在应用价值和最终可理解的模式的非平凡过程。 在这个描述中，数据是一系列事实的集合，模式是指用语言l 来表示的一个表达式e ， 它可用来描述数据集的特性，e 所描述的数据是集合f 的一个子集f e 。过程是在k d d 中包含的步骤，如数据的预处理、模式搜索、知识表示及知识评价等，非平凡是指 它已经超越了一般封闭形式的数量计算，而将包括对结构、模式和参数的搜索。知 识发现一般包括如下几个步骤： 8 扬州大学硕士学位论文 1 ) 数据准备包括3 个子步骤：数据集成、数据选择、数据预处理。数据集成 将多文件或多数据库运行环境中的数据进行合并处理，解决语义模糊性、处理数据 中的遗漏和清洗脏数据等。数据选择的目的是辨别出需要分析的数据集合，缩小处 理范围，提高数据采掘的质量。预处理是为了克服目前数据采掘工具的局限性。 2 ) 数据挖掘要先决定如何产生假设，是让数据挖掘系统为用户产生假设，还 是用户自己对于数据库中可能包含的知识提出假设。前一种称为发现型的数据挖掘， 后一种称为验证型的数据挖掘。 3 ) 选择合适的工具。 4 ) 挖掘知识的操作。 5 ) 证实发现的知识。 6 ) 结果表达和解释根据最终用户的决策目的对提取的信息进行分析，把最有 价值的信息区分出来，并且通过决策支持工具提交给决策者，因此这一步骤任务不 仅是把结果表达出来，还要对信息进行过滤处理，如果不能令决策者满意，需要重 复以上数据挖掘过程。 2 1 2 数据挖掘的概念，功能和方法 数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、随机 的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信 息和知识的过程。这个定义包括好几层含义：数据源必须是真实的、大量的、含噪 声的；发现的是用户感兴趣的知识；发现的知识要可接受、可理解、可运用；并不 要求发现放之四海皆准的知识，仅支持特定的发现问题。 数据挖掘通过预测未来趋势及行为，做出前摄的、基于知识的决策。数据挖掘 的目标是从数据库中发现隐含的、有意义的知识，主要有以下五类功能： 1 ) 自动预测趋势和行为数据挖掘自动在大型数据库中寻找预测性信息，以往 需要进行大量手工分析的问题如今可以迅速直接由数据本身得出结论。一个典型的 栾鸾：多关系的约简及聚类研究 9 例子是市场预测问题，数据挖掘使用过去有关促销的数据来寻找未来投资中回报最 大的用户，其它可预测的问题包括预报破产以及认定对指定事件最可能作出反应的 群体。 2 ) 关联分析数据关联是数据库中存在的一类重要的可被发现的知识。若两个 或多个变量的取值之间存在某种规律性，就称为关联。关联可分为简单关联、时序 关联、因果关联。关联分析的目的是找出数据库中隐藏的关联网。有时并不知道数 据库中数据的关联函数，即使知道也是不确定的，因此关联分析生成的规则带有可 信度。 3 ) 聚类数据库中的记录可被化分为一系列有意义的子集，即聚类。聚类增强 了人们对客观现实的认识，是概念描述和偏差分析的先决条件。聚类技术主要包括 传统的模式识别方法和数学分类学。8 0 年代初，m c h a l s k i 提出了概念聚类技术勃其 要点是，在划分对象时不仅考虑对象之间的距离，还要求划分出的类具有某种内涵 描述，从而避免了传统技术的某些片面性。 4 ) 概念描述概念描述就是对某类对象的内涵进行描述，并概括这类对象的有 关特征。概念描述分为特征性描述和区别性描述，前者描述某类对象的共同特征， 后者描述不同类对象之间的区别。生成一个类的特征性描述只涉及该类对象中所有 对象的共性。生成区别性描述的方法很多，如决策树方法、遗传算法等。 5 ) 偏差检测数据库中的数据常有一些异常记录，从数据库中检测这些偏差很 有意义。偏差包括很多潜在的知识，如分类中的反常实例、不满足规则的特例、观 测结果与模型预测值的偏差、量值随时间的变化等。偏差检测的基本方法是，寻找 观测结果与参照值之间有意义的差别。 利用数据挖掘进行数据分析常用的方法主要有关联规则、分类、回归分析、聚 类、特征、变化和偏差分析、w e b 页挖掘等，它们分别从不同的角度对数据进行挖 掘。 1 0扬州大学硕士学位论文 关联规则：关联规则是描述数据库中数据项之间所存在的关系的规则，即根据 一个事务中某些项的出现可导出另一些项在同一事务中也出现，即隐藏在数据间的 关联或相互关系。在客户关系管理中，通过对企业的客户数据库罩的大量数据进行 挖掘，可以从大量的记录中发现有趣的关联关系，找出影响市场营销效果的关键因 素，为产品定位、定价与定制客户群，客户寻求、细分与保持，市场营销与推销， 营销风险评估和诈骗预测等决策支持提供参考依据。 分类：分类是找出数据库中一组数据对象的共同特点并按照分类模式将其划分 为不同的类，其目的是通过分类模型，将数据库中的数据项映射到某个给定的类别。 它可以应用到客户的分类、客户的属性和特征分析、客户满意度分析、客户的购买 趋势预测等，如一个汽车零售商将客户按照对汽车的喜好划分成不同的类，这样营 销人员就可以将新型汽车的广告手册直接邮寄到有这种喜好的客户手中，从而大大 增加了商业机会。 回归分析：回归分析方法反映的是事务数据库中属性值在时间上的特征，产生 一个将数据项映射到一个实值预测变量的函数，发现变量或属性间的依赖关系，其 主要研究问题包括数据序列的趋势特征、数据序列的预测以及数据间的相关关系等。 它可以应用到市场营销的各个方面，如客户寻求、保持和预防客户流失活动、产品 生命周期分析、销售趋势预测及有针对性的促销活动等。 聚类：聚类分析是把一组数据按照相似性和差异性分为几个类别，其目的是使 得属于同一类别的数据间的相似性尽可能大，不同类别中的数据间的相似性尽可能 小。它可以应用到客户群体的分类、客户背景分析、客户购买趋势预测、市场的细 分等。 特征分析：特征分析是从数据库中的一组数据中提取出关于这些数据的特征式， 这些特征式表达了该数据集的总体特征。如营销人员通过对客户流失因素的特征提 取，可以得到导致客户流失的一系列原因和主要特征，利用这些特征可以有效地预 栾鸾：多关系的约简及聚类研究 防客户的流失。 变化和偏差分析：偏差包括很大一类潜在有趣的知识，如分类中的反常实例， 模式的例外，观察结果对期望的偏差等，其目的是寻找观察结果与参照量之间有意 义的差别。在企业危机管理及其预警中，管理者更感兴趣的是那些意外规则。意外 规则的挖掘可以应用到各种异常信息的发现、分析、识别、评价和预警等方面。 w e b 页挖掘：随着i n t e m e t 的迅速发展及w e b 的全球普及，使得w e b 上的信息 量无比丰富，通过对w e b 的挖掘，可以利用w e b 的海量数据进行分析，收集政治、 经济、政策、科技、金融、各种市场、竞争对手、供求信息、客户等有关的信息， 集中精力分析和处理那些对企业有重大或潜在重大影响的外部环境信息和内部经营 信息，并根据分析结果找出企业管理过程中出现的各种问题和可能引起危机的先兆， 对这些信息进行分析和处理，以便识别、分析、评价和管理危机。 2 1 3 数据挖掘中的分类，聚类 分类是通过给定的一系列元组的类标号，找出能够区分概念的模型，以便能够 使用模型预测类标记未知的对象类。分类的方法主要有以下几种： 1 ) 决策树：决策树归纳是经典的分类算法。它采用自顶向下递归的各个击破方 式构造决策树。树的每一个结点上使用信息增益度量选择测试属性。可以从生成的 决策树中提取规则。 2 ) k n n 法( k - n e a r e s tn e i g h b o r ) ：k n n 法即k 最近邻法，最初吐ic o v e r 和h a r t 于 1 9 6 8 年提出的，是一个理论上比较成熟的方法。该方法的思路非常简单直观：如果 一个样本在特征空间中的k 个最相似( 即特征空间中最邻近) 的样本中的大多数属于 某一个类别，则该样本也属于这个类别。该方法在定类决策上只依据最邻近的一个 或者几个样本的类别来决定待分样本所属的类别。 3 ) s v m 法：s v m 法即支持向量机( s u p p o r tv e c t o rm a c h i n e ) 法，l i t v a p n i k 等人于 1 9 9 5 年提出，具有相对优良的性能指标。该方法是建立在统计学习理论基础上的机 1 2 扬州大学硕士学位论文 器学习方法。通过学习算法，s v m 可以自动寻找出那些对分类有较好区分能力的支 持向量，由此构造出的分类器可以最大化类与类的间隔，因而有较好的适应能力和 较高的分准率。该方法只需要由各类域的边界样本的类别来决定最后的分类结果。 4 ) v s m 法：v s m 法即向量空间模型( v e c t o rs p a c em o d e l ) 法，由s a l t o n 等人于 6 0 年代末提出。这是最早也是最出名的信息检索方面的数学模型。其基本思想是将 文档表示为加权的特征向量：d = d ( t 1 ，w 1 ；t 2 ，w 2 ；t n ，w n ) ，然后通过计 算文本相似度的方法来确定待分样本的类别。当文本被表示为空间向量模型的时候， 文本的相似度就可以借助特征向量之间的内积来表示。 5 ) b a y e s 法：b a y e s 法是一种在已知先验概率与类条件概率的情况下的模式分 类方法，待分样本的分类结果取决于各类域中样本的全体。 6 ) 神经网络：神经网络分类算法的重点是构造阈值逻辑单元，一个值逻辑单 元是一个对象，它可以输入一组加权系数的量，对它们进行求和，如果这个和达到 或者超过了某个阈值，输出一个量。如有输入值x 1 ，x 2 ，x n 和它们的权系数： w 1 ，w 2 ，w n ，求和计算出的x i * w i ，产生了激发层a = ( x 1 w 1 ) + ( ) ( 2 w 2 卜+ ( x i 宰w i 卜+ ( x n 拳w n ) ，其中x i 是各条记录出现频率或其他参数，w i 是实 时特征评估模型中得到的权系数。神经网络是基于经验风险最小化原则的学习算法， 有一些固有的缺陷，比如层数和神经元个数难以确定，容易陷入局部极小，还有过 学习现象，这些本身的缺陷在s v m 算法中可以得到很好的解决。 而聚类是将数据对象分成类或簇的过程，使同一个簇中的对象之间具有很高的 相似性，而不同簇中的对象高度相异。聚类分析作为数据挖掘中的一个很活跃的研 究领域，提出了许多聚类算法。这些算法可以被分为划分方法、层次方法、基于密 度方法、基于网格方法和基于模型方法。 1 ) 划分方法( p a m ：p a r t i t i o n i n gm e t h o d ) ：首先创建k 个划分，k 为要创建的划分 个数；然后利用一个循环定位技术通过将对象从一个划分移到另一个划分来帮助改 栾鸾：多关系的约简及聚类研究1 3 善划分质量。典型的划分方法包括：k - m e a n s ，k - m e d o i d s ，c l a r a ( c l u s t e r i n gl a r g e a p p l i c a t i o n ) ，c l a r a n s ( c l u s t e r i n gl a r g ea p p l i c a t i o nb a s e du p o nr a n d o m i z e ds e a r c h ) 2 ) 层次方法( 1 l i e r a i i c i l i c a l lm e t h o d ) ：创建一个层次以分解给定的数据集。该方法 可以分为自上而下( 分解) 和自下而上( 合并) 两种操作方式。为弥补分解与合并 的不足，层次合并经常要与其它聚类方法相结合，如循环定位。典型的这类方法包 括：第一个是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 ) 方 法，它首先利用树的结构对对象集进行划分；然后再利用其它聚类方法对这些聚类 进行优化。第二个是c u r e ( c l u s t e r i n gu s i n gr e p r i s e n t a t i v e s ) 方法，它利用固定数目 代表对象来表示相应聚类；然后对各聚类按照指定量( 向聚类中心) 进行收缩。第 三个是r o c k 方法，它利用聚类间的连接进行聚类合并。最后一个c h e m a l o e n ， 它则是在层次聚类时构造动态模型。 3 ) 基于密度方法：根据密度完成对象的聚类。它根据对象周围的密度( d b s c a n ) 不断增长聚类。典型的基于密度方法包括：d b s c a n ( d e n s i t b a s e ds p a t i a lc l u s t e r i n go f a p p l i c a t i o nw i t hn o i s e ) ：该算法通过不断生长足够高密度区域来进行聚类；它能从含 有噪声的空间数据库中发现任意形状的聚类。此方法将一个聚类定义为一组“密度连 接”的点集。o p t i c s ( o r d e r i n gp o i n t st oi d e n t i f yt h ec l u s t e r i n gs t r u c t u r e ) ：并不明确产 生一个聚类，而是为自动交互的聚类分析计算出一个增强聚类顺序。 4 ) 基于网格方法：首先将对象空间划分为有限个单元以构成网格结构；然后利 用网格结构完成聚类。s t i n g ( s t a t i s t i c a li n f o r m a t i o ng r i d ) 就是一个利用网格单元 保存的统计信息进行基于网格聚类的方法。c l i q u e ( c l u s t e r i n gi nq u e s t ) 和 w a v e c l u s t e r 则是一个将基于网格与基于密度相结合的方法。 5 ) 基于模型方法：它假设每个聚类的模型并发现适合相应模型的数据。典型的 基于模型方法包括：统计方法c o b w e b ：是一个常用的且简单的增量式概念聚类方 法。它的输入对象是采用符号量( 属性值) 对来加以描述的。采用分类树的形式来 1 4 扬州大学硕士学位论文 创建一个层次聚类。c l a s s i t 是c o b w e b 的另一个版本。它可以对连续取值属性进 行增量式聚类。它为每个结点中的每个属性保存相应的连续正态分布( 均值与方差) ； 并利用一个改进的分类能力描述方法，即不象c o b w e b 那样计算离散属性( 取值) 和而是对连续属性求积分。但是c l a s s i t 方法也存在与c o b w e b 类似的问题。因此 它们都不适合对大数据库进行聚类处理神经网络方法s o m ，l v q ( l e a r n i n gv e c t o r q u a n t i z a t i o n ) 。 2 2 多关系数据挖掘 对于结构化数据，关系数据库最为流行。在关系数据库中，多个关系通过实体 联系连接在一起。而现有的许多方法只能用于单个“展平的 关系形式也就是说， 数据存放在单个表中。然而，许多实际应用，信用卡欺诈检测、信贷申请和生物学 数据分析都涉及基于信息的决策，这些信息存放在关系数据库的多个表中。因此， 多关系数据挖掘( m u l t i - r e l a t i o n a ld a t am i n i n g ) 已经成为一个具有战略意义的领域。 2 2 1 多关系数据挖掘的概念 原有的从单关系中发现模式的数据挖掘方法叫做命题学习方法或属性一值学 习方法，该方法使用命题逻辑表示知识和模式。而关系数据挖掘( r e l a t i o n a ld a t a m i n i n g ，r d m ) 也称为多关系数据挖掘( m u l t i - r e l a t i o n a ld a t am i n i n g ，m r d m ) ，是 在由多个关系表构成的关系数据库中抽取模式的一个多学科交叉的领域。它综合运 用归纳逻辑程序设计( i n d u c t i v el o g i c p r o g r a m m i n g ，i l p ) 、k d d 、机器学习和关系数 据库等方法，致力于直接从多关系数据集中发现知识的新方法的研究【2 9 】挖掘由复 杂的结构化对象组成的数据集也是该领域的研究方向之一。m r d m 不同于基于单关 系的挖掘方法，它可以直接对多关系数据进行挖掘，避免了复杂的预处理过程和由 于压缩带来的信息丢失等问题。m r d m 使用一阶谓词逻辑来表示知识和模式，具有 比命题逻辑更强的表达能力，因此m r d m 可以解决很多原有命题方法不能解决的 实际问题，能够方便地使用背景知识也是m r d m 的一个重要特征。 栾鸾：多关系的约简及聚类研究1 5 现在，数据挖掘中通常使用的模式类型和方法已经扩展到多关系的情况下，并 形成许多m r d m 方法，如关系关联规则挖掘方法、关系分类聚类方法等。这些方法 已成功地应用到多个领域，包括商务数据分析、生物信息学、医药设计以及w e b 挖 掘中的信息抽取等，而最成功的应用是在生物信息领域【3 0 】。 2 2 2 多关系数据挖掘的技术和方法 m r d m 主要是借鉴i l p 的思想和技术发展起来的。i l p 是机器学习和逻辑编程 结合的产物，主要研究多关系数据挖掘技术【2 9 】。i l p 利用背景知识从给定的实例发 现未知实例的规律。其基本任务是学习未知关系的逻辑定义，在s e m i n a lm i s ( i l p 最有影响力的先驱之一) 系统和f