2.3 數據挖掘理論與方法

2.3.1 數據挖掘理論

數據挖掘誕生于1995年在加拿大首次召開的國際知識發現與數據挖掘學術會議[95]。數據挖掘雖然年輕且歷史較短，但其發展極為迅速。數據挖掘最為常用和普遍接受的定義是：從大量的、不完全的、有噪聲的、模糊的、隨機的數據中，提取隱含在其中的、人們事先不知道的、潛在有用的信息和知識的過程[58]。數據挖掘是可以針對大量業務數據進行抽取、轉換和分析處理，從中挖掘出有價值的、隱含的、潛在的商業機遇[96]。目前數據挖掘應用在各行各業，如醫療、金融、物流、電子商務、互聯網、物聯網、智能交通、風險管理等。

數據挖掘是一門綜合模式識別、數據庫、機器學習、統計學、商業分析和人工智能等眾多學科領域的新興交叉學科，近年來發展十分迅速，并且引起了學術界、工業界及商界的廣泛關注[97]。經過二十多年的研究和發展，數據挖掘領域產生了許多模型，其中以C4.5決策樹、K-Means聚類、SVM支持向量機、Apriori關聯規則挖掘方法、EM聚類方法、PageRank網頁排名方法、AdaBoost迭代方法、k最近鄰分類方法、NaiveBayes樸素貝葉斯方法和CART方法最為經典。這些經典的方法最終是在2006年ICDM的國際會議上，由145名與會者以公開投票的方式選出的十大經典方法[8]。

數據挖掘任務可分為描述和預測兩大類[58]。描述性數據挖掘任務主要是描述和刻畫數據庫中數據的一般特性，如概念/類描述；預測性數據挖掘任務則是對將來的趨勢和行為作出預測，如分類預測[58]。數據挖掘的六大任務簡單介紹如下：

（1）概念/類描述：用概括性的、精練的方式對目標數據描述其相應的類和概念，其目的是對數據進行更好的濃縮，實現對目標數據的整體把握。

（2）關聯規則：數據庫中的數據之間可能存在某種潛在規律，關聯規則挖掘則是找出數據庫中數據間隱含的相互關聯關系，探索其潛在的規律模式或興趣。

（3）分類：各種分類方法從不同的角度對訓練數據集（已標注了類別的數據）進行分析，找出訓練數據集中存在的普遍規律，經過驗證后將其用來對具有類似數據結構的未知數據的類別進行預測。

（4）聚類分析：在無監督學習的情況下，聚類不考慮類標號，將目標數據劃分為類或簇，使得類或簇內部的相似性最大化，而類或簇間的相似性最小化。

（5）孤立點分析：與數據的一般行為或模型不一致的孤立點易被視為噪聲而丟棄，但在某些特殊問題中，如發現金融欺詐行為，孤立點分析則尤為重要。

（6）演變分析：演變分析是用來描述和發現行為隨時間變化的對象的演變規律或發展趨勢，并且對其建模。

2.3.2 數據挖掘方法

數據挖掘經過二十多年的研究和發展，已經產生了許多方法和模型。在數據挖掘的六大任務類型中，最典型、最熱點的還屬聚類和分類。本小節主要介紹聚類方法和分類方法。

2.3.2.1 聚類方法

聚類是一種無監督學習技術，不需要先驗知識，根據數據對象之間的相似性對數據進行分區。聚類方法可以處理各種類型的海量數據，以發現其隱藏的模式、未知的相關關系以及其他潛在有用的信息。現有的聚類方法已有近百種，可以把聚類方法分為通用聚類方法和特殊聚類方法。通用聚類方法可以分為參數的方法和非參數的方法。參數的方法試圖去最小化一個代價函數或優化標準。非參數的方法即是基于數據相識度或者距離的方法。特殊聚類方法包括一些特殊數據情況和特殊要求下的聚類方法[98]。大體上，主要的聚類方法可以分為以下幾類：基于劃分的聚類方法、基于層次的聚類方法、基于密度的聚類方法、基于網格的聚類方法、基于模型的聚類方法[99]。

1）基于層次的聚類方法

