English
Tiếng Việt
1. Giới thiệu
Thuật toán phân hoạch (clustering) thực hiện việc phân nhóm dữ liệu hay chia một tập dữ liệu lớn thành những tập nhỏ bao gồm các phần tử có sự tương đồng nào đó. K-Means là một thuật toán phân hoạch thuộc nhóm các thuật toán máy học không cần sự định hướng trước (unsupervised machine learning) được biết đến khá rộng rãi. Thuật toán này không cần quá trình huấn luyện để học, ghi nhớ các mô hình tri thức tách bạch với quá trình chạy. Điều này cũng đồng nghĩa với việc, K-means cho ra kết quả cuối cùng không thể đoán trước và rất khác nhau dù cho cùng điều kiện đầu vào. Quá trình học, cập nhật và chạy diễn ra đồng thời. K-means được sử dụng khi bạn có một tập hợp gồm các điểm dữ liệu (data point) không được dán nhãn ( dữ liệu chưa được phân loại theo nhóm hay danh mục ). Mục tiêu của thuật toán là tìm ra K nhóm của tập dữ liệu này với K cho trước. Thuật toán xử lý dựa trên thao tác lặp (iterative) để gán mỗi điểm dữ liệu vào 1 trong K nhóm dựa vào thuộc tính (feature) đã cho của từng điểm dữ liệu. Các điểm dữ liệu được phân nhóm (cluster) theo tiêu chí tương đồng về các thuộc tính của chúng. Kết quả của thuật toán K-means là:
- K điểm trung tâm (centroid) của K nhóm (cluster), K điểm này có thể được dùng để tiếp tục gắn nhãn cho dữ liệu mới khi chúng được thêm vào tập dữ liệu ban đầu.
- Gắn nhãn cho tập điểm dữ liệu (mỗi điểm dữ liệu được gán cho một nhóm xác định ứng với một điểm trung tâm)
Bỏ qua việc định nghĩa các nhóm nhãn dữ liệu trước khi thực thi thuật toán, việc phân cụm cho phép bạn tìm và phân tích các nhóm hình thành một cách có sắp xếp. Việc chọn số nhóm K là thao tác quan trọng cần quan tâm.
2. Ứng dụng
Thuật toán K-means clustering thường được sử dụng để tìm ra các nhóm mà không được gắn nhãn một cách rõ ràng trong tập dữ liệu. Điều này thường có ý nghĩa trong việc xác nhận tính đúng của các giả thiết về những kiểu nhóm đang tồn tại hay chỉ ra những nhóm chưa biết trong một tập dữ liệu phức tạp. Một khi thuật toán đã chạy và các nhóm đã được định nghĩa, bất kỳ dữ liệu mới nào đều có thể dễ dàng được gắn vào nhóm thích hợp.
Đây là một thuật toán rất phổ biến, được ứng dụng với bất kỳ kiểu phân hoạch, nhóm nào. Một vài ví dụ như sau:
- Một công ty chuyển vận muốn mở chuỗi các trung tâm giao nhận hàng trong một thành phố. Trong tình huống đó họ cần đối mặt với các vấn đề như sau:
+ Họ cần phải phân tích để biết khu vực mà có nhiều đơn đặt hàng thường xuyên.
+ Họ cần biết bao nhiêu trung tâm nên được mở để có thể đảm bảo giao nhận hiệu quả trong một khu vực.
+ Họ cần tìm ra vị trí thích hợp để mở trung tâm trong các khu vực nhằm đảm bảo tối ưu khoảng cách giữa trung tâm và khách hàng của họ.
- Phân tích thông tin tội phạm có liên quan tới nghiện ma túy ở Việt Nam. Nguồn dữ liệu bao gồm các loại hình phạm tội do nhiều loại thuốc khác nhau gây ra, bao gồm Heroin, Cocaine cho tới các loại gây nghiện trong toa bác sĩ, đặc biệt là với trẻ vị thành niên. Tỉ lệ phạm tội do lạm dụng thuốc có thể giảm nhờ việc xây dựng các trung tâm cai nghiện tại chổ trong những khu vực chịu tác động lớn bởi loại hình tội phạm này. Với nguồn dữ liệu được cho, các mục tiêu khác nhau có thể được định ra. Ví dụ như:
+ Phân loại tội phạm dựa trên việc lạm dụng dược chất để tìm ra các nguyên nhân chính.
+ Phân loại tội phạm dựa trên nhóm tuổi.
+ Phân tích dữ liệu để xác định hình thức trung tâm cai nghiện cần xây dựng
+ Tìm ra số lượng trung tâm cai nghiện cần xây dựng để đạt hiệu quả trong việc giãm tỉ lệ tội phạm do nghiện thuốc.
Ngoài ra, việc theo dõi nếu một điểm dữ liệu được giám sát chuyển đổi qua lại giữa các nhóm theo thời gian có thể đem lại thông tin hữu ích trong thay đổi của tập dữ liệu.
3. Thuật toán
Thuật toán K-Means hoạt động dựa vào các bước xử lý theo trình tự:
- Bước 1: Cho dữ liệu đầu vào là một tập S gồm M điểm (mỗi điểm là một phần tử có N thuộc tính (feature), hay có thể gọi là một vector N chiều), và giá trị K (số cluster).
- Bước 2: với mỗi cluster trong K cluster ta cần có một điểm trung tâm (cluster centroid hay Mean), vì vậy ta cần khởi tạo giá trị cho K điểm ngẫu nhiên, mỗi điểm cùng có N thuộc tính và giá trị nằm trong khoảng biên giá trị tương ứng với thuộc tính đó của tập dữ liệu được cho. Đôi khi người ta chỉ đơn giản là chọn ngẫu nhiên K điểm trung tâm từ trong số các điểm dữ liệu thuộc tập được cho.
- Bước 3: Lần lượt kiểm tra và nhóm mỗi điểm trong tập S vào một trong K nhóm mà nó gần nhất (dựa vào sự tương đồng, hay khoảng cách) với điểm trung tâm của nhóm đó.
Có rất nhiều dạng khoảng cách hay độ tương đồng (tham khảo thêm) có thể được sử dụng, trong đó phổ biến nhất có lẽ là khoảng cách Euclid.
- Bước 4: Cập nhật giá trị của các điểm trung tâm bằng giá trị trung bình của tập điểm trong mỗi nhóm.
- Bước 5: lặp lại bước 3 và 4 cho đến khi giá trị điểm trung tâm không còn thay đổi, khi đó thuật toán kết thúc.
4. Lựa chọn thay thế
Có nhiều thuật toán tương tự có thể được sử dụng để thay thế cho K-mean clustering như DBScan, spectral clustering, và mô hình phức hợp Gaussian (Gaussian mixture), hay một kỹ thuật giảm chiều dữ liệu như PCA (principal component analysis) có thể được dùng để phân nhóm các mẫu (pattern) dữ liệu.
-- BIOZ --
Thuật toán phân hoạch (clustering) thực hiện việc phân nhóm dữ liệu hay chia một tập dữ liệu lớn thành những tập nhỏ bao gồm các phần tử có sự tương đồng nào đó. K-Means là một thuật toán phân hoạch thuộc nhóm các thuật toán máy học không cần sự định hướng trước (unsupervised machine learning) được biết đến khá rộng rãi. Thuật toán này không cần quá trình huấn luyện để học, ghi nhớ các mô hình tri thức tách bạch với quá trình chạy. Điều này cũng đồng nghĩa với việc, K-means cho ra kết quả cuối cùng không thể đoán trước và rất khác nhau dù cho cùng điều kiện đầu vào. Quá trình học, cập nhật và chạy diễn ra đồng thời. K-means được sử dụng khi bạn có một tập hợp gồm các điểm dữ liệu (data point) không được dán nhãn ( dữ liệu chưa được phân loại theo nhóm hay danh mục ). Mục tiêu của thuật toán là tìm ra K nhóm của tập dữ liệu này với K cho trước. Thuật toán xử lý dựa trên thao tác lặp (iterative) để gán mỗi điểm dữ liệu vào 1 trong K nhóm dựa vào thuộc tính (feature) đã cho của từng điểm dữ liệu. Các điểm dữ liệu được phân nhóm (cluster) theo tiêu chí tương đồng về các thuộc tính của chúng. Kết quả của thuật toán K-means là:
- K điểm trung tâm (centroid) của K nhóm (cluster), K điểm này có thể được dùng để tiếp tục gắn nhãn cho dữ liệu mới khi chúng được thêm vào tập dữ liệu ban đầu.
- Gắn nhãn cho tập điểm dữ liệu (mỗi điểm dữ liệu được gán cho một nhóm xác định ứng với một điểm trung tâm)
Bỏ qua việc định nghĩa các nhóm nhãn dữ liệu trước khi thực thi thuật toán, việc phân cụm cho phép bạn tìm và phân tích các nhóm hình thành một cách có sắp xếp. Việc chọn số nhóm K là thao tác quan trọng cần quan tâm.
2. Ứng dụng
Thuật toán K-means clustering thường được sử dụng để tìm ra các nhóm mà không được gắn nhãn một cách rõ ràng trong tập dữ liệu. Điều này thường có ý nghĩa trong việc xác nhận tính đúng của các giả thiết về những kiểu nhóm đang tồn tại hay chỉ ra những nhóm chưa biết trong một tập dữ liệu phức tạp. Một khi thuật toán đã chạy và các nhóm đã được định nghĩa, bất kỳ dữ liệu mới nào đều có thể dễ dàng được gắn vào nhóm thích hợp.
Đây là một thuật toán rất phổ biến, được ứng dụng với bất kỳ kiểu phân hoạch, nhóm nào. Một vài ví dụ như sau:
- Một công ty chuyển vận muốn mở chuỗi các trung tâm giao nhận hàng trong một thành phố. Trong tình huống đó họ cần đối mặt với các vấn đề như sau:
+ Họ cần phải phân tích để biết khu vực mà có nhiều đơn đặt hàng thường xuyên.
+ Họ cần biết bao nhiêu trung tâm nên được mở để có thể đảm bảo giao nhận hiệu quả trong một khu vực.
+ Họ cần tìm ra vị trí thích hợp để mở trung tâm trong các khu vực nhằm đảm bảo tối ưu khoảng cách giữa trung tâm và khách hàng của họ.
 |
