決策樹加密算法是以實(shí)例為基礎(chǔ)的歸納學(xué)習(xí)算法，它著眼于從一組無次序、無規(guī)則的事例中推理出決策樹表示形式的分類規(guī)則，通常用來形成分類器和預(yù)測(cè)模型，可以對(duì)未知數(shù)據(jù)進(jìn)行分類或預(yù)測(cè)、數(shù)據(jù)挖掘等。那么我們今天就來給大家分析一下決策樹加密算法。

一、決策樹加密算法實(shí)現(xiàn)過程

決策樹加密算法通常分為兩個(gè)階段：第一個(gè)階段是建樹和剪枝。第二個(gè)階段是利用建好的決策樹對(duì)新的數(shù)據(jù)進(jìn)行分類。

1、決策樹加密算法的建樹階段

決策樹加密算法的建樹流程圖如圖所示。其中S表示訓(xùn)練樣本集，A表示分類樣本集合，N表示一個(gè)分類葉節(jié)點(diǎn)。

2、決策樹加密算法的剪枝階段

決策樹加密算法剪枝階段的任務(wù)是對(duì)生成的決策樹按照一定的方法進(jìn)行剪枝，剪枝是一種克服訓(xùn)練樣本集數(shù)據(jù)噪聲的基本技術(shù)，對(duì)樹進(jìn)行修剪優(yōu)化時(shí)要準(zhǔn)確理解分類的特征描述和防止過多的噪聲影響，從而達(dá)到更好的修剪效果，在確保精確程度的同時(shí)，提高可理解性。

二、決策樹加密算法的特點(diǎn)

基于決策樹的分類算法以其特有的優(yōu)點(diǎn)廣為人們采用。

首先，決策樹方法結(jié)構(gòu)簡(jiǎn)單，它在學(xué)習(xí)的過程中不需要了解很多的背景知識(shí)；

其次，決策樹模型效率較高，對(duì)訓(xùn)練樣本集數(shù)據(jù)量較大的情況較為適合；

再次，決策樹加密算法的計(jì)算量相對(duì)較小；

然后，決策樹方法通常不需要受訓(xùn)數(shù)據(jù)外的知識(shí)，擅長(zhǎng)處理非數(shù)值型數(shù)據(jù)；

最后，決策樹方法具有較高的分類精確度。據(jù)統(tǒng)計(jì)，目前決策樹加密算法利用率高達(dá)19％。

三、常見的決策樹加密算法

1、CLS加密算法

CLS加密算法是1966年提出的。它第一次提出用決策樹進(jìn)行概念學(xué)習(xí)，后來的許多決策樹學(xué)習(xí)算法都可以看作是CLS加密算法的改進(jìn)與更新。

CLS的主要思想是從一個(gè)空的決策樹出發(fā)，通過添加新的判定結(jié)點(diǎn)來改善原來的決策樹，直到該決策樹能夠正確的將訓(xùn)練實(shí)例分類為止。它對(duì)決策樹的構(gòu)造過程也就是假設(shè)特化的過程，所以CLS可以看作是只帶一個(gè)操作符的學(xué)習(xí)算法，此操作符可以表示為：通過添加一個(gè)新的判定條件（新的判定結(jié)點(diǎn)），特化當(dāng)前假設(shè)。CLS加密算法遞歸調(diào)用這個(gè)操作符，作用在每個(gè)葉結(jié)點(diǎn)，來構(gòu)造決策樹。

2、CART加密算法算法

CART加密算法是在1984年提出的。這種加密算法選擇具有最小基尼指數(shù)值的屬性作為測(cè)試屬性，并采用一種二分遞歸分割的技術(shù)，是將當(dāng)前樣本集分為兩個(gè)子樣本集，使得生成的決策樹的每一個(gè)非葉節(jié)點(diǎn)都有兩個(gè)分枝。最后生成的決策樹是結(jié)構(gòu)簡(jiǎn)潔的二叉樹。

CART加密算法使用后剪枝法。剪枝算法使用獨(dú)立于訓(xùn)練樣本集的測(cè)試樣本集對(duì)子樹的分類錯(cuò)誤進(jìn)行計(jì)算，找出分類錯(cuò)誤最小的子樹作為最終的分類模型。有些樣本集，由于樣本數(shù)太少而不能分出獨(dú)立的測(cè)試樣本集，CART加密算法采用一種稱為交叉確定的剪枝方法。該方法解決了在小樣本集上挖掘決策樹由于沒有獨(dú)立測(cè)試樣本集而造成的過度擬合問題。不過CART加密算法最初建立的樹也有錯(cuò)誤率，因?yàn)橛行┤~子節(jié)點(diǎn)并不是純的。

