第5章近鄰法則和集群

第5章近鄰法則和集群

近鄰法則近鄰法則的錯誤率

K-近鄰法則快速近鄰算法集群的準(zhǔn)則函數(shù)迭代最優(yōu)化方法等級集群方法一.近鄰法則設(shè)有一個已知類別的樣本集：樣本集中的樣本分別屬于個類別:設(shè)每類的樣本數(shù)分別為:如果這n個樣本中與待分類樣本X距離最近的一個樣本為X’，則把X分到X’所屬的類別。近鄰法則的判別函數(shù)為:決策規(guī)則:若則把分到類。

可以看出近鄰法則計算非常簡單，但是這個方法如何？（1）分類能力如何？（2）分類錯誤率如何？能否給出定性與定量的解釋？二.近鄰法則的分類能力中有個類別的樣本,每個類別有個樣本,每次從中取出一個樣本,比較與的相近程度,由于每次取出的樣本是隨機(jī)的,因而樣本的類別狀態(tài)也是隨機(jī)的。把的最近鄰的類別狀態(tài)看成一個隨機(jī)變量（可能是中的任意一個）。于是，的概率就是后驗(yàn)概率，當(dāng)樣本的數(shù)目越來越多時，可以認(rèn)為的最近鄰離它越來越近，從而：這樣，就可以把近鄰法則看成是由概率來決定的類別。（1）在近鄰法則中，的最近鄰的類別狀態(tài)為的概率為，所以分到類的概率為，而不分到的概率為（2）我們已經(jīng)知道，在Bayes決策中,有取作為的類別。比較Bayes決策和近鄰法則，可以看出：按Bayes決策法則：以概率1決策按最近鄰法則：以概率決策舉例說明:設(shè)在三個類別問題中，的后驗(yàn)概率分別為：按Bayes決策：因?yàn)樗园唇彿▌t決策：有0.4的概率有0.3的概率有0.3的概率（1）當(dāng)接近1時，近鄰法則的錯誤概率,與Bayes決策的結(jié)果幾乎相同，說明這兩種方法同樣“好”。（2）當(dāng)，兩者的錯誤概率都接近，說明兩種方法同樣“壞”。

由于Bayes分類器是最優(yōu)分類器，與Bayes分類器的比較可以看出，近鄰法則有較好的分類性質(zhì)。5.1.2近鄰法則的錯誤率回顧:最小錯誤概率的Bayes決策中的有關(guān)內(nèi)容模式特征是一個隨機(jī)變量，用后驗(yàn)概率作出分類決策時，會有錯誤分類的可能性,對于每個不同的值,其也不同,從而分類錯誤概率也不同,所以分類錯誤概率可以看作是的函數(shù).

如果已知連續(xù)隨機(jī)變量的概率密度函數(shù)為的數(shù)學(xué)期望為:

對于模式向量,由于是一個隨機(jī)變量,所以有:

對于每個觀察向量，如果使盡可能小的話，則上式積分也必定盡可能小。從而錯誤概率就達(dá)到極小。若記是的極小值，是的極小值，則：

在什么情況下可以取得最小值？

在，A為小于1的正常數(shù)下，最小。

也就是說，一個最大，其余都相等時，有最小值。這樣就有：對于近鄰法則,設(shè)是采用個樣本時的錯誤概率，并設(shè)則有近鄰法則錯誤率的上下限：先求

設(shè)用某一組N個已知類別的樣本對分類，如果的最近鄰樣本為，則把分到所屬的類別。如果用不同組的N個樣本對分類，則的最近鄰可能是完全不同的。由于近鄰決策完全取決于的最近鄰樣本，所以錯誤概率與，有關(guān)，即。每次取一組樣本做最近鄰決策，每次都有一定的錯誤概率，如果對取平均，則有：對于數(shù)學(xué)表達(dá)式是難以獲得的。如何考慮解決求的問題呢？

