(未完成，Reference未補)

決策樹

什么是決策樹?

• Tree
• if-then 規(guī)則的集合，該集合是決策樹上的所有從根節(jié)點到葉節(jié)點的路徑的集合
• 定義在特征空間與類空間上的條件概率分布，決策樹實際上是將特征空間劃分成了互不相交的單元，每個從根到葉的路徑對應(yīng)著一個單元。決策樹所表示的條件概率分布由各個單元給定條件下類的條件概率分布組成。實際中，哪個類別有較高的條件概率，就把該單元中的實例強行劃分為該類別。

構(gòu)建

• 遞歸過程
• 遞歸終止
  • 當前結(jié)點樣本全部屬于同一類別
  • 當前屬性集合為空，或所有樣本在所有屬性上取值相同 （利用當前節(jié)點的后驗分布）
  • 當前結(jié)點樣本集合為空（利用父結(jié)點的樣本分布作為先驗分布）

優(yōu)點？

• 數(shù)據(jù)預處理步驟少
• 解釋性較強
• 分類速度快
• 對噪聲數(shù)據(jù)不敏感

學習？

• 最小化損失函數(shù)
• 損失函數(shù)是正則化的極大似然函數(shù)
• 決策樹的學習本質(zhì)上就是從訓練數(shù)據(jù)集中歸納出一組分類規(guī)則，使它與訓練數(shù)據(jù)矛盾較小的同時具有較強的泛化能力。
• 基于訓練數(shù)據(jù)集估計條件概率模型
• 只能通過啟發(fā)式算法學習次最優(yōu)解
• 過擬合（可通過剪枝解決）

步驟？

• 特征選擇
• 模型生成
• 剪枝 (預、后)

特征選擇

• 選擇分類能力更好的特征

  • 信息增益
    表示得知特征 X 的信息而使得分類難度（不確定信息）減少的程度，信息增益越大越好。用信息增益去選擇特征有一個問題，即偏向于選擇取值較多的特征。解決思路就是對取值較多的特征進行適當?shù)膽土P。如使用信息增益比。

    
    
    G(D, A) = H(D) - H(D|A)

    • 熵和條件熵
      熵越大，隨機變量的不確定性就越大。當 p = 0 或者 p = 1 時可知，隨機變量沒有不確定性，所以熵為 0。

      
      
      H(p) = -\sum_{i}^{n}p_i logp_i
      
      
      H(Y|X) = -\sum_{i}^{n}p_i H(Y|X = x_i), p_i = P(X = x_i), i =1,2,...,n

  • 信息增益比
    特征 A 對數(shù)據(jù)訓練集 D 的信息增益比為信息增益與訓練數(shù)據(jù)集關(guān)于特征A的熵的比。

模型生成

• ID3
  在各個結(jié)點應(yīng)用信息增益準則選擇特征，遞歸構(gòu)建，直到停止。停止條件可單獨設(shè)立。信息增益準則對可取值數(shù)目較多的屬性有偏好。
• C4.5
  和 ID3 使用信息增益不同，該算法使用信息增益比準則選擇特征。停止條件可單獨設(shè)立。信息增益比對可取值數(shù)目較少的屬性有偏好。C4.5 算法使用了一個啟發(fā)算法：先選擇信息增益高于平均水平的屬性，然后在其中選擇信息增益比最大的屬性。
• 總結(jié)
  C4.5 算法有如下優(yōu)點：產(chǎn)生的分類規(guī)則易于理解，準確率較高。其缺點是：在構(gòu)造樹的過程中，需要對數(shù)據(jù)集進行多次的順序掃描和排序，因而導致算法的低效。另外，C4.5 只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集，當訓練集大得無法在內(nèi)存容納時程序無法運行。
  另外，無論是 ID3 還是 C4.5 最好在小數(shù)據(jù)集上使用，決策樹分類一般只試用于小數(shù)據(jù)。當屬性取值很多時最好選擇 C4.5 算法，ID3 得出的效果會非常差，因為使用信息增益劃分時它傾向于取值多的屬性。

