機(jī)器學(xué)習(xí)簡明教程-基于Python語言實(shí)現(xiàn) 課件 第4章基于距離的算法

基于距離的算法《機(jī)器學(xué)習(xí)簡明教程》高延增侯躍恩羅志堅(jiān)機(jī)械工業(yè)出版社04本章目標(biāo)?掌握分類和聚類的區(qū)別?理解幾種常用的距離度量方法?掌握K近鄰算法?掌握K均值算法邏輯回歸可以根據(jù)學(xué)生的作業(yè)成績和平時(shí)表現(xiàn)預(yù)測學(xué)生期末總評是否能及格，也就是說邏輯回歸算法將學(xué)生分成了“及格的”和“不及格的”兩種類別，類似這樣用已知標(biāo)簽的訓(xùn)練集訓(xùn)練一種機(jī)器學(xué)習(xí)算法給某個(gè)個(gè)體打上類別標(biāo)簽的過程稱為分類。還有一類問題，比如需要設(shè)計(jì)一套算法將學(xué)生按其特點(diǎn)歸類以制定個(gè)性化的人才培養(yǎng)方案，但算法事先并不知道訓(xùn)練樣本中的學(xué)生具體的類標(biāo)簽，類似這類問題被稱為聚類。分類是一種有監(jiān)督學(xué)習(xí)任務(wù)，其訓(xùn)練樣本有自變量及其對應(yīng)的因變量，即根據(jù)一堆已經(jīng)打上分類標(biāo)簽的訓(xùn)練數(shù)據(jù)尋找合適的分類算法；而聚類是一種無監(jiān)督學(xué)習(xí)任務(wù)，無監(jiān)督學(xué)習(xí)的處理對象是一堆無標(biāo)簽的數(shù)據(jù)，算法需要從數(shù)據(jù)集中發(fā)現(xiàn)和總結(jié)模式或者結(jié)構(gòu)來完成聚類任務(wù)。本章的重點(diǎn)是屬于有監(jiān)督學(xué)習(xí)的K近鄰算法、屬于無監(jiān)督學(xué)習(xí)的K均值算法。雖然K近鄰和K均值分別屬于有監(jiān)督、無監(jiān)督學(xué)習(xí)算法，但因其實(shí)現(xiàn)原理有一定相似性，本書將此兩種算法放在同一章節(jié)介紹。目錄/Contents4.14.2分類與聚類的區(qū)別距離度量問題4.3K近鄰4.4K均值聚類4.1分類與聚類的區(qū)別所謂分類就是從已知類別樣本組成的集合中訓(xùn)練出一種分類器，用這個(gè)分類器對未知類別的樣本進(jìn)行分類。分類算法的分類過程就是建立一種分類模型來描述預(yù)定的數(shù)據(jù)集或概念集，通過分析由屬性描述的數(shù)據(jù)庫元組來構(gòu)造模型。分類的目的就是使用分類對新的數(shù)據(jù)集進(jìn)行劃分，其主要涉及分類規(guī)則的準(zhǔn)確性、過擬合、矛盾劃分的取舍等，分類問題示意如圖：“物以類聚、人以群分”，在一個(gè)空間中，如果兩個(gè)樣本距離較近，那它們同屬一個(gè)類別的可能性也較高。根據(jù)這一思想，在對一個(gè)新的、未知類別的樣本進(jìn)行分類時(shí)可以參考與它距離較近的一些樣本的類別，據(jù)此來對新樣本進(jìn)行分類表決，這就是K近鄰分類的基本思想。4.1分類與聚類的區(qū)別聚類算法分為層次聚類、劃分聚類兩種。層次聚類初始階段將每個(gè)樣本點(diǎn)看成一類，然后再對這些類每次迭代的時(shí)候都進(jìn)行兩兩合并，直到所有的類聚集完成；劃分聚類首先指定類的個(gè)數(shù)K，然后將樣本集隨機(jī)分成K類，在每次迭代的時(shí)候?qū)颖炯M(jìn)行重新優(yōu)化組合成為新的K類，最后使得類內(nèi)的相似度、類間的差異或迭代次數(shù)達(dá)到設(shè)定值。與分類類似，聚類任務(wù)的流程也可劃分為數(shù)據(jù)準(zhǔn)備、特征選擇、特征提取、聚類、聚類結(jié)果評估等幾個(gè)階段。假設(shè)有一組樣本如下圖（a）所示，事先不知道這些樣本的具體類別，如果指定要分為2類（K=2），分類結(jié)果如圖（b），這就是劃分聚類。各種劃分聚類算法中，K均值是最著名的一種。4.1分類與聚類的區(qū)別K均值聚類是一種迭代求解算法，首先，隨機(jī)選取K個(gè)中心，計(jì)算樣本點(diǎn)與K個(gè)中心的距離并將此樣本點(diǎn)暫時(shí)歸類為離它最近的那個(gè)中心，這樣處理完每個(gè)樣本點(diǎn)后就可以臨時(shí)將樣本空間分為K個(gè)類；然后，將這K個(gè)類的中心作為新的中心點(diǎn)，再重新按樣本點(diǎn)與新的中心的距離來重新聚類一次；循環(huán)往復(fù)，直至達(dá)到循環(huán)結(jié)束條件。K近鄰分類和K均值聚類算法的一個(gè)重要依據(jù)是距離。數(shù)據(jù)挖掘中的樣本通常由一個(gè)多維度的向量表示，而樣本的相似性大小的度量可以轉(zhuǎn)化為對應(yīng)向量之間的距離的求解。