如果能夠趨近于一個中心在的函數(shù)，則該式的計算就可以大大簡化了。設(shè)想：因?yàn)槭堑淖罱彛梢云谕芏群瘮?shù)在的附近有一個陡峭的峰，而在其它地方則很小。這是什么含義呢？在已知的條件下，的最近鄰在的附近的概率密度最大?？梢赃@樣設(shè)想的依據(jù)：相同類別的樣本特征相同或相近，分布最集中。舉例說明：

為了證明當(dāng)n趨于無窮大時，可能趨于一個中心在的函數(shù)，我們設(shè)對于給定的，概率密度是連續(xù)的且不為零。這樣，任何樣本落在以為中心的一個超球S中的概率記為：落在S以外的概率為,

當(dāng)樣本獨(dú)立抽取時，全部n個獨(dú)立抽取的樣本落在S以外的概率就為當(dāng)時這就是說，總有一個以上的樣本落在S內(nèi)的概率為1.由于S可以任意小，所以當(dāng)S很小時，只要樣本數(shù)n足夠大，總有的近鄰在S內(nèi)，所以，以概率1收斂于。這就證明了當(dāng)n趨于無窮大時，趨于函數(shù)。即下面討論錯誤概率將n個獨(dú)立抽取的已知類別的樣本表示成二元對的形式：其中是C個類別狀態(tài)中的任意一個?，F(xiàn)在假定抽取一對，并假定是的最近鄰，類別為，即是的最近鄰，由于和是獨(dú)立抽取的，的類別狀態(tài)和的類別狀態(tài)無關(guān)，因此就有：當(dāng)采用近鄰法則時，如果就會產(chǎn)生分類錯誤，因?yàn)楫?dāng)時有（以概率1收斂于）所以錯誤概率為

對于當(dāng)可以寫成：這樣，近鄰法則的錯誤率為下面我們開始證明最近鄰法則錯誤率的上下界。要證明的下界為，只要指出在某些特定情況下存在就可以了。（為什么，請思考）1.在時（，）所以在這種情況下成立。2.在時（各后驗(yàn)概率都相等）

所以在這種情況下也成立。

思考：通過P的下界的證明，可以采用在特殊情況有P=P*就可以。那么對于P的上界的證明可不可以也這樣做？下面證明P的上界。

要證明P的上界，關(guān)鍵的問題是如何將最近鄰法則的錯誤率P和最小錯誤概率的貝葉斯錯誤率P*聯(lián)系起來。由前面的推導(dǎo)已經(jīng)知道了最近鄰法則的錯誤率為：由最小錯誤概率的Bayes決策()可知最小錯誤概率為：這兩個公式對我們的啟發(fā)是：對已知的而言，的最小值對應(yīng)著P的最大值，如果能求得P的最大值，就把P*和P聯(lián)系起來了。由數(shù)學(xué)知識可知：

在，A為小于1的正常數(shù)下，最小。

這樣就有：而所以，從而可得：

極小時得出即整理得：

由于根據(jù)方差的定義：有：（5-15）把右式展開，由于方差非負(fù)，所以從而，如果，對下式（5-15）兩邊取積分，得等號只在方差為0時成立可以看出，左式=P，所以5.1.3K-近鄰法則

K-近鄰法是最近鄰法的一個改進(jìn)。有個已知類別的樣本，

的個近鄰中，

用判別函數(shù)表示：決策規(guī)則為：若則取待識別樣本的個近鄰，看這個近鄰中多數(shù)樣本屬于哪一類，就把歸為那一類。最近鄰法則和K-近鄰法則的優(yōu)缺點(diǎn)：優(yōu)點(diǎn)：算法簡單缺點(diǎn)：（1）每次需要計算x與全部樣本間的距離并進(jìn)行比較。計算機(jī)存儲容量和計算量都很大。

