Phân cụm đồng thuận thông qua Apache Spark


Tạ Khánh Mai
1 năm trước
Hữu ích 3 Chia sẻ Viết bình luận 0
Đã xem 4257

Giới thiệu

Trong bài viết này, chúng tôi sẽ thảo luận về một kỹ thuật gọi là Phân cụm đồng thuận để đánh giá tính ổn định của các cụm được tạo bởi thuật toán phân cụm liên quan đến các nhiễu loạn nhỏ trong tập dữ liệu. Chúng tôi sẽ xem xét một ứng dụng mẫu được xây dựng bằng thư viện máy học Apache Spark để cho thấy cách phân cụm đồng thuận có thể được sử dụng với K-mean, Bisecting K-mean và Gaussian Mixture, ba thuật toán phân cụm khác nhau.

Phân tích cụm [1] trong học máy nhằm mục đích phân chia dữ liệu thành các bộ riêng biệt, không chồng chéo dựa trên thước đo tương tự giữa các điểm dữ liệu. Các điểm dữ liệu trong cùng một cụm phải càng gần (tương tự) với nhau càng tốt và các điểm dữ liệu trong các cụm khác nhau phải càng xa (không giống nhau) càng tốt. Phân tích cụm có nhiều ứng dụng trong các ngành khoa học khác nhau bao gồm sinh học, tin sinh học, y học, kinh doanh, khoa học máy tính và khoa học xã hội [1]. Dưới đây là một số ví dụ.

  • Phân cụm có thể được sử dụng để phân loại pixel của hình ảnh y tế để hỗ trợ chẩn đoán y tế [2].

  • Dữ liệu bệnh nhân ung thư có thể được phân cụm thành các nhóm dựa trên các thuộc tính nhất định, ví dụ: 'nhóm nút dương tính' và 'nhóm giai đoạn', để phân tích tuổi thọ của bệnh nhân thay đổi tùy thuộc vào cụm nào họ thuộc về [3].

  • Biểu hiện gen của các tế bào ung thư có thể được định hình thông qua các kỹ thuật phân cụm để phân tích cấu trúc tế bào và dự đoán tỷ lệ sống [4].

Nhiều kỹ thuật và thuật toán khác nhau có sẵn để phân tích phân cụm trong đó [5] và [6] cung cấp các đánh giá xuất sắc.

Báo cáo vấn đề

Các thuật toán phân cụm khác nhau có thể tạo các cụm khác nhau cho cùng một tập dữ liệu. Ở các lần thực thi khác nhau, ngay cả cùng một thuật toán có thể tạo ra các cụm khác nhau, ví dụ do bắt đầu ngẫu nhiên. Ví dụ, chúng tôi đã tải xuống một bộ dữ liệu từ Cổng dữ liệu GDC của Viện Ung thư Quốc gia về bệnh nhân Glioblastoma Multiforme (GBM) và Bệnh nhân Glioma cấp thấp (LGG) và phân vùng chúng thành ba cụm bằng thuật toán phân cụm K-mean.

Các kết quả được hiển thị trong Hình 1.a, 1.b cho hai lần thực hiện khác nhau.

Hình 1.a. Một tập hợp các cụm thu được bằng thuật toán K-nghĩa cho bệnh nhân GBM và LGG.

Hình 1.b. Một tập hợp các cụm khác thu được bằng thuật toán K-nghĩa cho bệnh nhân GBM và LGG.

Trong mỗi sơ đồ, có ba cụm được mô tả bởi các màu đen, xanh đậm và xanh nhạt. Các trục ngang đại diện cho phân loại biến thể (một đặc điểm cụ thể của alen biến thể liên quan đến đột biến gen TP53 được quan sát thấy ở bệnh nhân) và loại khối u. Trục dọc biểu thị số lượng phương pháp điều trị hóa trị được sử dụng cho bệnh nhân.

Lưu ý rằng các bộ cụm không nhất quán. Nếu một thuật toán tạo ra các cụm khác nhau đáng kể cho cùng một tập dữ liệu trong các lần thực hiện khác nhau, chúng ta có thể tin tưởng thuật toán đó không? Làm thế nào chúng ta có thể chọn một thuật toán so với thuật toán khác để cảm thấy tự tin nhất về cấu trúc của các cụm?

Trong bài viết này, chúng tôi sẽ thảo luận về một kỹ thuật phân tích được gọi là Phân cụm đồng thuận để thể hiện sự đồng thuận qua nhiều lần chạy thuật toán phân cụm và phân tích tính ổn định của các cụm được phát hiện liên quan đến biến thiên lấy mẫu [7].

Tổ chức bài viết

Trong phần tiếp theo, chúng ta sẽ thảo luận về những điều cơ bản của phân cụm đồng thuận. Phần sau đây liên quan đến đánh giá mã của một ứng dụng mẫu được phát triển với Thư viện máy học Apache Spark MLLib [8] để thực hiện phân cụm đồng thuận với ba thuật toán phân cụm khác nhau, K-mean, Bisecting K-mean và Gaussian Mixture [5] , [6]. Phần cuối cùng đưa ra kết luận.