基于層次的聚類方法對給定的數據對象進行層次的分解。按照層次的形成方式，層次方法可以分為凝聚法和分裂法。凝聚法是建立在聚類間距離尺度的基礎上的，最初把每個數據對象看成單獨的組，然后把最鄰近的組或對象合并、融合起來，重復直到最終只有一個或滿足某個終止條件結束。分裂法與凝聚法相反，它首先將所有對象置于一個簇中，每次迭代，逐漸劃分為越來越小的簇，直到最終每個對象自成一簇，或者達到某個終止條件結束。分裂的方法也有兩種類型，即單分裂和多分裂。單分裂是指每次用數據的一個屬性來分裂聚類，而多分裂的方法是對全部屬性綜合進行分析來分裂數據[98,100]。

2）基于劃分的聚類方法

對于一個給定的具有n個數據對象的數據集，通常構建數據的k個劃分，每個劃分為一組，k≤n，同時滿足以下兩個條件：每個類中至少包含一個數據對象和每個數據對象必須屬于且只屬于一個類。在某些模糊聚類、可能性聚類中，后者可以放寬要求。劃分的方法是一種參數的方法，其目的是將數據分為不同的子類。一般采用貪心啟發式方法，最小化某個優化函數，通過迭代最終獲取符合要求的劃分。典型的劃分聚類方法是k均值聚類方法[99,101]。

3）基于密度的聚類方法

基于密度的聚類方法，其思想是只要臨近區域的密度超過某個閾值就繼續聚類。也就是說，對給定類中的每個數據點，在一個給定范圍的區域中必須至少包含某個數目的點。這類方法能克服基于距離的方法只能發現類圓形聚類的缺點，可發現任意形狀的聚類，且對噪聲數據不敏感。但其計算復雜度大，需要建立空間索引來降低計算量，且對數據維數的伸縮性較差[99,102]。

4）基于網格的聚類方法

基于網格的聚類方法，首先將樣本所在的幾何空間進行切割，形成不同粒度的網格。然后根據每個網格中樣本的數量對數據進行劃分聚類。由于網格化的方法并不是直接對數據對象做處理，而是采用了一個多分辨率的網格數據結構。它的計算復雜度和處理時間獨立于樣本對象的記錄數目，只與量化空間中每一維度的單元數目有關[98,103]。

5）基于模型的聚類方法

基于模型的聚類方法為每個類假定了一個模型，認為數據是根據潛在的概率分布產生的，主要方法是尋找數據對給定模型的最佳擬合。在此基礎上，基于模型的聚類方法致力于尋找特定的數學模型，使得這一模型能夠擬合數據潛在的規律。基于模型的聚類通過構建反映數據點空間分布的密度函數來定位簇，主要包括基于統計學習的聚類和基于神經網絡的聚類。它能夠考慮“噪聲”數據和離群點的影響，從而產生魯棒的聚類方法[99,104]。

2.3.2.2 分類方法

所謂分類，是一種有監督學習方法，以待分析的目標問題為背景，采用一部分樣本數據建立一個關于類別屬性劃分的分類方法，并利用該模型對同類問題中類別標記未知的樣本進行學習和判斷的過程。分類是一個兩步過程：第一步，根據訓練數據，建立分類函數或分類器。這是訓練階段，也叫學習步，是通過對數據分析或者從樣本訓練集“學習”中完成。訓練集是由數據庫元組以及相關聯的類標號共同構成的。第二步，使用分類方法對數據進行分類。在使用分類方法之前，需要評估該分類器的預測準確率，在測試集上完成。該測試集是由檢驗元組和相關聯的類標號組成的。目前已有許多種分類方法，具有一套完整的分類方法庫，主要可分為以下幾類：基于貝葉斯技術的分類方法、決策樹分類方法、支持向量機分類方法、基于最近鄰分類方法、神經網絡分類方法等[99]。

1）基于貝葉斯技術的分類方法

