（计算机软件与理论专业论文）数据开采中的聚类算法研究.pdf

华中科技大学博士学位论文掘的结构发现e ，将描述同一类对象的，i 有 构按照相似度聚集到起，然后从类中发现满足用户兴趣度的结构。与同类算法比较，s t r u c t u r ed i s c o v e r v 为增量式算法，同时，聚类技术的使用提高了结构发现效率。分佰式数据丌采系统框架描述了个灵活的、具有交7j 性、扩展性的数据j l ：采系统。，2 产一关键词：数掘丌采：聚类分析：关联规则：分类数掘；高维数据；半结构化数搠f，结构荔e 现)一一1 ：见、i i华中科技大学博士学位论文a b s t r a c td a 托lm i n i n gi st od i s c o v e rt h ei m p l i c i t ，p r e v i o u s yu n k n o w n ，a n dp o l c n l i a l l yu s e f u lk n o w l e d g e ( p a t t e r n so rr e l a t i o n s ) f r o ml a r g ea m o u n to fd a t as e t sb yu s i n gm o d e l i z a t i o n d a t am i n i n gr e s e a r c hh a sd r a w no nan u m b e ro fo t h e rf i e l d ss u c ha sd a t a b a s es y s t e m ，a r t i f i c i a li n t e l l i g e n ta n ds t a t i s t i c se t c c l u s t e r i n ga n a l y s i sh a sb e e ns t u d i e di ns t a t i s t i c sa n dr e c o g n i z e da sa ni m p o r t a n ta r e ao fd a t am i n i n gr e s e a r c h a sad a t am i n i n gt a s k ，c l u s t e r i n ga n a l y s i si d e n t i f i e sc l u s t e r s ，a c c o r d i n gt os o m cm e a s u r e m e n t ，i nal a r g e ，m u l t i d i m e n s i o n a ld a t as e t ag o o dc l u s t e r i n gm e t h o do b t a i n sap a r t i t i o no ft h eo b j e c t si n t oc l u s t e r ss u c ht h a tt h eo b j e c t si nac l u s t e ra r em o r es i m i l a rt oe a c ho t h e rt h a nt oo b j e c t e si nd i f f e r e n tc l u s t e r s c l u s t e r i n ga n a l y s i si nd a t am i n i n gd e p l o y sm a n yt r a d i t i o n a lm e t h o d s a l lt h e s em e t h o d sh a v en o tb e e nc o n s i d e r e dl a r g ev o l u m ed a t as e t s h o w e v e r , t oe f f i c i e n t l yo b t a i nk n o w l e d g ef r o ml a r g ea m o u n to fd a t as e t si st h et o p l e a d i n gp r o b l e mi nd a t am i n i n ga r e a i na d d i t i o n ，t r a d i t i o n a lc l u s t e r i n ga n a l y s i sh a sm a r l yf o c u s do nn u m e r i cd a t ar a t h e rt h a no t h e rt y p e so fd a t at h a te x i s t si nr e a lw o r l d t h e r e f o r e ，c l u s t e r i n ga n a l y s i si nd a t am i n i n ga i m sa ti m p r o v i n ge f f i c i e n c yo fa l g o r i t h ma n da b i l i t yo fp r o c e s s i n gv a r i a n tt y p e so fd a t as u c ha sd o c u m e n t ，c a t e g o r i c a ld a t aa n dh i g h d i m e n s i o n a ld a t a f o l l o w i n ga r es e v e r a le f f i c i e n tc l u s t e r i n ga l g o r i t h m sd e a l i n gw i t hd i f f e r e n tt y p e so fd a t as e t sf o rr e a lw o r l da p p l i c a t i o n e x i s t i n ga l g o r i t h m sf o rc l u s t e r i n gc a t e g o r i c a ld a t ar e q u i r es e v e r a lp a s s e so v e rt h ed a t a b a s e s ，a n do b v i o u s l yt h er o l eo fi oo v e r h e a di ss i g n i f i c a n tf o rv e r yl a r g ed a t a b a s e s c c d c s ( c l u s t e r i n gc a t e g o r i c a ld a t au s i n gc l u s t e r i n gs u m m a r y ) i sa na l g o r i t h mf o rc l u s t e r i n gc a t e g o r i c a ld a t a i ti m p r o v e st h ee f f i c i e n c yb yu s i n gc o m p r e s st e c h n o l o g yt or e d u c et h es i z eo fo r i g i n a ld a t as e t s ，a n di ta l s op r e s e n t san e ws i m i l a r i t yc r i t e r i o nf o rc o m p r e s s e dc a t e g o r i c a ld a t a c c d c so n l yn e e d st os c a nt h ed a t a b a s eo n et i m e t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tc c d c sp e r f o r m sb e t t e rt h a no t h e ra l g o r i t h m sf o rc l u s t e r i n gc a t e g o r i c a ld a t a t h ec o m p r e s st e c h n o l o g yd o e sn o ta f f e c tt o om u c ht h eq u a l i t yo f c l u s t e r i n gr e s u l t a na l g o r i t h mc h i d ( c l u s t e r i n gh i g h - d i m e n s i o n a ld a t a ) i sp r o p o s e df o rh i g h - d i m e n s i o n a ld a t as e t s t h eb o t t l e n e c ko fd i s t a n c e b a s e dm e t h o d si nc l u s t e r i n gh i g h - d i m e n s i o n a ld a t as e t si sc a l c u l a t i n gt h ed i s t a n c eb e t w e e nd a t ap o i n t s i n s t e a do fd i s t a n c ec a l c u l a t i o n ，c h i ds e a r c h e st h ed e n s eu n i t si nn - d i m e n a i o ns p a c ea n ds u b s p a c e华中科技大学博士学位论文f r o mb o t hb o t t o m u pa n dt o p d o w nd i r e c t i o n si nt h em e a n t i m e ，t h e ni tc l u s t e r st h e s ed e n s eu n i t sb yu s i n gb i t w i s ea n d t h es e a r c hs t r a t e g yr e d u c e ss e a r c hs p a c e1 0i m p r o v ee f f i c i e n c ya n dt h eo n l yu s eo fb i t w i s ea n da n db i t s h i f tm a c h i n ei n s t r u c t i o n si nc l u s t e r i n gm a k et h ea l g o r i t h mm o v ee f f i c i e n c y t w oa l g o r i t h m sa r ep r o p o s e dt oa p p l yc l u s t e r i n ga n a l y s i st oo t h e rf i e l d s o n ei sm a r c i ti n t e g r a t e sc l u s t e r i n gi n t oa s s o c i a t i o nr u l e sd i s c o v e r yt or e d u c et h es i z eo fd a t as e t s i ta l s ou s e sc s ( c l u s t e r i n gs u m m a r y ) t r a n s f o r m a t i o nt oa l l e v i a t et h el o s so fi n f o r m a t i o nb r o u g h tb yt h ec o m p r e s s i o n t h eo t h e ri ss t r u c t u r e i s c o v e r y i tf i n d st h ec o m m o ns t r u c t u r eo fac l a s so fo b j e c t si nh i e r a r c h i c a l ，s e m i s t r u c t u r e dd a t ab yu s i n gc l u s t e r i n g t h e nt h ea l g o r i t h ml e a r n st h es t r u c t u r et h a ts a t i s f i e su s e r si n t e r e s t a tl a s t ，af r a m e w o r ko fad i s t r i b u t e dd a t am i n i n gs y s t e md e s c r i b e saf l e x i b l ei n t e r a c t i v ea n ds c a l a b l ed a t am i n i n gs y s t e m k e y w o r d s ：d a t am i n i n g ；c l u s t e r i n ga n a l y s i s ；a s s o c i a t i o nr u l e s ；c a t e g o r i c a ld a t a ；h i g h - d i m e n s i o n a ld a t a ；s e m i s t r u c t u r e dd a t a ；s t r u c t u r ed i s c o v e r yl v华中科技大学博士学位论文1 1引言1 综述切新事物的产生都是山需求驱动的，让计算机能够f 动智能地分析数掘库【 j 的大量数据以获取信息是推动数据丌采技术产生并发展的强大动力。例如，股票经纪人需要从同积月累起来的夫量股票行情变化的历史记录中发现其变化规律以供预测未来趋势之用；超级市场的经理人员希望能从过去几年的销售c 己泵中分析出顾客的消费习惯和行为，以便及时变换营销策略：地质学家想通过分析地球资源卫星发回的大量数据和照片柬发现有开采价值的矿物资源，等等。有一个例子可以说明数据丌采技术是如何对商业营销产生积极影响的：假设甲是移动电话服务供应商a 的客户，但是他最近决定中断和a 的合约，原因是另一个移动电话服务供应商b ( a 的竞争者) ，向他免费提供一种新型号的移动电话，这种新型号的移动电话比a 向他提供的要先进，这对供应商a 来说当然不是什么好消息，而且如果供应商a 事先知道供应商b 的营销策略会对甲有效，他会事先采取相应措施，如决定增加对甲的投资，只需多加l o o 元升级手机( 而甲的每月话费为3 5 07 亡) 就可以挽留住一位有价值的客户。那么如何能够事先知道客户甲会中断与a的合约呢? 答案是：在供应商a 的客户数据库中使用数掘丌采技术，建立一个预测模型显示这些容易更换服务商的风险人群。通过这个例子可以看到，数据丌采能为决策者提供重要的、极有价值的信息或知识，从而产生不可估量的经济效益【2 1 数据开采能够帮助人们从大型数据库中提取有用的信息和知识。数据丌采技术的意义在于所操作的对象是包含海量数据的大型数据库，对于小规模的数据库，人们不需要新的技术用以发现有用信息。例如，一个传统的小杂货店，它的顾客数量大约为一两百人，店主可以叫得出他们每个人的姓名，甚至他们的职业和购买习惯也了然于胸，所以不需要借助任何分析工具，直接利用人的大脑就可以进行数据分析及得出预测模型；而今天的大型超市和连锁店拥有数以月计的顾客，每天产生上百万条交易记录，仅依靠人的大脑记忆及分析这些数据显然是不可能的，有关顾客的所有数据都累积存储到数据库中，当数据量累积到一定程度时，原有的数据库工具已经无法满足用户的需求，用户不仅需要一般的查询和报表工具，更需要的是那些能够帮助他们从浩瀚的数据海洋中提取出高质量信息( 预测性) 的工具，数据开采的出现和发展正符合了这一潮流。华中科技大学博士学位论文1 2 数据开采1 2 1定义及过程订关数掘丌采d m ( d a t a m i n i n g ) 或数据库l 1 的知u 发现k d d ( k n o w l e d g ed i s c o v e r y i n d a t a b a s e ) 有多种定义，其中比较著名的如下：】数掘丌采或数据库中的知识发现( k d d ) 指从大量数据中提取隐含的、事先未知的、潜在有用的信息的非平凡过程。一w 川i a mjf r a w l e y ,g r e g o r yp i a t e t s k y s h a p i r oa n dc h r i s t o p h e rjm a t h e u s l 3 12 数据丌采指从大型数据库中搜寻那些隐含的模式和数据关系，如患者数据和医疗诊断之问的关系，这些关系或模式蕴含了数据库中一组对象之问的特定关系，揭示出一些有用的信息。m a r c e lh o l s h e m i e r a r n os i e b e s( 1 9 9 4 )3 数据丌采指利用多种技术从大量数据中识别并提取信息或决策知以以戍用到决策支持、预测估计等领域。c l e m e n t j n eu s e rg u i d e ，ad a t am i n i n gt o o l k i t这些定义从不同的角度说明了数据丌采的任务特征。用于数据丌采的数据集合规模巨大；数据丌采是一个多步骤的处理过程；数据开采综合了多种技术，可发现不同类型的知识；丌采出的结果直观易用。数据开采还有一些其它名称，如：数据挖掘、数据考古、知识提取、数据捕捞、数据分析等【4 j 。数据开采利用不同技术通过建立模型揭示隐藏在大量数据中的知识( 模式和关系) ，但是，要进行复杂的智能数据丌采，并不是简单地把一些数据代入模型进行计算，然后就可获得有意义的结果。它需要一个严谨的系统过程，一般包括确定问题、准备数据、数据开采、使用与监测四个步骤。1 确定问题：为了充分利用数据开采，客户必须明确表述出目标是什么，不同的目标需要不同的模型。例如某客户期望其用户能够对发送的邮寄宣传资料产生积极回应，对于两个不同的目标“提高用户对于宣传资料的回应率”和“提高用户的回应质量”将产生完全不同的数据开采模型。一个好的目标应该明确要解决的企业问题，并有可度量的结果，这些结果能够引发明智的行动，为企业提供有效的帮助。这样的目标还应该包括决华中科技大学博士学位论文策者可能做出的符种错误预测所造成的损失以及1 i i 确预测所带来的效益。2 ，数据准备：有效的数据准备：i ：作应该包括数掘收集、数抛预处理、数抛选择和数据转换等步骤，有时还需要反复地重复这些步骤。( 1 ) 数掘收集：这一步确定所需要丌采的数据源。如果所需要的某些数抓从来都没有收集过，这时就需要个数据收集阶段，这阶段i j 能需要从公共数据库或专用数据库获取外部数据( 例如人 ”1 普查或气象数据) 。( 2 ) 数据预处理：这一步是一个数据清沈过程。当数据来自多个数据源时，有必要把它们合并成一个单一的数据库，为此，可能需要着手处理小一致的数据定义、不同的数据编码、同一个数据中不一致的项 值等问题。即使数掘是来自单一的数掘源，也需要仔细检验是否存在影响数据完整性的问题。除此之外，还需要考虑数据的来源、物理数掘类型、度量单位，以及以什么样的频度、在什么时问和什么条件卜收集数据等问题。从根本上说，必须确保所有的数据以同样的方式度量i 司一个事物。另外，在这步要建立将要实施数据丌采的数据库。( 3 ) 数据选择：数据收集到位以后，就需要为数掘丌采任务选择恰“的数据。原则上，一些数据丌采算法会自动忽略无关的变量，并适当地计算相关变量，但实际上，般不会只依赖某一种：l ：具来进行数据玎采。( 4 ) 数据转换：选择好数据以后，有时还需要做一些数掘转换的工作，例如，可能需要用债务一收入比而不是把债务和收入都作为独立变量来预测信用风险。3 数据丌采：这单的数据开采指的是使用某种或某几种数据丌采方法和技术从准备好的数据中提取模式的过程。首先要确定模型，选择和使用丌采算法开采出模式，然后将模式表达成容易理解和使用的知识。对知识的评估可能导致该过程重复执行。4 使用与检测：知识在使用后，必须严格考察模型的工作情况。因为随着时间的推移，数据开采所涉及的因素会有不同程度的发展和变化，这就需要经常重新测试、甚至可能是彻底重构模型。1 2 2 相关领域数掘丌采综合利用了其它学科或领域中某些成熟的方法和技术，涉及到以下华中科技大学博士学位论文几个领域：机器学习i 甜、统计学、联机分析处理8 ( 0 l a p _ o 吐i 。i n ea n a l ) t i c a lp r o c e s s i n g ) 等。12 t 21 机器学习机器学习是一个自学爿过程，学习在这单的含义是通过观察环境状态的改变来构造规则，机器学习包括范例学习、强制学习和监督学习等。学习算法以数抛集及其附属信息为输入并输出学习结果，如概念。机器学习通过分析这些干丫本及其结果学习如何重复该过程并且能够举。反三。通常机器学习系统使用训练集一个完整的有限集合柬完成学习，训练集中包含有观察陈述和样本数据，它们由一种机器能够理解的形式来表达。由于这样的训练集是一个有限集合，所以机器学习系统学习到的概念不可能是完全的。数掘丌采与机器学习中有关范例学习部分有许多重叠部分，但还是存n j 斤异：数据开采关心易于理解的知识的获取，而机器学习则关心方法性能的提s t ：数据丌采面对的是海量的、现实世界中的数据库，而机器学习大多使用较小的数据集合，所以对于数据丌采，效率问题至关重要。可以将数据丌采看作是机器学习中某些技术在数据库系统上的应用，但与机器学习相比，数据丌采需要泞意以下两点：学习算法的效率要更高，因为真实数据库中的数据通常容量相”j 人而且存在噪音数据，而机器学习使用的是近乎理想的实验室数据。用于数掘 采的数据库通常并不专为丌采任务设计，那些能够简化学习过程的数据属性并不一定存在于数据库中，而且，真实数据库中的数据一定会存在不完整、不一致等错误，所以数据开采算法必须善于处理这些情况：更好的数据表达能力和知识表达能力。数据表达如关系数据库中的记录给出了一个问题域中的实例；知识表达如规则系统中的规则，可用来解决问题领域中的用户问题，以及关系组合中的语义信息。1 2 22 统计学统计学是一门成熟的学科，具有坚实的理论基础。大多数基于经典理论和分析方法的统计技术在数据量适度的数据集合上工作得相当好，但是随着计算机性能的提升以及成本的降低，再加上对分析大容量数据集合的需求迫使新的统计技术出现，数据开采因此成为传统统计方法的扩展。另外，由传统统计分析得出的结果难以理解，统计分析的过程也相当专业化，而数据丌采能够将专家知识和分析技术很好地结合起束。华中科技大学博士学位论文12 2 3o l a p数据丌采和o l a p 都属r 分析型】：具，但两者之问有着明显的区别。数执t ：川采能自动地发现隐藏在数掘中的模式，它与其他分析型工其的最大1 i i 司“j j ：它的分析过程是自动的。使用数据丌采j ：具的用户不必提出明确的问题，j l 需”岜七j r 采隐藏的模式并预测未来的趋势，这样更有利于发现未知的事实。o l 。a p 足种自上而下、不断深入的分析工具：用户提出问题或假设，o l a p 负贞从j ：仝卜深入地提取出关于该问题的详细信息，并以可视化的方式呈现给i l jj “。j 数掘丌采相比，o l a p 更多地依靠用户输入问题和假设，但用户先入为e 的j 1 0 限性i l j能会限制问题和假设的范围，从而影响最终的结论。因此，o l a p 更需葵对用，o需求有全面而深入的了解。一个典型的o l a p 问题可能会是这样：去年哪个城市的用户购买了更多的汽车，是上海还是广州? 而一个典型的数据玎采间题t ，r 能会是这样：预测上海和广州的汽车销售情况。数据丌采可以发现o l a p 所不能发现的更为复杂而细致的信息，f i i 某u 兰0 1 。a p 厂商声称他们的产品也具有数掘丌采的功能。实际上，如果减弱数掂j r 采的定义，o l a p 也能做数据丌采，但两者最关键的区别在于信息丌采过程是否是自动的。i 2 3数据开采技术邕銎一堑型兰兰匕斗型兰三堡b o 名续约青ii 没有续约者p o 名不续约者i怔。名不续约青客，一2 3 宅歹7 ：西荔3f 一0 名续约者5 名不续约肴有续约者名不续约着盘茎兰0 名续约者名不续约青1 名续约者名不续约者图1 1 决繁树用于客户分类数据开采的技术基础是人工智能a i ( a r t i f i c i a li n t e l l i g e n c e ) ，它采用了a i 中部分已经成熟的技术，包括决策树、神经网络、遗传算法、规则归纳等。华中科技大学博士学位论文1 2 31 决策树决策树是一个预测模型，呈树形，决策树中的每。个分支都是一个分类问 u ，树中的叶子则是整个数据集合上的一个分类。举例：给某移动电话服务商的用。分类查找哪些用，不易与当前服务商中断合约，图1 1 即为解决该问题的决策树，可以得出结论“拥有新型手机、与该服务商签约时间大f j ：2 - 3 年的川，。小易中断合约”。决策树的构造过程大致如图1 1 所示，从树的根符点丌始提问，问题的选择很重要，判断问题是否合适的标准是要使得树中的叶f 尽可能包含相似数掘，这单相似指有关预测目标相似，如图1 i 举的用户分类例子，决策树构造好之后，最好的情况是叶子节点包含的数据要么都是续约者要么都是不续约者。国际j 二最早的、也最有影响的决策树算法是1 9 7 0 年由j o h nr q u i n l a n 提出的1 d 3 1 9 f _ l l ，i d 3判断分支问题及分裂值的选取是否合适采用的标准如f ：比较分裂前后系统对预测结果作出正确判断所需的信息量，如果该信息量在分裂后减少了，则认为问题及分裂值的选取合适。1 2 3 2 神经网络简单地说，神经网络研究人类大脑是如何组织以及如何学习的。组成神经网络的两个主要结构如下：1 节点( n o d e ) 对应人类大脑中的神经元。2 链接( 1 i n k ) 对应人类大脑中连接神经元的轴突、树突和神经键。会拖敏?围1 2 神经网络用于贷教拖欠预测图1 2 给出了一个简单的神经网络，圆圈代表节点，连接圆圈的直线代表链接，该神经网络根据年龄和收入预测顾客是否会拖欠银行贷款。神经网络算法首先获取两个输入节点的值：年龄= 4 7 、收入= 6 5 0 0 0 ，将它们规格化后分别等于o 4 7 和o 6 5 ；接着，根据模型计算输出节点的值：( 年龄年龄权值) + ( 收入收入权值) = ( 0 4 7 x 0 7 ) + ( 0 6 5 0 1 ) = o 3 9 。在本例中，输出值为l 表示信用很差，输出值为0 代表顾客有着很好的信用，绝对不会欠款，o 3 9 与0 接近，6所以认为浚顾客不会搀欠贷款。 i | l 经网络模型的创建足个监督学爿过程，给定个训练集，比较神经网络算法得出的结果和训练集给定的标准结果，如果存舀：误筹，则通过修改链接的权值来修改神经网络的行为，直到结果i f 确为：。1233 最近邻居籍廿收入图13 最近邻居用于风险预；则最近邻居方法是一个监督学习方法。它利用特自i ：空i 刊为未知类别的记录在样本数据集合中找出与之最相似的记录所属的类? 并将这条新记录分配到该类中。数掘点之间的距离大小被用来判断记录是否相似，最常用的距离公式是曼哈顿距离( m a n h a t t a nd i s t a n c e ) 和欧几里得距离( e u c l i d e a nd i s t a n c e ) 。图1 3 给出了一个利用最近邻居方法预测某客户是否会拖欠贷款的例子，图中给出了一个基于年龄和收入的二维空白j ，样本数掘库中的记录根掘收入值和年龄值映射到这个二维空间中，形成数据点，其中实心圆代表不会拖欠贷款，空心矩形代表会拖欠贷款，a 、b 是两个待分类的数据点，距离已录a 最近的数掘点是一个空心矩形，并且a 周围的邻居都是空心矩形，那么自然a 被分配到会拖欠贷款的类别中；记录b 的情形没有a 那么清晰，b 周围有空心矩形也存在实心圆，但是距离b 最近的是空心矩形，所以，记录b 也要分配到会拖欠贷款的类别中。1 2 3 4 遗传算法遗传算法指所有模拟生物进化过程的系统，更确切地说，遗传算法是规定并控制有机群体如何形成、如何评估、如何变更的算法。遗传算法的难点是如何将现实世界问题的解决方法转换成模拟遗传物质的计算机表达形式。一个最简单的例子能够说明遗传算法是如何工作的，将遗传算法用于解决如下问题：邮寄给用华中科技大学博士学位论文，、的产品1 i 传信件中放胃多少优惠券能够产慢最大效益? 邮件数量j 效益关系如卜：l优惠券放胃过多会增加邮件藁量，提高邮件成本：2用户不会使用邮件中未提及的优惠券：3 优惠券种类过多增加用，、- 使用难度，达小到预期效果。该问题可以转换为一个简单的遗传算法，每个模拟有机体包含。个展w ，每食基因代表该有机体对于矿确优惠券数量的猜测，遗传算法最初随机刨建个有机群体，然后通过模拟进化过程，在这个过程中修改基因、删除表现很差的订机体、复制表现优异的有机体( 允许复制过程中对有机体的基因进行微小改动) ，直至产生最好结果。以下描述了遗传算法从一代演变到下一代的过程：1 定义需要解决的问题并将其转换为遗传算法形式，如有机体、染色体和纠i成染色体的基因等。2 初始化有机群体，这个有机群体随机产生。3 使用预先定义的评估函数计算群体巾币个有机体的适应值，评价t 丫1 个仃机体的适应性。4 复制那些具有最好适应值的有机体的遗传物质，同时删除适应值较小的有机体。5 让新形成的有机群体产生突变和有性繁殖。6 再次使用评估函数评价单个有机体的适应性。7 如果满足下列任何一个条件，则停止算法。( 1 ) 得到能够满足需求的解决方案。( 2 ) 系统演化已经到了第一代( 一是预先定义的阈值) 。( 3 ) 系统停滞不前，不再产生更好的有机体。8 重复步骤4 至7 。遗传算法在数据开采中的应用通常基于其它数据开采技术，如神经网络和最近邻居分类。遗传算法可以利用交叉验证作为评估函数找出数据丌= 采中的最优预测模型。华中科技大学博士学位论文123 5 规则归纳规则用来表示数据库中项c 了之1 1 j j 的关系，它的殷形式为“i f “t h e n ”，例如“如果购买了纸盘子，则购买了塑料叉”。规则可以很简单，前提只包含。个元素，也可以很复杂，前提包含由连接词连接的多个元素。规则的两个蓖要特性可以帮助用户评价一条规则是否有用：1 准确率前提为真时，结论也为真的概率。如果一条j ! i ! 则的准确率很高，则认为该规则相当可靠。2 覆盖率数据库中符合该规则的记录数。高覆盖率意味着这条规则经常被使用，错误的可能性很小，但它1 i 能用束体现数据库特征。规则归纳生成的规则与决策树生成的规则非常相似，但也存在一个七要的差异。决策树穷举了训练数据库中所包含的所有规则，并且这些规则具有互斥性，两规则归纳则不保证穷举所有规则，这些规则不具互斥性。这一差异是出产生规则的方式不同造成的，规则归纳自底向l 搜索可能的用户感兴趣的模式，而决策树是自顶向下的穷尽搜索。规则归纳算法的一般过程如下：1 数据预处理，主要是属性值的离散化，将连续值分成几个有限的区j 日j 值，如收入属性的值可离散化为以下几个区问( 2 0 0 ，8 0 0 ) 、( 8 0 0 ，1 5 0 0 ) 、( 1 5 0 0 3 0 0 0 等。2 生成初始规则，初始规则的生成通常选取每条记录的个属性值与其它属性值配对形成i f t h e n 舰则，初始舰则满足一个约束条件。3 新增一个约柬条件，从初始规则中找出满足该约束条件的规则作为候选规则。4 重复步骤3 ，直至满足中止条件。5 根据准确率、覆盖率等组织规则，并呈现给用户。1 2 4 数据开采模型数据开采通常分成两个大的类别：描述型( d e s c r i p t i v e ) 的数据丌采和预测型( p r e d i c t i v e ) 的数据开采，前者给出对数据集合简洁的、总结性的描述，而后者则通过剞建一个或多个模型，试图从当前数据集合推导出未知数据集合的行为。数据开采系统通常包含多个数据开采模型以完成多种数据开采任务，这些数据歼9华中科技大学博士学位论文采模型巾，分类h 2 0 1 ( c l a s s i f i c a t i o n ) 、刚p 】川( r e g r e s s i o n ) 和时m 序列( t i m es e r i e s )模型l 要用于预测，而聚类【2 2 l 1 2 8 1 ( c l u s t e r i n g ) 、关联分析旧( a s s o c i a t i o na n a l y s i s )和序夕u 发现f 3 8 j - 1 4 2 1 ( s e q u e n c ed i s c o v e r y ) 主要用二描述数据库行为。1 分类：分类模型识别并描述每个数据对象的特征，并根据这螳特征分类未知数据对象。由分类模型得到的模式既可用j j | 】理解现存的数据又可预测未知实例的行为，如解决如下问题：“谁最可能选择另一家长途电话服务供应商? ”以及“谁是外科手术的最佳候选人? ”。数据丌采通过分析训练数掘集( 数据集合中的数据对象已经打上了分类标签) 并根据类别特征构造预测模型。训练数据来自历史数据，如已经选择了另外的长途电话服务供应商的客户或做过该类外科手术的人员，要生成训练集首先从完整的数据库中挑选一部分数据作为样本，然后通过现实世界测试这些样本，最终根据测试结果为每个样本数据对象打上类别标签形成训练数据集，对训练数据集的分析结果是产生分类器，如决策树或一组分类规则。机器学习、统计学、神经网络和粗集等领域都有分类方法的研究，分类分析应用于客户分类、商业建模和信用分析。2 回归：回归分析利用现有的数据值预测将来的可能值，最简单的回归分析是线性回归，但在大多数实际问题中，数据值并不是简单的线性映射，如销售量、股票价格等。它们难以准确预测的原因足受太多因素的交互影响，因此需要更为复杂的分析方法。相同的数据丌采技术既可用于回归又可用于分类，如决策树技术c a r t ( c l a s s i f i c a t i o na n dr e g r e s s i o nt r e e s ) 和神经网络技术。3 时间序列：时间序列同回归相似，它利用现有的数据值序列预测将来的可能值，时间序列模型需要考虑数据的时间属性，尤其是时阳j 周期的层次( 包括时间周期的各种定义，如5 天制或7 天制工作周) 、季节性以及其它一些特殊的因素如过去对将来的影响程度。时间序列分析可以帮助用户根据以往的股票价格预测其走势、公司的经济状况和竞争对手的业绩等。4 聚类：聚类模型的任务是将数据集分成不同的组，一个组就是一个聚类，个聚类中的数据对象彼此相似而处于不同聚类中的数据对象相似度则很低。判断数据对象相似度的方法称作相似度判别标准，对于数值数据，通常采用距离函数作为相似度判别标准，目前也提出了针对非数值数据的相似度判别标准。好的聚类方法产生的高质量聚类能够确保类与类之间的相似度非常低而类中的相似度非常高。与分类不同，聚类是一个非监督学o华中科技大学博士学位论文二j 过程，输入集是一组没有分类标签的记录，也就足说每先得到的数据对象没有进行仟何分类。数据丌采领域有天聚类的研究1 ：委集i | jj i 办法的可扩展性和萨确性，以及算法的效率等方面。5 炎联分析：关联分析的目的是为了发现隐藏香：数据i 日j 的年| | j 天系。关联分析就是给定一组项日( i t e m ) 和一个记录集合，通过分析以来集合，推导出项目之间的相关性，这种相关性通常用规! | ! i j 来表达，形式为：x y ，表示数据库中包含项目x 的记录同时也包含项日y 。进行关联分析时，需要用户给出两个参数，最小置信度( m i n i m u mc o n f i d e n c e ) 和最小支持度( m i n i m u ms u p p o f l ) ，最小置信度用来滤掉可能性过小的规则，最小支持度表示规则发生的概率，即可信度。关联分析广泛庸川，：零售交易数据分析，用来获取哪些商品较可能同时被用户购买，关联分析还可应用于医疗保险业等。6 序列发现：序列发现和关联分析相似，其目的也是为了发现数据之白j 的联系，但序列发现的侧重点在于分析数据问的的后关系，在进行序列发现n 寸，同样也需要由用户指定最小置信度和最小支持度。运h j 序列发现分析零售交易数据可以发现客户潜在的购物模式，如客户在购买微波炉前最常购买何种商品；序列发现可以根据需要考虑前后时问问隔，如客户购买了锤子，在其后三周又购买钉子的概率为1 8 ，序列发现还呵应用于股市分析、医疗保险业、w e b 网站的访问模式发现等。其它重要的数据模型还有数据汇总和偏差分析等，数据“：总对数掘进行浓缩，给出紧凑描述，偏差分析用来发现实际数据与预期数据之删的不一致。不同的数据丌采模型有着不同的适用范围，一个真j 下的数据丌采系统通常是综合利用、协同使用这些模型的。1 2 5 研究与应用1 2 5 1 学术研究k d d 一词是在1 9 8 9 年8 月于美国底特律市召开的第一届k d d 国际学术会议上正式形成的。国际k d d 学术会议起初每两年召丌一次，1 9 9 3 年后每年召开一次。在几次国际k d d 学术会议上讨论的问题有：定性知识和定量知识的发现；数据汇总； 知识发现方法；数据依赖关系的发现和分析；发现过程中知识的应用；交互式的知识发现系统；知识发现的应用。华中科技大学博士学位论文1 9 9 5 年，在加拿大召丌了第一届知识发现和数掘丌采国际学术会议。山j ，- 数据库中的数据被形象地喻为矿床，因此数掘丌采一词很快流传丌柬。1 9 9 5 年以束，国外在数据丌采知议发现方面的论文非常多，已形成了热门研究方向。1 9 9 7 年，亚太地区举行了第一届知识发现和数据丌采国际会议( p a k d d ：p a c i f i c a s i ac o n f e r e n c eo nk 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 g ) ，在欧洲也举办有类似的幽际会议p k d d ( e u r o p e a nc o n f e r e n c eo np r i n c i p l e so fd a t am i n i n ga n dk n o w l e d g ed i s c o v e r y ) 。1 9 9 8 年，a c m ( 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 ) 正式成j z 】，有关k d d 的特别兴趣小组s i g k d d ( s p e c i a li n t e r e s tg r o u po nk n o w l e d g ed i s c o v e r yi nd a t aa n dd a t am i n i n g ) 。此外，数据库、人工智能、情报检索等领域的国际学术团体也将k d d 和数据开采作为研究讨论的热点问题。目前，有关数据丌采讨论的问题主要集中在因特网应用【4 3 1 - 1 5 8 1 和科学研究应用方面。在因特网应用方面包括数据开采在电子商务中的应用、w e b 丌采、w e b 语义学、x m l 与数据歼采：科学研究主要集中于生物信息学中的数据丌采应用。除了传统的研究方向如数据和知识表j 盘1 5 9 1 1 ”】、元数据、数据缩减和维数缩减、预处理l 胡j 1 7 ”和后处理技术f 7 2 j 。f 7 5 j 、开采语言f 7 6 】1 7 8 j 大家最新关注的问题还包括已发现知谚 的管理和精炼、文本开采 7 9 i - t 自s l 用于知识管理、数据丌采中的安全和隐私保护等。随着国外知识发现的兴起，我国也很快跟上了国际步伐。计算机世界报技术专题版于1 9 9 5 年3 月发表了由中国电子设备系统工程公司研究所李德毅教授组织的k d d 专题；于1 9 9 5 年4 月发表了由中国科学院史忠植研究员组织的“机器学习、神经网络”专题；于1 9 9 5 年1 2 月发表了由国防科技大学陈文伟教授组织的“机器发现和机器学习”专题，于1 9 9 9 年在北京召开的第三届p a k d d 国际学术会议，都对我国开展知识发现的研究起到了一定的推动作用。近几年，国内各计算机学术刊物也纷纷刊登有关知识发现和数据开采的论文，所涉及的研究领域集中于学习算法的研究和有关数据开采的理论研究。1 2 5 2 应用领域数据开采在各行各业都具有广阔的应用前景，如下：l 。零售，营销：分析顾客的购买行为和习惯；顾客关系管理c r m ( c u s t o m e rr e l a l i o n s h i pm a n a g e m e n t ) 研究消费者之间的特征关系 分析顾客对促销手段的回应；商品价格优化以及商品销售预测等。2 银行，电信：欺诈行为侦测：对于银行业是信用卡欺诈，对于电信则是恶2华中科技大学博士学位论文性欠费：发现在何种情况哪些顾客会更换服务提供商。另外，银行q p 还需要对借贷企业实施破产预测等。3 股票期货：从股票或期货交易的历史数据中得到交易的规则或规律，用j 二分析股票价格的未来走势、为某笔交易提供实时建议、进行投资分析、建立期货交易模型等。4 保险医疗保健：需求分析为顾客提供最适合的医疗保健程序；预测什么样的顾客将会购买新险种：议别高风险顾客的行为模式；欺诈甄别。5 生物，制药：d n a 蛋白序列分析；分析疾病的治疗方法，_ i ： 别疗效好的药品治疗案例等。6 行政机构的知识管理：集成机构中存在的多种异构数据源，包括电子邮件、文字文档、图片、幻灯片、电子表格等，并提供易于使用的可视化界面供查找、开采，如人力资源部可以通过分析应聘者的申请表格和简历挑选最合适的职位人选。7 w e b 分析：发现存在于w e bf 1 志数掘中的模式，用于分析网站浏览者的行为，可以为用户提供一对一的个性化服务，如提供个性化主页面、对用户的某个点击动作产生个性化回应等：对于电子商务网站还可以分析购买者行为，为不同的消费群体提供个性化产品信息；w 曲文本分析，包括文本总结、文本分类及解释、搜索有用的经过提取的信息；w e b 广告效益分析；w e b 站点信息流量的实时监控等。就我国现状来说，保险业、金融业和信息部门