Phân cụm đồng thuận

Phân cụm đồng thuận dựa trên giả định rằng thuật toán phân cụm đáng tin cậy sẽ tạo ra các cụm tương tự mỗi khi nó được thực thi trên một phiên bản hơi khác của một tập dữ liệu. Nói cách khác, nhiễu loạn nhỏ trên tập dữ liệu không nên thay đổi đáng kể các cụm kết quả.

Để thực hiện phân cụm đồng thuận, tập dữ liệu gốc được chia ngẫu nhiên m lần để tạo ra m tập dữ liệu khác nhau có kích thước nhỏ hơn một chút so với tập dữ liệu gốc. Sau đó, thuật toán phân cụm được lặp lại m lần (lặp), một lần cho mỗi bộ dữ liệu được lấy mẫu.

Tiếp theo, đối với mỗi cặp điểm dữ liệu trong bộ dữ liệu ban đầu, nó được xác định số lần cặp xuất hiện trong cùng một cụm trong một lần lặp cụ thể của thuật toán phân cụm. Ý tưởng là nếu cặp điểm dữ liệu là 'tương tự' thì lý tưởng nhất là chúng nên được đặt trong cùng một cụm trong mỗi lần lặp khi tập dữ liệu được lấy mẫu tương ứng với lần lặp chứa cả hai. Tương tự, nếu các điểm dữ liệu là 'không giống nhau' thì chúng nên được đặt trong các cụm riêng biệt trong mỗi lần lặp khi tập dữ liệu được lấy mẫu tương ứng với lần lặp chứa cả hai.

Để định lượng sự đồng thuận, cái gọi là 'ma trận đồng thuận' được xây dựng. Đặt tập dữ liệu gốc bao gồm N điểm dữ liệu. Khi đó, ma trận đồng thuận là ma trận đối xứng, N x N trong đó phần tử (i, j) bằng số lần dữ liệu điểm a ij được gán vào cùng một cụm chia cho số lần điểm dữ liệu a i và một j đã được chọn cùng nhau. Các phần tử đường chéo của ma trận đồng thuận luôn là 1 và bất kỳ phần tử không đường chéo nào nằm trong khoảng từ 0 đến 1, đã bao gồm.

Một ví dụ rất đơn giản, hãy xem xét một tập dữ liệu bao gồm 5 điểm dữ liệu {a 1 , 2 , 3 , 4 , 5 } trong không gian 2 chiều.

Hình 2. Một ví dụ về 5 điểm dữ liệu trong không gian 2 chiều.

Một ma trận đồng thuận cho các điểm dữ liệu đó có thể trông như thế này:



một 1
một 2
một 3
một 4
một 5
một 1

1
0,8
0,9
0,1
0
một 2

0,8
1
0,7
0,05
0,01
một 3

0,9
0,7
1
0,15
0,1
một 4

0,1
0,05
0,15
1
0,9
một 5

0
0,01
0,1
0,9
1

Hãy xem xét phần tử được tô sáng (1,3) tương ứng với cặp điểm dữ liệu 1 , 3 . Giá trị của phần tử đó ngụ ý rằng:

