機(jī)器學(xué)習(xí)（MATLAB版）-習(xí)題及答案 ch05

第五章K近鄰算法K近鄰算法的定義及流程定義：K近鄰算法是一種常用的監(jiān)督學(xué)習(xí)方法，它的基本思想是：要確定一個(gè)樣本的類別，可以計(jì)算它與所有訓(xùn)練樣本的某種距離（例如歐氏距離），然后找出與該樣本最接近的K個(gè)樣本，統(tǒng)計(jì)這些樣本的類別并進(jìn)行“投票”，得票最多的那個(gè)類就是分類結(jié)果。流程：當(dāng)先=1時(shí)，k近鄰算法退化為最近鄰算法。更通俗地說，先近鄰算法是按照一定規(guī)則將相似的樣本數(shù)據(jù)進(jìn)行歸類的，類似于現(xiàn)實(shí)生活中的“物以類聚，人以群分”。首先，計(jì)算待分類數(shù)據(jù)特征與訓(xùn)練數(shù)據(jù)特征之間的距離并排序，取出距離最近的k個(gè)訓(xùn)練數(shù)據(jù)特征；然后，根據(jù)這個(gè)相近訓(xùn)練數(shù)據(jù)特征所屬的類別來判定新樣本的類別：如果它們都屬于同一類，那么新樣本也屬于這一類；否則，對(duì)每個(gè)候選類別進(jìn)行評(píng)分，按照某種規(guī)則確定新樣本的類別。一般釆用投票規(guī)則，即少數(shù)服從多數(shù)，期望的先值是一個(gè)奇數(shù)。精確的投票方法是計(jì)算每一個(gè)測(cè)試樣本與k個(gè)樣本之間的距離。容易發(fā)現(xiàn)，k近鄰算法實(shí)現(xiàn)十分簡(jiǎn)單，只需計(jì)算待測(cè)樣本與每一個(gè)訓(xùn)練樣本的距離即可，這是它的優(yōu)點(diǎn)；其缺點(diǎn)是當(dāng)訓(xùn)練樣本容量大、特征向量維數(shù)高時(shí)，計(jì)算復(fù)雜度將變得十分可觀。因?yàn)槊看晤A(yù)測(cè)時(shí)都要計(jì)算待測(cè)樣本與每一個(gè)訓(xùn)練樣本的距離，而且需要對(duì)距離進(jìn)行排序找到最近的k個(gè)樣本。此外，一個(gè)不容忽視的問題是參數(shù)k的取值，除了必須是一個(gè)奇數(shù)外，還需要根據(jù)問題和數(shù)據(jù)的特點(diǎn)來確定。在算法實(shí)現(xiàn)時(shí)還可以考慮樣本的權(quán)重，即每個(gè)樣本有不同的投票權(quán)重，這種方法稱為加權(quán)為近鄰算法。另外，化近鄰算法也可以用于回歸問題。在得到待處理數(shù)據(jù)的必個(gè)最相似訓(xùn)練數(shù)據(jù)后,求取這些訓(xùn)練數(shù)據(jù)特征的平均值，并將該平均值作為待處理數(shù)據(jù)的特征值。也就是說，假設(shè)距離待測(cè)試樣本最近的k個(gè)訓(xùn)練樣本的標(biāo)簽值為饑，則對(duì)該樣本的回歸預(yù)測(cè)值為：K近鄰算法的距離函數(shù)都有哪些在樣本數(shù)有限的情況下，&近鄰算法的誤判概率和距離的具體測(cè)度有直接關(guān)系。因此,在選擇近鄰樣本數(shù)時(shí)利用適當(dāng)?shù)木嚯x函數(shù)能夠提高分類的正確率。通常，北近鄰算法可釆用歐氏距離(EuclideanDistance)、曼氏距離(ManhattanDistance)、馬氏距離(Mahalan-obisDistance)等距離函數(shù)。1.歐氏距離(EuclideanDistance)：2.曼氏距離(ManhattanDistance又叫街區(qū)距離)：3.馬氏距離(MahalanobisDistance)：歐氏距離，曼氏距離，馬氏距離的區(qū)別歐氏距離是最常用也是我們最熟知的距離。但在使用歐氏距離時(shí)，要注意將特征向量的分量歸一化，以減少因特征值的尺度范圍差異所帶來的干擾，否則數(shù)值小的特征分量會(huì)被數(shù)值大的特征分量所淹沒。也就是說，歐氏距離只是將特征向量看作空間中的點(diǎn)，并未考慮這些樣本特征向量的概率分布規(guī)律。與歐氏距離不同，馬氏距離則是一種概率意義上的距離，它與數(shù)據(jù)的尺度無關(guān)。馬氏距離更為一般的定義是：其中，S是對(duì)稱正定矩陣。這種距離度量的是兩個(gè)隨機(jī)向量的相似度。顯然，當(dāng)S為單位陣時(shí)，馬氏距離即退化為歐氏距離。矩陣S可以通過計(jì)算訓(xùn)練樣本的協(xié)方差矩陣得到，也可以通過對(duì)樣本的“距離度量學(xué)習(xí)”得到。另外還有一種巴氏距離(BhattacharyyaDistance),它定義了兩個(gè)離散型或連續(xù)型隨機(jī)向量概率分布的相似性。對(duì)于在同一域X的兩個(gè)離散型分布p(x)，q(x),其定義為：對(duì)于連續(xù)型分布，其定義為：顯然，兩個(gè)隨機(jī)向量越相似，這個(gè)距離值越小。注意,巴氏距離不滿足三角不等式。k近鄰算法的判別函數(shù)和判別準(zhǔn)則（1）初始化距離值為最大值，便于在搜索過程中迭代掉。（2）計(jì)算待分類樣本和每個(gè)訓(xùn)練樣本的距離disto（3）得到目前k個(gè)最近鄰樣本中的最大距離maxdisto（4）如果dist小于maxdist,則將該訓(xùn)練樣本作為k近鄰樣本。（5）重復(fù)步驟（2）、（3）、（4）,直到未知樣本和所有訓(xùn)練樣本的距離都計(jì)算完。（6）統(tǒng)計(jì)存近鄰樣本中每個(gè)類標(biāo)號(hào)出現(xiàn)的次數(shù)。（7）選擇出現(xiàn)頻率最高的類標(biāo)號(hào)作為未知樣本的類標(biāo)號(hào)。簡(jiǎn)述類的屬性（1）W與Y的長(zhǎng)度相同的非負(fù)數(shù)值向量，用于表示對(duì)應(yīng)樣本觀測(cè)值的權(quán)值。（2）Sigma數(shù)值向量，長(zhǎng)度等于特征變量的個(gè)數(shù)，表示對(duì)應(yīng)特征變量做歸一化時(shí)的標(biāo)準(zhǔn)差。（3）PredictorNames特征變量的變量名。（4）ResponseName標(biāo)簽變量的變量名。（5）ClassNames標(biāo)簽的種類，存放每種標(biāo)簽的名字。（6）Prior數(shù)值向量。每一類標(biāo)簽的先驗(yàn)概率，也就是每種類別在X中的占比。向量中的元素對(duì)應(yīng)ClassNames中的元素。（7）NumNeighbors正數(shù)，表示k近鄰的個(gè)數(shù)。（8）NumObservations用于訓(xùn)練分類器的樣本數(shù)，小于或者等于X的行數(shù)，因?yàn)槿绻鸛中存在NaN,這些數(shù)據(jù)無效，會(huì)導(dǎo)致訓(xùn)練數(shù)據(jù)小于X的行數(shù)?；蛘哒f，即使X中有些數(shù)據(jù)錯(cuò)誤，也不會(huì)導(dǎo)致程序報(bào)錯(cuò)，i玄個(gè)庫(kù)函數(shù)是具有容錯(cuò)性的。（9）Mu數(shù)值向量，長(zhǎng)度等于特征變量的個(gè)數(shù)，表示每個(gè)特征變量的均值，用于歸一化。（10）Distance字符向量或者函數(shù)句柄，表示A;近鄰所選擇的距離標(biāo)準(zhǔn)，比如是歐氏距離還是其他距離等，可用helpfitcknn查看。選擇不同的距離標(biāo)準(zhǔn)還受到搜索方法的限制，搜索方法由NsMethod參數(shù)決定。（11）ModelParameters訓(xùn)練分類器用到的參數(shù)。NsMethod就在其中。NsMethod參數(shù)有"exhaustive"和“kdtree”兩種，分別是窮舉搜索和基于樹的搜索。（12）DistanceWeight字符向量或者函數(shù)句柄，可選參數(shù)有'equal11inverse5'squareinverses分別表示無權(quán)重、與距離的一次方成反比、與距離的二次方成反比。（13）DistParameter距離標(biāo)準(zhǔn)的額外參數(shù)，可選參數(shù)^ahalanobis5'minkowski'七euclidean，，分別表示正定相關(guān)矩陣C、閔可夫斯基距離指數(shù)(一個(gè)正的標(biāo)量)、元素為正的向量且長(zhǎng)度等于X的列數(shù)。（14）ExpandedPredictorNames如果模型使用了編碼以后的特征變量，那么這個(gè)參數(shù)用于