數(shù)據(jù)挖掘 C4：近鄰分類

2023/5/51第4講近鄰分類2023/5/52基于實(shí)例的學(xué)習(xí)概述已知一系列的訓(xùn)練樣例，許多學(xué)習(xí)方法為目標(biāo)函數(shù)建立起明確的一般化描述。基于實(shí)例的學(xué)習(xí)方法只是簡單地把訓(xùn)練樣例存儲(chǔ)起來，從這些實(shí)例中泛化的工作被推遲到必須分類新實(shí)例的時(shí)候。每當(dāng)學(xué)習(xí)器遇到一個(gè)新的查詢實(shí)例，它分析這個(gè)新實(shí)例與以前存儲(chǔ)的實(shí)例的關(guān)系，并據(jù)此把一個(gè)目標(biāo)函數(shù)值賦給新實(shí)例。2023/5/53基于實(shí)例的學(xué)習(xí)概述基于實(shí)例的學(xué)習(xí)方法包括：假定實(shí)例可以表示成歐氏空間中的點(diǎn)最近鄰法局部加權(quán)回歸法對實(shí)例采用更復(fù)雜的符號(hào)表示基于案例的推理2023/5/54基于實(shí)例的學(xué)習(xí)概述基于實(shí)例的學(xué)習(xí)方法有時(shí)被稱為消極學(xué)習(xí)法，它把處理工作延遲到必須分類新的實(shí)例時(shí)。這種延遲的學(xué)習(xí)方法有一個(gè)優(yōu)點(diǎn)：不是在整個(gè)實(shí)例空間上一次性地估計(jì)目標(biāo)函數(shù)，而是針對每個(gè)待分類新實(shí)例作出局部的和相異的估計(jì)。2023/5/55基于實(shí)例的學(xué)習(xí)概述基于實(shí)例的學(xué)習(xí)方法的學(xué)習(xí)過程只是簡單地存儲(chǔ)已知的訓(xùn)練數(shù)據(jù)，當(dāng)遇到新的查詢實(shí)例時(shí)，一系列相似的實(shí)例從存儲(chǔ)器中取出，用來分類新的查詢實(shí)例。與其他方法相比，基于實(shí)例的學(xué)習(xí)方法的一個(gè)關(guān)鍵差異是：可以為不同的待分類查詢實(shí)例建立不同的目標(biāo)函數(shù)逼近。2023/5/56基于實(shí)例的學(xué)習(xí)概述許多技術(shù)不建立目標(biāo)函數(shù)在整個(gè)實(shí)例空間上的逼近，只建立局部逼近，并將其用于與新實(shí)例鄰近的實(shí)例。這樣做的好處是：有時(shí)目標(biāo)函數(shù)很復(fù)雜，但具有不太復(fù)雜的局部逼近描述。2023/5/57基于實(shí)例的學(xué)習(xí)概述基于實(shí)例的方法的不足：分類新實(shí)例的開銷可能很大。幾乎所有的計(jì)算都發(fā)生在分類時(shí)，而不是在第一次遇到訓(xùn)練樣例時(shí)。如何有效地索引訓(xùn)練樣例是一個(gè)重要的問題。當(dāng)從存儲(chǔ)器中檢索相似的訓(xùn)練樣例時(shí)，一般考慮實(shí)例的所有屬性，如果目標(biāo)概念僅依賴于很多屬性中的幾個(gè)，那么真正最“相似”的實(shí)例之間可能相距甚遠(yuǎn)。2023/5/58基于實(shí)例的學(xué)習(xí)概述K-近鄰算法和它的幾個(gè)變體。局部加權(quán)回歸法，這是一種建立目標(biāo)函數(shù)的局部逼近的學(xué)習(xí)方法，被看作k-近鄰算法的一般形式。基于案例的推理，是一種使用符號(hào)表示和基于知識(shí)的推理的方法。徑向基函數(shù)網(wǎng)絡(luò)，為基于實(shí)例的學(xué)習(xí)算法和神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法提供了一個(gè)有趣的橋梁。消極學(xué)習(xí)方法和積極學(xué)習(xí)方法之間的差異。2023/5/59K-近鄰學(xué)習(xí)概述不同于eager學(xué)習(xí)算法，K-近鄰方法在訓(xùn)練階段只是簡單地把訓(xùn)練樣例存儲(chǔ)起來，把建模過程推遲到了要預(yù)測新實(shí)例的工作階段。因此，K-近鄰方法是一種典型的lazy學(xué)習(xí)算法。k-近鄰方法既可以用于目標(biāo)函數(shù)值是離散的情況，也可以用于是連續(xù)的情況。離散的情況就是分類，連續(xù)的情況就是回歸。K-近鄰方法的學(xué)習(xí)過程分兩部：1）找到要預(yù)測新實(shí)例的K個(gè)鄰居；2）根據(jù)這K個(gè)鄰居來預(yù)測新實(shí)例的目標(biāo)值。2023/5/510k-近鄰算法k-近鄰算法假定所有的實(shí)例對應(yīng)于n維空間Rn中的點(diǎn)，任意的實(shí)例表示為一個(gè)特征向量<a1(x),...,an(x)>根據(jù)歐氏距離定義實(shí)例間的距離。兩個(gè)實(shí)例xi和xj的距離d(xi,xj)定義為2023/5/511偽代碼（離散）考慮離散目標(biāo)函數(shù)f:RnV，V={v1,...,vs}逼近離散值函數(shù)f:RnV的k-近鄰算法訓(xùn)練算法將每個(gè)訓(xùn)練樣例<x,f(x)>加入到列表training_examples分類算法給定一個(gè)要分類的查詢實(shí)例xq在training_examples中選出最靠近xq的k個(gè)實(shí)例，并用x1...xk表示返回其中2023/5/512偽代碼（連續(xù)）逼近連續(xù)值目標(biāo)函數(shù)f:RnR的k-近鄰算法訓(xùn)練算法將每個(gè)訓(xùn)練樣例<x,f(x)>加入到列表training_examples分類算法給定一個(gè)要分類的查詢實(shí)例xq在training_examples中選出最靠近xq的k個(gè)實(shí)例，并用x1...xk表示返回2023/5/513距離加權(quán)的k-近鄰算法（離散）對k-近鄰算法的一個(gè)改進(jìn)是對k個(gè)近鄰的貢獻(xiàn)加權(quán)，越近的距離賦予越大的權(quán)值，比如：其中為了處理查詢點(diǎn)xq恰好匹配某個(gè)訓(xùn)練樣例xi，從而導(dǎo)致d(xq,xi)2為0的情況，令這種情況下的等于f(xi)，如果有多個(gè)這樣的訓(xùn)練樣例，我們使用它們占多數(shù)的分類。2023/5/514距離加權(quán)的k-近鄰算法（連續(xù)）對k-近鄰算法的一個(gè)改進(jìn)是對k個(gè)近鄰的貢獻(xiàn)加權(quán)，越近的距離賦予越大的權(quán)值，比如：其中