剪枝

• 預
  • 設(shè)置深度
  • 葉節(jié)點包含樣本數(shù)最小值
• CART
  • 二叉樹決策樹算法

  • 使用 Gini 指數(shù)，Gini 指數(shù)越大，不純度越大，越不容易區(qū)分。這一點類似于熵。

    
    
    Gini_A(D) = \frac{D_1}{D} Gini(D_1) + \frac{D_2}{D} Gini(D_2)

缺失值處理

對于某些采樣數(shù)據(jù)，可能會缺少屬性值。在這種情況下，處理缺少屬性值的通常做法是賦予該屬性的常見值，或者屬性均值。另外一種比較好的方法是為該屬性的每個可能值賦予一個概率，即將該屬性以概率形式賦值。例如給定Boolean屬性B，已知采樣數(shù)據(jù)有12個B=0和88個B=1實例，那么在賦值過程中，B屬性的缺失值被賦為B(0)=0.12、B(1)=0.88；所以屬性B的缺失值以12%概率被分到False的分支，以88%概率被分到True的分支。這種處理的目的是計算信息增益，使得這種屬性值缺失的樣本也能處理。

聚類（Clustering）的本質(zhì)是對數(shù)據(jù)進行分類，將相異的數(shù)據(jù)盡可能地分開，而將相似的數(shù)據(jù)聚成一個類別（簇），使得同一類別的數(shù)據(jù)具有盡可能高的同質(zhì)性（homogeneity），類別之間有盡可能高的異質(zhì)性（heterogeneity），從而方便從數(shù)據(jù)中發(fā)現(xiàn)隱含的有用信息。。聚類算法屬于無監(jiān)督學習。

聚類算法的應(yīng)用
（1）其他數(shù)據(jù)挖掘任務(wù)的關(guān)鍵中間環(huán)節(jié)：用于構(gòu)建數(shù)據(jù)概要，用于分類、模式識別、假設(shè)生成和測試；用于異常檢測，檢測遠離群簇的點。
（2）數(shù)據(jù)摘要、數(shù)據(jù)壓縮、數(shù)據(jù)降維：例如圖像處理中的矢量量化技術(shù)。創(chuàng)建一個包含所有簇原型的表，即每個原型賦予一個整數(shù)值，作為它在表中的索引。每個對象用與它所在簇相關(guān)聯(lián)的原型的索引表示。
（3）協(xié)同過濾：用于推薦系統(tǒng)和用戶細分。
（4）動態(tài)趨勢檢測：對流數(shù)據(jù)進行聚類，檢測動態(tài)趨勢和模式。
（5）用于多媒體數(shù)據(jù)、生物數(shù)據(jù)、社交網(wǎng)絡(luò)數(shù)據(jù)的應(yīng)用。
基本方法
1）基于分層的聚類(hierarchical methods)：主要講給定的數(shù)據(jù)集進行逐層分解，直到滿足某種條件為止。具體可分為“自底向上”和“自頂向下”兩種方案。在“自底向上”方案中，初始時每個數(shù)據(jù)點組成一個單獨的組，在接下來的迭代中，按一定的距離度量將相互鄰近的組合并成一個組，直至所有的記錄組成一個分組或者滿足某個條件為止。代表算法有：BIRCH，CURE，CHAMELEON等。
2）基于劃分的聚類（partitioning methods）：給定包含N個點的數(shù)據(jù)集，劃分法將構(gòu)造K個分組，每個分組代表一個聚類，這里每個分組至少包含一個數(shù)據(jù)點，每個數(shù)據(jù)點屬于且僅屬于一個分組。對于給定的K值，算法先給出一個初始的分組方法，然后通過反復迭代的方法改變分組，使得每一次改進之后的分組方案較前一次好，這里好的標準在于同一組中的點越近越好，不同組中的點越遠越好。代表算法有：K-means，K-medoids，CLARANS。
3）基于密度的聚類（density-based methods）：基于密度的方法的特點是不依賴于距離，而是依賴于密度，從而克服基于距離的算法只能發(fā)現(xiàn)“球形”聚簇的缺點。其核心思想在于只要一個區(qū)域中點的密度大于某個閾值，就把它加到與之相近的聚類中去。代表算法有：DBSCAN，OPTICS，DENCLUE，WaveCluster。
（4）基于網(wǎng)格的聚類（gird-based methods）：這種方法通常將數(shù)據(jù)空間劃分成有限個單元的網(wǎng)格結(jié)構(gòu)，所有的處理都是以單個的單元為對象。這樣做起來處理速度很快，因為這與數(shù)據(jù)點的個數(shù)無關(guān)，而只與單元個數(shù)有關(guān)。代表算法有：STING，CLIQUE，WaveCluster。
（5）基于模型的聚類（model-based methods）：基于模型的方法給每一個聚類假定一個模型，然后去尋找能很好的擬合模型的數(shù)據(jù)集。模型可能是數(shù)據(jù)點在空間中的密度分布函數(shù)或者其它。這樣的方法通常包含的潛在假設(shè)是：數(shù)據(jù)集是由一系列的潛在概率分布生成的。通常有兩種嘗試思路：統(tǒng)計學方法和神經(jīng)網(wǎng)絡(luò)方法。其中，統(tǒng)計學方法有COBWEB算法、GMM(Gaussian Mixture Model)，神經(jīng)網(wǎng)絡(luò)算法有SOM(Self Organized Maps)算法。