對于距離概念的深入理解，是掌握數(shù)據(jù)挖掘算法的必要前提。目錄/Contents4.14.2分類與聚類的區(qū)別距離度量問題4.3K近鄰4.4K均值聚類4.2距離度量問題距離是一個(gè)函數(shù)，將樣本空間中的兩個(gè)樣本點(diǎn)映射為一個(gè)實(shí)數(shù)

機(jī)器學(xué)習(xí)中可能用到的距離函數(shù)有很多，包括歐式距離、曼哈頓距離、切比雪夫距離等。但一個(gè)距離函數(shù)又不是隨意的將兩個(gè)樣本點(diǎn)映射為一個(gè)實(shí)數(shù)，此映射函數(shù)只有在滿足一定前提條件后才能被當(dāng)成距離函數(shù)使用。4.2距離度量問題廣義的距離函數(shù)

描述樣本點(diǎn)的向量的維度值有兩類變量，表示身高、體重這一類屬性的數(shù)值型維度，以及表示性別、是否及格等的布爾型維度，根據(jù)向量的特點(diǎn)可以將距離函數(shù)分成數(shù)值向量距離和布爾向量距離兩類。4.2距離度量問題——數(shù)值向量距離數(shù)值向量距離函數(shù)有很多，常用的有歐式距離（Euclideandistance）、曼哈頓距離(Manhattandistance)、閔可夫斯基距離(Minkowskidistance)等。歐式距離(Euclideandistance)二維向量歐式距離示意圖

4.2距離度量問題——數(shù)值向量距離歐式距離簡明易懂，但在數(shù)據(jù)挖掘算法中使用時(shí)存在明顯缺陷。由歐式距離的計(jì)算公式知，它的結(jié)果與度量單位有關(guān)，這在應(yīng)用時(shí)往往會與實(shí)際意愿相背離。例如，在教育數(shù)據(jù)挖掘項(xiàng)目中要計(jì)算兩個(gè)學(xué)生的相似性，如果以米為單位他們的身高這一維度上可能有0.2的差距，但如果以厘米為單位，這一差距就變成20了，這樣和其他維度比如體重相結(jié)合計(jì)算兩個(gè)學(xué)生的相似性就沒有一致性。針對這一缺點(diǎn)，可以使用標(biāo)準(zhǔn)化歐式距離，先將向量的各個(gè)維度的數(shù)值都投影到[0,1]區(qū)間再進(jìn)行歐式距離計(jì)算。標(biāo)準(zhǔn)化歐式距離（StandardizedEuclideandistance）

經(jīng)過式（4.4）處理后，樣本空間中樣本向量的每個(gè)分量的均值都為0、方差為1。標(biāo)準(zhǔn)化后的樣本，進(jìn)行歐氏距離計(jì)算的公式如式

