資料挖掘分類技術
作者：sccot 撰寫日期：2012-02-28
1、過分拟合問題：
造成原因有：（1）噪聲造成的過分拟合（因為它拟合了誤标記的訓練記錄，導緻了對檢驗集中記錄的誤分類）；（2）根據少量訓練記錄做出分類決策的模型也容易受過分拟合的影響。（由于訓練資料缺乏具有代表性的樣本，在沒有多少訓練記錄的情況下，學習算法仍然繼續細化模型就會産生這樣的模型，當決策樹的葉節點沒有足夠的代表性樣本時，很可能做出錯誤的預測）（3）多重比較也可能會導緻過分拟合（大量的候選屬性和少量的訓練記錄最後導緻了模型的過分拟合）
2、泛化誤差的估計：
（1）樂觀估計（決策樹歸納算法簡單的選擇産生最低訓練誤差的模型作為最終的模型）（2）悲觀誤差估計（使用訓練誤差與模型複雜度罰項的和計算泛化誤差）（3）最小描述長度原則（模型編碼的開銷加上誤分類記錄編碼的開銷）（4）估計統計上界（泛化誤差可以用訓練誤差的統計修正來估計，因為泛化誤差傾向于比訓練誤差大，是以統計修正通常是計算訓練誤差的上界）（4）使用确認集（如2/3的訓練集來建立模型，剩下的用來做誤差估計）
3、處理決策樹中的過分拟合：
A)：先剪枝（提前終止規則）：當觀察到的不純性度量的增益（或估計的泛化誤差的改進）低于某個确定的門檻值時就停止擴充葉節點。B)：初始決策樹按照最大規模生長，然後進行剪枝的步驟，按照自底向上的方式修剪完全增長的決策樹。修剪有兩種方法：（1）用新的葉節點替換子樹，該葉節點的類标号由子樹下記錄中的多數類确定；（2）用子樹中常見的分支替代子樹。當模型不能再改進時終止剪枝步驟。與先剪枝相比，後剪枝技術傾向于産生更好的結果。
4、評估分類器的方法：
（A）：保持方法（用訓練集的一部分來做訓練一部分做檢驗，用檢驗的準确度來評估）（B）随機二次抽樣（第一種方法進行K次不同的疊代，取其平均值）（C）交叉驗證（每個記錄用于訓練的次數相同，并且用于檢驗恰好一次）（D）自助法（有放回抽樣）
1.1、決策樹分類
算法思想：遞歸的選擇一個屬性對對象集合的類标号進行分類，如果分類到某一屬性時發現剩下的對象屬于同一類，此時就不必再選擇屬性就行分類，而隻用建立一個葉節點并用共同的類來代表。否則，繼續選擇下一屬性進行分類操作，直到某一分類結果全在同一類或者沒有屬性可供選擇為止。根據選擇屬性的順序可以将決策樹算法分為ID3,C4.5等。其中，決策樹算法CART隻産生二進制劃分，它們考慮建立K個屬性的二進制劃分的所有2^(k-1)-1中方法。圖1顯示了把婚姻狀況的屬性值劃分為兩個子集的三種不同的分組方法。對于連續屬性來說，測試條件可以是具有二進制輸出的比較測試（A<v）或（A>=v），也可以是具有形如vi<=A<=vi+1（i=1,21，…，k）輸出的範圍查詢（如圖2所示）。
問：預測集中的每條記錄的屬性取值集合是否就和訓練集的某一個記錄的屬性取值集合相等？
答：不一定，一般來說是不可能的。但是建立的決策樹一定包含該取值集合（但是可能範圍會大些）。因為決策樹建過程是隻要目前的所有對象屬于同一個标号就不再繼續選擇屬性了，是以，實際上建立的決策樹所包含的對象是比訓練集中的對象要多得多的，這些多餘的對象可能就包含目前的預測對象。這也是決策樹能夠用來進行分類的原因。
決策樹歸納的特點：
（1）找到最優決策樹是NP完全問題；（2）采用避免過分拟合的方法後決策樹算法對于噪聲的幹擾具有相當好的魯棒性。
1.2、基于規則的分類
基于規則的分類使用一組if…then規則來分類記錄的技術。算法思想：先從訓練集生成規則集合，規則是使用合取條件表示的：如規則ri：（條件i）->yi,其中r1是如下形式：r1：（胎生=否）^（飛行動物=是）->鳥類;其中左邊稱為規則前件或前提；規則右邊稱為規則後件。如果規則r的前件和記錄x的屬性比對，則稱r覆寫x。當r覆寫給定的記錄時，稱r被激發或被觸發。建立規則集合後，就進行分類。對每個待分類的記錄和規則集合中的每條規則進行比較，如果某條規則被觸發，該記錄就被分類了。
問：由于規則集中的規則不一定是互斥的，所有有可能分類的時候某條記錄會屬于多個類（也就是說某條記錄會同時觸發規則集中的超過1條的過則，而被觸發的規則的類标号也不一樣），這種情況如何處理：
答：有兩種辦法解決這個問題。（1）有序規則。将規則集中的規則按照優先級降序排列，當一個測試記錄出現時，由覆寫記錄的最高秩的規則對其進行分類，這就避免由多條分類規則來預測而産生的類沖突問題（2）
無序規則。允許一條測試記錄觸發多條分類規則，把每條被觸發規則的後件看作是對相應類的一次投票，然後計票确定測試記錄的類标号。通常把記錄指派到得票最多的類。
問：假設現在有一個記錄它不能觸發規則集合中的任何一個規則，那麼它該如何就行分類呢？
答：解決辦法也有兩個：（1）窮舉規則。如果對屬性值的任一組合，R中都存在一條規則加以覆寫，則稱規則集R具有窮舉覆寫。這個性質確定每一條記錄都至少被R中的一條規則覆寫。（2）如果規則不是窮舉的，那麼必須添加一個預設規則rd：（）->yd來覆寫那些未被覆寫的記錄。預設規則的前件為空，當所有其他規則失效時被觸發。yd是預設類，通常被指定為沒有被現存規則覆寫的訓練記錄的多數類。
規則的排序方案：
（1）基于規則的排序方案：根據規則的某種度量對規則排序。這種排序方案確定每一個測試記錄都是有=由覆寫它的“最好的”規則來分類。（2）基于類的排序方案。屬于同一類的規則在規則集R中一起出現。然後這些規則根據它們所屬的類資訊一起排序。同一類的規則之間的相對順序并不重要，因為它們屬于同一類。（大多數著名的基于規則的分類器（C4.5規則和RIPPER）都采用基于類的排序方案）。
建立規則的分類器：
（1）順序覆寫。直接從資料中提取規則，規則基于某種評估度量以貪心的方式增長，該算法從包含多個類的資料集中一次提取一個類的規則。在提取規則時，類y的所有訓練記錄被看作是正例，而其他類的訓練記錄則被看作反例。如果一個規則覆寫大多數正例，沒有或僅覆寫極少數反例，那麼該規則是可取的。一旦找到這樣的規則，就删掉它所覆寫的訓練記錄，并把新規則追加到決策表R的尾部（規則增長政策：從一般到特殊或從特殊到一般）（2）RIPPER算法。(和前面那個差不多，隻是規則增長是從一般到特殊的，選取最佳的合取項添加到規則前件中的評判标準是FOIL資訊增益，直到規則開始覆寫反例時，就停止添加合取項。而剪枝是從最後添加的合取項開始的，給定規則ABCD->y，先檢查D是否應該被删除，然後是CD，BCD等)
基于規則的分類器的特征：
（1）規則集的表達能力幾乎等價于決策樹，因為決策樹可以用互斥和窮舉的規則集表示。（2）被很多基于規則的分類器（如RIPPER）所采用的基于類的規則定序方法非常适合于處理不平衡的資料集。
1.3、最近鄰分類器
算法思想：将要測試的記錄與訓練集的每條記錄計算距離，然後選擇距離最小的K個，将K個記錄中的類标号的多數賦給該測試記錄，如果所有的類标号一樣多，則随機選擇一個類标号。該算法的變種：先将訓練集中所有的記錄中相同類标号的記錄算出一個中心記錄，然後将測試記錄與中心記錄算距離，取最小的K個就行（這個方法大大的減少了計算量，原來的算法計算量太大了）。
問：該算法沒有學習的過程啊？
答：是的。是以這個算法稱為消極學習方法，而之前的那些算法稱為積極學習方法。
最近鄰分類器的特征
最近鄰分類器基于局部資訊進行預測，而決策樹和基于規則的分類器則試圖找到一個拟合整個輸入空間的全局模型。正因為這樣的局部分類決策，最近鄰分類器（K很小時）對噪聲非常敏感。
1.3、貝葉斯分類器
貝葉斯定理是一種對屬性集合類變量的機率關系模組化的方法，是一種把類的先驗知識和從資料集中收集的新證據相結合的統計原理。貝葉斯分類器的兩種實作：樸素貝葉斯和貝葉斯信念網絡。貝葉斯定理（如下）(樸素貝葉斯分類的前提假設是屬性之間條件獨立)：
P(Y | X) = P(X | Y)P(Y) / P(X)（1-1）
樸素貝葉斯分類分類思想
假設（1-1）中的X為要分類的記錄，而Y是訓練集中的類标号集合，要将X準确分類就必須使對特定的X和所有的分類标号yi，讓P(yi|X)最大的yi即為測試記錄的類标号。由（1-1）知道要讓左邊最大就是讓後邊最大，而因為X是特定的是以就是使P(X | Y)P(Y)（1-2）最大。此時的yi即為測試記錄的類标号。而要計算(1-2)因為各個屬性是獨立的，是以直接乘即可（具體見hanjiawei的書P203例6-4）。
問：在計算（1-2）時假設出現某項是零了怎麼辦？
答：有兩種方法：（1）拉普拉斯校準或拉普拉斯估計法。假定訓練資料庫D很大，使得需要的每個技術加1造成的估計機率的變化可以忽略不計，但可以友善的避免機率值為零的情況。（如果對q個計數都加上1，則我們必須在用于計算機率的對應分母上加上q）。（2）條件機率的m估計。P(Xi | Yi) = (nc + mp) / (n + m)其中，n是類yi中的執行個體總數，nc是類yi的訓練樣例中取值xi的樣例數，m是稱為等價樣本大小的參數，而p是使用者指定的參數。如果沒有訓練集（即n=0）則P(xi|yi)=p。是以p可以看作是在yi的記錄中觀察屬性值xi的先驗機率。等價樣本大小決定先驗機率p和觀測機率nc/n之間的平衡。
樸素貝葉斯分類器的特征
（1）面對孤立的噪聲點，樸素貝葉斯分類器是健壯的。因為在從資料中估計條件機率時，這些點被平均。通過在模組化和分類時忽略樣例，樸素貝葉斯分類器也可以處理屬性值遺漏問題。（2）面對無關屬性，該分類器是健壯的。如果xi是無關屬性，那麼P(Xi|Y)幾乎變成了均勻分布。Xi的條件機率不會對總的後驗機率産生影響。（3）相關屬性可能會降低樸素貝葉斯分類器的性能，因為對這些屬性，條件獨立假設已不成立。
貝葉斯信念網絡（該方法不要求給定類的所有屬性都條件獨立，而是允許指定哪些屬性條件獨立）：
貝葉斯信念網絡（BBN）
這個方法不要求給定類的所有屬性都條件獨立，而是允許指定哪些屬性條件獨立。貝葉斯信念網絡（用圖形表示一組随機變量之間的機率關系）建立後主要有兩個主要成分：（1）一個有向無環圖，表示變量之間的依賴關系（2）一個機率表（每個節點都有），把各節點和它的直接父節點關聯起來。一個貝葉斯信念網路的大體樣子如下（左邊）：其中表右表隻是LungCancer節點的機率表
貝葉斯信念網絡主要思想
根據已經建立好的貝葉斯信念網絡和每個節點的機率表來預測未知記錄的分類。主要是按照已建立好的網絡根據節點的機率計算先驗機率或後驗機率。計算機率的方法和前面的樸素貝葉斯計算過程相差無多。
貝葉斯信念網絡的建立
網路拓撲結構可以通過主觀的領域專家知識編碼獲得，由于要尋找最佳的拓撲網路有d！種方案計算量較大，一種替代的方法是把變量分為原因變量和結果變量，然後從各原因變量向其對應的結果變量畫弧。
BBN的特點:
（1）貝葉斯網路很适合處理不完整的資料。對屬性遺漏的執行個體可以通過對該屬性的所有可能取值的機率求或求積分來加以處理。（2）因為資料和先驗知識以機率的方式結合起來了，是以該方法對模型的過分拟合問題是非常魯棒的。
問：樸素貝葉斯沒有學習的過程，那麼是否可以說樸素貝葉斯是消極學習法分類？
答：（1）樸素貝葉斯隻是貝葉斯分類的一種實作形式，而實作形式還有貝葉斯網絡但是貝葉斯網絡是有學習過程的。是以不能說貝葉斯分類時消極學習法。（2）其實樸素貝葉斯是消極學習方法
1.4、人工神經網絡（ANN）
ANN是有互相連接配接的結點和有項鍊構成。
（1）感覺器。感覺器的一般模型如下所示：
分類思想：Ij = Sum(Wi*Oi) + a，其中Ij為特定的類标号,Wi為輸入向量的權重,Oi為輸入屬性的值，a為偏置因子。用這個模型就可以對未知的記錄分類。圖中的激活函數的用處是：将某個Ij的計算值映射到相應的類标号中。在訓練一個感覺器時，最初将所有的權重随機取值，而訓練一個感覺器模型就相當于不斷的調整鍊的權值，直到能拟合訓練資料的輸入輸出關系為止。其中權值更新公式如下：Wj(k+1) = Wjk + r(yi - yik)Xij。其中Wk是第k次循環後第i個輸傳入連結上的權值，參數r稱為學習率，Xij是訓練樣例的Xi的第j個屬性值。學習率值在0到1之間，可以用來控制每次循環時的調整量。自适應r值：r在前幾次循環時值相對較大，而在接下來的循環中逐漸減少。
（2）多層人工神經網絡
一個多層人工神經網絡的示意圖如下兩圖所示：其中左邊是多類标号情況，右邊是一類情況。
ANN學習中的設計問題：（1）确定輸入層的結點數目（2）确定輸出層的結點數目（3）選擇網絡拓撲結構（4）初始化權值和偏置（随機值）（5）去掉有遺漏的訓練樣例，或者用最合理的值來代替。
ANN的特點:
（1）至少含有一個隐藏層的多層神經網絡是一種普适近似，即可以用來近似任何目标函數。（2）ANN可以處理備援特征，因為權值在訓練過程中自動學習。備援特征的權值非常小。（3）神經網絡對訓練資料中的噪聲非常敏感。噪聲問題的一種方法是使用确認集來确定模型的泛化誤差；另一種方法是每次疊代把權值減少一個因子。（4）ANN權值學習使用的梯度下降方法經常會收斂到局部最小值。避免方法是在權值更新公式中加上一個自動量。
1.5、支援向量機（SVM）
它可以很好的應用于高維資料，避免了維災難問題，它使用訓練執行個體的一個子集來表示決策邊界，該子集稱作支援向量。SVM尋找具有最大邊緣的超平面（比那些較小的決策邊界具有更好的泛化誤差），是以也經常稱為最大邊緣分類器。最大邊緣的決策邊界如韓佳偉書P220圖6-21所示：分類思想（1）線上性可分的情況下就是要學習（找）到這個最大邊緣的決策邊界（通過線性規劃或拉格朗日乘子來求得），當然也允許有一定的誤差（可以有少量的結點分在了它不該在的類，但隻要在能夠容忍的範圍就行），然後利用這個最大邊緣的決策邊界來分類，結果落在一邊的為一類，在另一邊的為另一類（2）線上性不可分的情況下，将原來的資料從原先的坐标空間X轉換到一個新的坐标空間中，進而可以在變換後的坐标空間中使用一個線性的決策邊界來劃分樣本的類标号（主要技術包括：非線性變換、核技術和Mercer定理）。
SVM的特點:
（1）SVM學習問題可以表示為凸優化問題，是以可以利用已知的有效算法發現目标函數的全局最小值（2）通過對資料中每個分類屬性值引入一個啞變量，SVM可以應用于分類資料
1.6、組合方法
該方法聚集多個分類器的預測來提高分類的準确率，這些技術稱為組合或分類器組合方法。組合方法由訓練資料建構一組基分類器，然後通過對每個分類器的預測進行投票來進行分類。預測過程如下所示：
由上面的分類過程可以看出當誤差率大于0.5時，組合分類器的性能比基分類器更差。組合分類器的性能優于單個分類器必須滿足兩個必要條件：（1）基分類器之間應該是互相獨立的（輕微相關也行）；（2）基分類器應當好于随機猜測分類器。
建構組合分類器的方法
（1）通過處理訓練資料集。根據某種抽樣分布，通過對原始資料進行再抽樣來得到多個訓練集（如有放回随機抽樣）。一般得到的訓練集和原始資料集一樣大。然後使用特定的學習算法為每個訓練集建立一個分類器（裝袋和提升是兩種處理訓練集的組合方法）。（2）通過處理輸入特征。通過選擇輸入特征的子集來形成每個訓練集。對那些含有大量備援特征的資料集，這種方法的性能非常好（随機深林就是一種處理輸入特征的組合方法，它使用決策樹作為基分類器）。（3）通過處理類标号。這種方法适用于類數足夠多的情況。這種方法先将所有的類劃分為兩個大類，然後将兩個大類的每個大類劃分為兩個次大類……，預測時按照前面的分類遇到一個分類結點得一票，最後得票數最多的那個就是最終的類。（4）通過處理學習算法。如果在同一個訓練集上用同一個學習算法得到的分類器模型不一樣，就可以多做幾次以建立多個基分類器。
組合方法對于不穩定的分類器效果很好。不穩定分類器是對訓練資料集微小的變化都很面幹的基分類器。不穩定分類器的例子包括決策樹、基于規則的分類器和人工神經網絡。
（1）裝袋。裝袋又稱自助聚集，是一種根據均勻分布從資料集中重複抽樣的（有放回的）技術。每個自助樣本集都和原始資料一樣大。然後對每個樣本集訓練一個基分類器，訓練k個分類器後，測試樣本被指派到得票最高的類。用于噪聲資料，裝袋不太受過分拟合的影響。
（2）提升。是一個疊代過程，用來自适應地改變樣本的分布，使得基分類器聚焦在那些很難分的樣本上。例如開始時所有的樣本都賦予相同的權值1/N, 然後按這個機率抽取樣本集，然後得到一個分類器，并用它對原始資料集中的所有樣本進行分類。每一輪結束時更新樣本的權值。增加錯誤分類的樣本的權值，減少被正确分類的樣本的權值，這迫使分類器在随後的疊代中關注那些很難分類的樣本。通過聚集每一輪得到的分類器，就得到最終的分類器。目前有幾個提升算法的實作，它們的差别在于：（1）每輪提升結束時如何更新訓練樣本的權值；（2）如何組合每個分類器的預測。
Android：在該算法中，基分類器Ci的重要性依賴于它的錯誤率。算法思想：首先初始化N個樣本的權值（w = 1/N），然後對于第i次（總共k次，産生k個基分類器）提升（其他次一樣），根據w通過對D進行有放回抽樣得到訓練集Di,然後根據Di得到一個基分類器Ci,用Ci對訓練集D中的樣本進行分類。然後計算分類的權重誤差，如果權重誤差大于0.5，就将所有樣本的權值重設為為1/N，否則用ai更新每個樣本的權值。得到k個基分類器後，然後合并k個基分類器得到預測結果。Android 算法将每一個分類器Cj的預測值根據 aj進行權重，而不是使用多數表決的方案。這種機制允許Android 懲罰那些準确率很差的模型，如那些在較早的提升輪産生的模型。另外，如果任何中間輪産生高于50%的誤差，則權值将被恢複為開始的一緻值wi = 1/N，并重新進行抽樣。Android 算法傾向于那些被錯誤分類的樣本，提升技術很容易受過分拟合的影響。
（3）随機森林。它是一類專門為決策樹分類器設計的組合方法。它結合多顆決策樹做出預測。與Android算法使用的自适應方法不同，Android中機率分布是變化的，以關注難分類的樣本，而随機森林則采用一個固定的機率分布來産生随機向量。随機森林與裝袋不同之處在于（1）裝袋可以用任何分類算法産生基分類器而随機森林隻能用決策樹産生基分類器。（2）裝袋最後組合基分類器時用的投票方法二随機森林不一定用投票。（3）随機森林的每個基分類器是一個樣本集的随機向量而裝袋是用的有放回抽樣來産生樣本。随機森林的的決策樹在選擇分類屬性時，随機選擇F個輸入特征（而不是考察所有可用的特征）來對決策樹的節點進行分裂，然後樹完全增長而不進行任何剪枝，最後用多數表決的方法來組合預測（這種方法叫Forest-RI，其中RI是指随機輸入選擇）。注意此時如果F太小，樹之間的相關度就減弱了，F太大樹分類器的強度增加，折中通常F取log2d + 1，其中d是輸入特征數。如果d太小，可以建立輸入特征的線性組合，在每個節點，産生F個這種随機組合的新特征，并從中選擇最好的來分裂節點，這種方法稱為Forest-RC。随機森林的分類準确率和Android差不多，但是随機森林對噪聲更加魯棒，運作速度也快得多。
1.6、不平衡類問題
有時候需要準确分類訓練集中的少數類而對多數類不是太關心。如不合格産品對合格産品。但是這樣建立的模型同時也容易受訓練資料中噪聲的影響。
新定的名額（過去的名額不頂用如：準确率不頂用）：真正率（靈敏度）、真負率（特指度）、假正率、假負率、召回率、精度。
（1）接受者操作特征（ROC）曲線。該曲線是顯示分類器真正率和假正率之間的折中的一種圖形化方法。在一個ROC曲線中，真正率沿y軸繪制，而假正率沿x軸繪制。一個好的分類模型應該盡可能靠近圖的左上角。随機預測分類器的ROC曲線總是位于主對角線上。
ROC曲線下方的面積（AUC）提供了評價模型的平均性能的另一種方法。如果模型是完美的，則它在ROC曲線下方的面積等于1，如果模型僅僅是簡單地随機猜測，則ROC曲線下方的面積等于0.5。如果一個模型好于另一個，則它的ROC曲線下方的面積較大。為了繪制ROC曲線，分類器應當能夠産生可以用來評價它的預測的連續值輸出，從最有可能分為正類的記錄到最不可能的記錄。這些輸出可能對應于貝葉斯分類器産生的後驗機率或人工神經網絡産生的數值輸出。（繪制ROC曲線從左下角開始到右上角結束，繪制過程見hanjiawei P243）。
（2）代價敏感學習。代價矩陣對将一個類的記錄分類到另一個類的懲罰進行編碼。代價矩陣中的一個負項表示對正确分類的獎勵。算法思想：将稀有的類标号預測錯誤的代價權值設為很大，則在計算總代價時，它的權值較高，是以如果分類錯誤的話，代價就較高了。代價敏感度技術在構模組化型的過程中考慮代價矩陣，并産生代價最低的模型。例如：如果假負錯誤代價最高，則學習算法通過向父類擴充它的決策邊界來減少這些錯誤。
（2）代價敏感學習. 主要思想：改變執行個體的分布，而使得稀有類在訓練資料集得到很好的表示。有兩種抽樣方法：第一種選擇正類樣本的數目和稀有樣本的數目一樣多，來進行訓練（可以進行多次，每次選擇不同的正類樣本）。第二種複制稀有樣本（或者在已有的稀有樣本的鄰域中産生新的樣本）使得和正類樣本一樣多。注意，第二種方法對于噪聲資料可能導緻模型過分拟合。
1.6、多類問題(結果類标号不止兩個
解決方法：（1）将多類問題分解成K個二類問題。為每一個類yi Y（所有的類标号集合）建立一個二類問題，其中所有屬于yi的樣本都被看做正類，而其他樣本都被看做負類。然後建構一個二進制分類器，将屬于yi的樣本從其他的類中分離出來。（稱為一對其他（1-r）方法）。（2）建構K（K-1）/2個二類分類器，每一個分類器用來區分一對類（yi，yj）。當為類（yi，yj）建構二類分類器時，不屬于yi或yj的樣本被忽略掉（稱為一對一（1-1）方法）。這兩種方法都是通過組合所有的二進制分類器的預測對檢驗執行個體分類。組合預測的典型做法是使用投票表決，将驗證樣本指派到得票最多的類。
糾錯輸出編碼（ECOC）：前面介紹的兩種處理多類問題的方法對二進制分類的錯誤太敏感。ECOC提供了一種處理多類問題更魯棒的方法。該方法受資訊理論中通過噪聲信道發送資訊的啟發。基本思想是借助于代碼字向傳輸資訊中增加一些備援，進而使得接收方能發現接受資訊中的一些錯誤，而且如果錯誤量很少，還可能恢複原始資訊。具體：對于多類學習，每個類yi用一個長度為n的唯一位串來表示，稱為它的代碼字。然後訓練n個二進制分類器，預測代碼子串的每個二進制位。檢驗執行個體的預測類由這樣的代碼字給出。該代碼字到二進制分類器産生的代碼字海明距離最近（兩個位串之間的海明距離是它們的不同的二進制位的數目）。糾錯碼的一個有趣的性質是，如果任意代碼字對之間的最小海明距離為d，則輸出代碼任意 (d-1) / 2個錯誤可以使用離它最近的代碼字糾正。注意：為通信任務設計的糾正碼明顯不同于多類學習的糾正嗎。對通信任務，代碼字應該最大化各行之間的海明距離，使得糾錯可以進行。然而，多類學習要求将代碼字列向和行向的距離很好的分開。較大的列向距離可以確定二進制分類器是互相獨立的，而這正是組合學習算法的一個重要要求。