聚類分析的要求
不同的聚類算法有不同的應(yīng)用背景，有的適合于大數(shù)據(jù)集，可以發(fā)現(xiàn)任意形狀的聚簇；有的算法思想簡單，適用于小數(shù)據(jù)集?？偟膩碚f，數(shù)據(jù)挖掘中針對聚類的典型要求包括：

（1）可伸縮性：當數(shù)據(jù)量從幾百上升到幾百萬時，聚類結(jié)果的準確度能一致。
（2）處理不同類型屬性的能力：許多算法針對的數(shù)值類型的數(shù)據(jù)。但是，實際應(yīng)用場景中，會遇到二元類型數(shù)據(jù)，分類/標稱類型數(shù)據(jù)，序數(shù)型數(shù)據(jù)。
（3）發(fā)現(xiàn)任意形狀的類簇：許多聚類算法基于距離（歐式距離或曼哈頓距離）來量化對象之間的相似度?；谶@種方式，我們往往只能發(fā)現(xiàn)相似尺寸和密度的球狀類簇或者凸型類簇。但是，實際中類簇的形狀可能是任意的。
（4）初始化參數(shù)的需求最小化：很多算法需要用戶提供一定個數(shù)的初始參數(shù)，比如期望的類簇個數(shù)，類簇初始中心點的設(shè)定。聚類的結(jié)果對這些參數(shù)十分敏感，調(diào)參數(shù)需要大量的人力負擔，也非常影響聚類結(jié)果的準確性。
（5）處理噪聲數(shù)據(jù)的能力：噪聲數(shù)據(jù)通?？梢岳斫鉃橛绊懢垲惤Y(jié)果的干擾數(shù)據(jù)，包含孤立點，錯誤數(shù)據(jù)等，一些算法對這些噪聲數(shù)據(jù)非常敏感，會導致低質(zhì)量的聚類。
（6）增量聚類和對輸入次序的不敏感：一些算法不能將新加入的數(shù)據(jù)快速插入到已有的聚類結(jié)果中，還有一些算法針對不同次序的數(shù)據(jù)輸入，產(chǎn)生的聚類結(jié)果差異很大。
（7）高維性：有些算法只能處理2到3維的低緯度數(shù)據(jù)，而處理高維數(shù)據(jù)的能力很弱，高維空間中的數(shù)據(jù)分布十分稀疏，且高度傾斜。
（8）可解釋性和可用性：我們希望得到的聚類結(jié)果都能用特定的語義、知識進行解釋，和實際的應(yīng)用場景相聯(lián)系。