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