為了處理查詢點(diǎn)xq恰好匹配某個(gè)訓(xùn)練樣例xi，從而導(dǎo)致d(xq,xi)2為0的情況，令這種情況下的等于f(xi)，如果有多個(gè)這樣的訓(xùn)練樣例，則用它們的平均值來預(yù)測。2023/5/515對k-近鄰算法的的說明k-近鄰算法的所有變體都只考慮k個(gè)近鄰用以預(yù)測查詢點(diǎn)，如果使用按距離加權(quán)，那么可以允許所有的訓(xùn)練樣例影響對xq的預(yù)測，因?yàn)榉浅＿h(yuǎn)的實(shí)例的影響很小。唯一不足之處：使得預(yù)測的速度變得更慢。如果預(yù)測一個(gè)新實(shí)例時(shí)，考慮所有的訓(xùn)練樣例，我們稱為全局法；如果僅考慮靠近的訓(xùn)練樣例，稱為局部法。2023/5/516k-近鄰算法的優(yōu)點(diǎn)K-近鄰算法不是在整個(gè)實(shí)例空間上一次性地預(yù)測目標(biāo)函數(shù)值，而是針對每個(gè)待預(yù)測的新實(shí)例，建立不同的目標(biāo)函數(shù)逼近，作出局部的和相異的預(yù)測。這樣做的好處是：有時(shí)目標(biāo)函數(shù)很復(fù)雜，但具有不太復(fù)雜的局部逼近。距離加權(quán)的k-近鄰算法對訓(xùn)練數(shù)據(jù)中的噪聲有很好的健壯性，通過取k個(gè)近鄰的加權(quán)平均，可以消除孤立的噪聲樣例的影響。2023/5/517k-近鄰算法的不足K-近鄰方法的不足之處體現(xiàn)在：應(yīng)用K-近鄰算法來進(jìn)行預(yù)測的時(shí)候，經(jīng)常會(huì)遇到很多現(xiàn)實(shí)問題。這些問題包括：維度災(zāi)害問題、近鄰索引問題、近鄰大小問題、計(jì)算效率問題、歸納偏置問題。2023/5/518維度災(zāi)害問題k-近鄰算法的一個(gè)實(shí)踐問題：維度災(zāi)害許多學(xué)習(xí)方法，比如決策樹方法，選擇部分屬性作出判斷，而k-近鄰方法中實(shí)例間的距離是根據(jù)實(shí)例的所有屬性計(jì)算的。實(shí)例間距離會(huì)被大量的不相關(guān)屬性所支配，可能導(dǎo)致相關(guān)屬性的值很接近的實(shí)例相距很遠(yuǎn)。解決維度災(zāi)害問題的常用方法：1）屬性加權(quán)；2）屬性選擇。2023/5/519近鄰索引問題k-近鄰算法的所有計(jì)算幾乎都花費(fèi)在索引近鄰問題上。因此，如何建立高效的索引是k-近鄰算法的另外一個(gè)實(shí)踐問題。目前，已經(jīng)開發(fā)了很多對存儲(chǔ)的訓(xùn)練樣例進(jìn)行索引的方法，以便能高效地確定最近鄰。如kd-tree把實(shí)例存儲(chǔ)在樹的葉結(jié)點(diǎn)內(nèi)，鄰近的實(shí)例存儲(chǔ)在同一個(gè)或附近的節(jié)點(diǎn)內(nèi)，通過測試新查詢xq的選定屬性，樹的內(nèi)部節(jié)點(diǎn)把查詢xq排列到相關(guān)的葉結(jié)點(diǎn)。2023/5/520近鄰大小問題k-近鄰算法的預(yù)測結(jié)果與