數(shù)據(jù)挖掘和知識發(fā)現(xiàn)的技術(shù)、方法及應(yīng)用
Data Mining(數(shù)據(jù)挖掘)是指用非平凡的方法從海量的數(shù)據(jù)中抽取出潛在的、有價值的知識(模型或規(guī)則)的過程。該術(shù)語還有其他一些同義詞：數(shù)據(jù)庫中的知識發(fā)現(xiàn)(Knowledge discovery in databases)、信息抽取(Information extraction)、信息發(fā)現(xiàn)(Information discovery)、智能數(shù)據(jù)分析(Intelligent data analysis)、探索式數(shù)據(jù)分析(exploratory data analysis)、信息收獲(information harvesting)、數(shù)據(jù)考古(data archeology)等。
數(shù)據(jù)挖掘的發(fā)展歷程大致如下：
◆1989 IJCAI會議： 數(shù)據(jù)庫中的知識發(fā)現(xiàn)討論專題
–Knowledge Discovery in Databases (G. Piatetsky-Shapiro and W. Frawley, 1991)
◆1991-1994 KDD討論專題
–Advances in Knowledge Discovery and Data Mining (U. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and R. Uthurusamy, 1996)
◆1995-1998 KDD國際會議 (KDD’95-98)
–Journal of Data Mining and Knowledge Discovery (1997)
◆1998 ACM SIGKDD, SIGKDD’1999-2002 會議,以及SIGKDD Explorations
◆數(shù)據(jù)挖掘方面更多的國際會議
–PAKDD, PKDD, SIAM-Data Mining, (IEEE) ICDM, DaWaK, SPIE-DM, etc.
Data Mining(數(shù)據(jù)挖掘)是數(shù)據(jù)庫研究、開發(fā)和應(yīng)用最活躍的一個分支，是多學(xué)科的交叉領(lǐng)域，它涉及數(shù)據(jù)庫技術(shù)、人工智能、機器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)、數(shù)學(xué)、統(tǒng)計學(xué)、模式識別、知識庫系統(tǒng)、知識獲取、信息提取、高性能計算、并行計算、數(shù)據(jù)可視化等多方面知識。
數(shù)據(jù)挖掘技術(shù)從一開始就是面向應(yīng)用的，它不僅是面向特定數(shù)據(jù)庫的簡單檢索查詢調(diào)用，而且要對這些數(shù)據(jù)進行微觀、中觀乃至宏觀的統(tǒng)計、分析、綜合和推理，以指導(dǎo)實際問題的求解，企圖發(fā)現(xiàn)事件間的相互關(guān)聯(lián)，甚至利用已有的數(shù)據(jù)對未來的活動進行預(yù)測。例如加拿大BC省電話公司要求加拿大SimonFraser大學(xué)KDD研究組，根據(jù)其擁有十多年的客戶數(shù)據(jù)，總結(jié)、分析并提出新的電話收費和管理辦法，制定既有利于公司又有利于客戶的優(yōu)惠政策。這樣一來，就把人們對數(shù)據(jù)的應(yīng)用，從低層次的末端查詢操作，提高到為各級經(jīng)營決策者提供決策支持。這種需求驅(qū)動力，比數(shù)據(jù)庫查詢更為強大。同時，這里所說的數(shù)據(jù)挖掘，不是要求發(fā)現(xiàn)放之四海而皆準(zhǔn)的真理，也不是要去發(fā)現(xiàn)嶄新的自然科學(xué)定理和純數(shù)學(xué)公式，更不是什么機器定理證明。所有發(fā)現(xiàn)的知識都是相對的，是有特定前提和約束條件、面向特定領(lǐng)域的，同時還要能夠易于被用戶理解，最好能用自然語言表達發(fā)現(xiàn)結(jié)果。因此數(shù)據(jù)挖掘的研究成果是很講求實際的。
技術(shù)
Data Mining(數(shù)據(jù)挖掘)主要任務(wù)有數(shù)據(jù)匯總、概念描述、分類、聚類、相關(guān)性分析、偏差分析、建模等。具體技術(shù)包括：
統(tǒng)計分析(statistical analysis)
常見的統(tǒng)計方法有回歸分析(多元回歸、自回歸等)、判別分析(貝葉斯分析、費歇爾判別、非參數(shù)判別等)、聚類分析(系統(tǒng)聚類、動態(tài)聚類等)和探索性分析(主元分析法、相關(guān)分析法等)。其處理過程可以分為三個階段：搜集數(shù)據(jù)、分析數(shù)據(jù)和進行推理。
決策樹(decision tree)
決策樹是一棵樹，樹的根節(jié)點是整個數(shù)據(jù)集合空間，每個分節(jié)點是對一個單一變量的測試，該測試將數(shù)據(jù)集合空間分割成兩個或更多塊。每個葉節(jié)點是屬于單一類別的記錄。首先，通過訓(xùn)練集生成決策樹，再通過測試集對決策樹進行修剪。決策樹的功能是預(yù)言一個新的記錄屬于哪一類。
決策樹分為分類樹和回歸樹兩種，分類樹對離散變量做決策樹，回歸樹對連續(xù)變量做決策樹。
通過遞歸分割的過程來構(gòu)建決策樹：1 尋找初始分裂，整個訓(xùn)練集作為產(chǎn)生決策樹的集合，訓(xùn)練集每個記錄必須是已經(jīng)分好類的。決定哪個屬性(Field)域作為目前最好的分類指標(biāo)。一般的做法是窮盡所有的屬性域，對每個屬性域分裂的好壞做出量化，計算出最好的一個分裂。量化的標(biāo)準(zhǔn)是計算每個分裂的多樣性(diversity)指標(biāo)GINI指標(biāo)。2 樹增長到一棵完整的樹，重復(fù)第一步，直至每個葉節(jié)點內(nèi)的記錄都屬于同一類。3 數(shù)據(jù)的修剪，去掉一些可能是噪音或者異常的數(shù)據(jù)。
其基本算法(貪心算法)為：自上而下分而治之的方法，開始時，所有的數(shù)據(jù)都在根節(jié)點;屬性都是種類字段 (如果是連續(xù)的，將其離散化);所有記錄用所選屬性遞歸的進行分割;屬性的選擇是基于一個啟發(fā)式規(guī)則或者一個統(tǒng)計的度量 (如, information gain)。停止分割的條件：一個節(jié)點上的數(shù)據(jù)都是屬于同一個類別;沒有屬性可以再用于對數(shù)據(jù)進行分割。
偽代碼(Building Tree)為：
Procedure BuildTree(S){
用數(shù)據(jù)集S初始化根節(jié)點R
用根結(jié)點R初始化隊列Q
While Q is not Empty do {
取出隊列Q中的第一個節(jié)點N
if N 不純 (Pure) {
for 每一個屬性 A
估計該節(jié)點在A上的信息增益
選出最佳的屬性，將N分裂為N1、N2
}
}
}
|
屬性選擇的統(tǒng)計度量為：信息增益——Information gain (ID3/C4.5)，所有屬性假設(shè)都是種類字段，經(jīng)過修改之后可以適用于數(shù)值字段;基尼指數(shù)——Gini index (IBM IntelligentMiner)，能夠適用于種類和數(shù)值字段。
#p#
關(guān)聯(lián)規(guī)則(correlation rules)
規(guī)則反映了數(shù)據(jù)項中某些屬性或數(shù)據(jù)集中某些數(shù)據(jù)項之間的統(tǒng)計相關(guān)性，其一般形式為： X1∧…∧Xn Y(C,S)，表示由X1∧…∧Xn可以預(yù)測Y，其中可信度為C，支持度為S。
設(shè)I={i1, i2,…, im}是二進制文字的集合，其中的元素稱為項(item)。記D為交易(transaction)T的集合，這里交易T是項的集合，并且TÍI 。對應(yīng)每一個交易有唯一的標(biāo)識，如交易號，記作TID。設(shè)X是一個I中項的集合，如果XÍT，那么稱交易T包含X。
一個關(guān)聯(lián)規(guī)則是形如XÞY的蘊涵式，這里XÌI, YÌI，并且XÇY=F。規(guī)則XÞY在交易數(shù)據(jù)庫D中的支持度(support)是交易集中包含X和Y的交易數(shù)與所有交易數(shù)之比，記為support(XÞY)，即
support(XÞY)=|{T:XÈYÍT，TÎD}|/|D|
規(guī)則XÞY在交易集中的可信度(confidence)是指包含X和Y的交易數(shù)與包含X的交易數(shù)之比，記為confidence(XÞY)，即
confidence(XÞY)=|{T: XÈYÍT，TÎD}|/|{T:XÍT，TÎD}|
給定一個交易集D，挖掘關(guān)聯(lián)規(guī)則問題就是產(chǎn)生支持度和可信度分別大于用戶給定的最小支持度(minsupp)和最小可信度(minconf)的關(guān)聯(lián)規(guī)則。
基于規(guī)則中處理的變量的類別，關(guān)聯(lián)規(guī)則可以分為布爾型和數(shù)值型。布爾型關(guān)聯(lián)規(guī)則處理的值都是離散的、種類化的，它顯示了這些變量之間的關(guān)系;而數(shù)值型關(guān)聯(lián)規(guī)則可以和多維關(guān)聯(lián)或多層關(guān)聯(lián)規(guī)則結(jié)合起來，對數(shù)值型字段進行處理，將其進行動態(tài)的分割，或者直接對原始的數(shù)據(jù)進行處理，當(dāng)然數(shù)值型關(guān)聯(lián)規(guī)則中也可以包含種類變量?；谝?guī)則中數(shù)據(jù)的抽象層次，可以分為單層關(guān)聯(lián)規(guī)則和多層關(guān)聯(lián)規(guī)則。在單層的關(guān)聯(lián)規(guī)則中，所有的變量都沒有考慮到現(xiàn)實的數(shù)據(jù)是具有多個不同的層次的;而在多層的關(guān)聯(lián)規(guī)則中，對數(shù)據(jù)的多層性已經(jīng)進行了充分的考慮。基于規(guī)則中涉及到的數(shù)據(jù)的維數(shù)，關(guān)聯(lián)規(guī)則可以分為單維的和多維的。在單維的關(guān)聯(lián)規(guī)則中，我們只涉及到數(shù)據(jù)的一個維，如用戶購買的物品;而在多維的關(guān)聯(lián)規(guī)則中，要處理的數(shù)據(jù)將會涉及多個維。
Agrawal等于1993年首先提出了挖掘顧客交易數(shù)據(jù)庫中項集間的關(guān)聯(lián)規(guī)則問題，其核心方法是基于頻集理論的遞推方法。以后諸多的研究人員對關(guān)聯(lián)規(guī)則的挖掘問題進行了大量的研究。他們的工作包括對原有的算法進行優(yōu)化，如引入隨機采樣、并行的思想等，以提高算法挖掘規(guī)則的效率;提出各種變體，如泛化的關(guān)聯(lián)規(guī)則、周期關(guān)聯(lián)規(guī)則等，對關(guān)聯(lián)規(guī)則的應(yīng)用進行推廣。
Agrawal等在1993年設(shè)計了一個基本算法，提出了挖掘關(guān)聯(lián)規(guī)則的一個重要方法 — 這是一個基于兩階段頻集思想的方法，將關(guān)聯(lián)規(guī)則挖掘算法的設(shè)計可以分解為兩個子問題：
1.找到所有支持度大于最小支持度的項集(Itemset)，這些項集稱為頻集(Frequent Itemset)。
2.使用第1步找到的頻集產(chǎn)生期望的規(guī)則。
這里的第2步相對簡單一點。如給定了一個頻集Y=I1I2...Ik，k³2，Ij∈I，產(chǎn)生只包含集合{I1，I2，...，Ik}中的項的所有規(guī)則(最多k條)，其中每一條規(guī)則的右部只有一項，(即形如(Y-Ii)ÞIi，"1£i£k)。一旦這些規(guī)則被生成，那么只有那些大于用戶給定的最小可信度的規(guī)則才被留下來。對于規(guī)則右部含兩個以上項的規(guī)則，在其以后的工作中進行了研究。為了生成所有頻集，使用了遞推的方法。其核心思想如下：
L1 = {large 1-itemsets};
for (k=2; Lk-1¹F; k++)
{
Ck=apriori-gen(Lk-1); //新的候選集
for all transactions tÎD
{
Ct=subset(Ck,t); //事務(wù)t中包含的候選集
for all candidates cÎ Ct )
c.count++;
}
Lk={cÎ Ck |c.count³minsup}
}
Answer=ÈkLk;
|
首先產(chǎn)生頻繁1-項集L1，然后是頻繁2-項集L2，直到有某個r值使得Lr為空，這時算法停止。這里在第k次循環(huán)中，過程先產(chǎn)生候選k-項集的集合Ck，Ck中的每一個項集是對兩個只有一個項不同的屬于Lk-1的頻集做一個(k-2)-連接來產(chǎn)生的。Ck中的項集是用來產(chǎn)生頻集的候選集，最后的頻集Lk必須是Ck的一個子集。Ck中的每個元素需在交易數(shù)據(jù)庫中進行驗證來決定其是否加入Lk，這里的驗證過程是算法性能的一個瓶頸。這個方法要求多次掃描可能很大的交易數(shù)據(jù)庫，即如果頻集最多包含10個項，那么就需要掃描交易數(shù)據(jù)庫10遍，這需要很大的I/O負載。
Agrawal等引入了修剪技術(shù)(Pruning)來減小候選集Ck的大小，由此可以顯著地改進生成所有頻集算法的性能。算法中引入的修剪策略基于這樣一個性質(zhì)：一個項集是頻集當(dāng)且僅當(dāng)它的所有子集都是頻集。那么，如果Ck中某個候選項集有一個(k-1)-子集不屬于Lk-1，則這個項集可以被修剪掉不再被考慮，這個修剪過程可以降低計算所有的候選集的支持度的代價。
基于Apriori的頻集方法即使進行了優(yōu)化，但是Apriori方法一些固有的缺陷還是無法克服：1) 可能產(chǎn)生大量的候選集。當(dāng)長度為1的頻集有10000個的時候，長度為2的候選集個數(shù)將會超過10M。還有就是如果要生成一個很長的規(guī)則的時候，要產(chǎn)生的中間元素也是巨大量的。2) 無法對稀有信息進行分析。由于頻集使用了參數(shù)minsup，所以就無法對小于minsup的事件進行分析;而如果將minsup設(shè)成一個很低的值，那么算法的效率就成了一個很難處理的問題。以下兩種方法，分別用于解決以上兩個問題。
解決問題1的一種方法采用了一種FP-growth的方法。他們采用了分而治之的策略：在經(jīng)過了第一次的掃描之后，把數(shù)據(jù)庫中的頻集壓縮進一棵頻繁模式樹(FP-tree)，同時依然保留其中的關(guān)聯(lián)信息。隨后我們再將FP-tree分化成一些條件庫，每個庫和一個長度為1的頻集相關(guān)。然后再對這些條件庫分別進行挖掘。當(dāng)原始數(shù)據(jù)量很大的時候，也可以結(jié)合劃分的方法,使得一個FP-tree可以放入主存中。實驗表明，F(xiàn)P-growth對不同長度的規(guī)則都有很好的適應(yīng)性，同時在效率上較之Apriori算法有巨大的提高。
第二個問題是基于這個的一個想法：apriori算法得出的關(guān)系都是頻繁出現(xiàn)的，但是在實際的應(yīng)用中，我們可能需要尋找一些高度相關(guān)的元素，即使這些元素不是頻繁出現(xiàn)的。在apriori算法中，起決定作用的是支持度，而我們現(xiàn)在將把可信度放在第一位，挖掘一些具有非常高可信度的規(guī)則。對于這個問題的一個解決方法的整個算法基本上分成三個步驟：計算特征、生成候選集、過濾候選集。在三個步驟中，關(guān)鍵的地方就是在計算特征時Hash方法的使用。在考慮方法的時候，有幾個衡量好壞的指數(shù)：時空效率、錯誤率和遺漏率。基本的方法有兩類：Min_Hashing(MH)和Locality_Sensitive_Hashing(LSH)。Min_Hashing的基本想法是：將一條記錄中的頭k個為1的字段的位置作為一個Hash函數(shù)。Locality_Sentitive_Hashing的基本想法是：將整個數(shù)據(jù)庫用一種基于概率的方法進行分類，使得相似的列在一起的可能性更大，不相似的列在一起的可能性較小。對這兩個方法比較一下發(fā)現(xiàn)，MH的遺漏率為零，錯誤率可以由k嚴(yán)格控制，但是時空效率相對的較差。LSH的遺漏率和錯誤率是無法同時降低的，但是它的時空效率卻相對的好很多。所以應(yīng)該視具體的情況而定。最后的實驗數(shù)據(jù)也說明這種方法的確能產(chǎn)生一些有用的規(guī)則。
【編輯推薦】
