第6章分類預(yù)測6.3k-近鄰分類K-近鄰分類K-近鄰（K-NearestNeighbor，KNN）分類算法，最初是由Cover和Hart于1968年提出，是一個理論上比較成熟的方法。算法原理簡單直觀：未知樣本的類別，由特征空間中K個最相似（即特征空間中最鄰近）的樣本的大多數(shù)類別來確定。是一種基于實例的懶惰學(xué)習(xí)方法。K-近鄰分類K-近鄰分類算法的處理過程為：對于待預(yù)測的未分類樣本，計算其與數(shù)據(jù)集中每個樣本之間的相似度；篩選出最近鄰的K個數(shù)據(jù)樣本；根據(jù)K個最近鄰數(shù)據(jù)樣本的類別，采用多數(shù)投票機(jī)制確定待預(yù)測樣本的類別。K-近鄰分類這里有幾個問題需要詳細(xì)討論：以何種指標(biāo)來衡量數(shù)據(jù)樣本之間的相似度；K值如何確定；采用多數(shù)投票機(jī)制判定樣本類別時如何設(shè)計具體算法。相似度度量1.距離(1)歐幾里得距離（EuclideanDistance）(2)曼哈頓距離（ManhattanDistance）(3)明可夫斯基距離（MinkowskiDistance）(4)馬氏距離（Mahalanobisdistance）(5)漢明距離（HammingDistance）2.相似系數(shù)(1)余弦相似度(2)相關(guān)系數(shù)(3)Jaccard相似系數(shù)(JaccardSimilarityCoefficient)“距離”度量定義距離函數(shù)，基于屬性值進(jìn)行計算非負(fù)性對于任意x，y，兩者之間的距離d(x，y)≥0，當(dāng)x

=y時，等號成立。對稱性對于任意x，y，兩者之間的距離d(x，y)=d(y，x)，即距離是標(biāo)量而不是向量。三角不等式對于任意x，y，z，有d(x，y)

≤d(x，z)+d(z，y)。即對象x到對象y的距離小于等于途經(jīng)其他任何對象z的距離之和。也稱為相似性“距離”度量歐幾里得距離EuclideanDistance對于n維數(shù)據(jù)

X={x1，x2，…，xn}，Y={y1，y2，…，yn}，其歐幾里得距離為在二維空間中的歐幾里得距離就是平面中兩點之間的實際距離。在三維空間中的歐幾里得距離就是立體（三維）空間中兩點之間的實際距離?！熬嚯x”度量曼哈頓距離對于n維數(shù)據(jù)

X={x1，x2，…，xn}，Y={y1，y2，…，yn}，其曼哈頓距離為(6,6)(2,2)歐幾里得距離=5.66曼哈頓距離=(6-2)+(6-2)=844xy“距離”度量明可夫斯基距離MinkowskiDistance對于n維數(shù)據(jù)

X={x1，x2，…，xn}，Y={y1，y2，…，yn}，其明可夫斯基距離為相似系數(shù)余弦相似度對于n維數(shù)據(jù)

X={x1，x2，…，xn}，Y={y1，y2，…，yn}，即對于x，y兩個向量，有：cos(x,y)=(x?y)/‖x‖?‖y‖

余弦相似度【例如】分析以下兩個句子的相似性：

句子A：我喜歡看電視，不喜歡看電影。句子B：我不喜歡看電視，也不喜歡看電影。1)可以將兩個句子進(jìn)行分詞：句子A：我/喜歡/看電視/不/喜歡/看/電影句子B：我/不/喜歡/看/電視/也/不/喜歡/看/電影2)對所出現(xiàn)的各個詞匯（我

喜歡

看

電視

電影

不

也），計算其詞頻：句子A：我1，喜歡2，看2，電視1，電影1，不1，也0句子B：我1，喜歡2，看2，電視1，電影1，不2，也1余弦相似度【例如】分析以下兩個句子的相似性：