4.2距離度量問題——數(shù)值向量距離馬氏距離（MahalanobisDistance）

4.2距離度量問題——數(shù)值向量距離曼哈頓距離(Manhattandistance)前面的歐式距離是兩點(diǎn)之間的直線距離，但在路徑規(guī)劃這一類實(shí)際問題中，兩點(diǎn)之間很可能沒有直線相連，曼哈頓距離的定義就考慮到了這種情況。曼哈頓距離又稱城市區(qū)塊距離，在歐幾里得空間的固定直角坐標(biāo)系上兩點(diǎn)間的曼哈頓距離是這兩個(gè)點(diǎn)所形成的線段對坐標(biāo)軸產(chǎn)生的投影的距離總和。假設(shè)A、B兩點(diǎn)的坐標(biāo)分別為(x1,y1)和(x2,y2)，則AB兩點(diǎn)的曼哈頓距離如式

AB兩點(diǎn)間三條連接線，線1是歐式距離，線3是曼哈頓距離，而線2是與線3等效的一條曼哈頓距離線。從二維擴(kuò)展到更多維度時(shí)，曼哈頓距離的計(jì)算方式類似

相對于歐式距離，曼哈頓距離的求解只需要做加減法，不需要平方和開方運(yùn)算，使得計(jì)算效率提高的同時(shí)消除開方運(yùn)算的誤差影響。4.2距離度量問題——數(shù)值向量距離閔可夫斯基距離(Minkowskidistance)

除了上述歐式距離、馬氏距離、曼哈頓距離、閔可夫斯基距離外，常用的數(shù)值向量距離函數(shù)還有余弦相似度、切比雪夫距離、加權(quán)閔可夫斯基距離等。4.2距離度量問題——布爾向量距離0和1組成的字母“E”布爾向量又稱邏輯向量，與數(shù)值向量不同，一個(gè)邏輯向量儲存一組TRUE或FALSE值，即向量的各個(gè)維度的取值只能是0或1。例，如右圖所示為一個(gè)手寫大寫英文字母“E”圖像經(jīng)過預(yù)處理后的效果，圖中像素點(diǎn)的值全部是布爾值。常用的布爾向量函數(shù)包括漢明距離（HammingDistance）、杰卡德距離（JaccardDistance）、Dice系數(shù)（DiceDissimilarity）等。4.2距離度量問題——布爾向量距離漢明距離（HammingDistance）兩個(gè)等長字符串之間的漢明距離是兩個(gè)字符串對應(yīng)位置的不同字符的個(gè)數(shù)，就是將一個(gè)字符串變換成另外一個(gè)字符串所需要替換的字符個(gè)數(shù)。如果是兩個(gè)布爾向量，只需取異或運(yùn)算，結(jié)果中１的數(shù)目就是漢明距離，又稱漢明權(quán)重。漢明距離在數(shù)據(jù)處理與挖掘領(lǐng)域應(yīng)用非常廣泛，如Google、Baidu等搜索引擎都推出了“以圖搜圖”的功能，大致步驟如下：

最后，將兩張圖片的比較結(jié)果組合在一起，就構(gòu)成了一個(gè)64位的整數(shù)，這就是這張圖片的指紋。組合的次序并不重要，只要保證所有圖片都采用同樣次序就行了。得到指紋以后，就可以對比不同的圖片，看看64位中有多少位是不一樣的。在理論上，這等同于計(jì)算"漢明距離"（Hammingdistance）。如果不相同的數(shù)據(jù)位不超過5，就說明兩張圖片很相似；如果大于10，就說明這是兩張不同的圖片。4.2距離度量問題——布爾向量距離杰卡德距離（JaccardDistance）給定兩個(gè)集合A、B，Jaccard系數(shù)定義為A與B交集的大小與A與B并集的大小的比值，當(dāng)集合A，B都為空時(shí)，J(A,B)定義為1

與Jaccard系數(shù)相關(guān)的指標(biāo)叫做Jaccard距離，用于描述集合之間的不相似程度。Jaccard距離越大，樣本相似度越低。

4.2距離度量問題——布爾向量距離使用Jaccard距離函數(shù)來計(jì)算布爾向量間的距離

