你的问题，不单单是 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)