你的問題，不單單是 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)