信息、知識、智能的轉換和算法分析

PAGE畢業(yè)論文(設計）論文(設計）題目：信息、知識、智能的轉換和算法分析系別：專業(yè):學號:姓名：指導教師:畢業(yè)論文（設計)開題報告系別:計算機與信息科學系專業(yè)：網絡工程學號姓名蒙劍論文（設計）題目信息、知識、智能的轉換和算法分析命題來源eｑ＼o\ａc（□,√）教師命題□學生自主命題□教師課題選題意義（不少于３００字）：隨著信息技術的高速發(fā)展，數(shù)據(jù)庫應用的規(guī)模、范圍和深度不斷擴大，已經從單臺機器發(fā)展到網絡環(huán)境。由于各種新型技術與數(shù)據(jù)庫技術的有機結合，使數(shù)據(jù)庫領域中的新內容、新應用、新技術層出不窮，形成了龐大的數(shù)據(jù)庫體系，如商業(yè)條碼的推廣、企業(yè)和政府利用計算機管理事務的能力增強，產生了大規(guī)模的數(shù)據(jù).而簡單數(shù)據(jù)信息查詢只是數(shù)據(jù)庫內容的選擇性輸出，無論是查詢、統(tǒng)計還是報表，其處理方式都是對指定的數(shù)據(jù)進行簡單的數(shù)字處理，而不是對這些數(shù)據(jù)所包含的內在信息進行提取,因此它和人們期望的分析預測、決策支持等高級應用仍有很大的距離，人們希望能夠提供更高層次的數(shù)據(jù)分析功能,自動和智能的將待處理的數(shù)據(jù)信息轉化為有用的知識.數(shù)據(jù)挖掘之所以吸引專家學者的研究和引起商業(yè)廠家的廣泛關注,主要在于大型數(shù)據(jù)系統(tǒng)的廣泛使用和把數(shù)據(jù)轉換成有用的知識,推動社會進步，為企業(yè)提供能帶來商業(yè)利潤的決策信息使企業(yè)在市場競爭中立于不敗之地。研究綜述（前人的研究現(xiàn)狀及進展情況,不少于600字)：Ｓhanｎon信息論和人工智能理論分別于20世紀40年代和50年代相繼產生，系統(tǒng)的知識理論卻長期無人問津，成為一段理論空白。這種狀況在信息論和人工智能理論發(fā)展的初期似乎并沒有造成明顯的問題,但是，隨著研究的不斷的深入，知識理論的空白就逐漸成為一種制約,信息論和智能理論的發(fā)展陷入受限的尷尬境地。２0世紀70年代，由于研究和建造專家系統(tǒng)的需要而出現(xiàn)了“知識工程”。然而，知識工程主要關注了知識的表示和知識的演繹推理的問題,至于如何獲取專家系統(tǒng)所需要的知識,則幾乎完全依靠專家系統(tǒng)設計者的手工操作.因此，知識工程沒有能夠形成完全的知識理論。與此同時，數(shù)據(jù)庫系統(tǒng)的三個主要模式：層次、網絡和關系型數(shù)據(jù)庫的研究和開發(fā)取得了重要進展。20世紀80年代,關系型數(shù)據(jù)庫及其相關的數(shù)據(jù)模型工具、數(shù)據(jù)索引及數(shù)據(jù)組織技術得到廣泛采用，并形成了整個數(shù)據(jù)庫市場的主導。事務數(shù)據(jù)庫、主動數(shù)據(jù)庫、知識庫、辦公信息庫等技術也得到蓬勃發(fā)展.從20世紀８0年代中期開始，關系型數(shù)據(jù)庫技術和新型技術的結合成為數(shù)據(jù)庫研究和開發(fā)的重要標志。２0世紀90年代，數(shù)據(jù)挖掘與知識發(fā)現(xiàn)應運而生。數(shù)據(jù)挖掘是一個多學科交叉研究領域，它融合了數(shù)據(jù)庫技術、人工智能、機器學習、統(tǒng)計學、知識工程、面向對象方法、信息檢索、高性能計算以及數(shù)據(jù)可視化等最新技術的研究成果?；诮y(tǒng)計學、人工智能、面向對象方法等在內的理論與技術成果已經被成功的應用到商業(yè)處理和分析中，這些應用從某種程度上為數(shù)據(jù)挖掘技術提出和發(fā)展起到了極大的推動作用。然而,作為人工智能系統(tǒng)研究的三大主流學派,結構主義、功能主義、行為主義方法各自在信息智能決策中取得了不少的進展和成果，但卻是計算機科學研究中爭議最多而又始終保持強大生命力的研究領域。在這樣的背景下，我國著名信息學者、全信息創(chuàng)始人鐘義信教授提出智能系統(tǒng)智能生成的共性核心機制:信息—知識－智能的轉換.“信息—知識-智能的轉換”的研究方法將能夠更好地為智能理論研究服務，在社會走向信息化和智能化的時代將為人類做出更大的貢獻.研究的目標和主要內容(不少于400字）本選題將數(shù)據(jù)挖掘與機器知行學相結合,通過關聯(lián)規(guī)則挖掘算法，從事務數(shù)據(jù)庫中挖掘知識，實現(xiàn)信息、知識、智能的轉換。本選題研究內容如下：(1）對信息、知識、智能的轉換理論體系結構及數(shù)據(jù)挖掘原理的應用進行探究.（2)關聯(lián)規(guī)則Aｐriori算法分析，Apriori算法的內容分析如下：１）關聯(lián)規(guī)則挖掘實現(xiàn)的基本思路:關聯(lián)規(guī)則是用來揭示數(shù)據(jù)之間未知的相關依賴關系，通過設置支持度和置信度，生成所需要的數(shù)據(jù)信息。２）Apｒioｒi算法的實施思想：掌握Ａpｒiorｉ算法運算的基本思想，是實施Apriorｉ算法應用實現(xiàn)的基礎。3）Aｐriorｉ算法性能的分析：了解Ａpriｏｒi算法的優(yōu)點和不足，為算法的改進優(yōu)化具有重要意義。４）Aprioｒi挖掘算法的實現(xiàn)：根據(jù)關聯(lián)規(guī)則Apｒiｏｒi挖掘算法的描述，用VｉsuａｌC+＋編譯器編寫Aｐｒioｒi算法代碼，并于一例子中實現(xiàn)。5）對具有語義最小支持度的關聯(lián)規(guī)則挖掘方法的探討：傳統(tǒng)的關聯(lián)規(guī)則挖掘算法大都依賴于一個統(tǒng)一的支持度和置信度閾值設置，在此基礎上所挖掘出的結果有很多是沒有任何意義或是錯誤的關聯(lián)規(guī)則。如何引入具有語義最小支持度對算法做相應的改進，是舍棄無效的、虛假的、具有誤導性的規(guī)則起輔助作用，增強了決策功能。擬采用的研究方法查閱相關資料,借助機器知行學的思想和數(shù)據(jù)挖掘技術對關聯(lián)規(guī)則Aｐrｉori算法進行分析。使用ＶisualC＋+編譯器編寫代碼，實現(xiàn)Ａpｒioｒi算法。研究工作的進度安排２01０年11月２４號-11月30號與指導老師溝通交流,完成畢業(yè)論文選題;20１０年1２月1號－１2月31號搜集資料,查閱文獻，完成開題報告;?20１1年1月1號—1月3１號完成文獻綜述，定出算法的需求分析案例; ２011年2月1號—2月２８號整理相關資料并完成概要和詳細設計；?201１年3月1號—４月3０號扼寫及整理修改初稿； 2011年5月1０號—5月3１號總結畢業(yè)設計的整個過程，完成畢業(yè)設計論文初稿;20１１年６月1號—6月3號定稿，打印裝訂，參加答辯；參考文獻目錄(作者、書名或論文題目、出版社或刊號、出版年月日或出版期號)［1]毛國君，段立娟,王實，石云.數(shù)據(jù)挖掘原理與算法［Ｍ］.北京:清華大學出版社，20０7．12[2］何宏.關聯(lián)規(guī)則挖掘算法的研究與實現(xiàn)[Ｄ]。湖南:湘潭大學,２00６：4７－50[３]紀希禹,韓秋明,李微,李華鋒。數(shù)據(jù)挖掘技術應用實例［M］．北京:機械工業(yè)出版社,２0０9［4］陳競.基于數(shù)據(jù)挖掘技術的零售業(yè)精確營銷應用研究[J]。中國市場，201０，14:１6－１8［５］張玲玲,李軍，石勇,周琳.基于數(shù)據(jù)挖掘的智能知識管理模型構架研究［J].中國管理科學，２00９，17（１０)：６20－６2４［6］宮鐵峰,髙劍平,韓慧君.基于全信息的智能決策支持系統(tǒng)研究［J］．上海海運學院學報,１９９6，17(2)：84—89［7］張磊，夏士雄，周勇，牛強。具有語義最小支持度的關聯(lián)規(guī)則挖掘方法[J］.微電子學與計算機，２0０8,25(9)：１４－17[8］謝康林，葉瑾,周瑞凌。在數(shù)據(jù)倉庫中進行基于在語義層次的關聯(lián)規(guī)則挖掘［J］．小型微型計算機系統(tǒng)2００3，24（1）：58－60［9]Ｋ.P.Somaｎ,ShyaｍＤiwakaｒ,Ｖ。Aｊaｙ[印度］．數(shù)據(jù)挖掘基礎教程［M］。范明,牛常勇譯.北京：機械工業(yè)出版社,20０９［10］鐘義信.機器知行學原理：信息、知識、智能的轉換與統(tǒng)一理論[M]．北京：科學出版社，2０07指導教師意見簽名：年月日教研室主任意見簽名:年月日PAGE6目錄TOＣ＼o＂1—3"\h＼z\uＨYPEＲLINＫ\l”＿Toc２947０8304＂[摘要]?ＰAＧEREF＿Toc294７０830４\h1ＨYPERＬINＫ＼ｌ＂_Tｏｃ2９47０8305"［關鍵字］?PAGEＲEF_Ｔoc29４70８30５\h１HYPERＬINK\ｌ”＿Tｏｃ２94708３06＂引言 ＰAＧEREF_Toｃ29４7０8306\ｈ１HYPＥRLINK＼l＂_Ｔｏc２９4708307”１信息、知識、智能轉換的統(tǒng)一理論 PAGEＲＥF_Ｔoc2９４7０8３07＼h２HＹPＥRLＩNＫ＼l"_Toc29470８３０8＂1．1信息、知識、智能簡要概述 ＰAＧERＥF_Tｏc２９4７08３08＼h２HＹPERLINＫ\ｌ"＿Ｔoc2９4708３０9"１。１。1信息的基本概念?PＡＧEＲEF_Toc2９４7０83０9\ｈ2ＨYＰEＲLINK\l”＿Toc2９４708310"1.１．2知識的基本概念?PAＧＥREF＿Tｏc29４70８3１0\ｈ2HＹPERLINK\ｌ”_Toc294708311＂1.1．3智能的基本概念?PAＧEＲEF＿Toｃ２94７０８311\h2HＹPEＲLINK\l＂＿Toｃ2９47０8312＂1。２信息、知識、智能的轉換機制?ＰAGEＲEF_Toｃ２94708312\h２HＹPERLINK＼ｌ＂_Ｔｏc294７0８313＂2數(shù)據(jù)挖掘和知識發(fā)現(xiàn)?ＰAＧERＥF_Toｃ2９4708３13＼h3ＨYPＥRLINK\l”_Toｃ２9４７０8314＂２．1數(shù)據(jù)挖掘和知識發(fā)現(xiàn)的概念?PＡGEREF＿Ｔoc29４70831４\h３ＨYPERLＩNK\l”_Toc2９4７08315”2.１.１數(shù)據(jù)挖掘的基本概念 PAGEREＦ＿Toc294７08３15\ｈ3HYPＥRLINＫ２。2數(shù)據(jù)挖掘的分析方法?PAGEＲＥF_Ｔoc2９４７08317＼h4HYPEＲLＩNK\l”＿Tｏｃ２947０8３18"２.3知識發(fā)現(xiàn)的過程步驟及技術?ＰAGERＥＦ＿Ｔoc２9470８31８＼h4HＹPＥＲLINK＼ｌ”_Toc29４7０8３１9"２．３。1知識發(fā)現(xiàn)過程的步驟?PＡGEREＦ＿Tｏc2９４7０8３19＼ｈ4ＨYPERＬINＫ\l”_Tｏc29４708３20”2．3。2知識發(fā)現(xiàn)技術?ＰＡＧEREF＿Tｏｃ2９4708３20＼h5HYＰERLＩNK\l"_Toc2９470832１”3數(shù)據(jù)挖掘算法分析?ＰAＧEＲＥF_Ｔｏｃ294７０8321\h6HYＰERLIＮＫ＼l"＿Ｔoｃ２947０８322”3.1關聯(lián)規(guī)則挖掘算法基本概述 PAＧＥREF_Tｏｃ29４7０8322\h6HYＰERLIＮＫ＼ｌ＂＿Toc2947０83２3＂3.２Apriori算法基本原理與優(yōu)化分析?ＰAGEＲEＦ_Ｔoc２9470８323\h６ＨYPERLINK\ｌ”_Toc２94７08３２４＂3.2。1Ａｐｒioｒi算法基本原理?PAＧEREF＿Toc2９47０83２4\h6HYＰERＬINＫ＼l"_Ｔｏc2９４7０8３25＂3。2.２Ａｐrｉori算法優(yōu)化分析?PAGEREＦ_Tｏｃ２947０8３２5＼h8HＹPEＲLINK＼l”_Toｃ29470８3２6”3。3Aprioｒｉ算法的實現(xiàn)與應用?ＰAGERＥＦ_Ｔoc29470８３2６\h9HYPEＲLＩＮＫ\l＂_Ｔoc２94７０8327”３．３。1Ａpriｏｒi算法的實現(xiàn)?ＰＡGEREF＿Toc2９4７０8３27\h９HYPEＲLIＮK\ｌ”_Ｔoc294708328”3.3．2Ａprｉorｉ算法在購物籃中的應用?PＡＧＥＲＥF_Ｔoc2９470832８＼h13ＨＹPＥRLINK\ｌ"_Toｃ2９４7083２９＂4具有語義最小支持度的關聯(lián)規(guī)則挖掘方法?PＡＧEＲEF＿Ｔoｃ294７08329＼h14HYPEＲLIＮK\l”＿Toc2９470８３30＂5小結 ＰAGEＲＥＦ＿Ｔｏｃ２9４70８３３0＼ｈ15ＨYPEＲＬINK\l＂_Toc2947０833１"參考文獻 PAＧＥRＥF＿Tｏc2９４708３３1\ｈ16HYＰERＬINK\l”_Tｏｃ２9４７0833２”[Aｂｓtraｃt]?PAGＥRＥＦ_Ｔoｃ2947０8332\h16HＹPERLIＮK人工智能、HYPＥＲＬINK＂httｐ:／／wｉｋi。mbalｉｂ．ｃom/ｗiki／％Ｅ４％BF％Ａ１％E6％８1％AF％E６%A3％８０%Ｅ７%B4％Ａ2＂＼o＂信息檢索"信息檢索、數(shù)據(jù)庫、HYPEＲＬIＮＫ”http：／/ｗｉki。mbaliｂ.coｍ/wiｋi/%E７％ＢB％9F％E８％AE％Ａ1％Ｅ5％ＡD%A６”\ｏ＂統(tǒng)計學”統(tǒng)計學、模糊集和HYPERＬＩNＫ”httｐ://ｗiki。ｍbａlｉb。cｏm/wiｋｉ/%E7％B2%97%E７%Ｂ3％99％E9％9Ｂ％86”＼ｏ"粗糙集”粗糙集理論等領域中發(fā)展來的。典型的基于算法的知識發(fā)現(xiàn)技術包括：或然性和最大可能性估計的貝葉斯理論、衰退分析、最近鄰、HＹPＥRＬＩＮＫ＂hｔtｐ：//wiki．mｂ/wｉki/％E５%８６％B3％E7%AＤ％９６%E6％A0%9１＂\o”決策樹”決策樹、K一方法聚類、關聯(lián)規(guī)則挖掘、Wｅｂ和ＨYPERLINK”htｔp：／/ｗiki。mbaｌib。cｏm/wikｉ/%E6%90%９C％E７％Ｂ4%A2%E５%BC%9５％E6％９3%8E＂＼o”搜索引擎”搜索引擎、ＨYPERLINK”htｔp://wiki.mｂaliｂ.ｃoｍ/ｗiki/%E６％９5％B0％E6%8D％AE%E４％BB%９3%E5%BA%93”\o"數(shù)據(jù)倉庫”數(shù)據(jù)倉庫和HYPＥRLIＮK＂http：/／wｉki．mbalｉ/ｗｉki/%E8%81%９4％E6％９Ｃ％ＢA%E５％8８%8６%E６%9E%9０％E５％A4%84％E7％90％86＂\o"聯(lián)機分析處理"聯(lián)機分析處理(On—lineAｎalytｉcａlＰroｃeｓsiｎg，OLAP）、HＹPERLINK＂hｔｔｐ:／/wiki。mbalｉb．ｃｏm/wiki/%E7％A５%9E%E７％ＢＢ％８F％E7％ＢD%91％E7%BB％９C”\o"神經網絡＂神經網絡、ＨYＰERＬINＫ"hｔtｐ://ｗiki.ｍbａ/wiki/%E9%８1%97%Ｅ4%BＣ%A0％Ｅ７%ＡE％９７%E6%B３％95"\o＂遺傳算法"遺傳算法、模糊分類和聚類、粗糙分類和規(guī)則歸納等。3數(shù)據(jù)挖掘算法分析3。1關聯(lián)規(guī)則挖掘算法基本概述Ａgrawａl等人于1９93年首次提出了關聯(lián)規(guī)則挖掘,最初的動機是針對購物籃分析（BasketAnalysｉｓ）問題提出的，其目的是為了發(fā)現(xiàn)交易數(shù)據(jù)庫中的不同商品之間的相關關系。之后，諸多的研究人員對關聯(lián)規(guī)則的挖掘問題進行大量的研究，用來揭示數(shù)據(jù)之間未知的相關依賴關系，它是數(shù)據(jù)挖掘中最為活躍的研究方法之一。一個事務數(shù)據(jù)庫中的關聯(lián)規(guī)則挖掘可以描述如下：設Ｉ＝｛，，.。．，｝是一個項目集合，事務數(shù)據(jù)庫Ｄ＝｛,,..。，}是由一系列具有唯一標識TID的事務組成，每個事務（i=１,2，.．．，n)都對應I上的一個子集。設?Ｉ，項目集在數(shù)據(jù)集D上的支持度(Ｓuｐpoｒt）是包含的事物在Ｄ中所占的百分比,即sｕｐpｏｒｔ()=｜|｛t∈Ｄ|?t｝|｜/｜｜D||。對項目集Ｉ和事務數(shù)據(jù)庫D，T中所有滿足用戶指定的最小支持度的項目集,即大于或等于最小支持度的Ｉ非空子集,稱為頻繁項目集或者大項目集。在頻繁項目集中挑選出所有不被其它元素包含的頻繁項集稱為最大頻繁項目集或最大項目集。一個定義在Ｉ和D上的形如的關聯(lián)規(guī)則通過滿足一定的可信度或置信度(Cｏnfｉdence)來給出?？尚哦仁侵赴偷氖聞张c包含的事務數(shù)之比,即Ｃｏｎfｉdence（）＝ｓupport(∪）／ｓuppｏｒt（），其中,?Ｉ;∩＝Ф。把D在I上滿足最小支持度和最小置信度的關聯(lián)規(guī)則稱為強關聯(lián)規(guī)則。通過用戶給定的最小支持度，尋找所有頻繁項目集,即滿足支持度不小于最小支持度的所有項目子集.發(fā)現(xiàn)所有的頻繁項目集是形成關聯(lián)規(guī)則的基礎，在此基礎上尋找置信度不小于最小置信度則是生成關聯(lián)規(guī)則。3。２Aｐrｉori算法基本原理與優(yōu)化分析３．2．1Apriori算法基本原理Ａpriori算法是一個基于兩階段頻集思想的方法,關聯(lián)規(guī)則挖掘算法的設計可以分解為兩個子問題：(１)找到所有支持度大于最小支持度的項集（Iｔｅmseｔ),這些項集稱為頻集（FreｑuｅntIｔｅｍset）。（2)使用第1步找到的頻集產生期望的規(guī)則.具體地說，在第一次循環(huán)時，經掃描數(shù)據(jù)庫得到1階頻繁集，在之后的第k(ｋ>１)次循環(huán)中，對第k—1階頻繁項集Lk—１實施Apriro＿geｎ運算生成ｋ階侯選集Cｋ。再次掃描數(shù)據(jù)庫,得到Cｋ的支持度，從而得到Cｋ中支持度不小于最小支持度的ｋ階頻繁項集Ｌk.重復以上步驟,直到某一階的頻繁項集為空時算法停止。為生成所有頻繁項集，Ａpｒioｒi使用了遞推的方法，其核心思想是：（1）

L1

=fｉnd_ｆreｑｕeｎｔ＿１-iｔemｓets(Ｄ)；(2)ｆｏｒ(k＝2；Ｌk—1

≠Φ;ｋ＋＋){(3）

Ck

=apｒiｏｒi_ｇen（Lｋ－1

,mｉn＿ｓup);（４)

foreａchtｒａnsactiｏnt∈

D

{／／scaｎDforcounts（5)

Cｔ

＝ｓuｂｓｅt(Ｃk，t）；//getthｅsｕbsｅtsｏftthataｒecaｎdidａt(yī)ｅs(６)

ｆｏｒeａchｃandiｄateｃ∈Ct(７)

c．ｃｏunｔ++;（8）

}（９)

Lk

=｛ｃ∈Ｃk|c．ｃｏunt≥miｎ_ｓup｝（１0）

｝（1１)ｒeｔuｒnＬ=∪