3、ID3加密算法

ID3加密算法是在1986年提出的。它是決策樹算法的代表，絕大數(shù)決策樹算法都是在它的基礎(chǔ)上加以改進(jìn)而實(shí)現(xiàn)的。

ID3加密算法采用分治策略，在決策樹各級(jí)結(jié)點(diǎn)上選擇屬性時(shí)，用信息增益作為屬性的選擇標(biāo)準(zhǔn)，以便在每一個(gè)非葉結(jié)點(diǎn)上進(jìn)行測(cè)試時(shí)，能獲得關(guān)于被測(cè)試記錄最大的類別信息。

具體方法是：檢測(cè)所有的屬性，選擇信息增益最大的屬性產(chǎn)生決策樹結(jié)點(diǎn)，由該屬性的不同取值建立分支，再對(duì)各分支的子集遞歸調(diào)用該方法建立決策樹結(jié)點(diǎn)的分支，直到所有子集僅包含同一類別的數(shù)據(jù)為止。最后得到一棵決策樹，它可以對(duì)新的樣本進(jìn)行分類。

四、決策樹加密算法面臨的問題

1、可擴(kuò)展性亟待提高　

決策樹加密算法具有良好的可擴(kuò)展性是指算法具有處理大量的數(shù)據(jù)或加速數(shù)據(jù)挖掘過程的能力。在大型數(shù)據(jù)集中，能從中快速而準(zhǔn)確地發(fā)現(xiàn)隱藏于其中的主要分類規(guī)則，即認(rèn)為算法具有良好的可擴(kuò)展性。數(shù)據(jù)挖掘面臨的數(shù)據(jù)往往是海量的，對(duì)實(shí)時(shí)性要求較高的決策場(chǎng)所，數(shù)據(jù)挖掘方法的主動(dòng)性和快速性顯得日益重要。應(yīng)用實(shí)時(shí)性技術(shù)、設(shè)計(jì)快速的算法、數(shù)據(jù)分割、主動(dòng)關(guān)系數(shù)據(jù)庫技術(shù)和分布并行算法設(shè)計(jì)技術(shù)等現(xiàn)代計(jì)算機(jī)先進(jìn)技術(shù)，是數(shù)據(jù)挖掘方法實(shí)用化的有效途徑。

2、適應(yīng)多數(shù)據(jù)類型和容噪性

隨著計(jì)算機(jī)網(wǎng)絡(luò)和信息的社會(huì)化，數(shù)據(jù)挖掘的對(duì)象已不單是關(guān)系數(shù)據(jù)庫模型，而是分布、異構(gòu)的多類型數(shù)據(jù)庫，數(shù)據(jù)的非結(jié)構(gòu)化程度、噪聲等現(xiàn)象越來越突出，這也是決策樹技術(shù)面臨的困難問題。

3、遞增性問題

數(shù)據(jù)挖掘出來的知識(shí)，只是相對(duì)于某一時(shí)間的某些數(shù)據(jù)，新的數(shù)據(jù)可能使發(fā)現(xiàn)的新知識(shí)與原來的知識(shí)沖突。這是因?yàn)閿?shù)據(jù)挖掘基礎(chǔ)是歸納邏輯，而歸納邏輯是一個(gè)非單調(diào)的過程。因此，結(jié)合非單調(diào)邏輯的理論，設(shè)計(jì)具有遞增性決策樹挖掘方法，也是實(shí)用化的基本要求之一。

決策樹加密算法已經(jīng)有了廣泛的應(yīng)用，并且已經(jīng)有了許多成熟的系統(tǒng)，這些系統(tǒng)廣泛應(yīng)用于各個(gè)領(lǐng)域，如語音識(shí)別，醫(yī)療診斷，客戶關(guān)系管理，模式識(shí)別，專家系統(tǒng)等。決策樹各類加密算法，各有優(yōu)缺點(diǎn)，在實(shí)際工作中，必須根據(jù)數(shù)據(jù)類型的點(diǎn)及數(shù)據(jù)集的大小，選擇合適的加密算法。

admin

收藏 海報(bào)分享