Jaccard距離的應(yīng)用的場景包括：網(wǎng)頁去重、考試防作弊系統(tǒng)、論文查重等，特別適用于“文章查重”一類的稀疏度過高的向量相似性求解的領(lǐng)域。4.2距離度量問題——布爾向量距離Dice系數(shù)（DiceDissimilarity）與Jaccard系數(shù)類似，Dice系數(shù)本質(zhì)上也是一種集合相似度度量函數(shù)，通常用于計(jì)算兩個(gè)集合的相似度，計(jì)算方法如式Dice系數(shù)也可以用來測量兩個(gè)布爾型向量的相似性，其取值范圍在0-1之間。更一般的情況，Dice系數(shù)計(jì)算相似性的示意如下圖，Dice系數(shù)取值越大，表示兩個(gè)被比較的對象越相似。

除漢明距離、杰卡德差異、Dice系數(shù)外，常用的布爾型向量距離函數(shù)還有庫爾辛斯基差異（Kulsinskidissimilarity）、田本羅杰斯差異（Rogers-Tanimotodissimilarity）、拉塞爾差異（Russell-Raodissimilarity）、Yule差異（Yuledissimilarity）等。目錄/Contents4.14.2分類與聚類的區(qū)別距離度量問題4.3K近鄰4.4K均值聚類4.3K近鄰（K-NearestNeighbor,KNN）KNN在算法理論上較成熟，是最簡單、最流行的機(jī)器學(xué)習(xí)算法之一。KNN的基本思路是：如果已經(jīng)有一個(gè)分類好的樣本集，然后就可以用這個(gè)樣本集去對一個(gè)新的、未知分類標(biāo)簽的樣本點(diǎn)進(jìn)行分類，而分類的方式就是在這個(gè)樣本集中找到K個(gè)離新的樣本最近的點(diǎn)，然后利用一定的決策規(guī)則讓這個(gè)K個(gè)近鄰去決定新樣本點(diǎn)所屬類別。例如我們經(jīng)常通過地段來預(yù)估一個(gè)房子的價(jià)值。KNN算法既可以做分類也可以做回歸，主要區(qū)別在于最后做預(yù)測時(shí)的決策方式不同。KNN做分類預(yù)測時(shí)，一般是選擇多數(shù)表決法，即訓(xùn)練集里和預(yù)測的樣本特征最近的K個(gè)樣本，預(yù)測為里面有最多類別數(shù)的類別。而KNN做回歸時(shí)，一般是選擇平均法，即最近的K個(gè)樣本對應(yīng)輸出的平均值作為回歸預(yù)測值。KNN做分類和回歸的方法類似，本書只介紹KNN分類算法。4.3K近鄰——算法描述KNN是一種基于實(shí)例的算法，如下圖（a）有一個(gè)已知每個(gè)樣本所屬類別的樣本集，有了KNN算法就可以通過（a）中的樣本集來判斷一個(gè)新加入的點(diǎn)屬于哪一類（如下圖（b））。但是，在上圖（b）中，如果單看待識別點(diǎn)的一個(gè)最近鄰點(diǎn)可能并不能很準(zhǔn)確的對它進(jìn)行分類，因?yàn)樽罱哪莻€(gè)點(diǎn)有可能是噪聲點(diǎn)，一般會選擇K個(gè)點(diǎn)（K>1），然后讓這K個(gè)最近鄰的點(diǎn)進(jìn)行投票，以決定這個(gè)待識別的點(diǎn)到底屬于“矩形”類還是屬于“三角形”類。K值的選擇是由算法使用者自行決定的，兩分類問題，K應(yīng)該選為奇數(shù)值，投票的時(shí)候就不會出現(xiàn)兩個(gè)類別得票相等的情況。K值的選取需要視實(shí)際情況而定。多數(shù)實(shí)際應(yīng)用的場景中，樣本點(diǎn)的近鄰并不如二維平面直觀，需要根據(jù)4.2節(jié)中介紹的距離計(jì)算方案來求與待分類點(diǎn)距離最近的K個(gè)近鄰。看似民主的讓K個(gè)近鄰點(diǎn)具有相同的投票權(quán)利可能未必合理，在一些應(yīng)用場景需要設(shè)計(jì)更加合理的投票機(jī)制。4.3K近鄰——三要素（1）k值的選?。唬?）距離度量的方式；（3）分類決策規(guī)則。K值是待分類樣本點(diǎn)在訓(xùn)練集中選擇的近鄰點(diǎn)的個(gè)數(shù)，理論上講K越大分類錯(cuò)誤的可能性越小。但在工程實(shí)際中，K值增加并不能持續(xù)的降低錯(cuò)誤率，K值在增加到一定程度后反而會使錯(cuò)誤率變大。合理的解釋是，當(dāng)K值選擇過大時(shí)，將會引入和待分類點(diǎn)過遠(yuǎn)的點(diǎn)，而這些點(diǎn)和待分類點(diǎn)可能并沒有什么關(guān)聯(lián)，將過多的無關(guān)的點(diǎn)引入到投票中勢必會對分類產(chǎn)生干擾。4.3K近鄰——三要素（1）k值的選??；（2）距離度量的方式；（3）分類決策規(guī)則。另外，如果樣本的維度選擇不合理可能會使兩個(gè)并不相似的點(diǎn)距離反而很小、而相似的點(diǎn)卻距離很大，因此在使用KNN算法時(shí)需要謹(jǐn)慎選擇距離度量函數(shù)。4.3K近鄰——三要素（1）k值的選取；（2）距離度量的方式；（3）分類決策規(guī)則。使用的是5近鄰分類器，按照民主投票規(guī)則，待分類點(diǎn)被分為矩形類。但是，直觀上看，待識別點(diǎn)是三角形類的可能性更大。這是因?yàn)榇R別點(diǎn)的最近5個(gè)近鄰點(diǎn)中，3個(gè)矩形點(diǎn)距離待識別點(diǎn)較遠(yuǎn)而2個(gè)三角形點(diǎn)距離較近。針對這一問題，在實(shí)際應(yīng)用中KNN的決策規(guī)則多采用加權(quán)最近鄰。加權(quán)最近鄰，就是所選擇的K個(gè)近鄰點(diǎn)的第i個(gè)點(diǎn)在進(jìn)行投票決策時(shí)乘以一個(gè)系數(shù)后再進(jìn)行投票