（2）沒有考慮決策的風(fēng)險，如果錯誤代價很大時，會產(chǎn)生很大風(fēng)險。（3）錯誤率分析是情況下得出的，而對有限樣本集理論依據(jù)不充分?？梢钥闯觯?）和（3）是近鄰法則的固有問題，那么通過什么方法可以改善缺點(diǎn)(1)呢?

5.1.5快速近鄰算法

1.分量鄰域法思路：近鄰法則與的近鄰樣本有關(guān)，那就關(guān)注近鄰樣本。方法：是待分類的模式，以

為中心，構(gòu)造邊長為的鄰域，逐漸擴(kuò)大該鄰域，直至有一個樣本落入這個鄰域時為止。算法：輸入:

維訓(xùn)練樣本集,

,待分類樣本

；輸出:

的最近鄰

；步驟:(1)以

為中心,構(gòu)造一個

為邊長的鄰域。(2)在

中找出落入的訓(xùn)練集

的樣本，如果

為空，則增加

一個級差

,轉(zhuǎn)步驟(1)。(3)對全部

計算距離

，最小者即為的最近鄰。該算法存在一個什么問題？算法：輸入:

維訓(xùn)練樣本集,

,待分類樣本

；輸出:

的最近鄰

；步驟:(1)以

為中心,構(gòu)造一個

為邊長的鄰域。(2)在

中找出落入的訓(xùn)練集

的樣本，如

為空，則增加

一個級差

,轉(zhuǎn)(1)。(3)擴(kuò)大鄰域

到

，找出全部落入這個鄰域中訓(xùn)練集

的樣本，即

的一個子集

。(4)對全部

計算距離

，最小者即為的最近鄰。算法優(yōu)點(diǎn)：簡單，快速。缺點(diǎn)：特征維數(shù)高時，效率低。2.列表法(1)預(yù)處理階段在模式空間指定任意三個點(diǎn)。分別計算這三個點(diǎn)到訓(xùn)練樣本集中全部成員的距離。對

以從近到遠(yuǎn)的順序列出所有的成員。構(gòu)成三個表

?！?/p>

………計算待分類模式到的距離,。在表中分別按將嵌入相應(yīng)的位置上?！?/p>

……(2)搜索階段在表中取的近鄰形成三個子集若非空,則交集中的元素就可能包含的最近鄰。若為空,

則逐步擴(kuò)大的鄰域的范圍。直至非空,找到的最近鄰。5.2集群（聚類clustering)

采用有類別標(biāo)識的訓(xùn)練樣本集來實(shí)現(xiàn)對待識別模式的分類，稱為有監(jiān)督學(xué)習(xí)或有教師學(xué)習(xí)。如線性判別函數(shù)，Bayes決策，近鄰法則等。把沒有訓(xùn)練樣本集時的分類方法，即無監(jiān)督的或無教師的分類方法叫做集群。集群問題中有兩種情況：預(yù)先指定分群的數(shù)目預(yù)先不知道分群的數(shù)目

面對一組待分類的模式，根據(jù)什么分類呢？

實(shí)際上，集群的目的就是要在一組數(shù)據(jù)中找出自然形成的數(shù)據(jù)群，而一群中的樣本彼此之間應(yīng)該比其它群的樣本之間更相像一些。也就是說，根據(jù)各個待分類的模式特征的相似程度進(jìn)行分類，把相似的歸為一類。

因此，集群應(yīng)該解決兩個問題：（1）如何評定樣本之間的相似程度？（2）如何根據(jù)相似程度將給定樣本集劃分為不同的群？樣本間相似性的度量一個模式向量是特征空間的一個點(diǎn)，如果兩個樣本在特征空間相距很近，它們的各個特征也應(yīng)該相差不大，因此，兩個樣本在特征空間的距離可以作為樣本間相似性的一種度量。常用的方法是先定義一個適當(dāng)?shù)木嚯x來度量相似性。如果這個距離是相似性的一個好的度量，那么我們就可以期望在同一群內(nèi)樣本之間的距離將明顯小于不同群的樣本之間的距離。

