第5章近鄰法則和集群

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

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

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

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

如果已知連續隨機變量的概率密度函數為的數學期望為:

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

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

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

在，A為小于1的正常數下，最小。

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

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

如果能夠趨近于一個中心在的函數，則該式的計算就可以大大簡化了。設想：因為是的最近鄰，可以期望密度函數在的附近有一個陡峭的峰，而在其它地方則很小。這是什么含義呢？在已知的條件下，的最近鄰在的附近的概率密度最大。可以這樣設想的依據：相同類別的樣本特征相同或相近，分布最集中。舉例說明：

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

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

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

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

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

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

在，A為小于1的正常數下，最小。

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

極小時得出即整理得：

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

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

的個近鄰中，

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

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

5.1.5快速近鄰算法

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

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

維訓練樣本集,

,待分類樣本

；輸出:

的最近鄰

；步驟:(1)以

為中心,構造一個

為邊長的鄰域。(2)在

中找出落入的訓練集

的樣本，如果

為空，則增加

一個級差

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

計算距離

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

維訓練樣本集,

,待分類樣本

；輸出:

的最近鄰

；步驟:(1)以

為中心,構造一個

為邊長的鄰域。(2)在

中找出落入的訓練集

的樣本，如

為空，則增加

一個級差

,轉(1)。(3)擴大鄰域

到

，找出全部落入這個鄰域中訓練集

的樣本，即

的一個子集

。(4)對全部

計算距離

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

以從近到遠的順序列出所有的成員。構成三個表

。………………

………計算待分類模式到的距離,。在表中分別按將嵌入相應的位置上。…………

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

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

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

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

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

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

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

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

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

為了得到合適的自然數據群，閾值應當選得大于可作為代表的群內距離和小于可作為代表的群間距離。

（群內距離），（群間距離）

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

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

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

誤差平方準則設是中樣本的數目，是這些樣本的均值向量，

總的誤差平方和為：

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

當各群的樣本都很密集，且彼此之間明顯分開時，是一種合適的準則函數。

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

窮舉法只適合數據規模比較小的場合。

設有個樣本，要求分為組，使每組都不為空的劃分大約有種，如果將有種分法，顯然這時用窮舉法是不可取的。迭代最優化方法是尋找最優分劃的常用方法。基本思想：是找一個合理的初始劃分，然后試探性地將樣本從一個群搬到另一個群。只要某次搬動能使準則函數的值有所改進的話，就認為這次搬動是正確的，然后選擇下一個樣本繼續如法進行。如果某次搬動使準則函數的值變壞，則樣本退回到原來的群中去。

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

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

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

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

則說明對這次搬動改進了準則函數的值。

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

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

取

Step2

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

Step2分群

Step3計算新的群心

Step４判斷

Step２分群

Step３計算新的群心

Step４判斷

因為及所以算法收斂，分群結束。C-均值算法的結果受到下列因素的影響:C個初始分群中心的選取；與樣本的選取次序有關；與樣本的幾何分布有關；與樣本數量差異的大小有關；

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

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

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

這種方法效果比較好，容易實現，是經常使用的方法之一。２.分解法凝聚法的反方向

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

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

（3）平均法

（4）離差平方和法

關于近點距離法和遠點距離法的性能請參考教材的87-89頁的內容。

基于近點距離的等級集群算法步驟

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