基于矩阵的关联规则挖掘算法的设计与实现

《基于矩阵的关联规则挖掘算法的设计与实现》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

山东大学硕士学位论文基于矩阵的关联规则挖掘算法的设计与实现姓名：牛小飞申请学位级别：硕士专业：计算机软件与理论指导教师：石冰 山东大学很大的进步，然而，有一币架中还没有被发现，如规则天上涨，四天后下跌的可能我们称该规则为事务间关耳;出了挖掘1.维事务间关联关键字：数据挖掘、关联规 山东才AbstactDhaetpam•1bn1•1engmor0abundantdataaarchfr0nt■1erw•1nf0rmat■10nscat•10nshaVegre•1mpr0Vedtheabedt0af•1e1dthabr0adpr0spectescr•1besthec0funct•10n0fdatatam•1n•1ngsystd•1fferencebet pr0gresmu1'pe0srw¥ai•1st•1ngasm•1n•1ngfrMm•10csrt01s■10kfeurdaysafterc0mest•1ngwe•1ntertrec0n.cept■1nter—tp■1r0cessnter—traethnoaaanyroncapacat■亠faeoroeW8io111±1%11o•IXomnKeyWords：DataminiiUpdationassocia 日期:本人郑重声明：月立进行研究所取得的万包含任何其他个人或糜究作出重要贡献的个丿的法彳唸議*X诸 基于矩阵由第一章引言1・1课题提f随着信息技术的迅其主要原因是随着数据黍知俱种类甫例如, 则问题【2】，并于199書富弄奚联规则的挖掘问题算法进行优化，如引入随机算法挖掘规则的效率：有的㊁Apriori算法的挖掘刁挖掘频繁项集的FP—Gr(六珈关联规则的挑战性在于数扌用内存小、L/o操作少、扌关联规则挖凰編加4W 标数据中客体BI山东大第二章课题研究邸数据挖掘（Dat中提取隐含其中、人忙式进行高级处理的辽面关于关联规则的研究2.1数据衣 2.1.3分类（学会一个分类函数或分类杉据项映射到给定类别中的某集），以及基于训练集中数成一系列的分类规则，这些以更好地理解数据库中的每 距离度量。2・1・6演彳这可能包括时间相关数特点包括时间序列分析2o2数据挖掘1 典型的数据挖掘 山东大学彳用户确信方面的知识也可匸模式的兴趣度。•数据挖掘引擎：这是数据挖掘的最重要I成，用于特征化、关联、分类•模式评估模块：通常此成分使用兴趣度'以便将搜索聚集在有趣的模:评估模块也可以与挖掘模块3对于有效的数据挖掘，建议丿搜索限制在有兴趣的模式上。 概括说来，数据非的本质区别是数据挖掘据挖掘所得到的信息应是指该信息是预先未预或知识，甚至是违背直贤有价值。数据挖掘是从现呂数据挖掘出现之前早亡 准备的数据，这些数据 第三章ABM算法的理关联规则描述了数据库中，关联规则模式是比较重g出，是数据挖掘中一种简单彳联规则的算法属于无监督学习£3・1关联规则的有:子集设即iT厉项白 关联151116】山东刁状况不好，索赔率也木描述关联规则属I）支持度（S支持度s是Dsuppon(Az,事务中岀跳的概率。例m, 有100条，则关联夫频度。满足最小支持卫黑有3）擄®僵 山东大学供。例如对一个学校的50显示：60%的学生(3CN1(2000)既打篮球又匚则“打篮球j吃谷类早餐，，是-2000/3000=665因为总的吃谷类早餐的学生I即避免生感:鯉，旳卿則fl B)=P(B山东大是布尔型关联规则；性所以是一个数值型关联2.基于规则中数;在单层的关联规贝同的层次的；而在多层例如：IBM台式机==>Sony打印机，ABM算法挖掘的是单整数弓 山东大学TIDItemsetsT1BroadoCoke,CT2Coke,Beerl"3Coke.Mill(T4Bread・Coke.T5Bread・M盐T6Coke,Mi1kT7Bread.MiIkT8Bread,Coke,hz7n9Bread,Coke 山东大on高算法丿皆能就是产生的*上存在着问题。主K）都需要扫描数昨 L2是最耗床山东大学;第一遍，先把数据J个部分能够放入内彳项集）。然后汇总j全局支持度，以确;频繁集至少在一个；想，同样可以减轻（ 进行扫描的事务集 山东h最小支持度而它们不包当k=2时的性能是一使用哈希函数h(x,y)=(((£i口~q舌+(ord©t 山东大学项，并分别挖掘每个数据棒在内存中，将原来从磁盘耶比在磁盘中快数万倍57..论文［7］对FP—tr，(1)它有一个标记为prefixsubtree)的集合，itable).(2)每个项前缀子树［1inko_在旌联£2页目集。山东大接后缀。它使用最不频 索开销。142面给出的数据库0B¥Q7▼3月 2)可以被扩WI展为{1，2L”最小支持数211•z5｝也是频繁3—项集。3,5）都不能再扩展，算法终一图3. 翱渎駆外推g嘟4山东大第四章基于矩阵的前面我们介绍的纟需要多次扫描数据库，庞大，所以多次扫描数FP.Growth算但是FP.Growt中所学得知识，树和图 >21的必要条件是：（ 山东大学频繁2—项目集至少要有4.2ABM算法步骤ABM算法分为三步:给矩阵赋值并产生频繁2-第一步：-ABM算乞个项目建立一个比特向量， 个项目在第i个事务中宙幼E圈連鬱龜用趣裁羽顾｛山东大位都为0:定义一个一BVifiVi)中“]2ARV[j]+I(ARV[i1中存放的是否则ARM[i,j]述例子的矩 山东大学ARM[U]21：ARV_i_+21:End；>_萸药屎说i)1 山东大Fora11itemsetk)WLkdoBeginIfik=min项集也是按硬朮排獰 山东大学由于{ik,j}ELK-J；AR丫i所攻嘉'］根本没必要再fwweBvo2A,1,1.J八等V杏B曰覧[4再M,用R1不ALo1亠图过通043(是0,所以我们只需存 第五章ABM算法和Apriori算法的程序实现及性畿分析5・1程序实现环境ABM算法和Apriori算法是在Windows2000Server（CPU为P400MHz>内存为256M）平台上SQLServer2000和De1phi60的环境下实现的，为了1算法的正确性和对其进行性能分析，我们使用了三个事务数据库，分别称为test1.test2和north。test1如图5.1和5.2。共有*5条记录、5个事今Test2如图3.1和图3.2,共有9条记录、5个事务；north为SQLSe『ver2000附带的纟数据库样本NorthWind，该数据库表示的是公司、供货商和客户之间的关系，在本程序中我们使用的是0rderDetai1s表，它表示订单信息，如图5.3所示，第一条记录表示在10248号订单中包含11号产品，程序的冃的是要找到各产站之间的定购关系。对于test1和test2两个事务数据库，我们各分成两个表存放，以test1为例，分成以下两个表transactoin表和item表，如图5.4和图5.5。TIDItcmsets11DItemseIsTIOOBread,Coke,MiIkT102*3T200Bread,BeerT2001-4T300Coke,Mi1k,Beer,CakeT3002,3,4,5T400Bread,MiIk.Beer,CakeT4001,3,4,5T500Coke,Mi1k,CakeT5002*3*5图5.1原test1事务数据■库图5.2整数化的test1数据库5・2数据存储结构的设计 5・2.1频繁集存储结构 扁MXServerfnterpii^eMaojigrrS>vj•4-^"<^»tVw?SUi・■・■■■■■■tera!5Wf$(£)®n(S)«?a»：M)「:「厂usmmF的丹钦•代耐f讪心出碾i捕删i川HIW冋pa]A：裡Jh為mRAf府Mf&銅i鼻鼻Jki丄：0r44tIDFrb4L；・pIDII际、tFr・L®iOust]JlyJ2J呂▼WMA*l■••」■•4■1•***»•10?43102嗣JL102<810349102191(^50t02S0102SC1025J102^11!K12C20610"1X85UmePS3424404]?.710S1松4as€515815221&&6芦ise15RTIC0on-01用用用用氓用—用用用图5•3NorthWmd数据库中的0rdcrDetai1s表7fMMServerErrterpmeManager[JU「m，二"it卄}厂匸二■訂uoun;[g»n$XBTIH[IZDdtcdbodbgdbodbodbodbodborbn图5•4test1事务数据库中的Iransactoin-U如SQlServerfntcrprtvcMtMittijrr^IDIxlkmb(qBn(a)wsjxtp檢惟⑻«<(V)ar.-vr.^#Ar・*rw■r■扌,k-•f^r叭mtr鱼竺二计的St%viatiimiimtttwfitvaiti^iftfeIIIAMnt1*t*VS11*n1l>AVv1^4111141oTW4ktZi.i••亠4MB••右■LIlot1Br*%J□dbo2Co衣dbo巧…:est1事务数踌中的item表I風存；rv^Mrwrwi*iwf»irwritw^ahw:ESH亘E2巫二声丨i4彭叫「zrsftMor■-邛rvrosc^t咫Scr*石5QIServertS 曜咆吶航曇M|o(eA甄jnH：ibeginsetlength(s,5):fori：=0to4doCn：L=(T：'nbegin：2Li丄eETA”？1：5,hn血8吳理◎畲较陞畜b遍板屿邂蚯覇血起遥鹹 befigM卡山东大end：nbegin：k:end：ifnext=1tbeginfori：=obeginforJ：= 耐熾空趣堆］山东大掌elsebreaend：ifnbegiithenbreak：set1en0):end：ifJV=k—lth 山东大DM.end：ifn(enCJtend：end；LitemsLitemsIm：Ai遁価OB融礙癡 e唱心j(山东大学begini：=Litemin+k~*2_；forj：=i—o5doif(Arm[vD]>2k-beginfort：=n+k一3do<>1tift〉=nbthen 山东才end；end；nbegin：+k；end；Literns=Lnum•k:=k+1：end；九、Aprio enum)+，)，)；QS;s山东大学beginifLiternsi:=elsebegct(end； woItem1D=6(Litems irtidreifafnei-lt・+®・K5e|- £+bJ)t~HavsM艮星)唯00f干f，Wuf11eofe^tfe；begiUp«山东人字DMI丄t=mNtemID=，+intt0str0))：DM.en；it[o：ifinbegD0Deritmaarh亡斗”'為.hQiAt頭jKriitiaiiamhih^)；6iftdilH 山东大next1;setemsend；t：=t+1end；nbegin：-k+1；end；k:=k+1：首泸g电Psd乞2VMmIsH妃dSt许劭Ee 山东大学;参考文献l.JiaweiHan,MicandTechniques.曼Agrawa1RetalMinsin1argedatabasesIn：Prcagementofdata,Washingy1993207・2163.Agrawa1&SrikantlrulesIn：Proceed 山东大13・孙孝萍，基于娶2004.4o14.郑延峰，数据捷15.娄兰芳、蒋志方工程与应用，20016.周欣、沙朝皐机研究与发展，233。17・周皓峰、朱扬送 山东大学;DiscoveredAsso-nta1UpdatingTechni-Eng•1neb1928■D■w•menta1tmaintai•1fthIntenateer•1ng(96•Cheng,s.echniqU6n•1:ngdisc0iona1ConApplicationsApril卜4,199729.陈劲松、施小英，一不 山东夫rulestocorrona,USA,1997：265—2739.LingFeng,HInter——Trans;!!!E；』』！i馆§!/ygP°c.ust.hing一inter-ssociations.f.4牖埶麒礙越細囑独 山东大学1argedatabaseo3thInt'1Conf,onDataEngj4—502.29.王振宇、白石磊、ti型计算机系统，200：30.程继华、施鹏飞、郭1999,20(4)：274。51・武鹏程、袁兆山，浦24(5)：895〜898o 致谢衷心感谢我的导师尤的关怀。在课题的研究i行悉心指导，帮我指明了困难的时候，"听师一席「 颇深，从而能及时调整危