歐氏距離：用距離來度量相似性，存在閾值的選擇問題。

如果太大，則可能把全部樣本歸到同一個群中去。如果太小，則每個樣本為一個群。

顯然，上述兩種情況都失去了分群的意義。d1d2

為了得到合適的自然數(shù)據(jù)群，閾值應(yīng)當(dāng)選得大于可作為代表的群內(nèi)距離和小于可作為代表的群間距離。

（群內(nèi)距離），（群間距離）

兩向量間的距離度量有許多種，除了歐氏距離外還有幾個常用距離：1.Mahalanobis距離式中為樣本各特征的協(xié)方差矩陣。2.Minkovsky距離式中為樣本維數(shù)。3.Camberra距離4.Chebychev距離5.2.2集群的準(zhǔn)則函數(shù)

前面介紹了如何評定樣本間的相似性，現(xiàn)在討論如何根據(jù)樣本間的相似性把一組樣本劃分為不同的群的方法。假設(shè)有樣本集，要求把它分成c個不相交的子集，每個子集表示一群樣本。對這個劃分的要求是：在同一群內(nèi)的樣本比不同群的樣本更相像一些。由于距離閾值的選取不同，分群的結(jié)果也不同。群的劃分具有人為規(guī)定性。

所以需要定義一個準(zhǔn)則函數(shù)，利用它來度量數(shù)據(jù)劃分所形成的群的性質(zhì)，這樣就把分群的問題變成使這個準(zhǔn)則函數(shù)取極值的問題。

誤差平方準(zhǔn)則設(shè)是中樣本的數(shù)目，是這些樣本的均值向量，

總的誤差平方和為：

度量了用個群的中心來代表個樣本子集時所產(chǎn)生的總的誤差的平方。個群的劃分可能是不同的，對應(yīng)于每一種劃分，都有一個誤差平方和。所以，的值依賴于樣本的劃分，使最小的一種劃分就定義為最小誤差劃分。誤差平方準(zhǔn)則函數(shù)的性能：

當(dāng)各群的樣本都很密集，且彼此之間明顯分開時，是一種合適的準(zhǔn)則函數(shù)。

當(dāng)各群中樣本數(shù)目相差很大時，用誤差平方和準(zhǔn)則分群有時會產(chǎn)生一些問題，有可能把大的自然群拆成兩個。迭代最優(yōu)化方法集群劃分的準(zhǔn)則函數(shù)選定后，就要找出樣本的一種劃分，使準(zhǔn)則函數(shù)取極值，這樣集群問題就變成了一個組合優(yōu)化問題。由于樣本數(shù)目有限，所以可能的劃分也是有限的，我們首先想到的方法是窮舉法，即遍歷各種劃分，使準(zhǔn)則函數(shù)取極值的劃分為最優(yōu)劃分。

窮舉法只適合數(shù)據(jù)規(guī)模比較小的場合。

設(shè)有個樣本，要求分為組，使每組都不為空的劃分大約有種，如果將有種分法，顯然這時用窮舉法是不可取的。迭代最優(yōu)化方法是尋找最優(yōu)分劃的常用方法?；舅枷耄菏钦乙粋€合理的初始劃分，然后試探性地將樣本從一個群搬到另一個群。只要某次搬動能使準(zhǔn)則函數(shù)的值有所改進(jìn)的話，就認(rèn)為這次搬動是正確的，然后選擇下一個樣本繼續(xù)如法進(jìn)行。如果某次搬動使準(zhǔn)則函數(shù)的值變壞，則樣本退回到原來的群中去。

如圖示：初始劃分搬動一個樣本

下面我們通過誤差平方和準(zhǔn)則函數(shù)的極小化來說明迭代最優(yōu)化算法。其中假定我們把原來在中的一個樣本試探性地搬到中去，則變成：上式可寫成：而

