→ flowwinds:感謝回覆,受教了~沒考慮到 distance matrix需要更多空間 02/15 20:46
推 smallworld:Kmeans is NP hard 02/17 22:36
推 gmoz:AMAZON EC2 (誤 02/18 21:05
你的問題，不單單是 Java 平台的問題，使用任何語言實作，都有類似的狀況
要解你這個問題，首先得要分析你所使用的 distance function (norm)
不同的 distance function 所需的解法會不太一樣
我先回答幾個推文中所提到的狀況
※ 引述《jyleef (龍蝦)》之銘言：
: 我的資料量大約有五百萬筆(小於)
: 然後每一筆要分為45欄
: 所以陣列宣告下去等於 5百萬*45 (型態會用到String 或 double(二選一))
: 已經有將記憶體配置改成 -Xmx1575 (已經是最大了) → 無解
: 也有想過要改用分批讀取再寫入的方式
: 可是之後要跑 k-means 演算法，還是要一次看全部的資料 → 再度無解
: 目前我的電腦配備為(只用一台電腦跑)
:--
: ※ 發信站: 批踢踢實業坊(ptt.cc)
: ◆ From: 219.85.40.79
: 推 slalala:運算過程為什麼不透過資料庫紀錄? 02/13 16:04
五百萬筆資料，又要跑 k-means 演算法
如果使用資料庫的話，performance 基本上是無法想像
(或者找找看有什麼 database engine 有針對適合用於 k-means 演算法作優化)
: 推 a1234957:基本上這是最無腦的解法 02/13 20:49
原po的解法是否真的無腦，有時是迫於資料的形態，無法一概而論
: → flowwinds:你用到k-means的distance是一筆資料跟另一筆資料嗎? 02/13 23:55
: → flowwinds:一筆資料45個column跟另一筆資料45個column算出一個距離 02/13 23:58
: → flowwinds:如果是這樣可以不用 load 全部資料算出initial distance 02/14 00:01
: → flowwinds:matrix,而有initial distance matrix應該能跑之後集群法 02/14 00:03
計算 initial distance matrix 在其它地方合適
偏偏在原po這個例子中不合適
直接看這個 initial distance matrix 的 dimension 為 5,000,000 x 5,000,000
(好吧，其中有一半的是重覆，所以縮為 5,000,000 x 2,500,000)
共有 12,500,000,000,000 個
換句話說，整個 distance matrix 必須使用 12,500,000,000,000 個 double 儲存
(資料量 100T bytes)
不只記憶體塞不下，一般個人用或實驗室電腦的硬碟恐怕也塞不下這麼大量的資料
當然，這個 distance matrix 不是 sparse matrix
但我們曉得，這 12.5T 個 double 有絕大部分用不到
所以似乎我們可以只紀錄用的部分，以 sparse matrix 呈現
但問題在於，在還沒跑過 k-means 演算法之前，要如何知道有哪些被用到？
要嘛先跑一次 k-means 演算法 (那這樣問題等於解完了)
要嘛，要另外想一個演算法，猜測可能會用到哪些資料
但去想這種演算法，搞不好都可以發表論文了
----------
回答原 po 的問題
要處理這個問題，首先，降低執行期間所需的資料量是要務
如何降低則與這個問題所使用的 distance function 相關
一筆資料有45欄，先確認一件事
在計算兩筆資料的 distance 時，這45欄資料是否都會用到？
假設，只用到其中三欄，那問題就好辦多了
就只將會用到的這三欄資料讀進記憶體即可
這時，所需的記體體為 5,000,000 x 3 x 8 = 120M bytes
----------
如果這 45 欄資料都會用到
再來就尋求是否可以降低資料維度的函數，從 45 維降為少數維度
如果你的 distance function 可以表達為
d(x_1, x_2, ..., x_45, y_1, y_2, ..., y_45)
= f(
g_1(x_1, x_2, ..., x_a),
g_1(y_1, y_2, ..., y_a),
g_2(x_(a+1), x_(a+2), ..., x_b),
g_2(y_(a+1), y_(a+2), ..., y_b),
...,
g_n(x_(m+1), x_(m+2), ..., x_45),
g_n(y_(m+1), y_(m+2), ..., y_45)
)
時，而且 n 值很小時 (比如，n = 3)
那恭喜你，你只要先計算每筆資料的 g_1, g_2, ..., g_n 值
而記憶體只要記錄每筆資料的 g_1, g_2, ..., g_n 值即可
n 愈小，所需的記憶體愈少
不過，大家最常使用的 distance function: Euclidean norm
(x1-y1)^2 + (x2-y2)^2 + ... + (x45-y45)^2
卻無法依此方式降低資料維度
----------
如果上述方式均無效
那麼，就得要將資料存於硬碟中
這當然無法像前述將資料放在記憶體中那麼快
還好，k-means 演算法，每個 iteration
只要從頭到尾循序讀取一次硬碟資料即可
算句話說，如果 iterate 三次，就是從頭到尾讀取三次硬碟資料
如果 iterate 五次，就是從頭到尾讀取五次硬碟資料
如果 iterate 十次，就是從頭到尾讀取十次硬碟資料
那這時有另一種可能的做法，就是你可以考慮是否一定要解 exact solution？
接不接受 sub-optimal solution？
假如，exact solution 需要一百次 iteration
但，十次 itaration 的結果，total squared distance sum 只比最佳值多 0.1%
那這個結果是不是你可以接收的？
如果你可以接受類似上述的 sub-optimal solution
那，就不需要使用原本的結束判斷條件 (前後兩次 iteration 群集邊界不變動)
而可以使用較為寬鬆的結束判斷條件
(比如，前後兩次 iteration 的 total squared distance sum 變動量小於萬分之一)
----------
當然，還可能存在其它加速方法
不過，要如何加速，都要針對問題本身的特性處理
不單單只是 k-means 演算法本身是否可以加速的問題
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 60.250.129.52
※ 編輯: mgtsai 來自: 60.250.129.52 (02/15 19:33)