加權(quán)K近鄰法的基本思想是距離待識別點(diǎn)越近的點(diǎn)在進(jìn)行投票決策時(shí)的話語權(quán)越大。4.3K近鄰——訓(xùn)練集對KNN的影響樣本訓(xùn)練集的預(yù)處理工作主要是對兩類樣本點(diǎn)的處理：（1）對KNN的分類結(jié)果可能產(chǎn)生錯(cuò)誤導(dǎo)向的樣本點(diǎn)；（2）雖然不會影響分類結(jié)果的正確性但是會降低分類效率的點(diǎn)，即移除這些點(diǎn)不會影響分類結(jié)果但是可以提高分類的速度。A、B區(qū)域中各有一個(gè)三角形點(diǎn)，A區(qū)域中的三角形點(diǎn)被矩形點(diǎn)包圍、B區(qū)域中的三角形點(diǎn)處在三角形區(qū)域和矩形區(qū)域的交界處。A區(qū)域中的三角形點(diǎn)，可能是由噪聲引起的，也可能是在類別標(biāo)簽階段誤處理造成的；而B區(qū)域中的三角形點(diǎn)是比較敏感的，因?yàn)樗硞€(gè)（些）屬性值的輕微變動都可能會改變這個(gè)樣本點(diǎn)的類別。如果這兩種類別的點(diǎn)被包含在KNN的K近鄰點(diǎn)中，都有可能會對分類決策產(chǎn)生不好的影響，因此在進(jìn)行訓(xùn)練樣本集預(yù)處理時(shí)需要將這兩類點(diǎn)剔除。4.3K近鄰——訓(xùn)練集對KNN的影響多余樣例點(diǎn)，虛線圓中求圓形待識別點(diǎn)的K近鄰點(diǎn)，就需求解本集中所有點(diǎn)與待識別點(diǎn)的距離，運(yùn)算量較大。而且，如果將虛線圓框中的矩形點(diǎn)減少并不會影響待識別點(diǎn)的分類結(jié)果。有一些訓(xùn)練樣本點(diǎn)，如果剔除它們非但不會影響分類結(jié)果的正確性，還能降低計(jì)算復(fù)雜度，類似這樣的點(diǎn)就是多余點(diǎn)，在訓(xùn)練樣本集預(yù)處理時(shí)也要剔除4.3K近鄰——算法實(shí)現(xiàn)第一步，需要準(zhǔn)備合適的已知分類標(biāo)簽的訓(xùn)練樣本集；第二步，將待識別點(diǎn)輸入訓(xùn)練集用KNN算法進(jìn)行分類。KNN分類有兩個(gè)關(guān)鍵問題：（1）在分類樣本集中找出X的K個(gè)最近鄰點(diǎn)；（2）分類決策的實(shí)現(xiàn)。4.3K近鄰——算法實(shí)現(xiàn)最簡單的KNN分類決策4.3K近鄰——算法實(shí)現(xiàn)對訓(xùn)練樣本集預(yù)處理的流程，其關(guān)鍵步驟是：（1）有害點(diǎn)（容易使KNN分類結(jié)果出錯(cuò)的點(diǎn)）剔除；（2）多余點(diǎn)（剔除之后不影響KNN分類結(jié)果的點(diǎn)）剔除。剔除有害點(diǎn)的第一步檢測有害點(diǎn)，一種常用的辦法是通過托梅克（Tomek）連接技術(shù)來檢測有害點(diǎn)。所謂托梅克連接，是指樣本集中的兩個(gè)樣本點(diǎn)A和B，如果同時(shí)滿足兩個(gè)條件：（1）A和B互為最近鄰點(diǎn)、（2）A和B的類別不同，那A和B之間就構(gòu)成了托梅克連接。噪聲點(diǎn)、分界點(diǎn)有較大可能存在托梅克連接點(diǎn)。通過托梅克連接移除有害點(diǎn)的算法如下KNN的訓(xùn)練集可能會有大量的冗余點(diǎn)（刪除這些點(diǎn)不影響KNN分類的性能），而這些冗余點(diǎn)的存在使得K近鄰點(diǎn)的搜索運(yùn)算量大大增加。4.3K近鄰——算法實(shí)現(xiàn)