對于，取，就是說，只有一個樣本的群不要取消掉，則類似上面的推導(dǎo)方法，可得

如果把從第群搬到第群后，減少的量比增加的量多，即：

則說明對這次搬動改進(jìn)了準(zhǔn)則函數(shù)的值。

算法步驟：Step1選擇把個樣本分成個群的初始分劃，計算；Step2選擇下一個備選樣本，設(shè)從中選出；Step3若，則轉(zhuǎn)向Step6，否則計算Step4對于一切，若，則將放到中；Step5修改和的值；Step6若經(jīng)過次試驗(yàn)后，不變，則停止，否則轉(zhuǎn)Step2。這種方法的缺陷：（1）對初始劃分敏感；（2）結(jié)果與備選樣本的次序有關(guān)，會陷入局部極值。C-均值算法(基于最近距離的聚類方法)1.根據(jù)指定群數(shù)，任選個代表點(diǎn)作為群的群心，一般以開頭個樣本作為初始群心。2.逐個將樣本集中的每個樣本歸入與之最近的群心所代表的群，形成個群，即在第次迭代時，若則表示第次迭代時，以第個群心為代表群。3.計算新的群心，即

為第個群域中的樣本個數(shù)。4.若，算法收斂，算法停止，否則轉(zhuǎn)步驟2。Ｃ－均值算法舉例C=2設(shè)樣本集中的樣本為二維模式樣本，表示如下：１１２３４５２３４５x1x2··2.672.5Step1

取

Step2

分群Step3計算新的群心Step4判斷

Step2分群

Step3計算新的群心

Step４判斷

Step２分群

Step３計算新的群心

Step４判斷

因?yàn)榧八运惴ㄊ諗浚秩航Y(jié)束。C-均值算法的結(jié)果受到下列因素的影響:C個初始分群中心的選??；與樣本的選取次序有關(guān)；與樣本的幾何分布有關(guān)；與樣本數(shù)量差異的大小有關(guān)；

一般地，對于給定樣本集，分群結(jié)果是唯一的嗎？等級集群方法問題：當(dāng)不知道要分成幾群時，而要把一些未分類的樣本分成若干合理的群時，如何做呢？

在沒有指定群數(shù)的情況下，n個樣本至少可以分成一個群，這就是樣本的全體；最多可以把它們分成n個群，每個群只有一個樣本。顯然，這樣的分群沒有意義。但是，我們可以由此考慮(n個群一個群）的過程，這樣，我們就可以把集群看作是一個把n個樣本聚集成K個群的集群序列的結(jié)果。反之，把(一個群n個群），看做把n個樣本劃分成K個群的劃分序列的結(jié)果。這樣，可以有兩種產(chǎn)生序列的方法：１．凝聚法

從n個樣本劃分為n個群開始，每個群中只有一個樣本，然后通過不斷的合并而形成一個聚合的序列，最后凝聚成一個包含全部樣本的大群。

這種方法效果比較好，容易實(shí)現(xiàn)，是經(jīng)常使用的方法之一。２.分解法凝聚法的反方向

我們主要討論凝聚法這種等級集群方法可以表示成一棵分類樹，來實(shí)現(xiàn)樣本分群的過程。聚類水平高相似度

相似聚類，用距離度量，距離可以有不同的度量方法，采用的類間距離不同，聚類過程是不一樣的。（1）近點(diǎn)距離法（2）遠(yuǎn)點(diǎn)距離法

（3）平均法

（4）離差平方和法

關(guān)于近點(diǎn)距離法和遠(yuǎn)點(diǎn)距離法的性能請參考教材的87-89頁的內(nèi)容。

基于近點(diǎn)距離的等級集群算法步驟

對于樣本集，設(shè)表示第次合并時的第類（1）初始分類，令,，（2）計算各類間的距離，由此生成一個對稱的距離矩陣，為類的個數(shù)。（初始時）