非監督學(xué)習方法大全
篇一：非監督學(xué)習法
非監督學(xué)習法
本章重點(diǎn)
1. 什么叫非監督學(xué)習方法，什么叫有監督學(xué)習方法？
2. 非監督學(xué)習方法主要的用途
3. 非監督學(xué)習方法的兩種基本處理方法：按分布密集程度劃分，與按相似度聚類(lèi)劃分
4. 按分布密度程度劃分的基本方法
5. 動(dòng)態(tài)聚類(lèi)方法與分級聚類(lèi)方法的概念
6. 典型的動(dòng)態(tài)聚類(lèi)方法C-均值算法與ISODATA算法
7. 使用非歐氏距離計算相似度的動(dòng)態(tài)聚類(lèi)方法
8. 分級聚類(lèi)方法
本章課前思考題
1. 如果給機器一維數據，機器能自動(dòng)地找出其中存在的規律嗎？
2. 有人把非監督學(xué)習方法叫無(wú)教師的學(xué)習，而把第二章、第三章討論的內容成為有監督學(xué)習，又稱(chēng)有教師的學(xué)習，你知道誰(shuí)是教師嗎？教師的作用體現在哪里？
3. 機器能總結數據中存在的哪些規律呢？
4. 機器能總結天氣變化的規律，給出天氣預報嗎？
5. 機器能炒股嗎？
6. 非監督學(xué)習方法與數據有關(guān)系嗎？
知識樹(shù)
5.1 引 言
以前各章討論的分類(lèi)器設計方法都是在樣本集中的類(lèi)別標簽已知的條件下進(jìn)行的，這些樣本稱(chēng)為訓練樣本。在樣本標簽已知的情況下，可以統計出各類(lèi)訓練樣本不同的描述量，如其概率分布，或在特征空間分布的區域等，利用這些參數進(jìn)行分類(lèi)器設計，稱(chēng)為有監督的學(xué)習方法。然而在實(shí)際應用中，不少情況下無(wú)法預先知道樣本的標簽，也就是說(shuō)沒(méi)有訓練樣本，因而只能從原先沒(méi)有樣本標簽的樣本集開(kāi)始進(jìn)行分類(lèi)器設計，這就是通常說(shuō)的無(wú)監督學(xué)習方法。對一個(gè)具體問(wèn)題來(lái)說(shuō)有監督與無(wú)監督的作法是不相同的。
人們日常生活中經(jīng)常要觀(guān)察事物與分析事物，從中尋找其規律性，這就是非監督學(xué)習方法要解決的問(wèn)題。例如人們見(jiàn)到圖5.1的道路圖時(shí)，會(huì )發(fā)現中間有一條帶與圖中其它區域不同，見(jiàn)到圖5.3會(huì )發(fā)現在這個(gè)二維空間中有數據顯現出聚成兩類(lèi)的現象。這就是事物(對我們來(lái)說(shuō)就是數據集)自身體現出的一些規律性，非監督學(xué)習方法就是尋找數據集中體現出來(lái)的規律性。從中我們可以強調非監督學(xué)習與有監督學(xué)習方法的以下幾種不同點(diǎn)：
1． 有監督學(xué)習方法必須要有訓練集與測試樣本。在訓練集中找規律，而對測試樣本使用這種規律；而非監督學(xué)習沒(méi)有訓練集這一說(shuō)，只有一組數據，在該組數據集內尋找規律。
2． 有監督學(xué)習方法的目的就是識別事物，識別的結果表現在給待識別數據加上了標號。因此訓練樣本集必須由帶標號的樣本組成。而非監督學(xué)習方法只有要分析的數據集本身，預先沒(méi)有什么標號。如果發(fā)現數據集呈現某種聚集性，則可按自然的聚集性分類(lèi)，但不以與某種預先的分類(lèi)標號對上號為目的。例如圖
5.1道路圖像，有監督學(xué)習方法的目的是找到“道路”，而非監督學(xué)習方法則只是將中間一條帶狀區域區分開(kāi)來(lái)，本質(zhì)上講與“道路”這個(gè)標號沒(méi)有關(guān)系。
3． 非監督學(xué)習方法在尋找數據集中的規律性，這種規律性并不一定要達到劃分數據集的目的，也就是說(shuō)不一定要“分類(lèi)”。這一點(diǎn)是比有監督學(xué)習方法的用途要廣泛。譬如分析一堆數據的主分量，或分析數據集有什么特點(diǎn)都可以歸于非監督學(xué)習方法的范疇。
4． 用非監督學(xué)習方法分析數據集的主分量與用K-L變換計算數據集的主分量又有區別。應該說(shuō)后者從方法上講不是一種學(xué)習方法。因此用K-L變換找主分量不屬于非監督學(xué)習方法，即方法上不是。而通過(guò)學(xué)習逐漸找到規律性這體現了學(xué)習方法這一點(diǎn)。在人工神經(jīng)元網(wǎng)絡(luò )中尋找主分量的方法屬于非監督學(xué)習方法。 以上四點(diǎn)是對非監督學(xué)習方法的定義，及與有監督學(xué)習方法的區別。
例如圖5.1表示對一幅道路圖像按路面與非路面分類(lèi)可用兩種不同做法，其中左圖是在圖像中路面區與非路面中各找一個(gè)窗口，將其中每個(gè)象素分別作為這兩類(lèi)的訓練樣本集，用這兩個(gè)樣本集在特征空間的分布參數進(jìn)行設計。而無(wú)監督學(xué)習方法則不同，它不預先選擇樣本類(lèi)別的樣本集，而是將整幅圖的像素都作為待分類(lèi)樣本集，通過(guò)它們在特征空間中表現出來(lái)的聚類(lèi)現象，把不同類(lèi)別劃分開(kāi)。
圖5.1的有監督學(xué)習中，樣本集分布呈現交迭情況，而無(wú)監督學(xué)習方法由于沒(méi)有類(lèi)別樣本指導，無(wú)法確定它們的交迭情況，只能按分布的聚類(lèi)情況進(jìn)行劃分。在類(lèi)似于該例的實(shí)際應用問(wèn)題中，預先選定不同類(lèi)別的樣本往往不可能，如時(shí)間不允許，或無(wú)法用人工干予等因素。另外在某些有監督學(xué)習方法中，也往往需要
利用聚類(lèi)方法將樣本按其分布劃分成若干子類(lèi)等。聚類(lèi)方法就是無(wú)監督學(xué)習方法的一個(gè)內容，它是經(jīng)常應用的一門(mén)技術(shù)。
圖 5.1 無(wú)監督學(xué)習方法可以分成兩大類(lèi)，一類(lèi)為基于概率密度函數估計的直接方法，指設法找到各類(lèi)別在特征空間的分布參數再進(jìn)行分類(lèi)。另一類(lèi)稱(chēng)為基于樣本間相似性度量的間接聚類(lèi)方法，其原理是設法定出不同類(lèi)別的核心或初始類(lèi)核，然后依據樣本與這些核心之間的相似性度量將樣本聚集成不同類(lèi)別。下面分別討論這兩種方法。
最常用的基于概率密度估計的直接方法的例子是直方圖方法。例如我們統計一所學(xué)校中學(xué)生身高分布就往往可采用直方圖方法，把身高劃分成一段段，如1米到1米75算一段，然后對每一段統計身高在此范圍內的學(xué)生數，得到直方圖。如果這個(gè)學(xué)校的男女學(xué)生數目相近，則我們就會(huì )發(fā)現該直方圖會(huì )體現出有兩個(gè)分布高峰。那么找到兩高峰中的谷點(diǎn)，就會(huì )將學(xué)生劃分成兩類(lèi)。
因此，使用概率統計方法的關(guān)鍵是能找出各個(gè)峰值區，這就是5.2節中的主要內容。另一種方法則在5.3節中再進(jìn)一步討論。5.2 單峰子類(lèi)的分離方法
對于樣本在某一種度量中的分布統計，一般稱(chēng)為直方圖統計，在樣本數量很大時(shí)，又可作為概率統計的估計。由于這種方法基于將樣本投影到某個(gè)坐標軸上，因而稱(chēng)為投影方法。 使用投影方法有兩個(gè)組成部分，一個(gè)是如何設計合適的坐標系統， 另一是如何設計直方圖。
如果對于各類(lèi)別的類(lèi)條件概率分布一無(wú)所知，我們只按待分類(lèi)樣本在特征空間的自然聚集進(jìn)行劃分。如圖5.2所示的一維特征空間中，樣本在整個(gè)特征空間中呈現出兩個(gè)分布高峰，如果從分布的谷點(diǎn)將此特征空間劃分為兩個(gè)區，則對應每個(gè)區域，樣本分布就只有一個(gè)峰值，這些區域被稱(chēng)為單峰區域，而每個(gè)單峰區域則被看作不同的決策域。落在同一單峰區域的待分類(lèi)樣本就被劃分成同一類(lèi)，稱(chēng)為單峰子類(lèi)。下面討論一些單峰子類(lèi)的劃分算法。
圖 5.2
5.2.1 投影法
投影法的原理很簡(jiǎn)單，拿圖5.3顯示的一個(gè)二維空間為例。在該分類(lèi)問(wèn)題中，兩個(gè)類(lèi)別分別在其特征空間中形成兩個(gè)聚類(lèi)，圖中用兩個(gè)區域的輪廓勾出這兩類(lèi)樣本聚類(lèi)的區域。對人來(lái)說(shuō)一旦畫(huà)出這兩類(lèi)的空間分布，可以很容易地判斷出這兩類(lèi)在特征空間聚集的區域，但是對計算機來(lái)說(shuō)，要識別出這兩類(lèi)的分布情況，直接從二維的圖形來(lái)說(shuō)是很困難的，更不用說(shuō)在高維特征空間直接對樣本的分布作出判斷了。一個(gè)辦法是如果將樣本對某個(gè)方向的軸作投影，或換句話(huà)說(shuō)只取這些樣本的某一分量的統計值來(lái)看，樣本的分布往往顯現出高峰與低谷，找到低谷，將峰值分別劃分在不同的區域中，每個(gè)區域只有一個(gè)高峰，并把聚在同一高峰下的樣本劃分為一類(lèi)，這是計算機容易做到的。對于樣本在某一種度量中的分布統計，一般稱(chēng)為直方圖統計，在樣本數量很大時(shí)，又可作為概率統計的估計。由于這種方法基于將樣本投影到某個(gè)坐標軸上，因而稱(chēng)為投影方法。
圖 5.3
使用投影方法有兩個(gè)組成部分，一個(gè)是如何設計合適的坐標系統，另一是如何設計直方圖。在樣本屬性完全不知的情況下，如何選擇坐標系統，是比較困難的，因為這時(shí)還沒(méi)有一個(gè)準則函數來(lái)表征這樣一個(gè)坐標系統的性質(zhì)。一種啟發(fā)式的辦法是使待分類(lèi)的樣本在某個(gè)坐標軸方向具有最大的分散性，這可以采用上一章討論過(guò)的K-L變換方法。具體說(shuō)來(lái)是用混合樣本協(xié)方差矩陣作為K-L變換的產(chǎn)生矩陣，找到其特征值，并按大小排序，對應最大特征值的特征向量對此混合樣本來(lái)說(shuō)，離散程度最大，預期能發(fā)現明顯的峰值，但是這種方法并不能保證分出各個(gè)聚類(lèi)，例如圖5.4所示情況，其兩個(gè)特征向量 都只呈現單峰狀態(tài)，無(wú)法用此法將他們分開(kāi)。
圖 5.4
投影法的具體算法分以下幾個(gè)步驟：
步驟1： 計算樣本協(xié)方差矩陣具有最大特征值的特征向量Uj，把數據投影
到Uj軸上。
步驟2： 用直方圖方法求數據的邊緣概率密度函數。
步驟3： 在直方圖的峰值間求最小值，在這些最小點(diǎn)作垂直于Uj的各個(gè)超平面把數據劃分為若干個(gè)聚類(lèi)。
步驟4： 如果在這個(gè)軸上沒(méi)有這樣的最小值，則用下一個(gè)最大特征值對應的特征向量重復以上過(guò)程。
步驟5： 對每個(gè)得到的子集(聚類(lèi))重復上述過(guò)程，直到每個(gè)集不能再分(為單峰)為止。
5.2.2 基于對稱(chēng)集性質(zhì)的單峰子集分離法
不要求
在一個(gè)多維空間中給單峰區域下嚴格的定義是困難的。譬如一個(gè)單峰區域的數據集用Γ表示，峰值在處形成，則可寫(xiě)在
(5-1)
但是僅滿(mǎn)足(5-1)式的區域并不能保證是單峰區。另一方面，如果考慮數據Γ，其中任何一對點(diǎn)y1和y2之間的距離用
式的性質(zhì)外，還具有以下性質(zhì)： 表示，該數據集Γ除了具備(5-1)
篇二：有監督學(xué)習(supervised learning)和無(wú)監督學(xué)習(unsupervised learning)
有監督學(xué)習(supervised learning)和無(wú)監督學(xué)習(unsupervised learning) 機器學(xué)習的常用方法，主要分為有監督學(xué)習(supervised learning)和無(wú)監督學(xué)習(unsupervised learning)。監督學(xué)習，就是人們常說(shuō)的分類(lèi)，通過(guò)已有的訓練樣本（即已知數據以及其對應的輸出）去訓練得到一個(gè)最優(yōu)模型（這個(gè)模型屬于某個(gè)函數的集合，最優(yōu)則表示在某個(gè)評價(jià)準則下是最佳的），再利用這個(gè)模型將所有的輸入映射為相應的輸出，對輸出進(jìn)行簡(jiǎn)單的判斷從而實(shí)現分類(lèi)的目的，也就具有了對未知數據進(jìn)行分類(lèi)的能力。在人對事物的認識中，我們從孩子開(kāi)始就被大人們教授這是鳥(niǎo)啊、那是豬啊、那是房子啊，等等。我們所見(jiàn)到的景物就是輸入數據，而大人們對這些景物的判斷結果（是房子還是鳥(niǎo)�。┚褪窍鄳妮敵�。當我們見(jiàn)識多了以后，腦子里就慢慢地得到了一些泛化的模型，這就是訓練得到的那個(gè)（或者那些）函數，從而不需要大人在旁邊指點(diǎn)的時(shí)候，我們也能分辨的出來(lái)哪些是房子，哪些是鳥(niǎo)。監督學(xué)習里典型的例子就是KNN、SVM。無(wú)監督學(xué)習（也有人叫非監督學(xué)習，反正都差不多）則是另一種研究的比較多的學(xué)習方法，它與監督學(xué)習的不同之處，在于我們事先沒(méi)有任何訓練樣本，而需要直接對數據進(jìn)行建模。這聽(tīng)起來(lái)似乎有點(diǎn)不可思議，但是在我們自身認識世界的過(guò)程中很多處都用到了無(wú)監督學(xué)習。比如我們去參觀(guān)一個(gè)畫(huà)展，我們完全對藝術(shù)一無(wú)所知，但是欣賞完多幅作品之后，我們也能把它們分成不同的派別（比如哪些更朦朧一點(diǎn)，哪些更寫(xiě)實(shí)一些，即使我們不知道什么叫做朦朧派，什么叫做寫(xiě)實(shí)派，但是至少我們能把他們分為兩個(gè)類(lèi)）。無(wú)監督學(xué)習里典型的例子就是聚類(lèi)了。聚類(lèi)的目的在于把相似的東西聚在一起，而我們并不關(guān)心這一類(lèi)是什么。因此，一個(gè)聚類(lèi)算法通常只需要知道如何計算相似度就可以開(kāi)始工作了。
那么，什么時(shí)候應該采用監督學(xué)習，什么時(shí)候應該采用非監督學(xué)習呢？我也是從一次面試的過(guò)程中被問(wèn)到這個(gè)問(wèn)題以后才開(kāi)始認真地考慮答案。一種非常簡(jiǎn)單的回答就是從定義入手，如果我們在分類(lèi)的過(guò)程中有訓練樣本(training data)，則可以考慮用監督學(xué)習的方法；如果沒(méi)有訓練樣本，則不可能用監督學(xué)習的方法。但是事實(shí)上，我們在針對一個(gè)現實(shí)問(wèn)題進(jìn)行解答的過(guò)程中，即使我們沒(méi)有現成的訓練樣本，我們也能夠憑借自己的雙眼，從待分類(lèi)的數據中人工標注一些樣本，并把他們作為訓練樣本，這樣的話(huà)就可以把條件改善，用監督學(xué)習的方法來(lái)做。當然不得不說(shuō)的是有時(shí)候數據表達的會(huì )非常隱蔽，也就是說(shuō)我們手頭的信息不是抽象的形式，而是具體的一大堆數字，這樣我們很難憑借人本身對它們簡(jiǎn)單地進(jìn)行分類(lèi)。這個(gè)說(shuō)的好像有點(diǎn)不大明白，舉個(gè)例子說(shuō)就是在bag-of-words模型的時(shí)候，我們利用k-means的方法聚類(lèi)從而對數據投影，這時(shí)候用k-means就是因為我們當前到手的只有一大堆數據，而且是很高維的，當我們想把他們分為50個(gè)類(lèi)的時(shí)候，我們已經(jīng)無(wú)力將每個(gè)數據標記說(shuō)這個(gè)數應該是哪個(gè)類(lèi)，那個(gè)數又應該是哪個(gè)類(lèi)了。所以說(shuō)遇到這種情況也只有無(wú)監督學(xué)習能夠幫助我們了。那么這么說(shuō)來(lái)，能不能再深入地問(wèn)下去，如果有訓練樣本（或者說(shuō)如果我們可以獲得到一些訓練數據的話(huà)），監督學(xué)習就會(huì )比無(wú)監督學(xué)習更合適呢？（照我們單純地想，有高人教總比自己領(lǐng)悟來(lái)的準，來(lái)的快吧�。┪矣X(jué)得一般來(lái)說(shuō)，是這樣的，但是這要具體看看訓練數據的獲取。本人在最近課題的研究中，手動(dòng)標注了大量的訓練樣本（當然這些樣本基本準確了），而且把樣本畫(huà)在特征空間中發(fā)現線(xiàn)性可分性非常好，只是在分類(lèi)面附近總有一些混淆的數據樣本，從而用線(xiàn)性分類(lèi)器進(jìn)行分類(lèi)之后這樣樣本會(huì )被誤判。然而，如果用混合高斯模型(GMM)來(lái)分的話(huà)，這些易混淆的點(diǎn)被正確分類(lèi)的更多了。對這個(gè)現象的一個(gè)解釋?zhuān)褪遣还苁怯柧殬颖�，還是待聚類(lèi)的數據，并不是所有數據都是相互獨立同分布的。換句話(huà)說(shuō)，數據與數據的分布之間存在聯(lián)系。在我閱讀監督學(xué)習的大量材料中，大家都沒(méi)有對訓練數據的這一假設（獨立同分布）進(jìn)行說(shuō)明，直到我閱讀到一本書(shū)的提示后才恍然大悟。對于不同的場(chǎng)景，正負樣本的分布如果會(huì )存在偏移（可能是大的偏移，也可能偏移比較�。�，這樣的話(huà)用監督學(xué)習的效果可能就不如用非監督學(xué)習了。
篇三：監督學(xué)習算法基礎知識整理
第三章 監督學(xué)習算法
監督學(xué)習又稱(chēng)為分類(lèi)（Classification）或者歸納學(xué)習（Inductive Learning）。幾乎適用于所有領(lǐng)域，包括文本和網(wǎng)頁(yè)處理。給出一個(gè)數據集D，機器學(xué)習的目標就是產(chǎn)生一個(gè)聯(lián)系屬性值集合A和類(lèi)標集合C的分類(lèi)/預測函數（Classification/Prediction Function），這個(gè)函數可以用于預測新的屬性集合的類(lèi)標。這個(gè)函數又被稱(chēng)為分類(lèi)模型（Classification Model）、預測模型（Prediction Model）。這個(gè)分類(lèi)模型可以是任何形式的，例如決策樹(shù)、規則集、貝葉斯模型或者一個(gè)超平面。
在監督學(xué)習（Supervised Learning）中，已經(jīng)有數據給出了類(lèi)標；與這一方式相對的是無(wú)監督學(xué)習（Unsupervised Learning），在這種方式中，所有的類(lèi)屬性都是未知的，算法需要根據數據集的特征自動(dòng)產(chǎn)生類(lèi)屬性。其中算法中用于進(jìn)行學(xué)習的數據集叫做訓練數據集，當使用學(xué)習算法用訓練數據集學(xué)習得到一個(gè)模型以后，我們使用測試數據集來(lái)評測這個(gè)模型的精準度。
機器學(xué)習的最基本假設：訓練數據的分布應該與測試數據的分布一致。
訓練算法：訓練算法就是給定一組樣本，我們計算這些參數的方法。本節簡(jiǎn)要介紹以下幾種常用的機器學(xué)習算法，比如決策樹(shù)，樸素貝葉斯，神經(jīng)網(wǎng)絡(luò )，支持向量機，線(xiàn)性最小平方擬合，kNN，最大熵等。
3.1 兩類(lèi)感知器
見(jiàn)課本
3.2 多類(lèi)感知器
見(jiàn)課本
3.3 決策樹(shù)算法
決策樹(shù)學(xué)習算法是分類(lèi)算法中最廣泛應用的一種技術(shù)，這種算法的分類(lèi)精度與其他算法相比具有相當的競爭力，并且十分高效。
決策樹(shù)是一個(gè)預測模型；他代表的是對象屬性與對象值之間的一種映射關(guān)系。樹(shù)中每個(gè)節點(diǎn)表示某個(gè)對象屬性，而每個(gè)分叉路徑則代表的某個(gè)可能的屬性值，而每個(gè)葉結點(diǎn)則對應從根節點(diǎn)到該葉節點(diǎn)所經(jīng)歷的路徑所表示的對象的值（類(lèi)別）。決策樹(shù)僅有單一輸出，若欲有復數輸出，可以建立獨立的決策樹(shù)以處理不同輸出。
如何構造精度高、規模小的決策樹(shù)是決策樹(shù)算法的核心內容。決策樹(shù)構造可以分兩步進(jìn)行。
決策樹(shù)的生成：由訓練樣本集生成決策樹(shù)的過(guò)程。一般情況下，訓練樣本數據集
是根據實(shí)際需要有歷史的、有一定綜合程度的，用于數據分析處理的數據集。
1. 樹(shù)以代表訓練樣本的單個(gè)結點(diǎn)開(kāi)始。
2. 如果樣本都在同一個(gè)類(lèi)．則該結點(diǎn)成為樹(shù)葉，并用該類(lèi)標記。
3. 否則，算法選擇最有分類(lèi)能力的屬性作為決策樹(shù)的當前結點(diǎn)。
4. 根據當前決策結點(diǎn)屬性取值的不同，將訓練樣本數據集分為若干子集，每個(gè)取值形成一個(gè)分枝。
5. 針對上一步得到的一個(gè)子集，重復進(jìn)行先前步驟，形成每個(gè)劃分樣本上的決策樹(shù)。
6. 遞歸劃分步驟僅當下列條件之一成立時(shí)停止：
(a) 給定結點(diǎn)的所有樣本屬于同一類(lèi)。
(b) 沒(méi)有剩余屬性可以用來(lái)進(jìn)一步劃分樣本。以樣本組中個(gè)數最多的類(lèi)別作為類(lèi)別標記。
決策樹(shù)的剪技：決策樹(shù)的剪枝是對上一階段生成的決策樹(shù)進(jìn)行檢驗、校正和修下的過(guò)程，主要是用新的樣本數扼集（稱(chēng)為測試數據集）中的數據校驗決策樹(shù)生成過(guò)程中產(chǎn)生的初步規則，將那些影響預衡準確性的'分枝剪除。由于數據表示不當、有噪聲或者由于決策樹(shù)生成時(shí)產(chǎn)生重復的子樹(shù)等原因，都會(huì )造成產(chǎn)生的決策樹(shù)過(guò)大。因此，簡(jiǎn)化決策樹(shù)是一個(gè)不可缺少的環(huán)節。尋找一棵最優(yōu)決策樹(shù)，主要應解決以下3個(gè)最優(yōu)化問(wèn)題：
1. 生成最少數目的葉子節點(diǎn)；
2. 生成的每個(gè)葉子節點(diǎn)的深度最��；
3. 生成的決策樹(shù)葉子節點(diǎn)最少且每個(gè)葉子節點(diǎn)的深度最小。
例如，對于表3-1所示的貸款申請的數據集，可以學(xué)習到一種決策樹(shù)結構，表示為圖3-1。
表3-1 貸款申請數據
根據數據集建立的一種決策樹(shù)結構如下：
圖3-1 對應與表3-1的決策樹(shù)
樹(shù)中包含了決策點(diǎn)和葉子節點(diǎn)，決策點(diǎn)包含針對數據實(shí)例某個(gè)屬性的一些測試，而一個(gè)葉子節點(diǎn)則代表了一個(gè)類(lèi)標。
一棵決策樹(shù)的構建過(guò)程是不斷的分隔訓練數據，以使得最終分隔所得到的各個(gè)子集盡可能的純。一個(gè)純的子集中的數據實(shí)例類(lèi)標全部一致。決策樹(shù)的建立并不是唯一的，在實(shí)際中，我們希望得到一棵盡量小且準確的決策樹(shù)。
決策樹(shù)的典型算法有ID3，C4.5，CART（分類(lèi)與回歸樹(shù)）等。依次得到改進(jìn)。相對于其它算法，決策樹(shù)易于理解和實(shí)現，人們在通過(guò)解釋后都有能力去理解決策樹(shù)所表達的意義。決策樹(shù)可以同時(shí)處理不同類(lèi)型的屬性, 并且在相對短的時(shí)間
內能夠對大型數據源做出可行且效果良好的結果。
3.4 貝葉斯分類(lèi)算法
貝葉斯分類(lèi)器的分類(lèi)原理是通過(guò)某對象的先驗概率，利用貝葉斯公式計算出其后驗概率，即該對象屬于某一類(lèi)的概率，選擇具有最大后驗概率的類(lèi)作為該對象所屬的類(lèi)。目前研究較多的貝葉斯分類(lèi)器主要有四種，分別是：Naive Bayes、TAN、BAN和GBN。
▲準備知識
條件概率：設A, B是兩個(gè)事件，且Pr(A)?0稱(chēng)Pr(B|A)?
發(fā)生的條件事件B發(fā)生的條件概率。
乘法公式： 設Pr(A)?0 則有Pr(AB)?Pr(B|A)Pr(A)
全概率公式：設隨機事件A1，A2，...，An以及 B滿(mǎn)足：(1) A1，A2，…，An兩兩互不相容；(2)?An?S或者B??An；(3) Pr(A)?0(n=1,2,…)，則有
n?1n?1??Pr(AB)為在條件A下Pr(A)
Pr(B)??Pr(An)Pr(B|An)，稱(chēng)為全概率公式。
n?1?
全概率公式的應用：把事件B看作是某一個(gè)過(guò)程的結果，把A1，A2，…，An看作該過(guò)程的若干個(gè)原因，根據歷史資料，每個(gè)原因發(fā)生的概率已知（即Pr(Ai)已知），且每一個(gè)原因對結果的影響已知（即Pr(B|Ai)已知）則可用全概率公式計算結果發(fā)生的概率，即求Pr(B)。
貝葉斯公式：設隨機事件A1，A2，…，An以及B滿(mǎn)足：(1) A1，A2，…，An兩兩互不相容；(2)
PrA(nB)?PrB()???An?1?n?S或者B??An；(3) Pr(A)?0(n=1,2,…)，則n?1PrA(nB|?)PBr(An|
(?PrB
n?1A|jA)P)nr(，稱(chēng)為貝葉斯公式。 )PAr)j(
貝葉斯公式的使用：把事件B看作某一過(guò)程的結果，把A1，A2，…，An看作該過(guò)程的若干原因，根據歷史資料，每一原因發(fā)生的概率已知（即Pr(An)已知），如果已知事件B已經(jīng)發(fā)生，要求此時(shí)是由第i個(gè)原因引起的概率，用貝葉斯公式（即求Pr(Ai|B)）。
▲樸素貝葉斯（Naive Bayes，NB）算法
在貝葉斯分類(lèi)中，在數據集合D中，令A1,A2,…,An為用離散值表示的屬性
集合，設C具有|C|個(gè)不同值的類(lèi)別屬性，即c1,c2,…,c|c|，我們設所有的屬性都是條件獨立于類(lèi)別，給定一個(gè)測試樣例d，觀(guān)察到屬性值a1到a|A|，其中ai是Ai可能的一個(gè)取值，那么預測值就是類(lèi)別cj，使得Pr(C=cj | A=a1,…,A|A|=a|A|)最大。cj被稱(chēng)為最大后驗概率假設。
根據貝葉斯公式，有 Pr(C?cj)?Pr(Ai?ai|C?cj)|A|
Pr(A1?a1,...,A|A|?a|A||C?cj)??Pr(C?c)?Pr(A?a|C?c)kiik
k?1i?1|C|i?1|A|
因為分母對每一個(gè)訓練類(lèi)別都是一樣的，所以如果僅僅需要總體上最可能的類(lèi)別為所有測試樣例做預測，那么只需要上式的分子部分即可。通過(guò)下式來(lái)判斷最有可能的類(lèi)別：
c?argmaxPr(C?cj)?Pr(Ai?ai|C?cj)
cji?1|A|
例如，假設我們有圖4-1中的訓練數據，有兩個(gè)屬性A和B,還有類(lèi)別C，對于一個(gè)測試樣例：A=m B=q 求
C=?
圖4-1 訓練數據
計算如下：
對于類(lèi)別為t的概率
1222Pr(C?t)?Pr(Aj?aj|C?t)?Pr(C?t)?Pr(A?m|C?t)?Pr(B?q|C?t)????25525j?12
類(lèi)似的，對于類(lèi)別為f的概率 1121Pr(C?f)?Pr(Aj?aj|C?f)???? 25525j?12
因此C=t的可能性較大，因此將此種情況下的類(lèi)別判斷為t。
樸素貝葉斯分類(lèi)將每篇文檔看作一“袋子”的詞，需要做以下假設，這也是
篇四：融合無(wú)監督和監督學(xué)習策略生成的多分類(lèi)決策樹(shù)
第25卷第4期小型微型計算機系統 Vol.25 No.4 融合無(wú)監督和監督學(xué)習策略生成的多分類(lèi)決策樹(shù)
邱德紅，陳傳波
�。ㄈA中科技大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，湖北 武漢430074）
摘 要：提出了一種融合無(wú)監督和監督兩 種學(xué)習策略生成多分類(lèi)決策樹(shù)的方法 .它首先利用無(wú)監督聚類(lèi)方法能夠發(fā)現待分類(lèi)樣本之間的內在聯(lián)系和規律的特點(diǎn) ,確定出最為符合多類(lèi)樣本分布特征的決策樹(shù)的樹(shù)型 ,繼而利用監督學(xué)習支持向量機的方法對樣本進(jìn)行準確的分類(lèi) .通過(guò)采用核函數和不對稱(chēng)的 L agrangian系數限制條件 ,支持向量機很好的解決了樣本特征空間上的線(xiàn)性不可分性和決策樹(shù)型確定過(guò)程中出現的訓練樣本不對稱(chēng)性的影響 .該方法具有較高的計算效率和準確性 ,在實(shí)驗中取得了比較好的結果.
關(guān) 鍵 詞：多分類(lèi)決策樹(shù)；無(wú)監督聚類(lèi)；支持向量機
中圖分類(lèi)號：TP391.41 文獻辨識碼：A 文章編號：1000-1200(2004)04-0555-05
Construction of Multi-classification Decision Tree Combining
Unsupervised and Supervised Learning Strategy
QIU De-hong,CHENChuan-bo
(School of Comouter Science and Technology Huazhong University of Science and Technology,Wuhan 430074,china)
Abstract:In this paper,a new method which combines unsupervised and supervised learning steategy is put forward to construct the multi-classification decision tree,It firstly uses the unsupervised clustering to determine the structure of the multi-classification decision tree,whose each node has a binary branch.The unsupervised clustering is able to find out the relationship between the mulit-classes,therefore the decision tree’s structure determined by it is the best one that fits to the distribution of mulit-classes in feature space.Then,a supervised learning method,i.e.support vector machine,is used to classify the two groups of samples of each node of the decision tree.Most cases the multi-classes cannot be classified by a linear hyperplane,kernel functions are therefore introduced into to solve it.Simultaneously,unsymmetrical constrains of Lagrangian coefficients are set to overcome the negative influences of unbalanced train samples. These efforts guarantee the efficiency and accuracy of the multi-classification decision tree.Satisfying results were obtained in experiment.
Key words:multi-classification decision tree; unsupervised cluster support vector machine
1 引 言
多分類(lèi)問(wèn)題是一個(gè)比較常見(jiàn)的問(wèn)題，機器學(xué)習理論和方法
的研究在解決二分類(lèi)問(wèn)題上取得了比較滿(mǎn)意的結果
[3][1,2] 無(wú)監督學(xué)習和監督學(xué)習是機器學(xué)習方法研究的二大策略.無(wú)監督學(xué)習方法如無(wú)監督聚類(lèi)(UC)[8,9]是從樣本的特征向量出.多分發(fā)，研究通過(guò)某種算法特征比較相似的樣本聚集在一起，從而達到區分具有不同特征的樣本的目的.無(wú)監督聚類(lèi)的優(yōu)點(diǎn)是可
以發(fā)現樣本中隱含的共性和規律，但是由于沒(méi)有專(zhuān)家知識的監
督，分類(lèi)的準確性有限.監督學(xué)習方法是通過(guò)對已知類(lèi)別的訓
練樣本的學(xué)習，實(shí)現對未知樣本的分類(lèi)判斷.支持向量機
(SVM)[1,2]類(lèi)問(wèn)題雖然也有研究,但在理論構架和現實(shí)方法上還有相當大的困難.目前解決多分類(lèi)問(wèn)題主要運用多分類(lèi)決策數，決策樹(shù)上的每一個(gè)節點(diǎn)對應一個(gè)二分類(lèi)器，實(shí)際上是利用二分類(lèi)方法解決多分類(lèi)問(wèn)題.生成類(lèi)分類(lèi)決策樹(shù)的方法有（1）‘一對其余’，決策樹(shù)上N個(gè)節點(diǎn)對應的二分類(lèi)器只判斷是某一類(lèi)還是
其余類(lèi)；（2）‘一對一’，決策樹(shù)上N(N-1)/2個(gè)節點(diǎn)對應的二
分類(lèi)器只能對類(lèi)中的兩類(lèi)作出是否判斷；（3）‘一半對一半’，
即決策樹(shù)的節點(diǎn)對應的二分類(lèi)器將節點(diǎn)上的類(lèi)二等分（允許一
類(lèi)別在兩個(gè)節點(diǎn)上出現），直至葉節點(diǎn).決策樹(shù)上節點(diǎn)的數目為，
其中為大于或等于log2(N)最小整數.這三類(lèi)方法生成的決策
樹(shù)雖然具有不同的計算效率和分類(lèi)效果，但各自在應用中取得
了比較好的結果[4~7]是一種主要用于二分類(lèi)的準確率比較高的監督學(xué)習方法，其基礎是統計學(xué)習理論中的結構風(fēng)險最小化原則.它在許多領(lǐng)域得到了很好的應用[10~12]. 本文提出一種將無(wú)監督聚類(lèi)和監督學(xué)習的支持向量機方法結合起來(lái)生成多分類(lèi)決策樹(shù)的方法.它的基本思想如下：待方法的多類(lèi)樣本可以看成是某一宏觀(guān)層面之上的刺激機制激勵下，或者是在某個(gè)進(jìn)程中產(chǎn)生的.該宏觀(guān)層面之下刺激機制的差異，或者是進(jìn)程中的不同階段導致不同類(lèi)的出現。差異小.
收稿日期：2002-08-05 作者簡(jiǎn)介：邱德紅，博士，主要研究方向為機器學(xué)習和生物測定學(xué)；陳傳波，教授博士生導師，主要研究方向為圖像處理和計算機網(wǎng)絡(luò )應用。E-mail:qiudh.wh.hb.cn
的刺激機制，或者相鄰進(jìn)程階段產(chǎn)生的類(lèi)別之間的特征較為接
近，反之則分散.因而，多類(lèi)之間雖然具有向異性，但他們在
特征空間的分布上有內在規律.如果決策樹(shù)的樹(shù)形結構能夠體
現多類(lèi)之間的內在規律，就可能在計算效率和準確性上獲得較
好的均衡，從而提高決策樹(shù)的性能.本文介紹的方法的目的是
通過(guò)無(wú)監督聚類(lèi)確定反映多類(lèi)之間分布規律的決策樹(shù)的樹(shù)型，
繼而利用監督學(xué)習支持向量機方法的準確率高的特點(diǎn)對分布
接近的類(lèi)別進(jìn)行詳細分區，使多分類(lèi)決策樹(shù)具有較高的計算效
率和準確率.
2 多分類(lèi)決策樹(shù)的樹(shù)型確定
一個(gè)N(N≥3)類(lèi)的多分類(lèi)問(wèn)題可以描述為：給定組訓練樣
本：（x1,y1）,…（xl1,yl1）,(x1,y2),…(xl2,y2),……(x1,yN),…
(xlN,ydN),L=l1+l2+…+lN為N類(lèi)訓練樣本的總數目，xi∈R，
i=1,…,L是d維空間上的特征向量，yn∈
�。�1,2,…,N｝,n=1,…,N是N類(lèi)標號.多分類(lèi)問(wèn)題即函數F：Rd
→｛1,2,…,N｝確定待分類(lèi)向量x的類(lèi)別標號y.多分類(lèi)問(wèn)題
可以通過(guò)由二分類(lèi)器為節點(diǎn)構成的決策樹(shù)來(lái)解決.由于待分類(lèi)
的N類(lèi)樣本通常是其形成的刺激機制在某個(gè)宏觀(guān)層面之下的
差異，或者是同一進(jìn)程的不同階段形成的，刺激機制差異的大
小和進(jìn)程階段相隔時(shí)間的久遠導致N類(lèi)樣本在特征空間上分
布有一定的規律.如圖1所示的N=6的多分類(lèi)問(wèn)題，左下三類(lèi)
(○、□、△)和右上三類(lèi)(＋、×、*)之間的刺激機制相差較遠，
而左下三類(lèi)(○、□、△)之間、右上三類(lèi)(＋、×、*)之間的刺
激機制相差較小.如果多分類(lèi)決策樹(shù)型能夠反映出類(lèi)樣本之間
的分布規律，繼而實(shí)施輕重有別的詳細區分，必將能獲得比較
優(yōu)秀的性能，為此設計以下利用無(wú)監督聚類(lèi)確定決策樹(shù)型的方
法.
圖 1
多類(lèi)樣本的特征向量在特征空間上的分布
Fig.1 Distribution of multi-classes samples on
the feature space
第1步:計算N類(lèi)訓練樣本共L個(gè)特征向量中的任何兩個(gè)特征
向量,比如xr,xs之間的Minkowski距離
dd1/p
r,s={?|x,r,s=1,…,m+1,且r≠s,p=2
sj?xrj|}
j?1
第2步: 將N類(lèi)訓練樣本共L個(gè)特征向量編號為1,…,L
號葉節點(diǎn),從1號葉節點(diǎn)開(kāi)始在C2
L個(gè)距離之中找到最小距離,
將對應的兩個(gè)葉節點(diǎn)(比如為xr,xs,)做個(gè)連接,形成一個(gè)二叉樹(shù)枝.將此連接‘看成’為一個(gè)新葉節點(diǎn),編號為L(cháng)+1.該新葉節點(diǎn)到其余某個(gè)葉節點(diǎn)xk,k≠r,s(即xr,xs,之外的節點(diǎn))之間的距離定義為已經(jīng)連接的兩個(gè)葉節點(diǎn)(xr,xs)與該節點(diǎn)之間的最小距離,即dL+1,k=min(dr,k,ds,k) . 第3步:按照第2步同樣的規則,在新生成的葉節點(diǎn)和其余葉節點(diǎn)之中繼續生成一個(gè)新的二叉連接,重復 直到生成最后一個(gè)二叉連接而成為一棵聚類(lèi)樹(shù).如圖2所示的一棵聚類(lèi)樹(shù)，它對應于圖1中的60個(gè)樣本. 圖2 無(wú)監督聚類(lèi)生成的聚類(lèi)樹(shù) Fig.2 Decision tree produced by unsupervised clustering 第4步:將第3步中最后生成的一個(gè)二叉連接的左右兩個(gè)分枝連接的最底層的葉節點(diǎn)(即1,…,L葉節點(diǎn))對應的特征向量劃分到的左右兩個(gè)集合SR,SL中.依次檢查待分類(lèi)的1,…,N類(lèi)樣本的特征向量, 如果第n類(lèi)的Ln個(gè)特征向量被聚類(lèi)到左右兩個(gè)集合SR、SL中,數目分別為lnR和lnL(lnR+lnL=ln)則依下情況處理: ·如果lnR大于或等于lnL,且集合SL中特征向量的個(gè)數大于lnL,則將集合SL中對應的lnL個(gè)特征向量移至集合SR ·如果lnR大于或等于lnL,但集合SL中特征向量的個(gè)數等于lnL,則將集合SR中對應的lnR個(gè)特征向量移至集合SL ·如果lnL大于lnR ,且集合SR中特征向量的個(gè)數大于lnR,則將集合SR中對應的lnR個(gè)特征向量移至集合SL ·如果lnL大于lnR ,但集合SR中特征向量的個(gè)數等于lnR,則將集合SL中對應的lnL個(gè)特征向量移至集合SR 至此可以確定決策樹(shù)上的一個(gè)二叉節點(diǎn),它的訓練樣本是非空的左右兩個(gè)集合SR、SL,將集合SL中的特征向量的標簽設定為-1,集合SR中的特征向量的標簽設定為+1.它們將用于訓練支持向量機來(lái)生成該節點(diǎn)對應的二分類(lèi)器. 第5步:分別將左右兩個(gè)集合SR、SL中包含的特征向量看成一個(gè)新的分類(lèi)問(wèn)題,重復第1步到第4步,直到左右兩個(gè)集合SR、SL中均只包含N類(lèi)訓練樣本中的某一類(lèi)樣本.從而確定出完整的N分類(lèi)決策樹(shù)的樹(shù)型.圖1所示的N=6的分類(lèi)問(wèn)題對應的決策樹(shù)型如圖3所示. 無(wú)監督聚類(lèi)方法確定決策樹(shù)樹(shù)型與‘一對其余’,‘一對一’和‘一半對一半’確定決策樹(shù)樹(shù)型方法上是不一樣.后三者對于所有N 的多分類(lèi)問(wèn)題采用的決策樹(shù)型均是固定的,
而這
里介紹的方法將依據N 類(lèi)樣本之間的聯(lián)系和分布規律生成相
應的決策樹(shù)型.決策樹(shù)型本身在一定的程度上反映了N 類(lèi)樣本
之間的差異大小,可以一定程度的降低二分類(lèi)的難度.以此為
基礎的N 分類(lèi)問(wèn)題的計算效率將隨決策樹(shù)型有所變化.如果假
設這些方法均采用同樣的二分類(lèi)方法,二分類(lèi)器的計算復雜度
可大致描述為??cn?,其中為系數, n 為訓練樣本數,λ
≈為復雜度指數.則對于N 類(lèi)、樣本總數為L(cháng)的多分類(lèi)
圖3 無(wú)監督聚類(lèi)生成的決策樹(shù)型
Fig.3The structure of decision tree produced
byunsupervised clustering
問(wèn)題,‘一對其余’生成的決策樹(shù)的計算復雜度為NL?；
‘一對一’生成的決策樹(shù)的計算復雜度為
0.5cN(N?1)(li?lj)?li和lj為對應兩類(lèi)的訓練樣
本的數目;‘一半對一半’生成的決策樹(shù)的計算復雜度約為c
( 2k-1)(l?)2 ,其中k為大于或等于log2(N)的最小整數,訓練
樣本數l′逐步遞減.無(wú)監督聚類(lèi)生成的決策樹(shù)的節點(diǎn)數小于
‘一半對一半’和‘一對一’生成的決策樹(shù),其節點(diǎn)的訓練樣
本數小于‘一對其余’的生成方法,遞減速度大于‘一半對一
半’的生成方法.綜合來(lái)說(shuō),無(wú)監督聚類(lèi)生成的決策樹(shù)具有比較
高的計算效率.
3 支持向量機二分類(lèi)器
無(wú)監督聚類(lèi)生成的決策樹(shù)上的每個(gè)二叉節點(diǎn)對應于一個(gè)
二分類(lèi)器.無(wú)監督聚類(lèi)分類(lèi)的準確率有限，這里采用準確率高
的支持向量機來(lái)生成決策樹(shù)上每個(gè)二叉節點(diǎn)對應的二分類(lèi)器，
它的訓練樣本分別是該二叉節點(diǎn)連接的左右兩個(gè)集合SR、SL
中的樣本，它們可以統一表示為：(xd
i,yi),xi,∈R,yi∈{+1,-1}
,訓練樣本數為l.支持向量機是一種建立在統計學(xué)習理論基
礎上的機器學(xué)習方法他采用學(xué)習理論的結構風(fēng)險最小原則【1,2】
.其學(xué)習目的是在所有分割超平面中1確定最優(yōu)超平面
H:wx+b=0,該平面到兩類(lèi)之間的間隔最大,且滿(mǎn)足一下約束條
件：
1http:www.ics.uci.edu/^mlearn/MLR Repository,html
w?xi?b??1ifyi??1 w?xi?b??1 ifyi??1??w,b??2兩類(lèi)之間的間隔為w，因此, 確定最優(yōu)分割超平面即為求( w ,b)使得??w??1w2最小，它等效2求解二次優(yōu)化問(wèn)題，即求Lagrangian系數α使目標函數W (α)最大: iW?a??i?a1li?（1） ,j?12??i?jyiyj?xi?xj? i?1滿(mǎn)足條件αi≥0(i=1,2,…,l)和?l?iyi?0.然后可求i?1得（w,b）為； lW???x1iyii,b?????x??x?? i?12X+和x-分別是兩類(lèi)向量的支持向量，與它們對應的αi＞0，其余的αi=0,支持向量機學(xué)習確定的分類(lèi)器為： f?x??sign???x?b??sign?l?????iyi?xi?x??b?i?1?無(wú)監督聚類(lèi)確定的分類(lèi)決策樹(shù)的二叉節點(diǎn)對應的訓練樣本往往不具有線(xiàn)性的可分性.此時(shí)可以引入適當的核函數K (xi,xj)=φ(xi)·φ(xj),將將原空間中的向量映射到另一特征內積空間中去進(jìn)行分類(lèi).此時(shí)目標函數(1)相應修正為: iW?a???a1li???i?jyiyjK?xi?xj?（2） i,j?12i?1滿(mǎn)足約束條件： 引入核函數K?xi,xj?后新特征向量x的分類(lèi)器法則如下： f?x??sign?l????x??b?iyiK?xi??i?1? 核函數K(xi ,xj)需要滿(mǎn)足Mercer定理【2】,經(jīng)常采用的核函數有多項式函數:K(x,y)=(x·y+1)d,高斯徑向基函數?x2K?x,y??exp??y?????2?2??和多層感知器函數：K?x,y??tanh?k?x?y???? 訓練樣本中如果存在不可分的樣本(噪音),就需要適度對待訓練誤差.此時(shí),如果過(guò)份地強調減小訓練誤差可以導致二分類(lèi)器的性能惡化.因為這樣生成的二分類(lèi)器可能過(guò)于傾向訓練樣本的個(gè)性特征,而沒(méi)有體現出訓練樣本整體共性,不利于對未知樣本的判斷.這時(shí)候需要采用柔性邊界,它依然可以通過(guò)求解最大目標函數(2)得到,然而需要將約束條件αi>0改為0≤αi≤C. C可以協(xié)調訓練誤差和分類(lèi)器的綜合能力,其物
第25卷第4期小型微型計算機系統 Vol.25 No.4 理的解釋可以看成是與參數Ti對應的訓練樣本對分類(lèi)邊界的
作用力大小的變化范圍.無(wú)監督聚類(lèi)生成的決策樹(shù)型時(shí)經(jīng)常會(huì )
出現的左右兩個(gè)集合SR、SL中的樣本數目的不均衡,數目少的一
邊對分類(lèi)邊界確定的作用合力的大小往往有限,因而對分類(lèi)邊
界的確定影響力弱.為此我們對數目不等的兩類(lèi)樣本確定不對
稱(chēng)的作用力變化范圍,即使0≤Ti+ ≤C+,0≤Ti≤C-,C+和C-與訓
練樣本數目相關(guān),以此來(lái)消除訓練樣本數目不均衡性的影響. 決策樹(shù)型確定之后,采用監督學(xué)習支持向量機的方法來(lái)生成決策樹(shù)中二叉節點(diǎn)對應的二分類(lèi)器,采用的是徑向基核函數和非對稱(chēng)的Lagrangian系數限制條件.調節徑向基的寬度和系數限制條件,可以得到對應決策樹(shù)上每個(gè)二叉節點(diǎn)的性能很好的二分類(lèi)器.之后用5類(lèi)共74個(gè)心臟病變樣本的特征向量進(jìn)行了測試,測試結果列在表1之中.在表1中還給出了幾個(gè)其它研究人 表1 采用不同方法對Clev eland心臟病變
數據的處理結果
Table 1 Expermental results of cleveland
heartdisease datausing different classifer
方法
UC+SVM
UC+SVM
INC-NET
Na?ve Bayes
k-NN,VDM
GOT/SVM 準確率 93.2% 85.1% 90.0% 82.8%±1.3% 82.6% 82.5% 說(shuō)明 本文方法，如果只區分病變和非病變 本文方法，區分所有類(lèi)別 病變和非病變分類(lèi)，文獻[13] 病變和非病變分類(lèi)，文獻[14] 病變和非病變分類(lèi)，文獻[15] 樹(shù)型邊界分類(lèi)病變和非病變，文獻[16] 4 實(shí)驗結果 我們采用Cleveland心臟病變數據來(lái)檢驗上文介紹的融合無(wú)監督聚類(lèi)和監督學(xué)習支持向量機生成的多分類(lèi)決策樹(shù)的效果.Cleveland心臟病變數據在一個(gè)知名的有關(guān)機器學(xué)習研究的網(wǎng)站1 上公布,成為許多分類(lèi)方法的檢驗數據.這組數據包含有303個(gè)樣本,每個(gè)樣本的特征向量的維數為13.其中有6個(gè)樣本的特征向量不完整,這里將它們從樣本中剔出,因而可使用的樣本數據為297個(gè).樣本的特征向量被分為5類(lèi),其中心臟沒(méi)有病變的正常情況的樣本數目為160個(gè),標號為0.其余的樣本為心臟有病變的特征樣本,標號依此為1、2、3和
4,對應的樣本數目分別為54、35、35和13,標號遞增表示心
臟病變的程度越發(fā)厲害.我們對于每一類(lèi)樣本,選擇其中的四
分之三為訓練樣本,數目共為223個(gè),其余的四分之一用來(lái)驗
證,數目共為74個(gè).
利用第二節介紹的無(wú)監督聚類(lèi)方法,首先從224個(gè)訓練樣本
確定決策樹(shù)的樹(shù)型,結果如圖4所示.為了平衡樣本特征向量各
個(gè)特征值對決策樹(shù)型的影響程度,對所有樣本的特征向量的每
項特征值進(jìn)行了正規處理,即進(jìn)行了以下運算:員采用不同的研究方法對Cleveland心臟病變數據的分類(lèi)結果,更多的有關(guān)該組數據的處理結果可以參閱文獻[17]或網(wǎng)站.這些結果準確率均在85.1%之下,居多方法只區分樣本特征向量是病變還是非病變,是二分類(lèi)的研究結果.從表1的數據比較可以看出,本文提出的決策樹(shù)型確定和決策樹(shù)節點(diǎn)的二分類(lèi)器的生成方法一定程度的提高了分類(lèi)效果. 25 結 論 綜合利用多種學(xué)習策略來(lái)解決多分類(lèi)問(wèn)題是一種比較好
的指導思想,它可以提高解決問(wèn)題的效率和結果.本文利用無(wú)
監督聚類(lèi)學(xué)習策略和監督學(xué)習支持向量機的方法來(lái)生成多分
類(lèi)決策樹(shù),在實(shí)驗中獲得了比較好的效果.該方法不僅能夠針
對待處理的多分類(lèi)問(wèn)題多類(lèi)之間的內在聯(lián)系和分布特點(diǎn),生成
相應的決策樹(shù)型,具有靈活解決問(wèn)題的能力,而且采用了準確
率高的支持向量機對不易區分的類(lèi)別進(jìn)行分類(lèi),彌補了無(wú)監督
聚類(lèi)分類(lèi)準確率低的缺陷,實(shí)現了策略之間的優(yōu)勢互補.該方
法在解決多分類(lèi)問(wèn)題上體現了問(wèn)題產(chǎn)生的刺激機制和人們區
分多種類(lèi)別時(shí)先易后難的思維習慣,實(shí)現了比較高的計算效率
和分類(lèi)效果. ?????min???，表示所有樣本特征向量的同max??min?一項特征值構成的列向量.從圖4可見(jiàn),無(wú)監督聚類(lèi)方法確定的決策樹(shù)型明確地反映出Cleveland心臟病變數據中幾類(lèi)樣本之間的關(guān)系,如正常的樣本向量(0)與病變樣本向量首先被區分開(kāi)來(lái),嚴重病變的樣本向量(3、4)將與輕度病變(1、2)的樣本向量區分開(kāi)來(lái),最后區分比較難以區分的兩類(lèi)樣本.無(wú)監督聚類(lèi)方法生成的決策樹(shù)型不僅很好的體現了心臟病變這一進(jìn)程中不同階段的特點(diǎn),而且符合人們區分事物先易后難的習慣.
2References: 1. Vapnik V. The nature of statistical learning theory[M].NewYork: Springer-Verlag,1995. 2. Vapnik V. Statistical learning theory[M]. John Wiley &Sons,New York ,1998. 3. Weston J and Watkins . M ulti-class support vector machines
[R] .Technical Report CSD-T R-98-04, Royal Holloway,
University of London, Department of Computer 圖4 無(wú)監督聚方法生成的Cleveland心臟病變診斷決策樹(shù)型
Fig .4 The structure of decisiontree of clev eland heart
disease data produced by unsupervised clustering Science,EBIOL 1998. Available on http://www. clrc.
1http://www.phys.uni.torun.pl/kmk/projects/datasets.html
篇五：監督分類(lèi)是需要學(xué)習訓練的分類(lèi)方法
監督分類(lèi)是需要學(xué)習訓練的分類(lèi)方法,如最大似然分類(lèi),人工神經(jīng)網(wǎng)絡(luò )分類(lèi),即是需要事先為每類(lèi)地物在遙感圖像上采集樣本數據,之后通過(guò)學(xué)習訓練過(guò)程才來(lái)分類(lèi);非監督分類(lèi)不需要人工采集地物樣本點(diǎn)數據,多是通過(guò)聚類(lèi)的方法來(lái)自動(dòng)分類(lèi),主要有isodata,k均值等.總體來(lái)說(shuō),監督分類(lèi)的效果要優(yōu)于非監督分類(lèi).
遙感影像的分類(lèi)方法按照是否有先驗類(lèi)別可以分為監督分類(lèi)和非監督分類(lèi)，這兩種分類(lèi)法有著(zhù)本質(zhì)的區別但也存在一定的聯(lián)系．
監督分類(lèi)的主要方法
最大似然判別法.也稱(chēng)為貝葉斯(Bayes)分類(lèi),是基于圖像統計的監督分類(lèi)法,也是典型的和應用最廣的監督分類(lèi)方法.它建立在Bayes準則的基礎上,偏重于集群分布的統計特性,分類(lèi)原理是假定訓練樣本數據在光譜空間的分布是服從高斯正態(tài)分布規律的,做出樣本的概率密度等值線(xiàn),確定分類(lèi),然后通過(guò)計算標本(像元)屬于各組(類(lèi))的概率,將標本歸屬于概率最大的一組.用最大似然法分類(lèi),具體分為三步:首先確定各類(lèi)的訓練樣本,再根據訓練樣本計算各類(lèi)的統計特征值,建立分類(lèi)判別函數,最后逐點(diǎn)掃描影像各像元,將像元特征向量代入判別函數,求出其屬于各類(lèi)的概率,將待判斷像元歸屬于最大判別函數值的一組.Bayes判別分類(lèi)是建立在Bayes決策規則基礎上的模式識別,它的分類(lèi)錯誤最小精度最高,是一種最好的分類(lèi)方法.但是傳統的人工采樣方法由于工作量大,效率低,加上人為誤差的干擾,使得分類(lèi)結果的精度較差.利用GIS數據來(lái)輔助Bayes分類(lèi),可以提高分類(lèi)精度,再通過(guò)建立知識庫,以知識來(lái)指導分類(lèi)的進(jìn)行,可以減少分類(lèi)錯誤的發(fā)生[1],這正是Bayes分類(lèi)的發(fā)展趨勢和提高其分類(lèi)精度的有效途徑.
神經(jīng)元網(wǎng)絡(luò )分類(lèi)法.是最近發(fā)展起來(lái)的一種具有人工智能的分類(lèi)方法,包括BP神經(jīng)網(wǎng)絡(luò )、Kohonen神經(jīng)網(wǎng)絡(luò )、徑向基神經(jīng)網(wǎng)絡(luò )、模糊神經(jīng)網(wǎng)絡(luò )、小波神經(jīng)網(wǎng)絡(luò )等各種神經(jīng)網(wǎng)絡(luò )分類(lèi)法.BP神經(jīng)網(wǎng)絡(luò )模型(前饋網(wǎng)絡(luò )
型)是神經(jīng)網(wǎng)絡(luò )的重要模型之一,也是目前應用最廣的神經(jīng)網(wǎng)絡(luò )模型,它由輸入層、隱含層、輸出層三部分組成,所采取的學(xué)習過(guò)程由正向傳播過(guò)程和反向傳播過(guò)程組成.傳統的BP網(wǎng)絡(luò )模型把一組樣本的輸入/輸出問(wèn)題作為一個(gè)非線(xiàn)性?xún)?yōu)化問(wèn)題,它雖然比一般統計方法要好,但是卻存在學(xué)習速度慢,不易收斂,效率不高的缺點(diǎn).采用動(dòng)量法和學(xué)習率自適應調整的策略,可以提高學(xué)習效率并增加算法的可靠性[3].
模糊分類(lèi)法.由于現實(shí)世界中眾多的自然或半自然現象很難明確劃分種類(lèi),反映在遙感影像上,也存在一些混合像素問(wèn)題,并有大量的同譜異物或者同物異譜現象發(fā)生,使得像元的類(lèi)別難以明確確定.模糊分類(lèi)方法忽略了監督分類(lèi)的訓練過(guò)程所存在的模糊性,沿用傳統的方法,假定訓練樣本由一組可明確定義、歸類(lèi),并且具有代表性的目標(像素)構成.監督分類(lèi)中的模糊分類(lèi)可以利用神經(jīng)元網(wǎng)絡(luò )所具有的良好學(xué)習歸納機制、抗差能力和易于擴展成為動(dòng)態(tài)系統等特點(diǎn),設計一個(gè)基于神經(jīng)元網(wǎng)絡(luò )技術(shù)的模糊分類(lèi)法來(lái)實(shí)現.模糊神經(jīng)網(wǎng)絡(luò )模型由ART發(fā)展到ARTMAP再到FasART、簡(jiǎn)化的FasART模型[4],使得模糊神經(jīng)網(wǎng)絡(luò )的監督分類(lèi)功能不斷完善、分類(lèi)精確度不斷增加.
最小距離分類(lèi)法和Fisher判別分類(lèi)法.它們都是基于圖像統計的常用的監督分類(lèi)法,偏重于幾何位置.最小距離分類(lèi)法的原則是各像元點(diǎn)劃歸到距離它最近距離的類(lèi)別中心所在的類(lèi),Fisher判別分類(lèi)采用Fisher準則即“組間最大距離”的原則,要求組間距離最大而組內的離散性最小,也就是組間均值差異最大而組內離差平方和最小.用這兩種分類(lèi)法進(jìn)行分類(lèi),其分類(lèi)精度取決于對已知地物類(lèi)別的了解和訓練統計的精度,也與訓練樣本數量有關(guān).針對最小距離分類(lèi)法受模式散布影響、分類(lèi)精度不高的缺點(diǎn),人們提出了一種自適應的最小距離分類(lèi)法,在訓練過(guò)程中,將各類(lèi)樣本集合自適應地分解為子集樹(shù),定義待分類(lèi)點(diǎn)到子集樹(shù)的距離作為分類(lèi)依據[2],這種方法有效地提高了最小距離法的分類(lèi)正確率和分類(lèi)速度,效率較高.Fisher判別分類(lèi)也可以通過(guò)增加樣本數量進(jìn)行嚴密的統計分類(lèi)來(lái)增加分類(lèi)精度。
非監督分類(lèi)的主要方法
動(dòng)態(tài)聚類(lèi).它是按某些原則選擇一些代表點(diǎn)作為聚類(lèi)的核心,然后將其余待分點(diǎn)按某種方法(判據準則)分到各類(lèi)中去,完成初始分類(lèi),之后再重新計算各聚類(lèi)中心,把各點(diǎn)按初始分類(lèi)判據重新分到各類(lèi),完成第一次迭代.然后修改聚類(lèi)中心進(jìn)行下一次迭代,對上次分類(lèi)結果進(jìn)行修改,如此反復直到滿(mǎn)意為止.動(dòng)態(tài)聚類(lèi)的方法是目前非監督分類(lèi)中比較先進(jìn)、也較為常用的方法.典型的聚類(lèi)過(guò)程包括以下幾步:選定初始集群中心;用一判據準則進(jìn)行分類(lèi);循環(huán)式的檢查和修改;輸出分類(lèi)結果.聚類(lèi)的方法主要有基于最鄰近規則的試探法、K-means均值算法、迭代自組織的數據分析法(ISODATA)等.其中比較成熟的是K-means和ISODATA算法,它們較之其他分類(lèi)方法的優(yōu)點(diǎn)是把分析判別的統計聚類(lèi)算法和簡(jiǎn)單多光譜分類(lèi)融合在一起,使聚類(lèi)更準確、客觀(guān).但這些傳統的建立在統計方法之上的分類(lèi)法存在著(zhù)一定的缺點(diǎn):很難確定初始化條件;很難確定全局最優(yōu)分類(lèi)中心和類(lèi)別個(gè)數;很難融合地學(xué)專(zhuān)家知識.基于尺度空間的分層聚類(lèi)方法(SSHC)是一種以熱力學(xué)非線(xiàn)性動(dòng)力機制為理論基礎的新型聚類(lèi)算法[10],它與傳統聚類(lèi)算法相比最大的優(yōu)點(diǎn)是其樣本空間可服從自由分布,可獲取最優(yōu)聚類(lèi)中心點(diǎn)及類(lèi)別,可在
聚類(lèi)過(guò)程中融合后驗知識,有更多的靈活性和實(shí)用性.
模糊聚類(lèi)法.模糊分類(lèi)根據是否需要先驗知識也可以分為監督分類(lèi)和非監督分類(lèi).事實(shí)上,由于遙感影像的復雜性和不精確性等特點(diǎn),預先很難獲得所有有代表性樣本的各類(lèi)別的精確含量,因此很多情況下用純粹的監督方法作模糊分類(lèi)并不現實(shí).模糊聚類(lèi)屬于非監督分類(lèi)的一種,它根據樣本間的統計量的相似程度作為模糊隸屬度,在無(wú)預知類(lèi)別的前提下對數據集中各點(diǎn)作含量劃分.模糊聚類(lèi)算法有多種,如基于模糊等價(jià)關(guān)系的模糊聚類(lèi)分析法、基于最大模糊支撐樹(shù)的模糊聚類(lèi)分析法等
[11],最典型的模糊聚類(lèi)法是模糊迭代自組織的數據分析法———Fussy-ISODATA.但純粹的非監督分類(lèi)對影像一無(wú)所知的情況下進(jìn)行所得到的結果往往與實(shí)際特征存在一定的差異,因此聚類(lèi)結果的精度并不一定能夠滿(mǎn)足實(shí)際應用的要求,還需要地學(xué)知識的輔助,也就是部分監督的Fussy-ISODATA聚類(lèi).
系統聚類(lèi).這種方法是將影像中每個(gè)像元各自看作一類(lèi),計算各類(lèi)間均值的相關(guān)系數矩陣,從中選擇最相關(guān)的兩類(lèi)進(jìn)行合并形成新類(lèi),并重新計算各新類(lèi)間的相關(guān)系數矩陣,再將最相關(guān)的兩類(lèi)合并,這樣繼續下去,按照逐步結合的方法進(jìn)行類(lèi)與類(lèi)之間的合并.直到各個(gè)新類(lèi)間的相關(guān)系數小于某個(gè)給定的閾值為止.
分裂法.又稱(chēng)等混合距離分類(lèi)法,它與系統聚類(lèi)的方法相反,在開(kāi)始時(shí)將所有像元看成一類(lèi),求出各變量的均值和均方差,按照一定公式計算分裂后兩類(lèi)的中心,再算出各像元到這兩類(lèi)中心的聚類(lèi),將像元歸并到距離最近的那一類(lèi)去,形成兩個(gè)新類(lèi).然后再對各個(gè)新類(lèi)進(jìn)行分類(lèi),只要有一個(gè)波段的均方差大于規定的閾值,新類(lèi)就要分裂.
遙感影像的監督分類(lèi)是在已知類(lèi)別的訓練場(chǎng)地上提取各類(lèi)別訓練樣本,通過(guò)選擇特征變量、確定判別函數或判別式把影像中的各個(gè)像元點(diǎn)劃歸到各個(gè)給定類(lèi)的分類(lèi).它的基本思想是:首先根據類(lèi)別的先驗知識確定判別函數和相應的判別準則,利用一定數量的已知類(lèi)別樣本的觀(guān)測值確定判別函數中的待定參數,然后將未知類(lèi)別的樣本的觀(guān)測值代入判別函數,再根據判別準則對該樣本的所屬類(lèi)別做出判定.遙感影像的非監督分類(lèi)也稱(chēng)為聚類(lèi),它是事先無(wú)法知道類(lèi)別的先驗知識,在沒(méi)有類(lèi)別先驗知識的情況下將所有樣本劃分為若干類(lèi)別的方法.它的基本思想是事先不知道類(lèi)別的先驗知識,僅根據地物的光譜特征的相關(guān)性或相似性來(lái)進(jìn)行分類(lèi),再根據實(shí)地調查數據比較后確定其類(lèi)別屬性.
遙感影像的監督分類(lèi)和非監督分類(lèi)方法,是影像分類(lèi)的最基本、最概括的兩種方法.傳統的監督分類(lèi)和非監督分類(lèi)方法雖然各有優(yōu)勢,但是也都存在一定的不足.新方法、新理論、新技術(shù)的引入,為遙感影像分類(lèi)提供了廣闊的前景,監督分類(lèi)與非監督分類(lèi)的混合使用更是大大的提高了分類(lèi)的精度.
計算機技術(shù)對影像分類(lèi)的促進(jìn)與發(fā)展.計算機技術(shù)的引進(jìn),解決了影像分類(lèi)中海量數據的計算與管理問(wèn)題;計算機技術(shù)支持下的GIS用來(lái)輔助影像分類(lèi),主要通過(guò)四種模式進(jìn)行[12]:GIS數據作為影像分析的訓練樣本和先驗信息;利用GIS技術(shù)對研究區域場(chǎng)景和影像分層分析;GIS建立面向對象的影像分類(lèi);提取和挖掘GIS中的知識進(jìn)行專(zhuān)家分析.這些模式促進(jìn)了GIS與遙感的結合,提高了影像分類(lèi)精確性和準確性,使得影像分類(lèi)邁入了新的天地.
數學(xué)方法的引入和模型研究的進(jìn)展為影像分類(lèi)注入了新的活力.不同的數學(xué)方法被引用到模型研究上來(lái),為模型研究的發(fā)展提供了廣闊的天地,相應地,在遙感影像分類(lèi)中也產(chǎn)生了大量不同形式的分類(lèi)模型.如徑向基函數(RBF)與粗糙理論結合的基于粗糙理論的RBF網(wǎng)絡(luò )模型應用于遙感分類(lèi)[5],對于提供分類(lèi)精度、增加收斂性都有很好的作用;而基于RBF映射理論的神經(jīng)網(wǎng)絡(luò )模型更是融合了參數化統計分布模型和非參數化線(xiàn)性感知器映射模型的優(yōu)點(diǎn),不僅學(xué)習速度快,而且有高度復雜的映射能力[6].又如模糊數學(xué)理論應用于影像分類(lèi)產(chǎn)生模糊聚類(lèi),對影像中混合像元的分類(lèi)有很好的效果;模糊理論與各種模型結合,更使得影像分類(lèi)方法的不斷完善,分類(lèi)精度不斷提高.
人工智能技術(shù)對影像分類(lèi)的促進(jìn).專(zhuān)家分類(lèi)系統被用于影像分類(lèi)中,利用地學(xué)知識和專(zhuān)家系統來(lái)輔助遙感影像分類(lèi)
[12],大大提高了影像分類(lèi)和信息提取的精度.人工神經(jīng)網(wǎng)絡(luò )由大量神經(jīng)元相互連接構成網(wǎng)絡(luò )結構,通過(guò)模擬人腦神經(jīng)系統的結構和功能應用于影像分類(lèi),具有一定的智能推理能力.同時(shí),它還引入了動(dòng)量法和學(xué)習自適率調整的策略,并與地學(xué)知識集成,很好的解決了專(zhuān)一的BP神經(jīng)網(wǎng)絡(luò )法分類(lèi)的缺點(diǎn)和不足,提高了分類(lèi)效率和分類(lèi)精度.
監督分類(lèi)與非監督分類(lèi)的結合.由于遙感數據的數據量大、類(lèi)別多以及同物異譜和同譜異物現象的存在,用單一的分類(lèi)方法對影像進(jìn)行分類(lèi)其精確度往往不能滿(mǎn)足應用目的要求.用監督分類(lèi)與非監督分類(lèi)相結合的方法來(lái)對影像進(jìn)行分類(lèi),卻常�？梢缘竭_需要的目的.利用這種方法分類(lèi)時(shí)首先用監督分類(lèi)法如多層神經(jīng)網(wǎng)絡(luò )的BP算法將遙感圖像概略地劃分為幾個(gè)大類(lèi),再用非監督分類(lèi)法如K-Means聚類(lèi)和ISODATA聚類(lèi)對第一步已分出的各個(gè)大類(lèi)進(jìn)行細分,直到滿(mǎn)足要求為止[13].監督分類(lèi)與非監督分類(lèi)的結合的復合分類(lèi)方法,改變了傳統的單一的分類(lèi)方法對影像進(jìn)行分類(lèi)的弊端,彌補了其不足,為影像分類(lèi)開(kāi)辟了廣闊的前景.
【非監督學(xué)習方法大全】相關(guān)文章：
非誠勿擾經(jīng)典臺詞大全11-23
亞偉速錄學(xué)習方法大全08-09
奧數學(xué)習方法大全11-10
超強的韓語(yǔ)學(xué)習方法大全09-10
小提琴學(xué)習方法大全10-04
高中英語(yǔ)學(xué)習方法大全08-04
英語(yǔ)口語(yǔ)學(xué)習方法技巧大全08-19
韓語(yǔ)初學(xué)者學(xué)習方法大全11-13
監督與被監督醫學(xué)心理研究論文06-25