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