(# lần 13 được gán cho cùng một cụm) /
(# lần a 13 được chọn cùng nhau) = 0,9

Do đó, 90% thời gian khi các điểm 13 được chọn cùng nhau trong một mẫu dữ liệu, thuật toán đặt chúng trong cùng một cụm. Mặt khác, ma trận đồng thuận ngụ ý rằng chỉ 10% thời gian thuật toán đặt các điểm 14 trong cùng một cụm khi chúng được chọn cùng nhau (phần tử (1,4)).

Một sự đồng thuận thỏa đáng sẽ ngụ ý rằng bất kỳ phần tử không chéo nào của ma trận đồng thuận đều rất gần với 1, bởi vì cặp điểm dữ liệu cụ thể là tương tự nhau và do đó thuật toán đã gán chúng cho cùng một cụm trong hầu hết các lần lặp hoặc rất gần với 0 , bởi vì cặp điểm dữ liệu cụ thể không giống nhau và do đó thuật toán đã gán chúng cho các cụm khác nhau trong hầu hết các lần lặp. Mặt khác, các mục cách xa cả 0 và 1 hàm ý sự đồng thuận kém. Ví dụ, một mục nhập có giá trị 0,5 ngụ ý rằng thuật toán đã đặt cặp điểm dữ liệu tương ứng trong cùng một cụm trong 50% số lần lặp và trong các cụm riêng biệt trong 50% số lần lặp còn lại.

Các hàng và cột của ma trận đồng thuận có thể được cho phép đặt các điểm dữ liệu gần nhất với nhau nhất có thể, tạo ra bản đồ nhiệt đối xứng, sau đó giúp quyết định sự đồng thuận thông qua kiểm tra trực quan [9]. Xem [10] để xem xét các thuật toán để tạo bản đồ nhiệt từ ma trận đồng thuận.

Để kiểm tra trực quan, một cách tiếp cận khác đối với bản đồ nhiệt là phát triển biểu đồ liên quan đến ma trận đồng thuận, được gọi là biểu đồ của các chỉ số đồng thuận [7]. Trục hoành của biểu đồ biểu thị tỷ lệ số lần một cặp hai điểm dữ liệu riêng biệt xuất hiện trong cùng một cụm với số lần cặp đó nằm trong cùng một mẫu trong tất cả các lần lặp. Trục dọc của biểu đồ cho thấy tỷ lệ cụ thể đạt được bao nhiêu lần. Trong trường hợp lý tưởng, biểu đồ sẽ chỉ hướng về hai thùng, gần 1 và 0, trong đó thùng gần 1 đại diện cho cặp điểm dữ liệu riêng biệt nằm trong cùng một cụm và thùng gần 0 đại diện cho cặp điểm dữ liệu riêng biệt trong các cụm riêng biệt hầu hết thời gian trên tất cả các lần lặp.

Đối với mỗi thuật toán K-mean, Bisecting K-mean và Gaussian Mixture, chúng tôi đã áp dụng kỹ thuật phân cụm đồng thuận cho tập dữ liệu của mình để tạo ba cụm với m = 20 lần lặp. Trong mỗi lần lặp, mẫu phụ ngẫu nhiên bao gồm ~ 90% bộ dữ liệu gốc. Biểu đồ cho mỗi thuật toán được hiển thị bên dưới (mã nguồn của ứng dụng đã tạo các sơ đồ đó sẽ được xem xét trong phần sau).

Hình 3. Biểu đồ cho thuật toán K-mean.

Hình 4. Biểu đồ cho thuật toán Bisecting K-mean.

Hình 5. Biểu đồ cho thuật toán Gaussian Mixture.

Đối với các thuật toán kết hợp K-mean và Gaussian Mixture, dữ liệu chủ yếu được tích lũy trong các thùng gần 0 và 1, đặc biệt trong các khoảng [0,0.2] và [0.8,1.0]. Mặt khác, đối với thuật toán K-mean, các thùng trong khoảng từ 0 đến 1 chứa quá nhiều điểm dữ liệu, đặc biệt là trong khoảng [0,4,0,7]. Do đó, chúng tôi kết luận rằng thuật toán K-mean không đạt được sự đồng thuận thỏa đáng như Bisecting K-mean hoặc Gaussian Mixture cho tập dữ liệu cụ thể.

Đánh giá mã

Chúng tôi đã triển khai một ứng dụng Java mẫu để chứng minh phân cụm đồng thuận. Ứng dụng sử dụng API thư viện máy học Apache Spark cho K-mean, Bisecting K-mean và Gaussian Mixture (phiên bản Spark 2.3.0). Một lớp trừu tượng có tên  ConsensusCluster lưu trữ tất cả logic để tính toán biểu đồ. Ba lớp cụ thể  BisectingKMeansClusteringKMeansClustering và,  GaussianMixtureClusteringmỗi lớp đại diện cho một thuật toán phân cụm cụ thể, tạo ra các cụm thực tế.

Hình 6. Sơ đồ lớp cho ứng dụng demo.

Ứng dụng mẫu sử dụng một bộ dữ liệu, như đã đề cập trước đây trong 'Báo cáo sự cố', được tải xuống từ Cổng dữ liệu GDC của Viện Ung thư Quốc gia về bệnh nhân Glioblastoma Multiforme (GBM) và Bệnh nhân Glioma cấp thấp (LGG) [11]. Nó bao gồm 76 điểm dữ liệu riêng biệt. Để tính toán đồng thuận, chúng tôi đã chạy 20 lần lặp. Trong mỗi lần lặp lại, dữ liệu được lấy mẫu ngẫu nhiên với mỗi mẫu phụ chứa ~ 90% bộ dữ liệu gốc (đầy đủ).

Với mỗi thuật toán, chúng tôi tạo ra ba cụm trong mỗi lần lặp. Chúng tôi đã tạo dữ liệu biểu đồ sau khi tất cả các lần lặp lại được hoàn thành. Các sơ đồ của biểu đồ cho mỗi thuật toán được đưa ra trong Hình 3, 4, 5.

Đồng thuận

Lớp cha này thực hiện hầu hết các công việc để tính toán biểu đồ cho các chỉ số đồng thuận. Công việc duy nhất được giao cho các lớp con cụ thể là việc tạo ra các cụm.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;
import org.apache.spark.SparkConf;
import org.apache.spark.api.java.JavaRDD;
import org.apache.spark.api.java.JavaSparkContext;
import org.apache.spark.api.java.function.Function;
import org.apache.spark.mllib.linalg.Vector;
import org.apache.spark.mllib.linalg.Vectors;

public abstract class ConsensusCluster{

// Number of cluster we would like to construct
protected static int numClusters = 3;

// Stores how many times two data points were assigned to the same cluster 
// across all iterations.
//
// A data point is represented as a Row object. Key to the HashMap is a data point 
// (outer point) and the corresponding value is a HashMap that maps a data point 
// (inner point) to an integer. Hence, to find how many times two data points were 
// assigned to the same cluster across all iterations pass one of those data points 
// (outer point) to countSameCluster to get the corresponding HashMap. Then, pass 
// the second data point(inner point) to that HashMap to get the integer value, 
// which is how many times those data points were assigned to the same cluster.
protected HashMap<String, HashMap<String, Integer>> countSameCluster = 
  new HashMap<String, HashMap<String, Integer>>();

// Stores how many times two data points were assigned to the same data sample 
// across all iterations.
//
// A data point is represented as a Row object. Key to the HashMap is a data point 
// (outer point) and the corresponding value is a HashMap that maps a data point 
// (inner point) to an integer.Hence, to find how many times two data points were 
// in the same data sample across all iterations pass one of those data points 
// (outer point) to countSameSample to get the corresponding HashMap. Then, pass 
// the second data point (inner point) to that HashMap to get the integer value,
// which is how many times those data points were in the same data sample.
protected HashMap<String, HashMap<String, Integer>> countSameSample = 
   new HashMap<String, HashMap<String, Integer>>();

Những cấu trúc dữ liệu được khởi tạo theo phương pháp sau.

/**
 * Initialize 'countSameCluster' & 'countSameCluster' from full data set
 * 
 * @param fullData: full data set
 */
protected void initializeCounts(JavaRDD<String> fullData) {
       fullData.cache();
       List<String> pointsOuter = fullData.collect();
       List<String> pointsInner = fullData.collect();

       for (String pointOuter : pointsOuter) {
       HashMap<String, Integer> map = new HashMap<String, Integer>();
       for (String pointInner : pointsInner) {
       map.put(pointInner, 0);
       }
       countSameCluster.put(pointOuter, map);
       }

       for (String pointOuter : pointsOuter) {
       HashMap<String, Integer> map = new HashMap<String, Integer>();
       for (String pointInner : pointsInner) {
       map.put(pointInner, 0);
       }
       countSameSample.put(pointOuter, map);
       }
}

Phương pháp sau đây cập nhật countSameSamplecấu trúc dữ liệu '' từ một mẫu con nhất định tại một lần lặp cụ thể.

/**
* Given a subsample update the 'countSameSample' data structure.
* @param collectedSampledData - Data points in a subsample
*/
protected void updateSameSampleCounts(List<String> collectedSampledData) {
    ArrayList<String> clonedData = new ArrayList<String>();
    for (String s : collectedSampledData) {
        clonedData.add(s);
    }

    for (String s : collectedSampledData) {
        // Get all the points in 'countSameSample' for the particular
        // data point s in subsample
        HashMap<String, Integer> allPoints = countSameSample.get(s);

        for (String c : clonedData) {
            if(s.equals(c)){
                continue; // ignore self
            }
            // Increment # times c & s were together in a subsample
            int currentVal = allPoints.get(c);
            currentVal++;
            allPoints.put(c, currentVal);
        }
    }
}

Phương pháp sau đây cập nhật countSameClustercấu trúc dữ liệu '' từ các điểm dữ liệu trong một cụm tại một lần lặp cụ thể.

/**
* Given a cluster update 'countSameCluster' data structure
* from data points in a cluster
* @param clusterPoints - Data points in a cluster
*/
protected void updateSameClusterCounts(HashMap<Integer, Set<String>> clusterPoints) {
    // Each element in keys corresponds to a particular cluster, 0, 1, 2
    Set<Integer> keys = clusterPoints.keySet();

    for (int i : keys) {
        // Obtain points in that cluster
        Set<String> pointsOuter = clusterPoints.get(i);
        Set<String> pointsInner = clusterPoints.get(i);

        for (String pointOuter : pointsOuter) {
            // Get all the points in 'countSameCluster' for the 
            // particular data point pointOuter in cluster
            HashMap<String, Integer> allPoints = countSameCluster.get(pointOuter);

            for (String pointInner : pointsInner) {
                if(pointOuter.equals(pointInner)){
                    continue; // ignore self
                }
                // Increment # times pointInner & pointOuter were together in a 
                // cluster
                int currentVal = allPoints.get(pointInner);
                currentVal++;
                allPoints.put(pointInner, currentVal);
            }
        }
    }
}

Phương thức sau sử dụng các phương thức được giới thiệu trước đó để cập nhật ' countSameSample' và ' countSameCluster' vào cuối mỗi lần lặp.

/**
* At end of an iteration, update global data structures based on the subsample 
* used in the iteration and data points in the clusters created in that 
* iteration
*
* @param collectedSampledData - An ordered collection storing data points where 
* point at i-th element 
* belongs to the cluster defined in i-th element of collectedClusterIndexes
* @param collectedClusterIndexes - An ordered collection where each element 
* represents a cluster, 0, 1, 2 
* 
* @param clusterCenters - Coordinates of each cluster
*/
protected void updateHistogramData(List<String> collectedSampledData, 
       List<Integer> collectedClusterIndexes,
        Vector[] clusterCenters) {

    // Update the 'countSameSample' data structure
    updateSameSampleCounts(collectedSampledData);

    // Key to 'clusterPoints' is a cluster identifier, e.g. 0, 1, 2
    // The value is a Set where each element is a data point in the corresponding
    // cluster; data point is represented by its coordinates - a string of 
    // whitespace separated numbers
    HashMap<Integer, Set<String>> clusterPoints = new HashMap<Integer, 
         Set<String>>();
    int j = 0;

    for (Integer i : collectedClusterIndexes) {
        Set<String> points = clusterPoints.get(i);
        if (points == null) {
            points = new HashSet<String>();
            clusterPoints.put(i, points);
        }
        String tempRow = collectedSampledData.get(j++);
        points.add(tempRow);
    }

    // Update the 'countSameCluster' data structure
    updateSameClusterCounts(clusterPoints);
}

Sau khi hoàn thành tất cả các lần lặp, phương pháp này sẽ tính toán và in ra dữ liệu biểu đồ. Sau đó, biểu đồ có thể được vẽ bằng cách sử dụng một công cụ đồ họa như Microsoft Excel.

/**
* Calculate and print out histogram data. Data for 10 bins will be printed out:
* 0.0 <number to display in bin [0.0,0.1)>
* 0.1 <number to display in bin [0.1,0.2)>
* 0.2 <number to display in bin [0.2,0.3)>
* ...
* 0.9 <number to display in bin [0.9,1.0]>
*/ 
protected void generateHistogram() {
    // range: 0.1
    HashMap<Integer, Integer> histogram = new HashMap<Integer, Integer>();

    // Initialize with all 0's.
    histogram.put(0, 0);
    histogram.put(1, 0);
    histogram.put(2, 0);
    histogram.put(3, 0);
    histogram.put(4, 0);
    histogram.put(5, 0);
    histogram.put(6, 0);
    histogram.put(7, 0);
    histogram.put(8, 0);
    histogram.put(9, 0);

    for (String sOuter : countSameCluster.keySet()) {
       // sOuter is a particular data point.  
       // inSameCluster stores how many times a particular data point was in 
       // the same cluster as sOuter
       // inSameSample stores how many times a particular data point was in 
       // the same subsample as sOuter
        HashMap<String, Integer> inSameCluster = countSameCluster.get(sOuter);
        HashMap<String, Integer> inSameSample = countSameSample.get(sOuter);

        for (String sInner : inSameCluster.keySet()) {
            // sInner is a particular data point that was in the same cluster as 
            // sOuter
            if (sOuter.equals(sInner)) 
                continue; // Ignore self

            // how many times sInner and sOuter were in the same cluster
            int numTimesInSameCluster = inSameCluster.get(sInner);

            // how many times sInner and sOuter were in the same subsample
            int numTimesInSameSample = inSameSample.get(sInner);

            // Calculate the ratio and place into the corresponding bin
            float ratio = (numTimesInSameCluster == 0) ? 0f : 
                (float) numTimesInSameCluster / numTimesInSameSample;

            if (0 <= ratio && ratio < 0.1) {
                int val = histogram.get(0);
                val++;
                histogram.put(0, val);
            } else if (0.1 <= ratio && ratio < 0.2) {
                int val = histogram.get(1);
                val++;
                histogram.put(1, val);
            } else if (0.2 <= ratio && ratio < 0.3) {
                int val = histogram.get(2);
                val++;
                histogram.put(2, val);
            } else if (0.3 <= ratio && ratio < 0.4) {
                int val = histogram.get(3);
                val++;
                histogram.put(3, val);
            } else if (0.4 <= ratio && ratio < 0.5) {
                int val = histogram.get(4);
                val++;
                histogram.put(4, val);
            } else if (0.5 <= ratio && ratio < 0.6) {
                int val = histogram.get(5);
                val++;
                histogram.put(5, val);
            } else if (0.6 <= ratio && ratio < 0.7) {
                int val = histogram.get(6);
                val++;
                histogram.put(6, val);
            } else if (0.7 <= ratio && ratio < 0.8) {
                int val = histogram.get(7);
                val++;
                histogram.put(7, val);
            } else if (0.8 <= ratio && ratio < 0.9) {
                int val = histogram.get(8);
                val++;
                histogram.put(8, val);
            } else if (0.9 <= ratio && ratio <= 1) {
                int val = histogram.get(9);
                val++;
                histogram.put(9, val);
            }
        }
    }
    // Display histogram data
    System.out.println("HISTOGRAM");
    for (int i : histogram.keySet()) {
        System.out.println(String.format("%.1f", (double)(i * 0.1)) + " " + 
             histogram.get(i));
    }
}

Dưới đây là một hàm trợ giúp chuyển đổi một điểm dữ liệu, được biểu thị dưới dạng một chuỗi gồm 3 số, thành một vectơ 3 chiều.

/**
* This is a helper function that converts a data point, expressed as a string 
* consisting of 3 numbers, 
* into a 3-D vector of doubles. 
*/
@SuppressWarnings("serial")
static Function<String, Vector> mapFunction = new Function<String, Vector>() {
    public Vector call(String s) {
        String[] sarray = s.split(" ");
        double[] values = new double[sarray.length];                         

        for (int i = 0; i < sarray.length; i++)
            values[i] = Double.parseDouble(sarray[i]);

        return Vectors.dense(values);
    }
};

Đây là phương pháp trừu tượng được thực hiện bởi các lớp con. Nó phân vùng dữ liệu được chia thành các cụm.

/**
* Partition subsampled data into clusters. Implemented by a concrete class based 
* on a specific algorithm.
* 
* @param data - subsampled data
* @param numClusters - # clusters to create
* @param numIterations - # iterations to perform
* @return JavaRDD<Integer> - This data structure has the same number of elements 
* as input parameter 
* data. Each element in JavaRDD<Integer> indicates which cluster the corresponding 
* element in data belongs to, e.g. 0, 1, 2 etc.
* 
*/
protected abstract JavaRDD<Integer> dataCenters(JavaRDD<Vector> data, 
   int numClusters, int numIterations);

Đây là phương pháp chính. Nó khởi động cấu hình và bối cảnh Spark, khởi tạo cấu trúc dữ liệu và bắt đầu lặp lại. Trong mỗi lần lặp, nó tạo các cụm thông qua một lớp con cụ thể và cập nhật các cấu trúc dữ liệu từ lần lặp đó. Cuối cùng, nó tính toán và in ra dữ liệu biểu đồ.

/**
 * This is the main method that performs all the tasks. 
 */
protected void iterations() {
    // Set application name
    String appName = "Consensus Clustering Demo";

    // # iterations to determine clusters 
    int numIterations = 125;

    // Initialize Spark configuration & context
    SparkConf sparkConf = new SparkConf().setAppName(appName).
            setMaster("local[1]").set("spark.executor.memory",
            "1g");

    JavaSparkContext sc = new JavaSparkContext(sparkConf);

    // Read data file from file system.
    String path = "resources/TP53-VarClsf.txt";

    // Read the data file and return it as JavaRDD of strings
    JavaRDD<String> nonUniqueData = sc.textFile(path);
    System.out.println(nonUniqueData.count());

    // Remove any duplicates
    JavaRDD<String> fullData = nonUniqueData.distinct();
    System.out.println(fullData.count());

    // Initialize global data structures
    initializeCounts(fullData);

    // Number of iterations
    int MAX_ITER = 20;

    // Each execution of this loop corresponds to an iteration 
    for (int iteration = 0; iteration <= MAX_ITER; iteration++) {
        // Obtain a random subsample, consisting of 90% of the original data set
        JavaRDD<String> sampledData = fullData.sample(false, 0.9, (new 
            Random().nextLong()));

        // Convert data point, expressed as a string consisting of 3 numbers, into 
        // a 3-D vector of doubles
        JavaRDD<Vector> data = sampledData.map(mapFunction);
        data.cache();

        // Rely on concrete subclasses for this method. This is where clusters are 
        // created by a specific algorithm
        Tuple2<JavaRDD<Integer>, Vector[]> pair = 
            dataCenters(data, numClusters, numIterations);

        // Each element in clusterIndexes represents a cluster, 0, 1, 2
        JavaRDD<Integer> clusterIndexes = pair._1();

        // Each element in clusterCenters gives coordinates of a particular 
        // cluster, 0, 1, 2
        Vector[] clusterCenters = pair._2();

        // Bring all data to driver node for displaying results.
        // 'collectedSampledData' and 'collectedClusterIndexes' are ordered 
        // collections with the same size: i-th element in 'collectedSampledData' 
        // is a data point that belongs to the cluster defined in the i-th element 
        // in 'collectedClusterIndexes' 
        List<String> collectedSampledData = sampledData.collect();
        List<Integer> collectedClusterIndexes = clusterIndexes.collect();

        System.out.println(collectedSampledData.size() + " " + 
            collectedClusterIndexes.size());

        // Update global data structures based on cluster data
        updateHistogramData(collectedSampledData, collectedClusterIndexes, 
            clusterCenters);
    }

    // Generate histogram
    generateHistogram();

    // Stop spark
    sc.stop();
    sc.close();
}

Bây giờ, chúng tôi sẽ xem xét các lớp học trẻ em. Mỗi lớp con sẽ triển khai JavaRDD <Integer> dataCenters () trừu tượng được bảo vệ để phân vùng dữ liệu được chia thành các cụm dựa trên một thuật toán cụ thể.

KMeansClustering

Trong phương thức chính của nó, các  KMeansClustering kích hoạt được  iterations() thực hiện bởi lớp cha. Nó cũng thực hiện  dataCenters() phương thức tạo các cụm dựa trên thuật toán K-mean bằng cách sử dụng KMeans và KMeansModel trong gói org.apache.spark.mllib.clustering.

import org.apache.log4j.Level;
import org.apache.log4j.Logger;
import org.apache.spark.api.java.JavaRDD;
import org.apache.spark.mllib.clustering.KMeans;
import org.apache.spark.mllib.clustering.KMeansModel;
import org.apache.spark.mllib.linalg.Vector;

public class KMeansClustering extends ConsensusCluster {

    /**
     * The main method. It triggers iterations() implemented by the 
     * parent class.
     */
    public static void main(String[] args) throws Exception {
        Logger.getRootLogger().setLevel(Level.WARN);
           (new KMeansClustering()).iterations();
    }

    /**
     * In ConsensusCluster, this method was abstract; implementation
     * was left to child classes. Here we first create a KMeans object and then 
     * call its run() method on data to obtain a KMeansModel object. Then, we call 
     * the predict() method on KMeansModel object to obtain a data structure, 
     * clusterIndexes, that gives the cluster indexes for the input parameter 
     * data. The clusterIndexes and data have the same number of elements. The 
     * elements in the clusterIndexes and data have reciprocal sequence in the 
     * sense that the i-th element of clusterIndexes defines which cluster the 
     * i-th element of data belongs to, one of 0, 1, 2 ... etc.
     * 
     * @param data - Data points to partition into clusters
     * @param numClusters - number of clusters desired
     * @param numIterations - maximum # of iterations to perform during clustering
     * 
     */
    public JavaRDD<Integer> dataCenters(JavaRDD<Vector> data, int numClusters,
        int numIterations){
        KMeans km = new 
             KMeans().setK(numClusters).setMaxIterations(numIterations);
        KMeansModel clusters = km.run(data.rdd());
        JavaRDD<Integer> clusterIndexes = clusters.predict(data);
        return clusterIndexes;
    }
}

BisectingKMeansClustering

Trong phương thức chính của nó, các  BisectingKMeansClustering kích hoạt được  iterations() thực hiện bởi lớp cha. Nó cũng thực hiện  dataCenters() phương thức tạo các cụm dựa trên thuật toán Bisecting K-mean bằng cách sử dụng BisectingKMeans và BisectingKMeansModel trong gói org.apache.spark.mllib.clustering.

import org.apache.log4j.Level;
import org.apache.log4j.Logger;
import org.apache.spark.api.java.JavaRDD;
import org.apache.spark.mllib.clustering.BisectingKMeans;
import org.apache.spark.mllib.clustering.BisectingKMeansModel;
import org.apache.spark.mllib.linalg.Vector;

public class BisectingKMeansClustering extends ConsensusCluster{

    /**
     * The main method. It triggers iterations() implemented by the 
     * parent class.
     */
    public static void main(String[] args) throws Exception {
        Logger.getRootLogger().setLevel(Level.WARN);
        (new BisectingKMeansClustering()).iterations();
    }

    /**
     * In ConsensusCluster, this method was abstract; implementation 
     * was left to child classes. Here we first create a BisectingKMeans object 
     * and then call its run() method on data to obtain a BisectingKMeansModel 
     * object. Then, we call the predict() method on BisectingKMeansModel object 
     * to obtain a data structure, clusterIndexes, that gives the cluster indexes 
     * for the input parameter data. The clusterIndexes and data have the same 
     * number of elements. The elements in the clusterIndexes and data have 
     * reciprocal sequence in the sense that the i-th element of clusterIndexes
     * defines which cluster the i-th element of data belongs to, one of 0, 1, 
     * 2 ... etc.
     * 
     * @param data - Data points to partition into clusters
     * @param numClusters - number of clusters desired
     * @param numIterations - maximum # of iterations to perform during clustering
     * 
     */
    public JavaRDD<Integer> dataCenters(JavaRDD<Vector> data, int numClusters,
            int numIterations){
        BisectingKMeans bkm = new 
           BisectingKMeans().setK(numClusters).setMaxIterations(numIterations);
        BisectingKMeansModel clusters = bkm.run(data);
        JavaRDD<Integer> clusterIndexes = clusters.predict(data);
        return clusterIndexes;
    }
}

GaussianMixtureClustering

Trong phương thức chính của nó, các  GaussianMixtureClustering kích hoạt được  iterations() thực hiện bởi lớp cha. Nó cũng thực hiện  dataCenters() phương thức gán các điểm dữ liệu cho các cụm dựa trên thuật toán Gaussian Mixture bằng GaussianMixture và GaussianMixtureModel trong gói org.apache.spark.mllib.clustering.

import org.apache.log4j.Level;
import org.apache.log4j.Logger;
import org.apache.spark.api.java.JavaRDD;
import org.apache.spark.mllib.clustering.GaussianMixture;
import org.apache.spark.mllib.clustering.GaussianMixtureModel;
import org.apache.spark.mllib.linalg.Vector;

public class GaussianMixtureClustering extends ConsensusCluster {

    /**
     * The main method. It triggers iterations() implemented by the 
     * parent class.
     */
    public static void main(String[] args) throws Exception {
        Logger.getRootLogger().setLevel(Level.WARN);
        (new BisectingKMeansClustering()).iterations();
    }

    /**
     * In ConsensusCluster, this method was abstract; implementation 
     * was left to child classes. Here we first create a GaussianMixture object 
     * and then call its run() method on data to obtain a GaussianMixtureModel 
     * object. Then, we call the predict method on GaussianMixtureModel object to 
     * obtain a data structure, clusterIndexes, that gives the cluster indexes for 
     * the input parameter data. The clusterIndexes and data have the same number 
     * of elements. The elements in the clusterIndexes and data have reciprocal 
     * sequence in the sense that the i-th element of clusterIndexes
     * defines which cluster the i-th element of data belongs to, one of 0, 1, 
     * 2 ... etc.
     * 
     * @param data - Data points to partition into clusters
     * @param numClusters - number of clusters desired
     * @param numIterations - maximum # of iterations to perform during clustering
     * 
     */
    protected JavaRDD<Integer> dataCenters(JavaRDD<Vector> data, int numClusters, 
       int numIterations) {
        GaussianMixture gm = new 
        GaussianMixture().setK(numClusters).setMaxIterations(numIterations);
        GaussianMixtureModel clusters = gm.run(data.rdd());
        JavaRDD<Integer> clusterIndexes = clusters.predict(data);
        return clusterIndexes;
    }
}

Kết luận

Trong bài viết này, chúng tôi đã thảo luận về phân cụm đồng thuận, một kỹ thuật để thể hiện sự đồng thuận qua nhiều lần chạy thuật toán phân cụm và phân tích tính ổn định của các cụm được phát hiện liên quan đến biến thiên lấy mẫu. Chúng tôi đã xem xét một ứng dụng mẫu được xây dựng với thư viện máy học Apache Spark để cho thấy cách phân cụm đồng thuận có thể được sử dụng với K-mean, Bisecting K-mean và Gaussian Mixture, ba thuật toán phân cụm khác nhau. Đối với tập dữ liệu mẫu được xem xét trong ứng dụng, chúng tôi đã tính toán và vẽ sơ đồ biểu đồ của các chỉ số đồng thuận. Các biểu đồ chỉ ra rằng thuật toán Bisecting K-mean và Gaussian Mixture cung cấp các cụm ổn định hơn so với thuật toán K-mean. Một số nhận xét kết luận như sau.

  • Phân cụm đồng thuận có thể được áp dụng cho bất kỳ thuật toán phân cụm nào và rất hữu ích để so sánh các thuật toán khác nhau trên cùng một tập dữ liệu. Tuy nhiên, phân cụm đồng thuận không nhằm mục đích quyết định thuật toán phân cụm nào ổn định hơn các thuật toán khác nói chung . Các kết quả phụ thuộc vào một tập dữ liệu cụ thể và bản chất của mối quan hệ giữa các điểm dữ liệu. Ví dụ, thuật toán phân cụm phân cấp có thể không đạt được sự đồng thuận thỏa đáng cho một tập dữ liệu không có tính phân cấp hoặc ngược lại.

  • Ngoài ra, phân cụm đồng thuận có thể được sử dụng để xác định số lượng cụm tối ưu cho một tập hợp dữ liệu và thuật toán phân cụm. Một ma trận đồng thuận cũng có thể được sử dụng như một biện pháp tương tự, thay thế cho các biện pháp khác, ví dụ như khoảng cách Euclide [7].

  • Các đồ thị 3 chiều của các cụm mẫu trong Hình 1.a, 1.b được lấy bởi khung jzy3d dựa trên Java [12] và biểu đồ trong Hình 3 - 5 được vẽ bởi Microsoft Excel.

  • Mã nguồn hoàn chỉnh cho ứng dụng mẫu có thể được tìm thấy trong [13].

Tài liệu tham khảo

[1] Phân tích cụm , Wikipedia.

[2] Phương pháp tiếp cận cụm đối xứng tự động để xác định não bất thường trong hình ảnh quét PET - Phân tích , A. Meena và K. Raja, Thư viện Đại học Cornell.

[3] Phân cụm dữ liệu bằng Apache Spark , K. Unyelioglu, DZone / Vùng dữ liệu lớn.

[4] Phân loại và dự đoán khả năng sống sót trong ung thư biểu mô tế bào gan bằng Hồ sơ biểu hiện gen , JS Lee và cộng sự. al., Hepatology, 2004.

[5] Các yếu tố của học thống kê , T. Hastie et. al., Sê-ri Springer trong Thống kê, 2009.

[6] Phân loại mẫu , RO Duda et. al., John Wiley & Sons, 2000.

[7]Phân cụm đồng thuận: Phương pháp dựa trên việc lấy mẫu lại để khám phá lớp và trực quan hóa dữ liệu microarray biểu hiện gen , S. Monti et. al., Machine Learning, 52, 91 mộc118, 2003.

[8] Apache Spark , spark.apache.org.

[9] Bản đồ nhiệt , Wikipedia.

[10] Lịch sử của Bản đồ nhiệt cụm , L. Wilkinson và M. Thân thiện, Nhà thống kê người Mỹ Tập 63 Số 2, 2009.

[11] Dự án dữ liệu gen của Viện Ung thư Quốc gia , gdc.cancer.gov.

[12] API nguồn mở cho biểu đồ 3D , jzy3d.org.

[13] Phân cụm đồng thuận , github.com.

Hữu ích 3 Chia sẻ Viết bình luận 0
Đã xem 4257