我有一組 10,000 個點，每個點由 70 個布爾維度組成。我想從這 10,000 個集合中選擇 100 個點來代表整個 10,000 個集合。換句話說，我想選出彼此最不同的 100 個點。有一些既定的方法可以做到這一點嗎？我首先想到的是貪心算法，它首先隨機選擇一個點，然后選擇下一個點作為距離第一個點最遠的點，然后選擇第二個點作為具有最長平均值的點與前兩個的距離等。這個解決方案不需要完美，只要大致正確即可。最好，這個 100 分的解決方案也可以在大約 10 分鐘內找到，但在 24 小時內完成也可以。我并不關心距離，特別是，這只是我想到的捕捉“差異”的一種方式。如果重要的話，每個點都有 10 個 TRUE 值和 60 個 FALSE 值。一些已經構建的 Python 包來執行此操作將是理想的選擇，但如果有人可以向我指出維基百科文章，我也很樂意自己編寫代碼。
2 回答
墨色風雨
TA貢獻1853條經驗 獲得超6個贊
您使用的“代表性”不是標準術語，但我讀了您的問題，因為您希望找到 100 個項目，涵蓋數據集中各種不同的示例。因此，如果 10000 件商品中的 5000 件幾乎相同，您可能更愿意只看到該大子組中的一兩個商品。根據通常的定義，100 個代表性樣本將包含該組中的約 50 個項目。
可能符合您既定目標的一種方法是識別數據中的不同子集或組，然后從每個組中選取一個示例。
您可以使用聚類算法在數據集中為固定數量的組建立組標識（每個組允許不同的成員資格大?。=100 的k 均值聚類可能是一個不錯的選擇。這將在您的數據中找到 100 個組，并根據簡單的距離指標將所有 10,000 個項目分配給這 100 個組之一。然后，您可以從每組中選取中心點，也可以從每組中隨機抽取樣本來找到 100 組。
k 均值算法基于最小化成本函數，該函數是每個組成員與其組中心的平均距離。團體中心和成員資格都可以改變，交替更新，直到成本不能再降低為止。
通常，您首先將每個項目隨機分配到一個組中。然后計算每組的中心。然后根據最近的中心將項目重新分配到組中。然后重新計算中心等。最終應該收斂?？赡苄枰啻芜\行才能找到一組良好的最佳中心（它可能會陷入局部最優）。
該算法在 Python 中有多種實現。您可以從scikit learn 庫實現開始。
根據IBM 支持頁面（來自sascha的評論），k-means 可能無法很好地處理二進制數據。其他聚類算法可能效果更好。您還可以嘗試將記錄轉換為歐氏距離更有用的空間，并繼續使用 k 均值聚類。可以為您做到這一點的算法是主成分分析 (PCA)，它也在 scikit learn 中實現。
茅侃侃
TA貢獻1842條經驗 獲得超21個贊
圖劃分工具METIS聲稱能夠在幾秒鐘內將具有數百萬個頂點的圖劃分為 256 個部分。
您可以將 10.000 個點視為無向圖的頂點。具有 5000 萬條邊的全連接圖可能太大了。因此，您可以將邊限制為漢明距離低于某個閾值的點之間的“相似性鏈接”。
一般來說，70 位字的漢明距離值介于 0 和 70 之間。在您的情況下，上限為 20，因為每個點有 10 個真坐標和 60 個假坐標。如果兩個點的所有真實坐標都位于不同的位置，則會出現最大距離。
圖的創建是一個 O(n^2) 的昂貴操作。但也許可以在您設想的時間內完成它。
添加回答
舉報
0/150
提交
取消