數(shù)據(jù)挖掘技術(shù)綜述

數(shù)據(jù)挖掘技術(shù)綜述

1新一代知識基于數(shù)據(jù)的提取隨著數(shù)據(jù)庫技術(shù)的發(fā)展和數(shù)據(jù)庫管理系統(tǒng)的廣泛應(yīng)用，數(shù)據(jù)庫中存儲的數(shù)據(jù)數(shù)量急劇增加（指數(shù)增加），數(shù)據(jù)理解和數(shù)據(jù)生成之間存在著越來越大的差距。在堆積如山的數(shù)據(jù)中包含著許多待提取的有用知識,這些有用知識如同成熟的莊稼,不及時收割便會浪費,人們迫切需要新一代的計算技術(shù)和工具來幫助開采數(shù)據(jù)山中蘊藏的礦藏,并加以提煉,使之成為有用知識。于是,一個新的研究領(lǐng)域——知識發(fā)現(xiàn)應(yīng)運而生。由于蘊藏知識的數(shù)據(jù)信息大多存儲于數(shù)據(jù)庫中,因此又稱作數(shù)據(jù)庫中的知識發(fā)現(xiàn)(KnowledgeDiscoveryinDatabase)或者數(shù)據(jù)挖掘(DM——DataMining)。2工資計算的一般過程在KDD96國際會議上,根據(jù)知識發(fā)現(xiàn)研究領(lǐng)域知名學(xué)者的闡述,一個被一致接受的KDD定義表述如下:“對數(shù)據(jù)庫中蘊涵的、未知的、有潛在應(yīng)用價值的、非平凡的模式的提取”。其中,“模式”是指用高級語言表示的表達一定邏輯含義的信息,通常指數(shù)據(jù)庫中數(shù)據(jù)之間的邏輯關(guān)系(也即要發(fā)現(xiàn)的知識)。而“非平凡”則是指在KDD中,知識的發(fā)現(xiàn)過程應(yīng)具有某種不斷定性和一定的自由度。對于能夠以確定的計算過程提取的模式(如在人事數(shù)據(jù)庫中,已知職工的工資,求出職工的總工資或平均工資等問題),一般稱之為平凡知識,而平凡知識不是KDD的目標。一般地,KDD的基本原理可用如下的處理過程加以說明:(1)首先熟悉應(yīng)用領(lǐng)域的數(shù)據(jù)、背景知識,明確所要完成的KDD/DM任務(wù)性質(zhì);(2)數(shù)據(jù)選擇根據(jù)用戶要求,從數(shù)據(jù)庫中提取與KDD相關(guān)的數(shù)據(jù),KDD將主要從這些數(shù)據(jù)中進行數(shù)據(jù)提取;(3)數(shù)據(jù)預(yù)處理與轉(zhuǎn)換從與KDD相關(guān)的數(shù)據(jù)集合中除去明顯錯誤的數(shù)據(jù)和冗余的數(shù)據(jù),進一步精減所選數(shù)據(jù)中的有用部分,并將數(shù)據(jù)轉(zhuǎn)換成為有效形式,以使數(shù)據(jù)開采更有效;(4)數(shù)據(jù)挖掘(DM)根據(jù)KDD發(fā)現(xiàn)任務(wù)的要求,選擇合適的數(shù)據(jù)開采算法(包括選取合適的模型和參數(shù)),在數(shù)據(jù)庫中尋求感興趣的模型,并用一定的方法表達成某種易于理解的形式;(5)模式解釋對發(fā)現(xiàn)的模式進行解釋和評估,必要時需要返回前面處理中的某些步驟以反復(fù)提取;(6)知識評價將發(fā)現(xiàn)的知識以用戶能理解的方式提供給用戶,并試用之。從以上的處理步驟來看,整個發(fā)現(xiàn)過程不是簡單的線性流程,步驟之間包含了循環(huán)和反復(fù)。上述眾多處理環(huán)節(jié)實際上也可簡化為:KDD=數(shù)據(jù)預(yù)處理十DM十解釋評價。由于預(yù)處理和解釋評價研究較為成熟,目前KDD的研究和實現(xiàn)難點都集中在數(shù)據(jù)挖掘上。作為KDD的一個特定而關(guān)鍵步驟,數(shù)據(jù)挖掘是最為重要的。正是因為如此,人們在很多場合往往不加區(qū)分地使用KDD和DM這兩個術(shù)語。3數(shù)據(jù)庫中的常用研究算法鑒于數(shù)據(jù)挖掘?qū)τ贙DD的重要性,數(shù)據(jù)挖掘集中了研究人員的主要精力,相關(guān)的研究工作也取得了較大的進展。通常,根據(jù)發(fā)現(xiàn)任務(wù)與發(fā)現(xiàn)目標的不同,數(shù)據(jù)挖掘器所能發(fā)現(xiàn)的典型知識主要包括以下幾類:(1)關(guān)聯(lián)規(guī)則(Associationrule)所謂關(guān)聯(lián)規(guī)則,是指數(shù)據(jù)對象之間的相互依賴關(guān)系,而發(fā)現(xiàn)規(guī)則的任務(wù)就是從數(shù)據(jù)庫中發(fā)現(xiàn)那些確信度(Confidence)和支持度(Support)都大于給定值的強壯規(guī)則。從數(shù)據(jù)庫中發(fā)現(xiàn)關(guān)聯(lián)規(guī)則近幾年研究最多。目前,已經(jīng)從單一概念層次關(guān)聯(lián)規(guī)則的發(fā)現(xiàn)發(fā)展到多個概念層次的關(guān)聯(lián)規(guī)則的發(fā)現(xiàn)。在概念層次上的不斷深入,使得發(fā)觀的關(guān)聯(lián)規(guī)則所提供的信息越來越具體,實際上這是個逐步深化所發(fā)現(xiàn)知識的過程。在許多實際應(yīng)用中,能夠得到的相關(guān)規(guī)則的數(shù)目可能是相當(dāng)大的,而且,用戶也并不是對所有的規(guī)則感興趣,有些規(guī)則可能誤導(dǎo)人們的決策,所以,在規(guī)則發(fā)現(xiàn)中常常引入“興趣度”(指一則在一定數(shù)據(jù)域上為真的知識被用戶關(guān)注的程度)概念。而基于更高概念層次上的規(guī)則發(fā)現(xiàn)研究(如一般化抽象層次上的規(guī)則和多層次上的規(guī)則發(fā)現(xiàn))則是當(dāng)前研究的重點之一。在數(shù)據(jù)挖掘中,常見的關(guān)聯(lián)規(guī)則發(fā)現(xiàn)算法有:AIS、SETM、APriori、DHP、ML-T2L1、ML-TML1等,其中,Apriori和DHP是比較成功的兩個算法。(2)分類(Classification)分類是最基本的一種認知形式。數(shù)據(jù)分類就是對數(shù)據(jù)庫中的每一類數(shù)據(jù),挖掘出關(guān)于該類數(shù)據(jù)的描述或模型,而這些數(shù)據(jù)庫中的類是事先利用訓(xùn)練數(shù)據(jù)建立起來的。作為數(shù)據(jù)挖掘的一個重要主題,數(shù)據(jù)分類在統(tǒng)計學(xué)、機器學(xué)習(xí)、人工智能等領(lǐng)域中得到了較早的研究,只是近些年來,人們才將它與數(shù)據(jù)庫技術(shù)結(jié)合起來解決實際問題。在數(shù)據(jù)挖掘中,分類算法的研究成果較多,常用的數(shù)據(jù)分類算法有:CART、C45、ID3、SLIQ、Knn、GA-Knn等。(3)聚類(Clustering)在機器學(xué)習(xí)中,數(shù)據(jù)分類稱為監(jiān)督學(xué)習(xí),而數(shù)據(jù)聚類則稱為非監(jiān)督學(xué)習(xí),兩者所采用的方法相差甚遠。數(shù)據(jù)聚類是將物理的或抽象的對象分成幾個群體,在每個群體內(nèi)部,對象之間只有較高的相似性,而在不同群體之間,相似性則比較低。一般地,一個群體也就是一個類,但與數(shù)據(jù)分類不同的是,聚類結(jié)果主要基于當(dāng)前所處理的數(shù)據(jù),我們事先并不知道類目結(jié)構(gòu)及每個對象所屬的類別。另外,數(shù)據(jù)聚類計算量巨大,其時間復(fù)雜度也要比數(shù)據(jù)分類大得多。目前,數(shù)據(jù)聚類已有很多不同的方法和技術(shù),常見的算法有PAM、CLARA、CLARANS、BIRCH等。除上述主要發(fā)現(xiàn)目標外,數(shù)據(jù)挖掘所發(fā)現(xiàn)的知識類型還有特征規(guī)則、趨勢分析、異常分析、模式分析等。數(shù)據(jù)挖掘中使用的技術(shù)和方法主要來自以下相關(guān)學(xué)科和技術(shù)領(lǐng)域:(1)統(tǒng)計學(xué)統(tǒng)計學(xué)方法旨在從抽樣分析中提取未知的數(shù)學(xué)模型。在數(shù)據(jù)挖掘中常常會涉及一定的統(tǒng)計過程,如數(shù)據(jù)抽樣和建模、判斷假設(shè)以及誤差控制等。(2)決策樹(DecisionTree)決策樹方法上要用于數(shù)據(jù)分類。一般分成兩個階段:樹的構(gòu)造和樹的修剪。首先利用訓(xùn)練數(shù)據(jù)生成一個測試函數(shù),根據(jù)不同取值建立樹的分支;在每個分支子集中重復(fù)建立下層結(jié)點和分支,從而生成一棵決策樹。然后對決策樹進行剪枝處理,最后把決策樹轉(zhuǎn)化為規(guī)則,利用這些規(guī)則可以對新事例進行分類。基于決策樹的分類方法與其它分類方法比較起來,具有速度較快、較易轉(zhuǎn)化成簡單且容易理解的分類規(guī)則、較易轉(zhuǎn)換成數(shù)據(jù)庫查詢語句等優(yōu)點,尤其在問題維數(shù)高的領(lǐng)域可以得到很好的分類結(jié)果。(3)人工神經(jīng)網(wǎng)絡(luò)(NeuralNetworks)人工神經(jīng)網(wǎng)絡(luò)在結(jié)構(gòu)上模仿生物神經(jīng)網(wǎng)絡(luò),是一種通過訓(xùn)練來學(xué)習(xí)的非線性預(yù)測模型,在數(shù)據(jù)挖掘中可用來進行分類、聚類、特征采掘等操作。(4)遺傳算法遺傳算法走一種優(yōu)化技術(shù),它利用生物進化的一系列概念進行問題的搜索,最終達到優(yōu)化的目的。在遺傳算法的實施中,首先要對求解的問題進行編碼(稱為染色體),產(chǎn)生初始群體,然后計算個體的適應(yīng)度;再進行染色體的復(fù)制、交換、突變等操作,產(chǎn)生新個體。重復(fù)這個操作,直到求得最佳或較佳個體。在數(shù)據(jù)挖掘中,往往把數(shù)據(jù)挖掘任務(wù)表達為一種搜索問題,使用遺傳算法強大的搜索能力,找到最優(yōu)解。(5)粗集(RoughSet)粗集理論是一種處理含糊和不確定問題的新型數(shù)學(xué)工具,它具有較強的數(shù)學(xué)基礎(chǔ)、方法簡單、較強的針對性和計算量小等優(yōu)點。利用粗集理論可以處理的問題包括數(shù)據(jù)簡化、數(shù)據(jù)相關(guān)性發(fā)現(xiàn)、數(shù)據(jù)意義的評估、數(shù)據(jù)的近似分析等。(6)模糊邏輯(FuzzyLogic)模糊邏輯糙模糊集合與布爾邏輯的融合。一個公式的真值,可在區(qū)間任意取值。在數(shù)據(jù)挖掘和KDD中,常用來進行證據(jù)合成、置信度計算等。(7)可視化技術(shù)可視化技術(shù)采用直觀的圖形方式將信息模式、數(shù)據(jù)的關(guān)聯(lián)成趨勢呈現(xiàn)給用戶(決策者),以便用戶交互地分析數(shù)據(jù)關(guān)系。一般說來,不存在一個普遍適用的數(shù)據(jù)挖掘方法。一個方法或算法在某個領(lǐng)域非常有效,但在另一個領(lǐng)域卻可能不太適合。因此,在實際應(yīng)用中,需要針對特定的領(lǐng)域,精心選擇有效的數(shù)據(jù)挖掘模型與挖掘算法。而對于一個成功的KDD系統(tǒng),選擇合適的模型與算法常被視為是一個非常重要的技巧。4drs頁面過濾方法在個人網(wǎng)頁上的應(yīng)用—數(shù)據(jù)挖掘技術(shù)的應(yīng)用從已經(jīng)出現(xiàn)的KDD/DM原型系統(tǒng)和應(yīng)用系統(tǒng)來看,應(yīng)用KDD/DM技術(shù)的領(lǐng)域都是信息豐富、環(huán)境多變、尚無模型、需要知識幫助進行管理和決策的領(lǐng)域。例如,由美國市場研究公司A.C.Nielsen公司推出的市場預(yù)測系統(tǒng)OpportunityExplorer、通用電器公司(GE)和法國飛機制造公司(SNECMA)合作研制的飛機故障發(fā)現(xiàn)系統(tǒng)CASSIOPEE、用于醫(yī)療保健的KEFIR系統(tǒng)、監(jiān)測地殼構(gòu)造活動的Quakfinder系統(tǒng)、宇宙圖像分類分析系統(tǒng)SCICAT、基因發(fā)現(xiàn)和構(gòu)造核糖核酸模型的HAMMs和SAM系統(tǒng)、尋找最佳投資時機的AI(AutomatedInvestor)系統(tǒng),等等。上述系統(tǒng)大多基于傳統(tǒng)的數(shù)據(jù)庫技術(shù),在KDD領(lǐng)域多已取得較好的應(yīng)用效果,有關(guān)它們的詳細情況,很多期刊和會議文獻中都有介紹和分析。本文對此不打算多做論述,這里主要想對近年來數(shù)據(jù)挖掘在Web上的一些應(yīng)用研究進行說明和介紹。目前,基于Web的數(shù)據(jù)挖掘工作才剛剛起步,比較典型的幾個系統(tǒng)有:(1)Ahoy!這是一個個人主頁搜索系統(tǒng)。用戶只要輸入個人的姓名以及機構(gòu)或單位名稱等信息,Ahoy!就可以在WWW網(wǎng)上找到此人的主頁(URL)。Shakes在Ahoy!系統(tǒng)中,使用DRS(DynamicsReferenceSift)頁面過濾方法,實現(xiàn)了個人網(wǎng)頁的挖掘和較為精確的定位。其實現(xiàn)原理是:首先,根據(jù)用戶輸入的姓名等信息,DRS把它傳遞給元搜索引擎MetaCrawler,MetaCrawler查詢后,會返回許多候選主頁;DRS還同時把名字傳給E-mail目錄服務(wù)(WhoWhere和IAF),得到許多E-mail地址(以便于與機構(gòu)名對比)。然后,利用內(nèi)部數(shù)據(jù)庫,DRS采用兩種類型的過濾器(基于交叉的過濾和基于啟發(fā)的過濾)將明顯不正確的URL排除,剩下的URL則作為候選URL排列在一些稱為桶的類別中。最后,分別判斷候選的URL是否和個人姓名、機構(gòu)名匹配以及頁面和個人主頁的相似程度,從而得到最終的個人主頁。DRS最關(guān)鍵之處是它的模式抽取,即它能夠從成功的搜索結(jié)果中抽取某一國家或機構(gòu)URL的通用模式,并記錄下來,供將來使用。這種學(xué)習(xí)適應(yīng)能力,使得DRS在使用過程中,能逐步提高精確率和覆蓋面。(2)ParaSite這是一個比較簡單的WWW網(wǎng)結(jié)構(gòu)知識挖掘系統(tǒng)。在ParaSite系統(tǒng)中,Spertus把超級鏈接按方向分成這樣幾類:.向上鏈接:所指向的文檔目錄是同一服務(wù)器的上層目錄;.向下鏈接:所指向的文檔目錄是同一服務(wù)器的下層目錄;.交叉鏈接:所指向的文檔父目錄與本目錄沒有父子關(guān)系;.向外鏈接:所指向的文檔在其它的服務(wù)器。通過考察一些搜索引擎(例如Yahoo!等)的目錄結(jié)構(gòu),獲取一系列啟發(fā)性規(guī)則,如:.如果兩個URLU1和U2在同一個頁面中距離很近,那么它們有可能具有類似的主題或特征;.在一個層次索引中,從一個頁面開始,由向下或交叉鏈接得到的頁面,其主題和原始頁面的主題相關(guān):.從一個索引開始,任何由本頁面的向外鏈接得到的頁面,其主題很可能是相同的;……利用這些規(guī)則,ParaSite系統(tǒng)中的搜索器就可以得到頁面之間的結(jié)構(gòu)關(guān)系,從而實現(xiàn)發(fā)現(xiàn)個人主頁、搜索新頁面和自動索引等目的。(3)WebKBWebKB是卡內(nèi)基梅隆大學(xué)(CMU)的萬維網(wǎng)信息挖掘研究項目。它致力于建造一個大型的知識庫,這樣的知識庫能夠推動對WWW網(wǎng)更有效的信息抽取,以及對基于Web的知識推理和問題求解的支持。WebKB中提供了多種信息挖掘的方法,這些方法采用了許多比較成熟的NLP技術(shù),功能很強,既可以適應(yīng)多個特定的類別,也可以在理論上支持通用信息的挖掘,不過實現(xiàn)的難度都比較大。WebKB具有多種基本的學(xué)習(xí)能力,其采用的學(xué)習(xí)方法主要是文本分類的統(tǒng)計方法和一階文本分類方法。(4)ShophotShopbot是這樣一個系統(tǒng),它能夠針對商業(yè)網(wǎng)頁,從產(chǎn)品制造商或銷售商的主頁中提取關(guān)于產(chǎn)品的一些屬性,如價格等,通過比較,為用戶選擇一個最佳的購買商。(5)Predict(6)WebMiner這是國家自然科學(xué)基金會資助的一項研究。WebMiner的目標是實現(xiàn)一個人機交互的基于Web的數(shù)據(jù)挖掘系統(tǒng),它采掘的對象是Web上指定的某類事物,通過對該類事物領(lǐng)域知識和文本格式的學(xué)習(xí),從中提取有用的數(shù)據(jù)放到數(shù)據(jù)倉庫中,然后在數(shù)據(jù)倉庫中進行關(guān)聯(lián)規(guī)則采掘和數(shù)據(jù)分類。整個系統(tǒng)主要由五部分構(gòu)成:Web資源獲取模塊WebObtainer、Web數(shù)據(jù)過濾模塊WebFilter、數(shù)據(jù)挖掘模塊Miner以及用來進行挖掘的數(shù)據(jù)倉庫和一個領(lǐng)域知識庫。與數(shù)據(jù)庫中的信息不同,Web網(wǎng)上的信息具有無序、非結(jié)構(gòu)化、動態(tài)、多樣性等特點,有時數(shù)據(jù)源之間還可能存在冗余、不一致甚至矛盾,因此基于Web的數(shù)據(jù)挖掘工作難度很大,上述系統(tǒng)或研究項目所做的工作還都是初步的、開創(chuàng)性的。但數(shù)據(jù)挖掘技術(shù)應(yīng)用于WWW網(wǎng),特別是和Web上的搜索引擎技術(shù)的結(jié)合,無疑會對網(wǎng)絡(luò)信息的發(fā)現(xiàn)、搜集、查詢、利用等帶來巨大的效益和光明的前景。5dd/dm研究的前景展望數(shù)據(jù)挖掘是一個多學(xué)科交叉的新興研究領(lǐng)域,在這個新興領(lǐng)域中,匯集了來自機器學(xué)習(xí)、模式識別、數(shù)據(jù)庫、統(tǒng)計學(xué)、人工智能以及管理信息系統(tǒng)等各學(xué)科的成果,多元化的投入,使得這一學(xué)科得以蓬勃發(fā)展,而且已初具規(guī)模。除學(xué)術(shù)上的需要外,極大的商業(yè)應(yīng)用前景更是推動KDD/DM研究不斷深入的關(guān)鍵因