ｋ

Lk；如何利用Lk和如何找到Lk是Aprｉｏｒｉ的關鍵所在，主要有如下兩個步驟：（1)連接步.為找Lｋ，通過Ｌk—1與自己連接產生侯選k—項集的集合。該侯選項集的結合記作Cｋ。（2）剪枝步。Ｃｋ是Lｋ的超集，即它的成員可以是也可以不是頻繁的，但所有的頻繁k-項集都包含在Ｃk中。發(fā)現(xiàn)頻繁集中調用了apriorｉ-ｇeｎ（Ｌk-１），是為了通過（k-1)—頻繁項集產生Ｋ-候選集。產生候選集可以描述如下：（1）FORaｌlitemsｅｔp∈Lk－1DＯ(2）FORａllitｅmsｅｔq∈Lk—1DO（3)ＩＦp．iteｍ1＝ｑ．ｉｔｅm1,p。ｉtｅm２=q。iteｍ2，…，p．iｔemｋ-2=q。ｉtemk－２,p.itemｋ—1q.itemｋ－1THＥNBEGI（4）c=ｐ∞q;（5）IFｈas＿infｒequｅnt_subsｅｔ(ｃ,Lk-１）ＴHEN(6）ｄｅletｅｃ；（7）EＬSＥaddｃｔoCk；（8）EＮＤ(9）ＲeturnCk；根據(jù)Ａgrａwal的項目集格空間理論，含有非頻繁項子集的元素不可能是頻繁項目集，候選集生成算法中調用了has＿ｉｎfｒequeｎt_ｓｕbsｅｔ（c,Lk－1)，是為了判斷ｃ是否需要加入到候選集中,以便及時裁減那些含有非頻繁項集子集的項集,以提高效率.判斷候選集的元素算法描述如下:（１）ＦＯRall(ｋ—1)—sｕbsｅtsofcＤO（2）IFS￠Lk—１THENReturnTRＵE；(3)RｅｔuｒｎFＡLＳＥ；Apｒiorｉ算法是通過項集元素數(shù)目的不斷增長來逐步完成頻繁項目集的發(fā)現(xiàn)，在得到所有頻繁項集后，從給定的頻繁項集中生成強關聯(lián)規(guī)則.強關聯(lián)規(guī)則算法可以描述如下:Rｕlｅ—genｅｒate(Ｌ，ｍｉnconｆ)(1）FOReaｃｈｆrｅquentitemsｅtｌＫiｎL（2）ｇeｎｒules（ｌｋ，lk）；該算法的核心是geｎrules遞歸過程，它實現(xiàn)一個頻繁項集中所有強關聯(lián)規(guī)則的生成。３。2.2Apriori算法優(yōu)化分析雖然Ａpriori算法自身已經進行了一定的優(yōu)化，但是在實際的應用中,還是存在不令人滿意的地方，于是人們相繼提出了一些優(yōu)化的方法:（1)

基于劃分的方法。Sａvaｓere等人設計了一個基于劃分（ｐaｒtition）的算法，這個算法先把數(shù)據(jù)庫從邏輯上分成幾個互不相交的塊，每次單獨考慮一個分塊并對它生成所有的頻集，然后把產生的頻集合并,用來生成所有可能的頻集，最后計算這些項集的支持度。這里分塊的大小選擇要使得每個分塊可以被放入主存，每個階段只需被掃描一次。而算法的正確性是由每一個可能的頻集至少在某一個分塊中是頻集保證的。上面所討論的算法是可以高度并行的,可以把每一分塊分別分配給某一個處理器生成頻集。產生頻集的每一個循環(huán)結束后,處理器之間進行通信來產生全局的候選k-項集。通常這里的通信過程是算法執(zhí)行時間的主要瓶頸；而另一方面,每個獨立的處理器生成頻集的時間也是一個瓶頸。其它的方法還有在多處理器之間共享一個雜湊樹來產生頻集。（2）基于hａｓｈ的方法。一個高效地產生頻集的基于雜湊（ｈash)的算法由Paｒｋ等人提出來。通過實驗可以發(fā)現(xiàn)尋找頻集主要的計算是在生成頻繁2—項集Lk上，Park等就是利用了這個性質引入雜湊技術來改進產生頻繁２—項集的方法。(3)基于采樣的方法。基于前一遍掃描得到的信息,對此仔細地作組合分析，可以得到一個改進的算法，Mannila等人考慮了這一點,他們認為采樣是發(fā)現(xiàn)規(guī)則的一個有效途徑。隨后又由Toivoneｎ進一步發(fā)展了這個思想，先使用從數(shù)據(jù)庫中抽取出來的采樣得到一些在整個數(shù)據(jù)庫中可能成立的規(guī)則,然后對數(shù)據(jù)庫的剩余部分驗證這個結果。Toivonｅn的算法相當簡單并顯著地減少了Ｉ/Ｏ代價，但是一個很大的缺點就是產生的結果不精確，即存在所謂的數(shù)據(jù)扭曲(dａt(yī)ａｓkew）。分布在同一頁面上的數(shù)據(jù)時常是高度相關的,可能不能表示整個數(shù)據(jù)庫中模式的分布,由此而導致的是采樣５％的交易數(shù)據(jù)所花費的代價可能同掃描一遍數(shù)據(jù)庫相近。Lｉn和Duｎhaｍ討論了反扭曲（Anti—ｓｋew)算法來挖掘關聯(lián)規(guī)則，他們引入的技術使得掃描數(shù)據(jù)庫的次數(shù)少于2次,算法使用了一個采樣處理來收集有關數(shù)據(jù)的次數(shù)來減少掃描遍數(shù)。Bｒｉｎ等人提出的算法使用比傳統(tǒng)算法少的掃描遍數(shù)來發(fā)現(xiàn)頻集,同時比基于采樣的方法使用更少的候選集，這些改進了算法在低層的效率.具體的考慮是，在計算k-項集時,一旦我們認為某個（k+１)-項集可能是頻集時,就并行地計算這個(k+1)－項集的支持度，算法需要的總的掃描次數(shù)通常少于最大的頻集的項數(shù)。這里他們也使用了雜湊技術，并提出產生“相關規(guī)則”（CorrelaｔｉｏｎRules）的一個新方法，這是基于他們工作基礎上的。(４）減少交易的個數(shù),減少用于未來掃描的事務集的大小。一個基本的原理就是當一個事務不包含長度為k的大項集，則必然不包含長度為ｋ+1的大項集。從而我們就可以將這些事務移去，這樣在下一遍的掃描中就可以要進行掃描的事務集的個數(shù)。這個就是AprｉoriTid的基本思想。3。３Ａｐrｉｏｒi算法的實現(xiàn)與應用3。３．1Apｒioｒｉ算法的實現(xiàn)根據(jù)Aprioｒｉ算法的思想，用ＶC++編輯器編寫代碼的相關步驟如下:(１)對函數(shù)進行聲明:＃ｉncｌude〈iostream。ｈ>#inclｕde〈ｓtｄlib．ｈ〉＃inｃlｕdｅ＜ｆsｔrｅam。h〉（2）定義一個無類型有返回值的suｍ函數(shù)；n,m,s為整型變量，分別表示事務數(shù)、項數(shù)和支持數(shù)；d是雙精度型;h表示有多少個項，K表示是第幾個頻繁項集,y表示前有多少項規(guī)則，qian存前件，hoｕ存后件,ｃrｅdiｔ存置信度。voｉdsum（inｔt[3０][２0］）;iｎtget(intt[30]［2０］，iｎta［1０0］［２0]，iｎtb［1０0]［２0]，iｎtk0，ｉｎtk，ｉｎtｈ)；intｊield（iｎｔt[3０］[２0],intl[１０0］[２０］，intk，iｎth，inｔｑiaｎ［5０］［１0],iｎthｏu［５0][1０],ｉｎｔy,ｄｏｕblｅｃｒedit[5０］）；ｉｎｔｎ,m;dｏｕbｌes，ｄ；(３)定義一個不返回任何值得主函數(shù)voidｍａｉn（)。在函數(shù)里，每個行數(shù)組中的第一個用來計數(shù)，如：ｔ[1］［0］＝3表示第二行有三個元素;ck［i］用于記錄一個集中有多少個頻繁項集;k1用于記錄L１中項數(shù);l［ｋ］［0］表示第一項存出現(xiàn)次數(shù)，tｏtal為頻繁項集的總計數(shù)。(4）生成頻繁項集函數(shù)：inｔｇet(iｎtt［3０］［2０]，ｉntａ［1０0][2０］,ｉntb[100]［20],ｉntｋ0，intk，intｈ）{?／/ko表示L中前K-2一共有多少項,表起點;Ｋ表示Ｋ—1上一次有多少項,H表示L中有幾位數(shù)有用?if（ｋ=＝0)ｒｅtuｒn（0)；?ｉｎｔab［100］[20］;iｎｔi，j，ｐ，q,m1，x,y，k１，z，z1;?y=0;//用于記數(shù)產生了多少條項集?z=0；／/用于記錄有用的項集 ｉntc［1００]；/／計數(shù)inｔdｃh［1０0］；?intｂiao［１００]；?for（i=0;ｉ<100;ｉ++）?{?ｃ[ｉ]＝0；?dcｈ［i］=0；ｂiaｏ[ｉ]=０；｝?foｒ（ｉ=ｋ０；i<k０+k;i＋＋)? ｆoｒ（j=i＋1;j〈ｋ０+k；j＋+) ?{?ｆoｒ（k1＝0；k１〈１00；k1＋+）{ c［ｋ1］=0；｝???m1＝0;???for（p=1;p〈h;p＋+)? ?{? ??foｒ（q=１;q<h;q++）?? ?｛? ?? if（a[ｉ］［p]＝＝ａ［j］［ｑ］）? ???{??????m1＋+；c［q］=1;?? ? }????}???｝???ｉf（m1＝=h-2）???{//第一項存出現(xiàn)次數(shù)????fｏｒ(ｘ=1;x<h;x+＋)??? ab［ｙ］［x］=a［i］［x］；? ??ｆor（x=1；x＜h；x++)? ?if（c［x］＝=0）ａb［ｙ］［h]=ａ[ｊ］[x]；y++;???｝??}? fｏr(k1=0；ｋ１＜y;k１++)??{?? ｚ1＝0；?? foｒ(ｉ=0；ｉ＜n;ｉ++） {????z=0;??? ｆor（ｊ=1;j〈=ｈ；j+＋) ???{ ?? ｆｏｒ（x=１；ｘ＜=t［ｉ]［0］；x++）? ??{??? ??iｆ(ａｂ［k1］［j］==ｔ[i]［ｘ]) ? ??{ｚ＋+;breaｋ；} ? ??｝????｝????ｉf(z=＝ｈ）z１＋+；???}???if(ｚ1>＝s）{dcｈ[ｋ1]=１;｝ab［k1][0]=z1;??}for（i=0；i<y；ｉ++) {??fｏr(ｊ=i+１；ｊ<y;j++） ?｛? ?m1=0；???ｆoｒ（p＝1；p＜=ｈ；p＋+）? ?｛????for(ｑ=1；ｑ＜=ｈ；q＋+) ? ?｛ ????if（ab［ｉ][p]==aｂ［j][q］）??? ?｛??????m1++； ????}?? ?｝???}if（ｍ1==ｈ）???｛ ???ｂiao［j］=1； ??｝??}?}?ｘ＝ｋ+ｋ0；z＝0; ｆor（i＝0；i<y;ｉ+＋)?if(dｃh［i]＝=1＆&biao[i］==0) ｛? ｆor(j=0；j〈=ｈ；ｊ+＋) ?{b[x］［j]=ａb［i］[ｊ］; ?}??ｚ++;x++; ｝reｔuｒnｚ;｝（５）對jielｄ函數(shù)作出相應的設置，統(tǒng)計ｎ、ｍ的值，推出關聯(lián)規(guī)則.（相應的代碼省略）3．3。2Ａｐrｉori算法在購物籃中的應用通常，我們將客戶一次購買商品的總和稱為一個購物籃。在零售行業(yè)中,我們可以把關聯(lián)規(guī)則和Ａpriｏｒｉ算法應用于研究顧客購物籃中，以期發(fā)現(xiàn)顧客購物規(guī)律。一個購物籃就是一張收款小票，購物小票就是購物籃分析的一個重要依據(jù)。一張購物小票包含3個層面的含義：購買商品的客戶、購物籃的商品和購物籃的金額.在數(shù)據(jù)分析行業(yè)中，將購物籃的商品相關性分析稱為“數(shù)據(jù)挖掘算法之王",可見購物籃商品相關分析算法的重要性。對購物籃分析即從購物籃的商品相關度分析入手，表３－1為購物數(shù)據(jù)內容。表３—1購物內容Ｃlaｓｓ（商品名稱）Price(單價／元）Ｓum（購買總數(shù)）面包3．50300果凍２．80６00………花生醬８.８０400牛奶4.0060０………啤酒4。5０50０可樂3.０0１00由于本次挖掘只是針對購物籃的商品相關性進行分析,不進行多層的關聯(lián)規(guī)則挖掘，因此不必進行概念分層及數(shù)據(jù)離散化處理。隨機搜取4個購物籃，５個項數(shù)作為采點數(shù)據(jù),模擬實驗樣本數(shù)據(jù)如表3－2。表３—2模擬實驗樣本數(shù)據(jù)購物籃編號項目集支持度計數(shù)代號A1、3、4３“1”表示面包，“２”表示果凍,“3”表示花生醬，“4”表示牛奶“5”表示啤酒B２、3、5３C1、２、3、5４Ｄ2、52為了了解商品間的關聯(lián)關系,顧客買了果凍是否就一定會買啤酒。要求挖掘出支持度大于等于60％、置信度大于等于8０%的商品間的關聯(lián)。結果如圖3—１所示。圖３—1Ａpｒiori算法設計實現(xiàn)結果從圖３—１可以看出,在購物數(shù)據(jù)樣本模擬實驗中，發(fā)現(xiàn)了以下規(guī)則：顧客如果購買面包（花生醬、啤酒或果凍、花生醬），那么購買花生醬（果凍或啤酒）的可能性是１00%；如果,顧客購買果凍,那么購買啤酒的可能性是10０%；反之,如果顧客購買啤酒，那么購買果凍的可能性是100%。由此可以得出:該商城在商品排放策略上應該將啤酒、果凍、花生醬的貨架相鄰擺設。4具有語義最小支持度的關聯(lián)規(guī)則挖掘方法傳統(tǒng)的關聯(lián)規(guī)則挖掘算法大都依賴于一個統(tǒng)一的支持度和置信度閾值設置，項目的最小支持度是限制關聯(lián)規(guī)則產生的數(shù)量的主要因素.可是事件在現(xiàn)實中發(fā)生和存在頻度上有很大的不一致性，始終保持單一的最小支持度顯然是不合理，就此問題，人們采用多個支持度的關聯(lián)規(guī)則方法來解決單一支持度的不可靠問題。然而馬占欣等人則提出加入項集之間的“相關度”來對關聯(lián)規(guī)則的挖掘進行約束。以下將語義信息引入關聯(lián)規(guī)則挖掘之中，提出了具有語義最小支持度的關聯(lián)規(guī)則挖掘。設Ｉ={，，.．．，｝為數(shù)據(jù)中所有項的集合，（1≤j≤ｎ）為數(shù)據(jù)集中的項目,每一個項目均為本體中的一個概念。給定數(shù)據(jù)集ＤB＝{,，。。。，｝，DB表示所有事務的集合，每個事務包含的項集都是Ｉ的子集。設項目集X是事務的子集,項目集X的支持度計算為：Ю(Ｘ)=｜|Ｘ?｜∈T｜。設X、Y?I，且X∩Y=Ф,則ＸＹ為關聯(lián)規(guī)則，該規(guī)則的支持度用Ｓ表示，可信度用C表示。Ｓ(ＸY）=｜{t｜ｔ包含Ｘ和Y}｜/｜DB｜C(ＸY)=｜｛t｜ｔ包含Ｘ和Y｝|/|ｔ｜ｔ包含X}｜具有語義最小支持度的關聯(lián)規(guī)則挖掘是找到支持度大于語義最小支持度，可信度大于最小可信度的關聯(lián)規(guī)則。本體為元組Я＝（C,H，Rｏｏt,RT，Ｒ,I)。C表示概念集合;Ｈ表示概念層次集合，H?C×Ｃ，（，)∈Ｈ表示為的字概念，Ｈ為有向無環(huán)圖；Rｏoｔ為本體的根概念;ＲT為語義關系類集合，RＴ={SaｎｅAｓ，DisｊointＷitｈ，Equｉvａｌent};Ｒ表示概念之間的非層次關系集合,R?Ｃ×C;（,）∈R表示概念、之間存在關系，∈RT;其中，doｍain（)=,ranｇe()=；I表示概念實例集合，概念c∈C的實例集合記為I(ｃ），|I（c)|表示概念實例的數(shù)目。對于項目，∈Ｉ，ｐ≠ｑ，計算其在本體中的概念語義相關度CR（,），對于項集P＝（，，…，）,其語義相關度記為Ｓｅm（P):對于項目集=｛，,…,，｝，設項目集Ｐ的語義最小支持度為：＝MIＮ+（MAX—ＭIN)×（1—Ｓem(P）)。其中,MIＮ，MAX分別為支持度下限和上限.具有語義相關支持度的關聯(lián)規(guī)則挖掘算法采用和語義相關的支持度，對于候選集，首先計算候選集的語義相關度,而后根據(jù)語義相關度計算出每個候選集對應的最小支持度.5小結信息到知識、知識到智能的轉換過程非常復雜.當前，國內外探究機器知行學理論還屬于起步階段，沒有通用性的算法和可操作性強的技術支撐,但是通過借鑒數(shù)據(jù)挖掘和知識發(fā)現(xiàn)的相關技術，可以將信息、知識、智能的轉換效益在商業(yè)中應用。而Ａpriｏｒi作為經典的頻繁項集生成算法,在數(shù)據(jù)挖掘中具有里程碑的作用,但多次掃描事務數(shù)據(jù)庫需要很大的I/0負載，可能產生龐大的候選集性能瓶頸。探索新的理論和算法來減少數(shù)據(jù)庫的掃描次數(shù)和候選集空間的占用，采用并行挖掘、增加關聯(lián)規(guī)則約束參數(shù)等方式提高挖掘效率等已成為關聯(lián)規(guī)則挖掘研究的熱點之一.參考文獻［1］毛國君，段立娟，王實，石云．數(shù)據(jù)挖掘原理與算法[M］．北京：清華大學出版社,２０07。１２[２]何宏．關聯(lián)規(guī)則挖掘算法的研究與實現(xiàn)［D］。湖南:湘潭大學，20０６：47—5０[3]紀希禹，韓秋明，李微,李華鋒。數(shù)據(jù)挖掘技術應用實例［M].北京：機械工業(yè)出版社，2００9[４］陳競?；跀?shù)據(jù)挖掘技術的零售業(yè)精確營銷應用研究［Ｊ].中國市場，2０1０,１４：1６－18[５]張玲玲，李軍，石勇，周琳．基于數(shù)據(jù)挖掘的智能知識管理模型構架研究［J］．中國管理科學，200９，1７（1０):6２０－62４[6］宮鐵峰,髙劍平，韓慧君?；谌畔⒌闹悄軟Q策支持系統(tǒng)研究[J］.上海海運學院學報，１996，17(2）：８4-8９[７]張磊，夏士雄，周勇,牛強.具有語義最小支持度的關聯(lián)規(guī)則挖掘方法[J]．微電子學與計算機，2００８，２5(9）：14—17［８］謝康林，葉瑾，周瑞凌。在數(shù)據(jù)倉庫中進行基于在語義層次的關聯(lián)規(guī)則挖掘[J]。小型微型計算機系統(tǒng)20０3，24(１):5８-6０［9]K．