如何計算K近鄰中稀疏數據集時的距離

我正在爲非常稀疏的數據實現K最近鄰居算法。我想計算測試實例和訓練集中每個樣本之間的距離，但我很困惑。如何計算K近鄰中稀疏數據集時的距離

因爲大部分的訓練樣本的特徵不測試實例或反之亦然存在（缺少的功能）。

我如何計算在這種情況下的距離？

2011-09-19 Ahmed

爲了確保我正確認識這個問題：每個樣本形成一個非常稀疏填補載體。缺失的數據在樣本之間是不同的，因此很難使用任何歐幾里得或其他距離度量來衡量樣本的相似性。

如果是這樣的情況，我已經看到這個問題之前顯示在機器學習 - 在Netflix的獎大賽，但沒有具體應用到KNN。這種情況非常相似：每個用戶配置文件都有一些電影的評級，但幾乎沒有用戶看過所有17,000部電影。平均用戶配置文件相當稀少。

不同的人有解決問題的方式不同，但我記得的方式是，他們在虛擬值插入的缺失值，在所有樣本數據的特定值通常的平均值。然後他們正常使用歐幾里德距離等。您可能仍然可以在該論壇上找到圍繞這個缺失值問題的討論。對於那些試圖實現奇異值分解的人來說，這是一個特別常見的問題，這個問題變得非常流行，所以如果我沒有記錯的話就會被討論。

你不妨從這裏開始： http://www.netflixprize.com//community/viewtopic.php?id=1283

你將不得不挖了一下。 Simon Funk對此有一點不同的看法，但對SVD更具體。你可以在這裏找到它：http://www.netflixprize.com//community/viewtopic.php?id=1283 如果你想跳到相關章節，他會稱它們爲空格。

祝你好運！

來源

2011-09-19 03:39:39

如果您在非常高維的空間工作。在所有可用數據上使用SVD，LDA，pLSV或類似方法進行空間縮減比較好，然後對這種方式轉換後的訓練數據進行訓練算法。其中一些算法是可擴展的，因此您可以在Mahout項目中找到實現。特別是我更喜歡使用更通用的功能，然後進行這種轉換，因爲它更容易調試和功能選擇。爲了這樣的目的，結合一些特徵，使用詞幹分析者，思考更一般。

來源

2011-09-19 11:52:54 yura

其實，我想實現對數據集隨機投影（約翰遜Lindenstrauss），但每個定義我能找到的是完全沒有意義，我方程。事實上，我想我需要在這裏提出這個問題。 – Ahmed

這裏：http://stackoverflow.com/questions/7474508/random-projection-algorithm-pseudo-code – Ahmed

艾哈邁德：我不相信複雜的算法方程的很多...我肯定知道LDA和SVD是如何工作的。所以如果我像你的問題一樣，我會使用開源庫來獲得結果（mahout，mallet，dragon toolkit）。 – yura

如何計算K近鄰中稀疏數據集時的距離

回答

相關問題