Chạy thuật toán phân nhóm

Trong công nghệ máy học, đôi khi bạn có thể gặp những tập dữ liệu có thể có hàng triệu ví dụ. Các thuật toán máy học phải mở rộng hiệu quả một cách hiệu quả cho các tập dữ liệu lớn này. Tuy nhiên, nhiều thuật toán phân nhóm không mở rộng quy mô vì chúng cần tính toán mức độ tương đồng giữa tất cả các cặp điểm. Điều này có nghĩa là thời gian chạy của chúng tăng lên dưới dạng hình vuông của số điểm, được biểu thị là \(O(n^2)\). Ví dụ: các thuật toán phân nhóm mang tính tổng hợp hoặc phân chia sẽ xem xét tất cả các cặp điểm và có độ phức tạp tương ứng của \(O(n^2 log(n))\) và \(O(n^2)\).

Khoá học này tập trung vào k-means vì quy mô là \(O(nk)\), trong đó \(k\) là số cụm. Các nhóm k-means trỏ vào \(k\) các cụm bằng cách giảm thiểu khoảng cách giữa các điểm và tâm của cụm (như trong Hình 1 bên dưới). Trung tâm của một cụm là giá trị trung bình của tất cả các điểm trong cụm đó.

Như được hiển thị, k-mean tìm thấy các cụm gần như hình tròn. Về mặt lý thuyết, điều này có nghĩa là k có nghĩa là xử lý dữ liệu hiệu quả dưới dạng một số lượt phân phối gần như vòng tròn và cố gắng tìm các cụm tương ứng tương ứng với các kiểu phân phối này. Trên thực tế, dữ liệu có chứa các điểm bất thường và có thể không phù hợp với mô hình này.

Trước khi chạy k-mean, bạn phải chọn số lượng cụm, \(k\). Ban đầu, hãy bắt đầu phỏng đoán cho \(k\). Sau đó, chúng ta sẽ thảo luận về cách tinh chỉnh số này.

Thuật toán phân cụm k-means

Để nhóm dữ liệu thành \(k\) các cụm, k-mean sẽ làm theo các bước dưới đây:

Hình 1: k-mean khi khởi chạy.

Bước 1

Thuật toán sẽ chọn ngẫu nhiên một trung tâm cho mỗi cụm. Trong ví dụ này, chúng tôi chọn \(k\) trong số 3 và do đó thuật toán chọn ngẫu nhiên 3 centroid.

Hình 2: Các cụm ban đầu.

Bước 2

Thuật toán sẽ chỉ định từng điểm cho trọng tâm gần nhất để lấy \(k\) các cụm ban đầu.

Hình 3: Tính toán lại các trọng tâm.

Bước 3

Đối với mọi cụm, thuật toán sẽ tính toán lại trọng tâm bằng cách lấy giá trị trung bình của tất cả các điểm trong cụm đó. Những thay đổi trong centroid được thể hiện trong Hình 3 bởi các mũi tên. Vì centroid thay đổi, nên thuật toán sẽ chỉ định lại các điểm cho centroid gần nhất. Hình 4 hiển thị các cụm mới sau khi gán lại.

Hình 4: Các cụm sau khi gán lại.

Bước 4

Thuật toán sẽ lặp lại cách tính trọng tâm và gán điểm cho đến khi điểm dừng thay đổi cụm. Khi nhóm các tập dữ liệu lớn, bạn sẽ dừng thuật toán trước khi đạt được sự hội tụ bằng cách sử dụng các tiêu chí khác.

Bạn không cần phải hiểu toán học đằng sau k-mean cho khóa học này. Tuy nhiên, nếu bạn muốn biết, hãy xem phần bên dưới để biết bằng chứng toán học.

Nhấp vào biểu tượng dấu cộng để có bằng chứng toán học

Với các \(n\) ví dụ được chỉ định cho \(k\) các cụm, hãy giảm thiểu tổng khoảng cách của các ví dụ theo tâm điểm của chúng. Trong trường hợp:

• \(A_{nk} = 1\) khi ví dụ thứ \(n\)được gán cho cụm \(k\), và nếu không thì 0
• \(\theta_k\) là trọng tâm của cụm \(k\)

Chúng ta muốn giảm thiểu biểu thức sau: $$\min_{A,\theta} \sum_{n=1}^N \sum_{k=1}^{K} A_{nk} ||\theta_k - x_n ||^2$$ phải tuân thủ: $$A_{nk} \in \{0,1\} \forall n,k$$ và $$\sum^{K}_{k=1}A_{nk}=1 \forall n$$ Để giảm thiểu biểu thức liên quan đến các trọng tâm của cụm \(\theta_k\), hãy lấy đạo hàm có liên quan đến \(\theta_k\) và làm tương đương với 0. $$f(\theta) = \sum^{N}_{n=1} \sum_{k=1}^{K} A_{nk} ||\theta_k - x_n||^2$$ $$\frac{\partial f}{\partial \theta_k} = 2 \sum_{n=1}^{N} A_{nk}(\theta_k - x_n) = 0$$ $$\implies \sum_{n=1}^{N} A_{nk}\theta_{k} = \sum^N_{n=1} A_{nk}x_{n}$$ $$\theta_k \sum_{n=1}^{N} A_{nk} = \sum_{n=1}^{N} A_{nk} x_n$$ $$\theta_k = \frac{\sum^N_{n=1} A_{nk} x_n}{\sum^N_{n=1} A_{nk}}$$ Số tử là tổng tất cả các khoảng cách lấy ví dụ theo trọng tâm trong cụm. Mẫu số là số lượng ví dụ trong cụm. Do đó, cụm trung tâm của cụm\(\theta_k\) là giá trị trung bình của các khoảng cách trung tâm mẫu trong cụm. Do đó đã được chứng minh.

Vì ban đầu, các vị trí trung tâm được chọn ngẫu nhiên, nên các k-mean có thể trả về kết quả khác biệt đáng kể khi chạy liên tiếp. Để giải quyết vấn đề này, hãy chạy k-mean nhiều lần và chọn kết quả có các chỉ số chất lượng tốt nhất. (Chúng tôi sẽ mô tả các chỉ số chất lượng sau trong khóa học này.) Bạn sẽ cần một phiên bản nâng cao của k-mean để chọn vị trí trung tâm ban đầu tốt hơn.

Thử nghiệm: Sử dụng trình mô phỏng k-means này tại Stanford, hãy thử chạy nhiều k-means nhiều lần và xem bạn có nhận được các kết quả khác nhau hay không.

Thuật ngữ quan trọng

• centroid