這個事起源于跟朋友一次聚會，他比較忙，一刻也不能停地處理工作。我就看他一直在看Excel表格，根據資料的特征不斷地做決定。我比較好奇就問什麼樣的資料要做什麼樣的處理，他說了一些名額，比如X名額、Y名額都高，就執行A方案；X名額高、Y名額低，就執行B方案。
我程式員思維就冒出來了，說這也不用你一條條地看吧，你把标準列出來，例如X、Y到多少算高，處理方案訂下來，寫個Python程式跑一遍Excel表格結果就出來了——這其實就是給資料分類打标簽。這就引出了本文想說的——聚類。
分類是指根據已經給出的正确的分類資料，通過其分類模型，對新資料進行分類。
而聚類，雖然也是将一堆資料分成幾“類”——在聚類中，這叫“簇”，但是相比分類有明确的定義，聚類則是将相似的資料“聚”成一“簇”，至于這一“簇”是什麼，我們不關心，我們隻關心如何計算相似度。
算法很多，這裡隻介紹K均值算法。算法很簡單，過程如下：
1、确定要聚成K個簇。
2、随機選擇K個對象，作為每個簇的質心。
3、周遊其他對象，計算其與每個質心的距離(距離算法後述)，并将其劃分到最近質心的簇中。
4、計算每個簇中所有資料的平均值，将其設為新的質心。
5、重複3、4，直到新舊質心相等，我們視為其已經收斂。注意：不斷地重複3、4步驟，質心的位置一定會在某處收斂，這是經過數學證明了的。
6、輸出結果。
直接上代碼：
public class KMeans { public static void main(String[] args) { List nodes = KMeans.buildNodes(100); int k = 3; // 因為是随機選初始質心，資料也是随機生成，是以本例就直接選前K個作為質心。 List centres = Lists.newArrayListWithCapacity(k); Map> centreMap = Maps.newHashMap(); for (int i = 0; i < k; i++) { Node n = nodes.get(i); centres.add(n); centreMap.put(i, new ArrayList()); } // System.out.println("初始質心："); // System.out.println(centres.toString()); // System.out.println("資料："); // System.out.println(nodes.toString()); // System.out.println("=================="); KMeans kmeans = new KMeans(); kmeans.kmean(nodes, centres, centreMap, k); } public void kmean(List nodes, List centres, Map> centreMap, int k) { boolean flag = true; while (flag) { // 周遊所有對象，計算其與所有質心的距離，并分簇 for (int i = 0; i < nodes.size(); i++) { Node node = nodes.get(i); int tmpDistance = Integer.MAX_VALUE; int tmpCode = Integer.MAX_VALUE; // System.out.println("計算Node" + node.toString() + "到各質心的距離"); for (int j = 0; j < centres.size(); j++) { Node centre = centres.get(j); // if (KMeans.nodeEquals(centre, node)) { // continue; // } //質心就是節點，不再計算距離 if (centre.equals(node)) { continue; } int distance = Distance.euclidean(node, centre).intValue(); // System.out.println("臨時距離=" + tmpDistance); // System.out.println(node.toString() + "到質心" + centre.toString() + "的距離" + distance); if (distance < tmpDistance) { tmpDistance = distance; tmpCode = j; } } centreMap.get(tmpCode).add(node); // System.out.println("============="); } // 分簇完畢，根據每簇的節點計算新的質心。質心可以為虛拟的坐标點 List newCentres = Lists.newArrayListWithCapacity(k); Map> newCentreMap = Maps.newHashMap(); for (Map.Entry> entry : centreMap.entrySet()) { if (entry.getValue().size() == 1) { // 如果每簇隻有一個Node，則不再計算，它就是質心 newCentres.add(entry.getValue().get(0)); newCentreMap.put(entry.getKey(), new ArrayList()); } else { // 計算新質心 Node newCentre = KMeans.getCentre(entry.getValue()); //某簇沒有節點，也就沒有新質心 if (Objects.isNull(newCentre)) { continue; } newCentres.add(newCentre); newCentreMap.put(entry.getKey(), new ArrayList()); } } // 新質心與原質心清單完全相同，代表已經收斂，最終結果已出，跳出循環 if (newCentres.containsAll(centres) && centres.containsAll(newCentres)) { flag = false; } // System.out.println("原質心："); // System.out.println(centres.toString()); // System.out.println("計算結果："); // System.out.println(centreMap.toString()); // System.out.println("新質心："); // System.out.println(newCentres.toString()); // // System.out.println("是否收斂：" + converge); // KMeans.show(centres, centreMap); // System.out.println("-----------------"); if (!flag) { System.out.println("最終結果："); KMeans.show(newCentres, centreMap); } centres.clear(); centreMap.clear(); centres = newCentres; centreMap = newCentreMap; } } /** * 列印結果 * * @param centres 質心清單 * @param centreMap 已分簇的資料 */ public static void show(List centres, Map> centreMap) { int i = 0; for (Map.Entry> entry : centreMap.entrySet()) { for (Node n : entry.getValue()) { System.out.println("[" + n.getX() + ", " + n.getY() + "," + i + "],"); } i++; } for (Node node : centres) { System.out.println("[" + node.getX() + ", " + node.getY() + "," + i++ + "],"); } } /** * 根據坐标判斷是否為同一節點 * * @param n1 * @param n2 * @return */ public static boolean nodeEquals(Node n1, Node n2) { return n1.getX() == n2.getX() && n1.getY() == n2.getY(); } /** * 計算每簇Node的平均值，擷取質心 * * @param nodes * @return */ public static Node getCentre(List nodes) { // 分簇之後，很有可能所有資料都離某一個質心最近，導緻有些質心周圍沒有資料 if (nodes.isEmpty()) { return null; } int x = 0, y = 0; int size = nodes.size(); for (Node node : nodes) { x = x + node.getX(); y = y + node.getY(); } return new Node(x / size, y / size); } /** * 初始化散點資料 * * @return */ public static List buildNodes(int size) { List nodes = Lists.newArrayListWithCapacity(size); // 生成随機資料。Node除了X、Y的坐标外，後面還有一個Code值，這是我為了在圖表中标注顔色用的，實際不參與計算 for (int i = 0; i < size; i++) { Node node = new Node((int) (Math.random() * 100), (int) (Math.random() * 100)); nodes.add(node); System.out.println("[" + node.getX() + ", " + node.getY() + ",0],"); } // nodes.clear(); // 以上是随機生成節點清單，下面是為了示範質心的選擇會導緻分簇結果不同而寫的固定資料 // nodes.add(new Node(42, 7)); // nodes.add(new Node(94, 44)); // nodes.add(new Node(96, 66)); // nodes.add(new Node(62, 84)); // nodes.add(new Node(29, 33)); return nodes; }}
Node就坐标XY與Code三個值，Code是我為了在圖表中b區分顔色所用，實際不參與計算。
有些要單獨說說：
1、質心的選擇。文獻上都說初始質心要從資料中随機選取，因為我的資料都是随機生成的，是以就偷懶直接取前K個資料作為初始質心。
2、随機擷取初始質心，可能會導緻同一份資料，分簇結果不同，如下：
資料集合：[62, 84],[29, 33],[42, 7],[94, 44],[96, 66]。兩次運算，選取的初始質心不同，結果如下圖：
結果1
結果2
紅藍節點為分簇結果，黃綠為收斂最後的虛拟質心。
原因就是初始質心不同，導緻第一次分簇結果不同，導緻新計算的質心不同，導緻最終分簇結果不同。
為了解決此問題，就有了KMeans++算法，後續篇我會說一下，如果有的話~~。
3、距離計算。本文采用了歐幾裡得距離，詳情可參看前文。本文隻有XY二維資料，如果是XYZ三維資料，可以寫成√( (x1-x2)^2+(y1-y2)^2+(z1-z2)^2，高維資料以此類推。歐幾裡得距離隻适用于連續變量。
歐幾裡得距離計算的是點與點的距離，并沒有考慮方向這一因素。舉例：
A商品原價100，漲價到150；B商品原價1000，漲價到1500；C商品200，降價到150。
如果按照價格絕對值看，AC的價格差不多，歐幾裡得距離相近，應聚為一類。
但是按照價格波動來看，AB都是漲價，幅度一緻，C則是降價，是以AB應聚為一類。這時候就不适用歐幾裡得距離了，我們可以采用夾角餘弦距離，來計算其相似度。其公式為：
(X1*X2+Y1*Y2)/(√X1^2+Y1^2+√X2^2+Y2^2)。
同歐幾裡得距離一樣，也可以計算高維資料。
除了這兩個距離計算方式，還有其他的，後續篇我會說一下，如果有的話~~。
KMeans也有不少缺陷，故衍生了不少算法，例如KMeans++等，後續篇我會說一下，如果有的話~~
下圖是我某次跑的資料結果：