各種改進(jìn)型的KNN算法層出不窮，對于KNN的改進(jìn)主要包括：（1）對三要素的升級，包括K值選擇算法、距離度量算法、分類決策算法的改進(jìn)；（2）對訓(xùn)練樣本集的優(yōu)化處理，包括樣本屬性的預(yù)處理、有害樣本點(diǎn)和多余樣本點(diǎn)的預(yù)處理等。4.3K近鄰——應(yīng)用案例例：對用戶手寫的數(shù)字進(jìn)行識別。例如下圖中，計(jì)算機(jī)采集到用戶手寫的圖片，能夠?qū)⑵渥R別為數(shù)字“8”。

問題分析根據(jù)前面對K近鄰分類算法的介紹，使用K近鄰分類進(jìn)行手寫體數(shù)字識別的本質(zhì)是將用戶手寫的數(shù)字在0-9這十個(gè)類別上進(jìn)行分類。而訓(xùn)練樣本集是很多已經(jīng)處理好的手寫數(shù)字向量，每個(gè)向量的數(shù)字類別是已知的，待識別的手寫數(shù)字就是待分類的向量，將此向量放到訓(xùn)練集中尋找與之最近的K個(gè)點(diǎn)，最后根據(jù)制定好的決策規(guī)則來對待識別向量進(jìn)行分類。4.3K近鄰——應(yīng)用案例訓(xùn)練集中圖像的預(yù)處理包括大小統(tǒng)一、二值化處理、平滑去噪等。最終目標(biāo)是將每一張已知數(shù)字的手寫體照片轉(zhuǎn)變成形狀相等的布爾向量，將這些向量存為訓(xùn)練集。待識別的圖像需要經(jīng)過類似處理，成為與訓(xùn)練集中等長的布爾向量后才能進(jìn)行K近鄰法識別。訓(xùn)練集構(gòu)建要構(gòu)建訓(xùn)練集。從0-9十個(gè)阿拉伯?dāng)?shù)字，每個(gè)數(shù)字采集若干（200張左右）照片，然后將每張圖片都進(jìn)行圖像縮放、二值化、去噪處理。簡單起見，可將二值化后的向量存為文本文件，文本命名為“數(shù)字_編號”的樣式，如4.3K近鄰——應(yīng)用案例K近鄰識別測試機(jī)器學(xué)習(xí)算法的測試需要注意的內(nèi)容主要包括：屬性測試、測試組件、測試流程、應(yīng)用場景等幾個(gè)方面。屬性測試包括機(jī)器學(xué)習(xí)算法的正確性、健壯性、公平性等；測試組件包括測試過程中需要用到的數(shù)據(jù)、學(xué)習(xí)程序、框架等；測試流程則包括測試結(jié)果生成、測試評估等工作；應(yīng)用場景則是機(jī)器學(xué)習(xí)算法在自動駕駛、機(jī)器翻譯、OCR識別等具體應(yīng)用場景中的測試。本案例僅對算法正確性進(jìn)行測試，測試數(shù)據(jù)集的構(gòu)建和訓(xùn)練集類似，測試集中的每一張手寫數(shù)字圖片向量都要與訓(xùn)練集中的所有向量計(jì)算距離，然后找出K（取K=3或5一類的奇數(shù)值）個(gè)最近的向量點(diǎn)，然后進(jìn)行投票決定測試向量的數(shù)字。目錄/Contents4.14.2分類與聚類的區(qū)別距離度量問題4.3K近鄰4.4K均值聚類4.4K均值“k-均值”聚類算法目的是把n個(gè)未標(biāo)記類別標(biāo)簽的點(diǎn)（可以是樣本的一次觀察或一個(gè)實(shí)例）劃分到K個(gè)聚類中，使得每個(gè)點(diǎn)都屬于離他最近的均值（此即聚類中心）對應(yīng)的聚類，以之作為聚類的標(biāo)準(zhǔn)，是一種無監(jiān)督學(xué)習(xí)算法。由此可以看出，K均值和K近鄰是兩種不同的機(jī)器學(xué)習(xí)算法。例