| [Nguồn từ: Internet] |
+ Phân loại tội phạm dựa trên việc lạm dụng dược chất để tìm ra các nguyên nhân chính.
+ Phân loại tội phạm dựa trên nhóm tuổi.
+ Phân tích dữ liệu để xác định hình thức trung tâm cai nghiện cần xây dựng
+ Tìm ra số lượng trung tâm cai nghiện cần xây dựng để đạt hiệu quả trong việc giãm tỉ lệ tội phạm do nghiện thuốc.
Ngoài ra, việc theo dõi nếu một điểm dữ liệu được giám sát chuyển đổi qua lại giữa các nhóm theo thời gian có thể đem lại thông tin hữu ích trong thay đổi của tập dữ liệu.
3. Thuật toán
 |
| Công thức biểu diễn thuật toán |
Thuật toán K-Means hoạt động dựa vào các bước xử lý theo trình tự:
- Bước 1: Cho dữ liệu đầu vào là một tập S gồm M điểm (mỗi điểm là một phần tử có N thuộc tính (feature), hay có thể gọi là một vector N chiều), và giá trị K (số cluster).
- Bước 2: với mỗi cluster trong K cluster ta cần có một điểm trung tâm (cluster centroid hay Mean), vì vậy ta cần khởi tạo giá trị cho K điểm ngẫu nhiên, mỗi điểm cùng có N thuộc tính và giá trị nằm trong khoảng biên giá trị tương ứng với thuộc tính đó của tập dữ liệu được cho. Đôi khi người ta chỉ đơn giản là chọn ngẫu nhiên K điểm trung tâm từ trong số các điểm dữ liệu thuộc tập được cho.
- Bước 3: Lần lượt kiểm tra và nhóm mỗi điểm trong tập S vào một trong K nhóm mà nó gần nhất (dựa vào sự tương đồng, hay khoảng cách) với điểm trung tâm của nhóm đó.
 |
| Khoảng cách Euclid |
- Bước 4: Cập nhật giá trị của các điểm trung tâm bằng giá trị trung bình của tập điểm trong mỗi nhóm.
- Bước 5: lặp lại bước 3 và 4 cho đến khi giá trị điểm trung tâm không còn thay đổi, khi đó thuật toán kết thúc.
4. Lựa chọn thay thế
Có nhiều thuật toán tương tự có thể được sử dụng để thay thế cho K-mean clustering như DBScan, spectral clustering, và mô hình phức hợp Gaussian (Gaussian mixture), hay một kỹ thuật giảm chiều dữ liệu như PCA (principal component analysis) có thể được dùng để phân nhóm các mẫu (pattern) dữ liệu.
-- BIOZ --