句子A：我喜歡看電視，不喜歡看電影。句子B：我不喜歡看電視，也不喜歡看電影。3)將詞頻轉(zhuǎn)換為向量：句子A：x=(1221110)句子B：y=(1221121)4)計算其余弦相似度，有：余弦相似度由此，我們就得到了“找出相似文章”的一種算法：使用TF-IDF算法，找出兩篇文章的關(guān)鍵詞；每篇文章各取出若干個關(guān)鍵詞（比如20個），合并成一個集合，計算每篇文章對于這個集合中的詞的詞頻（為了避免文章長度的差異，可以使用相對詞頻）；生成兩篇文章各自的詞頻向量；計算兩個向量的余弦相似度，值越大就表示越相似。相似系數(shù)余弦相似度相關(guān)系數(shù)反映變量之間相關(guān)關(guān)系密切程度的統(tǒng)計指標(biāo)相關(guān)系數(shù)按積差的方法計算，以兩變量與各自平均值的離差為基礎(chǔ)，通過兩個離差相乘來反映兩變量之間相關(guān)程度。x與y之間的協(xié)方差x,y的均方差相似系數(shù)余弦相似度相關(guān)系數(shù)Jaccard相似系數(shù)(JaccardSimilarityCoefficient)用于比較有限樣本集之間的相似性與差異性A、B的相似性：Jaccard距離：余弦相似度TF-IDF算法TF-IDF通過統(tǒng)計方法，對字詞對于語料庫中的一份文件或文件集的重要程度進(jìn)行評估。字詞的重要性隨其在文件中出現(xiàn)的次數(shù)正比增加，隨其在語料庫中出現(xiàn)的頻率成反比下降，即如果某字在一篇文章中出現(xiàn)的頻率TF高，而在其他文章中很少出現(xiàn)，則認(rèn)為該字詞具有很好的類別區(qū)分能力，適合用于分類。這里TF為詞頻(TermFrequency)，表示詞條在文檔d中出現(xiàn)的頻率；IDF為逆向文件頻率(InverseDocumentFrequency)，表示包含詞條的文檔的數(shù)量，值越大，表明詞條具有很好的類別區(qū)分能力。TF-IDF加權(quán)的各種形式常被搜索引擎應(yīng)用，作為文件與用戶查詢之間相關(guān)程度的度量或評級。除了TF-IDF以外，因特網(wǎng)上的搜索引擎還會使用基于鏈接分析的評級方法，以確定文件在搜尋結(jié)果中出現(xiàn)的順序。K-近鄰分類這里有幾個問題需要詳細(xì)討論：以何種指標(biāo)來衡量數(shù)據(jù)樣本之間的相似度；K值如何確定；采用多數(shù)投票機(jī)制判定樣本類別時如何設(shè)計具體算法。K值如何確定K值是K-近鄰算法的一個超參數(shù)，表示選擇多少個最近鄰的樣本來進(jìn)行預(yù)測。K值的選擇對算法的性能有很大影響，需要根據(jù)具體的應(yīng)用問題和數(shù)據(jù)的特征進(jìn)行設(shè)置和調(diào)整。K值如何確定K值如何確定當(dāng)K值設(shè)置偏小時算法會更多地關(guān)注局部的細(xì)節(jié)，精確度較高，同時對訓(xùn)練數(shù)據(jù)中的噪聲和異常值較為敏感，增加了過擬合風(fēng)險，泛化性降低，導(dǎo)致分類結(jié)果不穩(wěn)定。當(dāng)K值設(shè)置偏大時算法更多地關(guān)注整體的趨勢，對局部噪聲和異常值的敏感度降低，但可能使模型過于平滑，忽略了數(shù)據(jù)中的某些重要細(xì)節(jié)，導(dǎo)致分類結(jié)果過于籠統(tǒng)。K值的增加通常意味著計算復(fù)雜度的提高。在實際應(yīng)用中通過交叉驗證等方法來選擇合適的K值除了K值外，還可以考慮調(diào)整其他參數(shù)（如相似度度量方式、特征權(quán)重等）來進(jìn)一步優(yōu)化算法的性能。K-近鄰分類這里有幾個問題需要詳細(xì)討論：以何種指標(biāo)來衡量數(shù)據(jù)樣本之間的相似度；K值如何確定；采用多數(shù)投票機(jī)制判定樣本類別時如何設(shè)計具體算法。多數(shù)投票機(jī)制判定方法：以出現(xiàn)次數(shù)最多的樣本類別以樣本類別的平均值必要時可對類別屬性進(jìn)行編碼以鄰樣本類別加權(quán)平均值權(quán)重可以選近鄰樣本距離的倒數(shù)或與最大值的差變化：以近鄰半徑判定變化：K-近鄰回歸計算待預(yù)測樣本與K個最近鄰樣本的距離，取平均值作為預(yù)測結(jié)果數(shù)據(jù)點0數(shù)據(jù)點1變化：K-近鄰回歸計算待預(yù)測樣本與Radius半徑內(nèi)的樣本的距離，取平均值作為預(yù)測結(jié)果數(shù)據(jù)點0數(shù)據(jù)點1算法特點K-近鄰方法算法原理簡單，易于理解和實現(xiàn)算法基于實例進(jìn)行分類判別，直接利用數(shù)據(jù)集進(jìn)行預(yù)測沒有顯式的訓(xùn)練過程，能夠較為輕松地處理多分類問題算法從原理上依賴于極限定理，但在類別判別時，只與少量的相鄰樣本有關(guān)，因此可以較好地處理非線性數(shù)據(jù)，也能夠避免樣本的不平衡問題對于