：快遞員設(shè)置自助取貨點(diǎn)問題。假設(shè)有個(gè)快遞員負(fù)責(zé)幾個(gè)挨著的農(nóng)村（共1000戶）的送貨任務(wù)，快遞員要設(shè)置4個(gè)自助取貨點(diǎn)，請問如何較好設(shè)置取貨點(diǎn)位置盡量照顧到所有的村民呢？4.4K均值一開始快遞員隨意選4個(gè)取貨點(diǎn)，并且把這4個(gè)點(diǎn)的位置公告給了所有的村民，于是每個(gè)村民到離自己家最近的取貨點(diǎn)取貨。一些村民覺得距離太遠(yuǎn)經(jīng)常投訴，于是快遞員統(tǒng)計(jì)到各取貨點(diǎn)取貨的村民的地址，然后將取貨點(diǎn)位置搬到對應(yīng)的村民地址的中心位置，并且再公告給所有村民。快遞點(diǎn)的位置更新后，所有村民重新選擇離自己最近的快遞點(diǎn)。然后，又有村民投訴快遞點(diǎn)較遠(yuǎn)，快遞點(diǎn)重新更新位置。就這樣，快遞點(diǎn)每更新一次自己的位置，村民根據(jù)自己的情況重新選擇快遞點(diǎn)，直到最終穩(wěn)定下來。4.4K均值——算法描述

子集的均值向量μi又被稱為質(zhì)心，每次迭代都需要重新計(jì)算質(zhì)心的位置。因此，對于K均值聚類算法只需要找到K個(gè)合適的質(zhì)心就可以將n個(gè)點(diǎn)分成K個(gè)滿足條件的類。下圖展示了將一個(gè)未知類標(biāo)簽的集合如何通過不停優(yōu)化兩個(gè)質(zhì)心的位置分成2個(gè)類的過程（K=2），由圖中看出K均值式是一種啟發(fā)式的迭代方法。