貝葉斯分類是一種基于統計學的分類方法，可以預測一個類成員關系的可能性，即給定樣本屬于一個特定類的概率。數據挖掘領域主要使用兩種貝葉斯方法，即樸素貝葉斯方法和貝葉斯網絡方法。樸素貝葉斯方法使用貝葉斯公式進行預測，把從訓練樣本中計算出的各個屬性值與類別頻率之比作為先驗概率，并假定各個屬性之間是相互獨立的，然后利用貝葉斯公式及有關概率公式計算各實例的條件概率值，并選取其中概率值最大的類別作為預測值。此方法簡單易行且精度較好。貝葉斯網絡也叫貝葉斯信念網絡，是一個帶有概率注釋的有向無環圖，圖中的每一個節點均表示一個隨機變量，兩節點間若存在著一條弧，則表示這兩節點相對應的隨機變量是概率相依的，反之則說明這兩個隨機變量是條件獨立的。事實上，貝葉斯網絡也是一種適合表示不確定性知識的方法[99,105]。

2）決策樹分類方法

決策樹分類方法是數據挖掘領域研究分類問題最常采用的方法，其原因歸納為以下三點：一是決策樹構造的分類器易于理解；二是采用決策樹分類，其速度快于其他分類方法；三是采用決策樹分類方法得到的分類準確性通常優于其他方法[106]。絕大多數決策樹分類方法分兩步：第一步是樹的生成，根據給定數據集進行建樹，主要是對原數據源進行機器學習。第二步是根據建立好的決策樹對數據進行分類學習。對于未知數據的樣本，從決策樹的根節點開始掃描，依次測試樣本的屬性值，直到到達對應的葉節點，那么數據所屬于的類就是該葉節點代表的類。在數據量較大時，決策樹方法能較快地構造出分類器：其樹型結構可以很方便地轉化為SQL語言形式，以便用來更有效地訪問數據庫[99,106,107]。

3）支持向量機分類方法

支持向量機是Vapnik在20世紀90年代中期提出來的一種分類方法，使用一種非線性映射，將原訓練數據映射到較高的維，在新的維度上，搜索線性最佳分離超平面。支持向量機脫離了傳統方法中降維的定式，建立在計算學習理論的結構風險最小化的原則之上，利用反轉技術有目的地增加問題空間的維數，使得分類問題變得相對容易，也可以提高學習機的泛化能力。支持向量機的復雜度與實例集的維數無關，適合于兩分類問題和線性不可分問題，因為它可將樣本空間映射到一個高維空間，使原來線性不可分的情況在高維空間中得到解決。支持向量機可以用來分類和預測，且在很多領域得到廣泛應用，如對象識別、語音識別、基準時間序列預測檢驗等[99,108,109]。

4）基于最近鄰分類方法

基于最近鄰分類方法的分類思想是：如果在一個樣本的屬性空間里，與這個樣本相似的k個樣本都屬于同一個類，則這個樣本也一定屬于這個類。該方法僅使用與待分類樣本最相似的樣本所屬的類別來判斷待分類樣本。k最近鄰分類方法是基于類比學習，通過給定的檢驗元組與和它相似的訓練元組進行比較來學習的。為了克服最近鄰法錯判率較高的缺陷，k最近鄰分類方法不是僅選取一個最近鄰進行分類，而是選取k個近鄰，然后檢查它們的類別，并歸入比重最大的那一類。此外，由于k最近鄰分類方法主要依據附近有限的樣本，并不是依據類域的判斷來確定樣本所在類別的，故對于樣本類域的交叉或重疊較多的待分樣本集來說，k最近鄰分類方法較其他方法更為適合[99,110]。

5）神經網絡分類方法

神經網絡是一組連接的輸入輸出單元，其中每個連接都與一個權重相關聯，在學習階段，通過調整這些權重，能夠預測輸入元組的正確類標號。由于單元之間的連接，神經網絡學習又可稱為連接著學習。神經網絡可分為4種類型，即前向型、反饋型、隨機型和自組織型。前向神經網絡是數據挖掘中廣為應用的一類網絡，其原理和方法也是其他一些網絡的基礎。神經網絡具有對噪聲數據的承受能力，尤其是它對未經訓練的數據具有很好的分類能力[99,106,111]。