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