第6章分類預(yù)測(cè)6.3k-近鄰分類K-近鄰分類K-近鄰（K-NearestNeighbor，KNN）分類算法，最初是由Cover和Hart于1968年提出，是一個(gè)理論上比較成熟的方法。算法原理簡(jiǎn)單直觀：未知樣本的類別，由特征空間中K個(gè)最相似（即特征空間中最鄰近）的樣本的大多數(shù)類別來確定。是一種基于實(shí)例的懶惰學(xué)習(xí)方法。K-近鄰分類K-近鄰分類算法的處理過程為：對(duì)于待預(yù)測(cè)的未分類樣本，計(jì)算其與數(shù)據(jù)集中每個(gè)樣本之間的相似度；篩選出最近鄰的K個(gè)數(shù)據(jù)樣本；根據(jù)K個(gè)最近鄰數(shù)據(jù)樣本的類別，采用多數(shù)投票機(jī)制確定待預(yù)測(cè)樣本的類別。K-近鄰分類這里有幾個(gè)問題需要詳細(xì)討論：以何種指標(biāo)來衡量數(shù)據(jù)樣本之間的相似度；K值如何確定；采用多數(shù)投票機(jī)制判定樣本類別時(shí)如何設(shè)計(jì)具體算法。相似度度量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)行計(jì)算非負(fù)性對(duì)于任意x，y，兩者之間的距離d(x，y)≥0，當(dāng)x

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

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

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

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

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

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

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

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

喜歡

看

電視

電影

不

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

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