[發明專利]一種處理缺失數據的新型決策樹分類器方法

有效

• 申請號: 201110100232.0
• 申請日: 2011-04-21
• 公開（公告）號: CN102750286A
• 公開（公告）日: 2012-10-24
• 發明（設計）人: 吳軍
• 申請（專利權）人: 常州藍城信息科技有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 蘇州廣正知識產權代理有限公司 32234
• 代理人: 張利強

技術領域

本發明屬于數據挖掘與機器學習領域，涉及一種可以處理缺失數據的新型決策樹分類器的方法。

背景技術

隨著信息技術的高速發展，人們收集、存儲和訪問數據的數量越來越多，在這些大量的歷史數據背后蘊藏著豐富的有效知識。如何去發現和分析這些數據之間所存在的關系和規則在目前是個十分重要的課題。數據挖掘(DM)技術在這種背景下應運而生了，它融合了數據庫，人工智能，機器學習，統計學等多個領域的理論和知識。數據挖掘工具能夠對未來趨勢進行預測，可以很好的支持人們的決策。其中常用的方法有神經網絡，遺傳算法，決策樹，規則推理，貝葉斯分類等等。其中決策樹方法較容易被人們理解，輸出的精度高，因此在數據挖掘領域應用較為廣泛。但決策樹方法也有其缺點，比如它很難基于多個變量組合發現規則，不同的決策樹分支之間的分裂也不平滑，傳統決策樹算法的計算復雜度較高等等。決策樹方法是目前應用最廣泛的歸納推理算法之一，是一種逼近離散值函數的方法，也可以把它看作是一個布爾函數。它是以實例為基礎的歸納學習算法，通常用來形成分類器和預測模型，著眼于從一組無次序、無規則的事例中推理出決策樹表示形成的分類規則。它采用自頂向下的遞歸方式，在決策樹的內部結點進行屬性值的比較并根據不同的屬性值判斷從該結點向下的分支，最后在決策樹的葉結點得到結論。因此從根到葉結點的一條路徑就對應著一條合取規則，而整棵決策樹就對應著一組析取表達式規則。

到目前為止決策樹有很多實現算法。例如：由Hunt等人提出的CLS，在1986年由Quinlan提出的ID3和1993年提出的C4.5算法，以及CART，C5.0，Fuzzy?C4.5，OC1，QUEST，和CAL5等。傳統決策樹算法的缺點包括：(1)缺失數據的存在是導致分類器性能下降的一個重要原因，目前的分類器大多不能有效處理缺失數據的分類問題。(2)算法往往偏向于選擇取值較多的屬性，而在很多情況下屬性較多的屬性并不總是最優的屬性。(3)在建樹時，每個結點僅含一個特征，是一種單變元的算法，特征間的相關性不夠緊。雖然在一棵樹上連在一起，但聯系還是松散的。(4)對燥聲比較敏感，不容易除去燥聲。也就是特征值取錯或類別給錯。(5)當訓練集增加時，ID3決策樹隨之變化。在建樹過程中，各特征的相互信息會隨例子的增加而改變，決策樹也隨之變化，這對變化的數據集的學習是不適合的。(6)算法雖然理論清晰，但它的計算比較復雜，在學習和訓練數據集的過程中機器內存占用率比較大，比較耗費資源，影響數據學習的時間和成本。

發明內容

為了克服以上缺陷，本發明要解決的技術問題是：提出一種同時解決估算缺失數據的可能屬性，以及遞歸地構造決策樹的分枝，完成決策樹的構造，精細了分類規則的處理缺失數據的新型決策樹分類器的方法。

本發明所采用的技術方案為：一種處理缺失數據的新型決策樹分類器方法，包括以下步驟：

a、將待處理的原始樣本數據集進行初始化設置，且將所述數據集進行權重值初始化分配；

b、選擇一將所述數據集中的節點分裂為子節點的特征屬性；

c、將樣本數據根據節點的特征屬性分類到各子節點；

d、通過計算出各子節點選擇的特征量值將各子節點分裂出來；

e、根據分裂出來的各子節點的樣本屬性確定葉子節點。

根據本發明的另外一個實施例，一種處理缺失數據的新型決策樹分類器方法進一步包括所述數據集包括缺失數據、非缺失數據。

根據本發明的另外一個實施例，一種處理缺失數據的新型決策樹分類器方法進一步包括所述節點特征量值包括特征量的信息熵、特征量的信息增益率。

根據本發明的另外一個實施例，一種處理缺失數據的新型決策樹分類器方法進一步包括計算出特征量的信息增益率將子節點分裂出來時，子節點所選擇的特征量就是最大信息增益率，則繼續分裂節點為子節點；若子節點所選擇的特征量不是最大信息增益率，則重新選擇分裂為子節點的特征屬性，直至子節點所選擇的特征量為最大信息增益率。

根據本發明的另外一個實施例，一種處理缺失數據的新型決策樹分類器方法進一步包括在根據各子節點的樣本屬性確定葉子節點時，若每個子節點只含有同一類樣本，則將此節點設置為葉子節點，結束此節點的分裂；若每個子節點不只含有同一類樣本，則重新選擇分裂為子節點的特征屬性。