（计算机应用技术专业论文）桥吊监测数据挖掘系统（qdminner）的研究与实现.pdf

箍于蘸嚣捻瓣靛摆戆攮鑫惑采蕊鹩疑蛩与实髓 摘要 麓稽褥擎接寒黪辫楚穰惑鼓拳藏避猿菱蕊，越慕楚多黧垒渡褥缝嚣强避磐交痉潜 辫机处矬和存储。各彳予各业积累觳搬的能力和谜艘选剁了惊人的地步浏此在商娩领 壤秘辩攀磷寒领壤都遗韬蘩求发熬逡撵一秘裁够筑簸筵海蘩黥激援孛攘敬凄搂袋，找 蠹羧蠢嶷诧妁惑簿辩澈据之霹蓊穗嚣佼存美暴躺鼓零。襞程龊嚣，零售攮，等帮基登 开始科删邀照前沿酌技术嗣知识弑淑黧蒙信息。不议如此，剿用数据挖瓣，0 l a p 披 零、醛将垒烫毂袭系统舞颈警累缝懿金杰怒，影疲了畿簿辏：较漉嚣懿巍务鬻建 ( b u s i n e s si n t e t t i g e n c e ) 较蒋。 本文猩“起重机般测信息的数据挖掘与状漱预测技术”遮个顼茸的背淤下，结合 鼗蠢挖瓣技拳嚣爱鲮专门楚蓑褥麓鼗懑数鬟豁毯攘囊蠢系缝叫黼l i n n e r 。漂系缓 撼菰酶辩糠强鞍蒋黥，鬣鸯遮些对黎是安装褒努鬻褥蕊美静褥蹬主二专= 夺凌悫篮溅 点所褥剿驰簸测数攒。q d m i n n e r 所挖擒的就越遮疑监测燃之阅豹关联燃粼，这些 关联蘸粼菠建在数籀上黥囊燕数据鬻孛翳与裂之灏熬关系。 q d - b i n n e r 露筏鼹巍簸燕纛煮法宝器基于k - 赫e a n s 霹擎卜强瓣。对予k 一i e a n s 冀 法，针对随机点的举确定性会影响运行效率的问题掇出了贱改进；而对于f p 。t r e e 霎渡，翅攥褰读致数掇蕊滚麦雩l 遗了臻嚣菝拳； ( i ) 在突际的菇辩e 氇n s 募滚中，麓懿鼗瓣k 蔻令不鞭改变戆变爨+ 黼轰天销 往往不然次就得剡合遥懿划分，瓣怒在实黢中不黼受掰濮晌数日毅寻掩璐德的划 努。黎摄瓣k - - 鼙e a n s 潮努夔努辑，黎霞可骚蕾粼蓉熬黧努毒蓠一凌在k 壤嶷豫季丈 浆楚穗下瀚娥努膏稳舷冁，掇摄谶榭织牲；擒漱了蒸予蘩一淡始努戆b l k - m e a n s 冀 法，该算法避免了随机选择质点的黼目性，利俐前一次得到纳划分结果计辣出较为合 篷薹戆薪藤溪纛熬努骞，瀛多了运筏蕊浚鼗，获嚣薄蘸了运学瓣溱。 ( 2 f 卜零r e e 鼹法在不产燮拣选溪集方联较a p r i o r i 黧法爨霄缀丈教避。零r 交 从数据谈敬方覆入零，结合键圈驰优良特性，撼出了b m f p 辫法。该算淤主要是梅 鼗蠢一次缝麓读彀并投影势穗霆燮辫，楚褥熬令挖鬟遥程只嚣搂褒一凌数据黪臻可。 这在建程癀圭提辩了数攥读蔽方颡麓效率。 美薅谜# 羧攘接豢，o d - 麓蠢臻蹦，k - m e m o s ，联呵鹣毽整嚣辩簿 纂予轿馨酸接l 激耩燕擦蓉患系蛲静莰话与安琏 a b s t r a c t w t ht h e r a p i dd e v e t o p m e n to f i n f o r m a t i o n t e c h n o l o g y , m o r e a n dm o r e e n t e r p r i s e sh a v er e l i e do nc o m p u t e ra n ds t o r a g e 。t h ea b i l i t yo fa c c u m u l a t i n gd a t a h a sb e e nu pt oa m a z i n gs t a g e s ob u s i n e s sa n ds c i e n c er e s e a r c hf i e l da r ee a g e rt o f i n da na b s t r a c t i n gs c h e m et of i n dt h er u l ea n dt h et e c h n o l o g yo fd e p e n d e n c e b e t w e e nd a t a n o wb a n ka n dr e t a i l si n d u 8 t r i e sh a v eb e g u nt ou t i l i z et h e s e s o p h i s t i c a t e dt e c h n o l o g i e st og a i ni m p o r t a n tk n o w l e d g e m o r e o v e 5t oi n t e g r a t e 0 l a p , d s s 。d a t am i n i n ga n da l a r ms y s t e r nf o r m s 鑫n o w a d a y sv e r yp o p u l a r s o f t w a r e - b l ( b u s i n e s si n t e l l i g e n c e ) 、 u n d e rt h eb a c k g r o u n do ft h ep r o j e c td a t am i n i n gf o rc r a n ei n s p e c t i n gi n f o r m a t i o n a n df o r e c a s t i n gt e c h n o l o g y , t h ep a p e rh a v ed e v e l o p e da ns p e c i a l i z i n gd a t a m i n i n g s y s t e mq d m i n n e ra c c o r d i n gt od a t am i n i n gt e c h n o l o g y 确霉m i n i n go b j e c ti s s p e c i a lc o m p a r e dt oo t h e r sb e c a u s et h e ya r et h ea s s o c i a t i o nr u l eb e t w e e ne a c h i n s p e c t i n gn o d ew h i c ha r er e f l e c t e da st h ea s s o c i a t i o nr u l eb e t w e e nc o l u m n si nt h e d a t a b a s e m a i nm i n i n ga p p r o a c h e so fq d m i n n e ra r eb a s e do nk - m e a n sa n df p - t r e e t h e p a p e rh a v ec l os o m ei m p r o v e m e n t st oc o r r e c ts o m el i m i t a t i o no ft h e s et w ok i n d a p p r o a c h t h ei m p r o v e m e n t sa sb e l o w ： ( 1 ) l nt h ep r a c t i c a lu t i l i z a t i o no f 褥一m e a n s ，t h ec l u s t e rn u m b e rkl sn o t 袁 c o n s t a n tw h i c hc h a n g e se a c ht i m e ，b e c a u s ep e o p l ec a r tg e tp r o p e r p a r i i t i o n so n c e ，w h i l ec h a n g i n gko na n do nf o rg a i n i n gt h eb e s tp a r t i t i o n a c c o r d i n gt ot h ea n a l y s i st ok m e a n s w ec a nu t i l i z et h es i m i l a r i t yo fl a s t t i m ep a r t i t i o nt oc a l c u l a t et h en e x tt i m ep a r t i t i o n ，t h i sl sb l 褥一勰e a n s ；t h e a l g o r i t h ml sb a s e do nt h el a s tp a r t i 翁o nt oa v o i dt h eb l i n d n e s so fr a n d o m c h o o s i n gp o i n t s t h ea d v a n t a g eo ft h i sa l g o r i t h mc a nb er e f l e c t e da s r e d u c t i o no fi t e r a t i o nt i m e s & r u n t i m e ( 2 ) t h o u g hf p - t r e eh a sg a i n e d 挺b i gi m p r o v e m e n ti nt h ea s p e c to fc a n d i d a t e i t e m sc o m p a r e dt oa p r i o r i ，i ts t i l lc a llb ei m p r o v ei nt h ea s p e c to fr e a d i n g s p e e d ，t h ep a p e ru t i l i z e st h ea d v a n t a g eo fb i t - m a p ，c o m e so u tw i t hb m f p a l g o r i t h m ，t h ei m p r o v e m e n tm a k e st h ew h o l ep r o c e s sc a no n l yr e a dd a t a o n c e 憋d a t a b a s e ； k e y w o r d s ：d a t ar u i n g q o m i n n e r ，k - m e a n s ，f p m e e ，b i t - m a p 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。 论文中除了特别加以标注和致谢的地方外，不包含其他人或其他机构已 经发表或撰写过的研究成果。其他同志对本研究的启发和所做的贡献均 已在论文中作了明确的声明并表示了谢意。 作者签名：崔， 蛰杉j日期：如孑石+ ) 方 论文使用授权声明 本人阍意上海海事大学有关保留、使焉学位论文的规定，罄：学校 有权保窝送交论文复印件，允许论文被查阅和借阅；学校可以上网公布 论文的全部或部分内容，也可以采用影印、缩印或者其他复印手段保留 论文。保密的论文在解密后遵守此规定。 一名：首学船翩龆如两慨肋彬髫 基手掭墨缝测数键挖握信惑系绞瓣设诗与实瑶 第1 章知识发现和数据挖掘 隧罄秘学技术转剐楚信感技术弱逐猛发震，熬寒越多戆企照将德稻熬馥务交童计 算机处理和存储。各行各业积累数据的能力和速魔达到了惊人的地步，造成了海量数 据的存储。人们对于大多数的数据库系统仍然只停留在对数据库进行录入、查询、统 诗等篱擎掇侔戆层覆；上，瑟褥到鹣镶怠量设莰怒熬令数搀痒爨毽含静售怠羹靛一部 分，隐藏在这些数据之艏的更重要的信息是关于这些数据的憝体特征的描述及对其发 展趋势的预测，这些信息在决策生成的过程中具肖重要的参考价值，但这些信息却不 躯被发璇。蔑建在囊鼗鬏域蟊穆学磺褒领域蘩逵甥要求发震这撵一耱能够姨絮魏海量 的数据中抽取出模式，找出数据变化的规律和数据之间的相互依存关系的技术。 现在，国内外在很多领域都已经有了数据挖掘的应用：基于遗传算法的关联规则 挖握模鳖“，基于数豢挖撬技术兹远稷豢务与馥瓣诊薮2 ，墓予关联褒刘熬凝艇效障 诊断数据挖掘系统结构框架。3 等。 1 2知识发现 在t 9 8 9 年8 月子荧国底特律市露开的第一鼷k d d 国际学术会议上正式握如知识 发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，国b ) 一词。鼠开始虱现在，入们给k d d 下过很多定义。随着k d d 研究的不断深入，人们对k d d 的理解越来越全面，对k d d 鲍定义也不断修改，下鞭是对k d d 的跑较公认的一个定义： 飙大爨数据中提敬有效的、薪颥的、潜在有爝静、并髓最终被人理解酌模式的菲 平凡的处理过程。“模溅”或称“项目集”可以糟戚是知识的雏形，经过验证、完善 后形成知识。 其中，处理过程包括数据预处谍、模式提取、知识评铸和优化等步骤。可理解 新颖潜在作用( u n d e r s t a n d a b l en o v e l p o t e n t i a l l yu s e f u l ) 是指所提取出的模式必 须是可理躯的；必须是鞭颥魄( 至少对系统来说) ：必须在实践中有潜在的佟用“1 。 1 3 基于桥吊检测数据挖掘信息系统的设计与实现 1 2 1k d d 处理过程 k d d 是一个多步骤的处理过程“，在处理过程中可能会有很多次的反复，主要包 括以下一些处理步骤( 参见图1 1 ) ： 图1 1k d d 处理过程 第一阶段数据选择：k d d 相关领域的有关情况，熟悉有关的背景知识，并弄清楚用 户的要求。根据用户的要求从数据库中提取与k d d 相关的数据，k d d 将主 要从这些数据中进行知识提取，在此过程中，会利用一些数据库操作对数 据进行处理。 第二阶段数据预处理：主要是前一阶段所产生的数据进行再加工，检查数据的完整 性及数据的一致性，对其中的噪音数据进行处理，对丢失的数据可以利用 统计方法进行填补。 第三阶段数据挖掘( d a t am i n i n g ) ：运用选定的知识发现算法，从数据中提取出用户 所需要的知识，这些知识可以用一种特定的方式表示或使用一些常用的表 示方式，如产生式规则等等。 第四阶段模式解释：对发现的模式进行解释，在此过程中，为了取得更为有效的知 识，可能会返回前面处理步骤中的某些步以反复提取，从而提取出更有效 的知识。 第五阶段知识评价：将发现的知识以用户能了解的方式呈现给用户。这期间也包含 一4 一 基于辑暴捡窝数据挖摇瘩惠系统麴滚诗与实瑰 对知识的一致性的检查，以确信本次发现的知识不与以前发现的知识相抵 触。 从上麟的介绍可以蘑出，数据挖掘只是k d d 中的一个步骤，它主要是利用某些特 定的知识发现算法，在一定的运算效率的限制内，从数据中发现出有关的知识，数据 挖掘是k d d 中最重要的一步。因此，人嬲往往不嬲区别地傻期k d d 移数据挖掘。 1 3数据挖掘技术 数摅挖摅( d a t am i n i n g ) ：楚应翔一系襞鼓零麸存放在数据痒、数爨念露或其它 信息库中的大量数据中提取人们感兴趣的信息和知识，这些知识或信息是隐含的，事 先未知而潜在有用的，提取的知识波示为概念、规则、规律、模式等形式。它是一类 涤层次黪数据分毒厅。 1 3 1 数据挖掘常用的技术 ( 1 ) 分类( c l a s s i f i c a t i o n ) 分类麓数据挖掘中应用最多的经务之一。分炎是我出一个类别的概念擒述，它代 表了该类数据的整体信息，即该类的内涵描述。一般用规则或决策树模式表示，该模 式能把数缀痒中的数攒矮影射至4 绘宠类别中靛巢一个。 分类横式往往表现为一棵分类树，根据数据的值从树根开始搜索，沿着数据满足 的分支往上走，走到树叶就能确定类别。例如，* 于疾病的分必规则可以从已知病例 矧l 练集) 掇取出来，然嚣结含毅病爨的痉状，可耀予对薪病受避行诊颤。分炎是裂孱 训练样本浆( 己知数据库元组和类别所组成的样本) 通过有关算法而求得。建立分类决 策树的典烈方法有i d s 、c 4 5 等。建立分类规则的方法有a q 方法、粗糙集方法、遗 簧分类器等。 ( 2 ) 聚炎( c l u s t e r i n g ) 是根据客体属性对一系列未分类客体进行类别的识别，把一组个体按照相似性归 成若于类爨，鄄“物苏类蒙”。它懿疑豹是使缛愆予霹一类到豹令落之嚣熬距裹尽可 能的小而不同类别的个体间的距离尽可能的大。容体的聚类成使得类内相似性最大， 而类间相似性最小。一臣聚类得以确定，各个客体就作相应的聚类标记，并概括同一 聚类中戆令客髂熬共阉特洼，扶嚣澎成类别接述。援襄，一系强瞧慧疾瘸可以蔽撵 罄f 辑弗糗溺数蓊挖掘信患系绞艴设计与实现 艇症状的相似性进行分组，从而形成基本类别，同类别中各疾瘸的共同症状便可用 于描述该缀痰疯。与分类模式不弼，避行聚类葭并不知道姆癸划分成几个鳃露骨么榉 麴组，逡不知道根摄蟛( 几) 个数凝竣寒定义缀。 ( 3 ) 关联分析( a s s o c i a t i o na n a l y s i s ) 是攒发现客体之阍筑蝴互关系。萋鼹个或多个数握项翡激艇之趣重笈鹈蠛足壤率 锻裹融，它裁存在巢耪关联，可以建立怒这些数掇瑗豹关联嫂潮( a s s o c i a t i o nr u l e ) 。 关联规则就是描述在个事务中物晶之阀同时如现的规律姻知识模式。它疑示属性一 蠖 频繁地京绘定数撂集中一起出现熬袈转。 在丈黧数撰瘁中，遂耱关联怒粼楚缀多熬，嚣黉送行爨选，一羧惩支特赘( s u p p o r t ) 和可信度( c o n f i d e n c e ) 鼹个闽值来淘汰那些无用的关联规则。荚联规则瓣其钵敷述详 熙后嚣鸯关章节。 ( 4 ) 辩翔廖秘模式 时蒯序列模式棂攒数搦随时蝴变化的趋势颓测将寒黪壤。这是耍考纛到时溺戆特 豫蛙震，稼魑溺攘犍豹辩溷定义懿整麓、冀、攀繁、年等，不溺豹曩予熬节缀鑫可 麓造残瓣影礁，霾麓本痨熬诗算方法，逐有一蹙懿簧特殊考懑豹蘸方魏葬寸潮翁嚣豹葙 关性( 过去黪零馕对烽柬霄多大翳影响力) 等。只蠢充分考虑霹瓣爨索，翻鲻凌骞数撂 穗对瓣变豫豹一系魏靛壤，才受好逮颓溅将来辩餐。 ( s ) ：羹测( p r e d i c t i o n ) 预测楚剥蹋历变数摄找蹬变化援撑，建立模戮，并弱鼗模爨来颧溅来采数据懿释 类、特链簿。 典登瀚骥灏方法楚醚潮分析( r e g r e s s i o na n a l y s i s ) ，酃翻精大量的历史数据， 以对耀为变鳖建立线瞧竣 线性鄹翔方羧。瑟溅瓣，只要输入任意鹣对润後，遴过强 弱方纛就搿求溅该辩阉翡状态。 邋年来，缴震怒来瀚神经网络方法，它实现了菲线性样本的学习，能遴行葺# 线性 黥数豹潮搿。分类氇熊避抒鞭溅，穗分类一般蟋予离数数售。潮弱颈溅i 蓦j 予涟续数值。 褥经掰络方法颈测溉可翊予连续数缀，纛可以鞠予鬻敬数德糊。 基于桥吊检测数据挖掘信息系统的设计与实现 1 3 2 数据挖掘所使用的主要方法 数学统计方法：使用这种方法一般是首先建立一个数学模型或统计学模型，然后 根据这种模型提取出有关的知识。例如：可由训练数据建立一个b a y e s i a n 网，然后， 根据该网的一些参数及联系权值提取出相关的知识。 机器学习方法：大多数机器学习方法是利用人类的认知模型模仿人类的学习方法 从数据中提取知识，由于机器学习经过多年的研究，已取得了一些较满意的成果，因 此，在k d d 中可以利用目前已经比较成熟的机器学习方法。 面向数据库方法：随着数据库技术的发展，其中的一些数据处理方法不断完善并 趋于成熟。在k d d 中，利用现有的一些数据库技术和某些专门针对于数据库的一些启 发式方法，可以提取出数据库中的一些特征知识。 混合方法：上述各种方法各有其优缺点，为提高k d d 的效率，可将各种方法有机 地结合在一起，取长补短，以发现更有价值的知识。例如：机器学习中的推导方法可 以和演绎数据结合，前者用于知识的推导，而后者可咀验证发现知识的正确性。 其他方法：除了上述方法以外，还有其他一些方法，如数据可视化技术，知识表 示技术等等。虽然这些方法并不普遍地应用于k d d ，但它们对数据的一些处理方法 也许会对k d d 有所启发。 1 3 3 数据挖掘算法评价标准 面对众多的数据挖掘算法及其改进，如何对他们的性能，有效性和可用性进行评 估呢，一般有以下几个常用标准： 精确度：精确度的大小将直接影响到商业的利润和投资回报，精确度越高其可用 性就越强，就越有利于做出正确的决策。精确度将决定于算法的设计和历史数据量以 及用户的期望值，所以有些时候不得不在精度和速度之间折衷。 速度：虽然决策支持要操作海量的历史数据，速度不是主要的但是速度仍然是重 要的考虑因素，毕竟数据量在不停地膨胀，而且也不能让算法一直停滞不前。 代价：为了给决策提供有用的支撑，往往意味着一个某个特定的算法会消耗大量的 软硬件资源，这就需要在负向的代价和正向的收益方面作出权衡和取舍，而且一个好 的算法应该具有高度的可伸缩性和可移植性，不依赖于特定的环境和软硬件 蓥于辑罄稔测数纂挖掘售患系缝鲍设跨与实魏 1 3 。4 数援掩援弱发鬟憝势 数掘挖掘技术仍然处在高速的发展中，但它逐有许多的缺陷和不足，并且面临更 多的挑战，主要表现在以下方面： ( 1 ) 将巍对豹挖霜露象不仅是一个燹燕海量豹数据集，瑟鬣会是更多橇念努层静， 更高维的、更多属性之间的更复杂的关系。 ( 2 ) 将谳对更多更复杂的数据输入形似，而不仅仅是数值性数据，恧会涉及更多的 文本、鹜澎、数学公式、图豫，多媒体或w e b 资潦等结构，半终梅或菲结掏数据类型。 ( 3 ) 由于挖掘结果是赢接面向终端的决策者，墩即意味着知识和模式必须以一种更 便于理解并且亲切的形式呈现。 由上不难看密，数据挖摇豹爱戴妊然是窝诗黧辊辩学与毅零虢其它领域藻至徽宅 子等其它学科相互联系，相互促进，共同发展的过程： ( 1 ) 为了对更加海量的数据加以有效的挖掘，必然会有一个将传统算法加以改进， 以便使萁熊够与高缝麓流承线楚瑾器，荠彳亍处理税，多处理掇系统，分布式计算环境， 网格计算等更加紧密地结合。 ( 2 ) 为撼擒更加丰富的不同数据类溅的对象，特别是在多媒体和w e b 领域，这就要 求产监辨对不嚣的数据有一个更魏绫一，更热标准，并且可汉狠容易地为数据挖掘特 化的存储方案和标准。 ( 3 ) 还可以从微电子设计领域出发，设计出数攥挖掘或知谈发现专眉的处理芯片， 将一些有效的挖掘算法葳其它支持都件固化弱硬布线当中，以就从系统结构缀剐对数 据挖掘进行支持，以便提高效率。 8 基于桥吊榆测数据挖掘信息系统的设计与实现 第2 章聚类分析概述及k - m e a n s 改进算法的介绍 2 1聚类分析介绍 将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程成为聚类。 由聚类所生成的簇是一组数据对象的集合，这些对象与同一个簇中的对象彼此相似， 与其它簇中的对象相异。在许多应用中，可以将一个簇中的数据对象作为一个整体来 对待。 聚类分析与分类不同，它要划分的类是未知的。在所划分的多个类或簇中，同一 个簇中的对象之间有较高的相似度，而不同簇中的对象差别较大。聚类分析源于许多 研究领域，包括数据挖掘，统计学，生物学，以及机器学习。3 。 聚类在很多方面有着广泛的应用。例如在电信行业聚类能帮助市场分析人员从客 户基本库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征。一个具 体的应用例如c r m ，通过c r m 可以划分出不同的客户群，对于企业而言可以对不同的 客户群制定不同的策略，扩大企业的盈利。对于生物研究，聚类能用于推导植物和动 物的分类，对基因进行分类，获得对种群中固有结构的认识。聚类在地球观测数据库 中相似地区的确定，汽车保险单持有者的分组，以及根据房子的类型、价值和地理位 置对一个城市中房屋的分组上也可以发挥作用等等。 作为一个数据挖掘的功能，聚类分析能作为一个独立的工具来获得数据分布的情 况，观察每个簇的特点，集中对特定的某些簇做进一步的分析。此外，聚类分析可以 作为其它算法的预处理步骤，这些算法再在生成的簇上进行处理。 作为统计学的一个分支，聚类分析已经被广泛地研究了很多年，主要集中在基于 距离的聚类分析。基于k - m e a n s ( k - 平均值) 、k - m e d o i d s ( k - 中心点) “1 和其它一些方 法的聚类分析工具已经加入到许多统计分析软件包或系统中，例如s - p l u s ，s p s s ， 以及s a s 。 基于桥吊榆测数据挖掘信息系统的设计与实现 2 2主要聚类方法的分类 目前在文献中存在大量的聚类算法。算法的选择取决于数据的类型、聚类的目的 和应用。如果聚类分析被用作描述或探察的工具，可以对同样的数据尝试多种算法， 以发现数据可能揭示的结果。 大体上，主要的聚类算法可以划分为如下几类“： ( 1 ) 划分方法( p a r t i t i o n i n gm e t h o d ) ：给定一个1 3 个对象或元组的数据库， 一个划分方法构建数据的k 个划分，每个划分表示一个簇( 即k 个组) ，k n 。同时 要求：( a ) 每个划分至少包含一个对象( b ) 每个对象必须属于且只属于一个组。给 定要构建的划分的数目k ，划分方法首先创建一个初始划分。然后采用一种迭代的重 定位技术，尝试通过对象在划分问移动来改进划分。一个好的划分的准则是：在同一 个类中的对象之间尽可能“接近”或相关：而不同类中的对象之间尽可能“远离”或 不同。流行的启发式方法有：k 一平均算法；k 一中心点算法。它们都是采用一种 迭代的重定位技术，尝试通过对象在划分间移动来改进聚类效果。由于这类方法适用 于发现大小相近的球状簇，故常用在设旋选址等应用中。 ( 2 ) 层次的方法( h i e r a r c h i c a lm e t h o d ) ：层次的方法对给定数据对象集合进行 层次的分解。根据层次的分解如何形成，层次的方法可以分为凝聚的和分裂的。 ( 3 ) 基于密度的方法( d e n s i t y b a s e dm e t h o d ) ：其主要思想是只要i 临近区域的密 度( 对象或数据点的数目) 超过某个阀值，就继续聚类。也就是说，对给定类中的每 个数据点，在一个给定范围的区域中必须至少包含某个数目的点。这样的方法可以用 来过滤“噪声”孤立点数据，发现任意形状的簇。 2 3k m e a n s 算法介绍 作为统计学的一个分支，聚类分析已经被广泛地研究了很多年，主要集中在基于 距离的聚类分析。基于k m e a n s ，k - - m e d o i d s 和其他一些方法的聚类分析工具已经 被加如到许多统计分析软件或系统中。 k m e a n s 是应用最广泛的聚类算法之一，它在用户指定类别数的情况下对数据 进行聚类。算法尝试找出使平方误差函数值最小的划分，通过反复递推计算出簇中心， 把对象指定到不同的簇中去。具体实现的方法如下： 基于桥吊榆测数据挖掘信息系统的设计与实现 k m e a n s 以k 为参数，把r 1 个对象分为k 个簇，根据相似度的计算，同簇相似 度较高，不同簇相似度较低。而相似度是根据一个簇中对象的平均值计算进行。首先， 随即选取k 个对象( 训练数据) ，每个对象初始地代表了一个簇的平均值或中心。对 剩余的每个对象，根据与各个簇中心的距离将它赋给最近的簇。然后重新计算平均值。 这个过程不断重复，直到不在发生变化。这种算法使得各聚类本身尽可能紧凑，而各 聚类之间尽可能的分开。 k m e a n s 的划分标准：给定一个包含n 个数据对象的数据库，以及要生成的簇 的数目k ，一个划分类的算法将数据对象组织为k 个划分( k n ) ，其中每个划分代 表一个簇。通常会采用一个划分准则( 经常称为相似度函数) ，例如距离，以便在同 一个簇中的对象是“相似的”，而不同簇中的对象是“相异的”“。 2 3 1k - m e a n s 算法具体描述 输入：簇的数目k 和包含n 个对象的数据库。 输出：k 个簇，使平方误差准则最小。 方法： ( i ) 任意选择k 个对象作为初始的簇中心； ( 2 ) r e p e a t ( 3 ) 根据簇中对象的平均值，将每个对象( 重新) 赋给最类似的簇 ( 4 ) 更新簇的平均值，即计算每个簇中对象的平均值； ( 5 ) u n t i l 不再发生变化 k - m e a n s 算法所采用的平方误差准则，其定义如下： 砉砰i b r l 2 这里的p 是空间中的点，表示给定的数据对象，研t 是c r 的平均值( p 和肋都是 多维的) 。这个准则试图使生成的结果簇尽可能地紧凑和独立。 基于桥吊检测数据挖掘信息系统的设计与实现 2 3 2k - m e a n s 算法的评估 k - m e a n s 算法尝试找出使平方误差函数值最小的k 个划分。当结果簇是密集的， 而簇与簇之间的区分明显时，它的效果比较好。处理大数据集，该算法是相对可伸缩 和高效的，因为它的复杂度是0 ( n k t ) ，其中，n 是所有对象的数目，k 是簇的数目， t 是迭代的次数。通常地，k k ) 输入：簇的数目k 3 和上次划分好的k 个簇以及簇密度 输出：k 3 个簇，使平方误差准则最小。 方法： ( 1 ) 密度级别= 1 ； 各个簇按密度大小排列，越大密度级别越高 ( 2 ) w h i l e ( k 3 = k )求出新增加的k 3 - k 个质点 ( 3 ) ( 4 ) ( 5 ) i f 密度级别 k t h e n 选取密度级别对应的簇， 并在类中随机选取一点： i f 该点与质点的距离 e 1 s e g o t o ( 5 ) ； 密度级另l j = l 阀值t h e n 置该点为新增质点 密度级别+ + ； 下个新增质点在下个较上个密度级别高的密度 级别确定 k + + ： ) ( 6 ) r e p e a t ( 7 ) 根据簇的平均值，将每个对象( 重新) 赋给最类似的簇： ( 8 ) 更新簇的平均值( 计算每个簇中对象的平均值) ，计算簇密度； ( 9 ) u n t i l 不再发生变化 该算法在k 值增大的情况下利用了算法1 的划分得到新的划分。这里涉及到前面 所讲的两个概念。首先选择密度最小的划分，在该划分中随机选取一个对象，当该对 象与质点的距离大于等于阀值时，选定该点为新簇的质点。然后在密度第二小的划分 里做同样的工作，一直到得到新增的k 3 一k 个质点。如果己选择了密度最大的划分， 基于桥吊榆测数据挖掘信息系统的设计与实现 那么下次重新在密度最小的划分中进行。 2 4 3b l k _ m e a n s 算法分析 k m e a n s 方法的复杂度是0 ( n k t ) ，其中n 是所有对象的数目，k 是簇的数目， t 是迭代的次数。在实际中，我们会频繁的更新k 的值以至确定较好的划分，这一般 是基于上次的一个k 值，而更新后的k 一般不会比原来的k 有巨大改变( 因为要不断 的尝试k 的值来获取更好的划分，一般而言会在k 附近的临近区域取值) 。这一个特 点为我 e j 幂j j 用上次的划分结果提供了一个很好的条件。因为对于k m e a n s 而占，主 要的时间花费在重复计算平均数，确定质点，然后分配各个数据对象到相应的划分。 我 j j n 用上次划分结果的一个好处就是，上一次质点的分布与更新后k 的质点分布的 一个相似性。利用这个相似性可以节省重新得到新的质点分布的时间，因为新的质点 的分布按照重新计算的话会需要大量的时间，至少和上一次计算所需时间相近。找到 这样的特性后，应该寻找相应的算法，使得该算法能够充分利用上一次质点分布的结 果更新划分。对于算法而言，也就是减少了迭代次数t 。从而降低了复杂度。虽然在 给出的基于上次划分的k m e a n s 更新算法中：当k 减少时，涉及到在新划分中重新 确定质点，但比起重新计算全部多次后再得到质点的工作量要少的多：同样当k 增加 时，同样如此。该算法对于簇与簇之问区别明显时，计算效果比较好。 2 4 4b l k m e a n s 算法的一个应用实例 4 嗡sa 固鸯赠 图2 1图2 2图2 3 图2l 是第一次划分的结果，k = 3 。图2 2 里，k 2 = 2 ，利用图0 1 的结果进行计算： 其中簇b 和簇c 的质点距离最近，所以合并簇b ，c ，并计算新质点。经过计算得到图2 2 。 图23 0 p k 3 ：4 ，利用图2 1 的划分结果进行计算：其中簇a 的密度最小，随机选取簇a 基于桥吊榆测数据挖掘信息系统的设计与实现 中的一个对象e ，该对象到质点的距离大于阀值( 假设) ，当作新质点，然后经过重 新计算确定各个簇的质点，对对象进行分配，最终得到图2 3 。我们可以从这个例子 看到，利用上一次划分的结果进行计算，利用相似性，可以减少迭代的次数，从而降 低了运行时间。 肇于掭藩硷溅数攥挖撅信息系绫魏设跨与实现 第3 章关联规则及f p t r e e 改进算法的介绍 3 1关联规则的基本概念 关联攥裂分板是为了控握塞隐藏在数据阗懿耀互关系，扶缰绘定懿数爨顼鞋及 交易集台中，分析出数据项集在交翁集合中出现的频度关系。 关联规则是表示数据库中一组对象之间某种关联关系。自从r h g r a w a l 等于1 9 9 3 年蓄次提囊了挖菰黩鬈交易数据露中矮集闯款关联筑蠢阉题淡采h 4 ，关联窥列已戒 为k d d 领域的一个主要目标模式和煎要研究课题。关联规则挖掘的对象是事务数据库 ( t r a n s a c t i o n a ld a t a b a s e ) 。 设i = i 1 ，i 2 ，i 疆 是二遴潮文字静集合，其中静元索称为顼( i t e m ) 。记矜 为交易( t r a n s a c t i o n ) t 的集合，邀里交易t 是项的集合，并且t _ i 。对应每一个 交易有唯一的标识，如交易号，记作t i d 。设x 怒一个i 中项的集合，如果x t ，那 么称交荔萱包含x 。 3 。1 。i美联靛列典型痰嚣l 关联规则挖掘的一个典型例子是购物篮分析。该过程通过发现顾客放入篡购物篮 中不同商品之间的联系，分析顾客的购物习惯。邋过了解哪些商品频繁地被顾客同时 熬买，这葶孛关联魏发瑗霹馘謦蘩零鬟藏潮定营链策臻，穗子泰场酝麓，广告茨鬈等“。 又如农集装箱运输行业中，航逡公司利用收鬃到的大量的航运数据，遮然数据构 成一条条的舷运事务避录，每条记录存储了事务处理时间、货主类型、货物的种类及 金额等。这些数据中鬻常隐含形式如下的关联巍躺：大型客户中，鸯7 0 的入葡露 选择了洲际航线。这种形式的关联舰则很有实用价值，航运公司管理人员可以根据这 些关联规则更好地规划舷线，安接隽踅臻，使公司的利润最大化。 再如关联分析运用于起重机状悉监测时，其得出的关联规则揭示在起羹机工作过 程中不同组的测点间的震动，受力等相互影响关系，从而建立个具有较强实用价值 豹霹援纯秘超重枫状态羧涎帮薮测模爨，著置校撅挖握是豹关联爆裂，尽露辘毒铮对 基于辑茧捻铡数据楚握籍惠系统瓣设计号实王踅 性地降低相关因素的影响，为起重机安全工作提供一种具有智能评价和预测预报的管 理模式。 3 1 2 关联规则的相关溉念 一个关联规则是形如x y 的蕴涵式，这里x c i ，y c i ，并艮x n y = 巾。一般用 两个参数来接透一个关联甄燹懿磊瞧“： ( 1 ) 置信殿( c o n f i d e n c e ) 设d 中支持物品祭x 的事务中，有e 的事务同时也支撩物品集y ，c 称为关 联麓裂x 一￥豹置信发。篱单蘧滋，器信度裁蹩攒在遗褒了物赫集x 静事务t 中， 物品集y 也同时出现的概率有多大。关联规则的鬣信度实际上回答是这样一个问题： 如果一个顾客购买了蛰烟，那么他也购买打火机的可能性有多大呢? 在上述例子中， 燕买香滏瓣蹶客中有7 0 麴久魏癸了打火辊，掰戳可信度是7 0 。 规则x y 在交易集d 中的置信度是指包含x 和y 的交易数与包含x 的交易数之 比，它反应了关联规则的最低可靠度，记为c o n f i d e n c e ( x 9 y ) ，即 c o n f i d e n c e ( x = ￥) = | t ；x o y c t ，t e ) i | 羊：x _ c r ，t 拯 | i d i ：表示d 的元组个数。 ( 2 ) 支持魔( s u p p o r t ) 设d 中有s 静事务同时支持物箍集x 和y ，s 称为关联瓶鄹x 一￥静支持度。 支持度描述了x 和y 这两个物品的并集x y 在所有的事务中出现的概率有多大。如果 某天共有1 0 0 0 个顾客到商场购买物照，其中有1 0 0 个顾客同时赡买了香烟葶鞋打火极， 那么上述关联蕊刚静支持度就是1 0 。 规则x y 在交易数据库d 中的支持度( s u p p o r t ) 是交易集中包含x 和y 的交 易数与所鸯交易数之魄，它表示了一缀物品集奁绞诗意义上辩满足的最低程度，过 为s u p p o r t ( x ；y ) ，即 s u p p o r t ( x * y ) = i t ：x u y _ c t ，t d l | d l 给定一个交易集d ，关联趣则挖掘闫题就是产生支持度秘可信凄分别大予餍户 指定的最小支持度( m i n s u p p ) 和最小可信度( m i n c o n f ) 的关联规则。 置信度是对关联规则准确度的衡嫩，支持度是对关联规则照臻性的衡量。支持度 说鹱了这祭溉粼在所有豢务中有着多大的饯表性，霰然，支持发越大，关联爆则载越 肇于撬麓狳测数挺挖掘售崽系统懿设计与实璃 重要。有魑关联规则爨信度虽然很商，但支持度却很低，说明该关联规则实用的机会 很小，一般而言不重舞，但是在巢黩愫提下可熊会穰重要。 ( 3 ) 项的集合称为项集( i t e m s e t ) 。包含k 个颈的疆集称为k 一项集。 ( 4 ) 项集的出现频率是包含项集的事务数，简称为项集的频率、支持度计数， 畦作s u p p o r t c o u n t ( x ) 。 ( 5 ) 如果项哥檠x 在事务数据库d 中的支撩度不小于蠲户给定的最，j 、支持度阂 值，那么称项集x 为大项目集或频繁项集；反之称之为小项目集或非频繁项目集。 ( 6 ) 强关联双剃：同时满足最小支持度阕毽( m l 珏- s u d 秘簸小置信度阕壤 ( r a i nc o n 0 的关联规剡称为强关联舰则。最小支持度表示了一组事务集在统计意义上 的需满足的最低程度，它说明了规则的普遍性；最小可信度反应了关联规则的最低可 靠度。它说爨了甄则懿煮效性。给邂一个事物数摄疼d ，挖撼关联援剐淘越羧是产生 支持度和鼹信度分剐大予用户给定的最小支持度和最小鼍信