Month: April 2018

Phân cụm Websites với K-MEANS

1.Thuật toán K-MEANS

Thuật toán K-MEANS thuộc nhóm các phương pháp phân cụm dựa vào cụm trung tâm. Thuật toán K-MEANS trong quá trình học không cần giám sát, nghĩa là trước khi chạy không định sẵn các kết quả trả về. Quá trình học, cập nhật và chạy có thể diễn ra đồng thời.Mục tiêu của thuật toán là phân chia tập dữ liệu có sẵn thành k cụm khác nhau với số là số cho trước. Đối với dữ liệu mới cần phân cụm có thể chạy lại thuật toán từ đầu để phân cụm được kết quả tốt nhất, điều này gây mất thời gian do thuật toán sử dụng việc lặp các thao tác tìm cụm trung tâm và tính khoảng cách giữa cụm trung tâm và các phần tử. Trên thực tế, quá trình xác định dữ liệu mới sẽ được phân vào các cụm nào người ta thường dựa trên khoảng cách từ dữ liệu mới tới các cụm trung tâm của lần phân cụm cuối cùng. Sau một khoảng thời gian định trước hoặc số lượng tới hạn dữ liệu mới được thêm, thuật toán K-MEANS sẽ được chạy lại để tăng độ chính xác các cụm.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, hay có thể gọi là một vector N chiều), và giá trị K (số cụm).

Bước 2: Với mỗi cụm trong K cụm ta cần có một điểm trung tâm, 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 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 lại điểm trung tâm của mỗi nhó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à bước 4 cho đến khi giá trị điểm trung tâm không còn thay đổi hoặc sự thay đổi của giá trị điểm trung tâm giữa 2 lần chạy đạt một giá trị epsilon (e) cho trước. Khi đó thuật toán kết thúc, tập dữ liệu đã được phân vào K cụm, mỗi cụm có một điểm trung tâm xác định.

Để việc phân cụm được chính xác và tốc độ phân cụm được nhanh, người ta có thể kết hợp một hoặc nhiều cải tiến sau để nâng cao hiệu quả của thuật toán K-MEANS:

+ Sử dụng K số cụm phù hợp đảm bảo tốc độ và số cụm được phân

+ Chuẩn hóa dữ liệu trước khi phân cụm

+ Chọn các điểm trung tâm ban đầu và số epxilon phù hợp

+ Sử dụng công thức tính độ tương đồng hoặc khoảng cách giữa 2 điểm dữ liệu phù hợp

2.Ứng dụng thuật toán K-MEANS trong phân cụm website

Đối với bài toán phân cụm Website, thuật toán K-MEANS là ứng cử viên hàng đầu để giải bởi tính đơn giản, dễ cài đặt của thuật toán và đặc thù của website là sự phức tạp của dữ liệu. Có nhiều hướng tiếp cận bài toán với thuật toán K-MEANS, sau đây là hướng tiếp cận cơ bản được nhiều nhà nghiên cứu sử dụng:

+ Đối với mỗi website được coi là một điểm dữ liệu, tập dữ liệu M chính là tập các website cần phân cụm.

+ Số thuộc tính (N) của một điểm dữ liệu là tập hợp danh sách các từ khóa, các từ khóa này được lấy có thể dựa vào thuật toán trích trọn đặc trưng từ trang, danh sách các thẻ được gắn, các từ khóa trong thẻ metadata…

+ Để tính khoảng cách giữa các điểm dữ liệu ta có thể sử dụng hoặc sự kết hợp giữa các phương pháp sau: độ tương tự giữa từ với từ, sử dụng độ đo Cosin, lập từ điển từ khoá…

+ Lựa chọn các website lớn làm các điểm trung tâm ban đầu thay vì việc lựa chọn ngẫu nhiên.

3.Khó khăn trong sử dụng K-MEANS để phân cụm website

Trong phân cụm Website, K-means là một lựa chọn tốt nhưng cũng có một số điểm hạn chế cũng như khó khăn nhất trong việc triển khai thực tế như sau:

+ Dữ liệu trên các website ngày càng đa dạng, việc trích lấy danh sách các từ khóa cũng là một chủ đề lớn cần nghiên cứu. Ví dụ việc lấy thông tin từ khóa từ các website chuyên về ảnh, video, âm thanh…

+ Số lượng các website ngày càng lớn, việc chạy thuật toán lặp nhiều lần là cả một vấn đề. Cần đưa ra những chiến lược mới về việc lựa chọn phương pháp đo khoảng cách hiệu quả, áp dụng các thuật toán chạy song song…

+ Một số các website là các trang tin tức nhiều chủ đề, các website mạng xã hội… cần nghiên cứu loại bỏ hoặc sắp xếp sau do những trang này có thể sẽ thuộc vào nhiều cụm sẽ làm thuật toán chạy chậm và kém hiệu quả.

+ Các website ngày càng phát triển nhiều về nội dung đồng nghĩa với việc sẽ có nhiều chủ đề dẫn tới việc phân chia thành các cụm phẳng (đồng mức) làm tăng số cụm. Việc này sẽ không hiệu quả trong thực tế, cần phải nghiên cứu việc phân cụm theo từng mức.