4.4K均值——算法描述K均值聚類算法，首先要注意的是K值的選擇，一般根據(jù)對數(shù)據(jù)的先驗(yàn)經(jīng)驗(yàn)選擇一個(gè)合適的k值，如果沒有什么先驗(yàn)知識，則可以通過交叉驗(yàn)證選擇一個(gè)合適的k值。在確定了分類個(gè)數(shù)K后，需要選擇K個(gè)初始化的質(zhì)心，可以采用隨機(jī)質(zhì)心。因?yàn)槭菃l(fā)式算法，K個(gè)初始化的質(zhì)心的位置選擇對最后的聚類結(jié)果和運(yùn)行時(shí)間都影響，這些質(zhì)心不應(yīng)太近。更一般地，K均值聚類算法描述如下：4.4K均值——算法描述K均值進(jìn)行集群聚類時(shí)做了一些假設(shè)：（1）數(shù)據(jù)集由K個(gè)聚類組成；（2）數(shù)據(jù)集是一個(gè)凸數(shù)據(jù)集，即聚類結(jié)果內(nèi)任意兩點(diǎn)的連線上所有點(diǎn)都在數(shù)據(jù)集內(nèi)，否則聚類效果差；（3）每個(gè)聚類中的元素個(gè)數(shù)幾乎一樣。錯(cuò)誤的聚類4.4K均值——算法描述傳統(tǒng)K-Means是個(gè)簡單實(shí)用的聚類算法，具有以下優(yōu)點(diǎn)：（1）原理比較簡單、實(shí)現(xiàn)容易；（2）收斂速度快；（3）算法的可解釋度比較強(qiáng)。同時(shí)，它也有幾個(gè)比較明顯的缺點(diǎn)：（1）K值不好選取；（2）采用迭代方法得到的結(jié)果容易陷入局部最優(yōu)；（3）對噪音和異常點(diǎn)比較的敏感；（4）無法完成對非凸數(shù)據(jù)集的聚類。4.4K均值——算法優(yōu)化K-Means++初始質(zhì)心的選取對K均值聚類結(jié)果影響較大，K-Means++的主要改進(jìn)就在初始質(zhì)心的合理選擇，其它步驟和經(jīng)典K-Means算法相同。K-Means++能顯著改善分類結(jié)果的最終誤差。盡管計(jì)算初始點(diǎn)時(shí)花費(fèi)了額外的時(shí)間，但在迭代過程中，由于初始中心選取更合理使得算法本身能快速收斂，因此算法實(shí)際上降低了計(jì)算時(shí)間。4.4K均值——算法優(yōu)化ISODATA經(jīng)典K-Means算法和K-Means++算法的K值是固定不變的，而ISODATA算法可以根據(jù)分類情況自動調(diào)整K值的大小。ISODATA算法通過分裂操作增加K值、通過合并操作來減少K值，以此調(diào)整K值的大小。

4.4K均值——算法優(yōu)化ISODATA

4.4K均值——應(yīng)用案例例：通過地理位置對城市群進(jìn)行聚類。城市群是工業(yè)化、城市化進(jìn)程中，區(qū)域空間形態(tài)的高級現(xiàn)象，能夠產(chǎn)生巨大的集聚經(jīng)濟(jì)效益，是國民經(jīng)濟(jì)快速發(fā)展、現(xiàn)代化水平不斷提高的標(biāo)志之一。城市群是在特定的區(qū)域范圍內(nèi)云集形成，以一個(gè)或兩個(gè)特大城市為中心，依托一定的自然環(huán)境和交通條件，城市之間的內(nèi)在聯(lián)系不斷加強(qiáng)，共同構(gòu)成的一個(gè)相對完整的城市“集合體”。4.4K均值——應(yīng)用案例解題思路本例為使問題簡化，只研究省會城市，并以經(jīng)緯度為城市坐標(biāo)，另外僅將所有城市聚成2個(gè)類。城市名經(jīng)度緯度城市名經(jīng)度緯度北京E116°28′N39°54′上海E121°29′N31°14′天津E117°11′N39°09′重慶E106°32′N29°32′哈爾濱E126°41′N45°45′長春E125°19′N43°52′沈陽E123°24′N41°50′呼和浩特E111°48′N40°49′石家莊E114°28′N38°02′太原E112°34′N37°52′濟(jì)南E117°N36°38′鄭州E113°42′N34°48′西安E108°54′N34°