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