Cluster analysis cực thú vị!


Cluster analysis hay clustering là quá trình phân cụm một tập dữ liệu hay các quan sát thành các tập dữ liệu nhỏ. Mỗi tập dữ liệu nhỏ này đươc gọi là một cụm (cluster), các object trong cùng một cụm sẽ tương tự nhau và các object không cùng một cụm sẽ khác nhau. Câu hỏi đặt ra như thế nào là tương tự nhau và như thế nào là không tương tự nhau?

Ví dụ nhé 😎 : Một người phụ nữ sinh ra 3 đứa trẻ và mọi người đều nói có một đứa trẻ trông khác hai đứa còn lại và cả 3 đứa trẻ đều không giống mẹ. Rồi thình lình xuất hiện hai ông người yêu của bà mẹ. Sau quan sát một hồi thì có hai đứa trẻ ngũ quan gương mặt giống hệt người đàn ông A (centroid 1) và đứa trẻ còn lại giống người đàn ông B (centroid 2) ⇒ chẳng cần xét nghiệm cũng ra kết quả rồi 😉 (Thế là có người có cặp sừng dài vài mét òi 😑).

Ví dụ trên là một minh họa cho “tương tự nhau” trong đó hai người đàn ông có thể được coi là centroid tương ứng của hai cluster và ngũ quan trên gương mặt được coi feature để xác định độ tương đồng giữa các object.

Cluster analysis được sử dụng rộng rãi và ứng dụng trong buisness intelligence, image pattern recognition, web search, biology, security. Trong business intelligence, clustering có thể được sử dụng để phân nhóm khách hàng, ở đây khách hàng trong cùng một nhóm sẽ chia sẻ những đặc trưng tương đồng mạnh mẽ. Điều này tạo điều kiện để phát triển chiến lược kinh doanh phù hợp cho từng nhóm khách hàng, nâng cao quản lý quan hệ khách hàng,…. Hay trong image pattern recognition, clustering cũng có thể được dùng để xác định các cluster hay subclass. Ví dụ như trong bài toán phân lớp chữ số viết tay thì thay vì sử dụng các thuật toán model cao siêu thì cluster cũng có thể dữa vào các đường nét hoặc mảng màu để xác định độ tương đồng giữa các bức ảnh để đưa ra kết quả phân cụm. Nó cũng được ứng dụng trong web search, khi người dùng search một keyword nào đó thì hệ thống sẽ trả về một loạt các kết quả khớp với keyword (số lượng trả về là cực kỳ đồ sộ). Khi đó việc ứng dụng cluster để gom nhóm, tổ chức lại kết quả và hiển thị kết quả theo nhóm là một giải pháp tốt để đưa ra những nhóm kết quả tốt cho người dùng….

Ngoài ra clustering được coi như một data mining function, nó được sử dụng như một tool đọc lập để phân tích hiểu sâu về phân phối của dữ liệu quan sát đặc trưng của dữ liễu trong mỗi cụm. Ngoài ra nó có thể sử dùng như bước tiền xử lý cho các bài toán khác (attribute subset selection, and classification). Clustering có thể được gọi với cái tên khác như automatic classification hay data segmentation. Nó cũng có thể được dùng cho việc xử lý outlier.

Như một nhánh trong statistics, clustering được học một cách chuyên sâu, mục tiêu tập trung vào “distance-based cluster analysis”. Các thuật toán clustering như kmeans, k-medoids, … được xây dựng dựa trên statistical analysis hay một số software package hoặc systems như S-Plus, SPSS hay SAS cũng dựa trên statistical analysis.

Trong machine learning thì cluster analysis được phân vào nhóm unsupervised learning.

Lan man một hồi thế rồi thì mình đi đào sâu hơn một tý xem cluster analysis có gì nhé 😊

Overview of Basic Clustering Methods

Partitioning methods là phương pháp đơn giản và được sử dụng phổ biến nhất. Cho một tập dữ liệu D gồm n objects, k — số cluster, partition algorithms sẽ chia n object vào k cluster (k≤n). Khi đó các object được chia vào k-cluster sẽ đáp ứng điều kiện tương tự nhau trong cùng một cluster và không tương tự nhau nếu nằm trong hai cluster khác nhau (thường sự giống nhau “similar” được đo đếm dựa trên độ đo khoảng cách — có nhiều độ đo khoảng cách được sử dụng cho partitioning methods).

Hai giải thuật partitioning phổ biến nhất là K-means và K-mediods

K-means: A centroid-based technique

Đặt vấn đề: Cho tập D: n objects trong không gian euclidean. Chia D thành k-clusters:$C_1, C_2, … , C_k ( k < n) text trong đó C_i subset D text , C_i cap C_j = empty$ . ( 1≤ i, j ≤ k).

Xây dựng một hàm mục tiêu f (objective function) nhằm mục đích cho độ tương đồng cao trong nội bộ cluster và độ tương đồng thấp giữa hai cluster bất kỳ.

Centroid-based partitioning technique sử dụng centroid của cluster $C_i$ để đại diện cho cluster đó. Centroid được hiểu là điểm trung tâm của cluster và nó thường được xác định là mean hoặc mediod của tập dữ liệu (mean thì chắc mọi người đều biết rồi rồi mediod thì mọi người tự tìm hiểu nhé 😜).

Vì mình xác định trong không gian euclidean nên độ đo dùng để đo lường sự tương đồng giữa các objects (hay points) là euclidean distance.

Chất lượng cụm được đo lường đánh giá bằng một cost function, hàm cost function sử dụng là sum of squared error.

$E = sum_i=1^k sum_p in C_i dist(p, c_i)²$

Trong đó:

$c_i: text centroid of cluster$

$p: textis the point in space representing a given object (multidimentional)$

Mục tiêu của object funtion là cố gắng trả về k-clusters với mong muốn k-clusters là các tập compact (càng tacts biệt càng tốt).

Vậy vấn đề cần đưa ra là làm sao để tối ưu objective function??? Nó thực sự là một thách thức rất lơn đó ☹️ trong trường hợp tệ nhất chúng ta phải liệt kê các phân vùng theo cấp số nhân và kiểm tra giá trị biến thiên trong mỗi lần liệt kê. ⇒ Bài toán này là bài toán NP-khó (xin là xin vĩnh biệt cụ 😰). Nếu dữ liệu cần phân làm k-clusters, dimention=d thì thời gian giải bài toán $O(n^dk+1 logn)$.

Lan man một hồi thì cũng chưa ra vấn đề gì cả 🤟 vậy túm cái quần lại thì k-means hoạt động như thế nào 🤭.

Các bước xử lý k-means clustering:

Bước 1: Chọn random k-points làm centroid cho k-clusters từ n_points.

Bước 2: Mỗi object sẽ được gán vào một cluster mà nó tương tự với centroid của cluster đó nhất. Và độ đo sự tương đồng là dựa vào khoảng cách euclidean giữa nó và centroid của cluster nó được phân.

Bước 3: Cái thiện objective function (tối ưu hóa hàm mục tiêu — chính là tối ưu hóa hàm cost function được định nghĩa ở trên).

Cập nhật lại centroid của mỗi cluster bằng mean value ⇒ lặp lại bước 2

Điệu kiện dừng:

Cách 1: Cost function < threshold (thường không được dùng)Cách 2: Các cluster không đổi sau khi cập nhật và tính toán phân cụm lại

Nhìn vào hoạt động của K-means bạn có thấy điều gì đặc biệt cần chú ý không?

Nếu không có gì cần chú ý hoặc thấy nó hoàn hảo thì bạn có thể bê nó đi và dùng ngay được rồi 😉 Còn nếu bạn có cùng suy nghĩ vấn đề giống như mình thì chúng ta sẽ đi tiếp 🙏.

k-Medoids: A Representative Object-Based Technique

Nhược điểm của K-means là rất nhạy cảm với outlier. Lý do K-means nhạy cảm với outlier là gì??? Làm thế nào để giảm bớt ảnh hưởng của outlier lên model?

Yes! Chính nó thay vì chúng ta tính mean value để xác định centroid của cluster vậy tại sao chúng ta không dùng dữ liệu thực tế làm centroid 🥲.

Hàm cost function được sử dụng: absolute-error criterion

$E = sum_i=1^k sum_p in C_i dist(p, o_i)$

Trong đó:

E: gọi là tiêu chuẩn lỗi tuyệt đối          $o_i: \text là điểm đại diện cho cluster$

Mấy cái thay đổi nho nhỏ này so với K-means đã tạo ra K-medoids giải quyết vấn đề outlier tương đối tốt mà vẫn dễ hiểu như K-means vậy 😎. (Tuy nhiên thì nó vẫn là bài toán NP-khó thôi ⇒ dữ liệu mà lớn thì kết quả cũng không quá tốt đâu, độ phức tạp tính toán cũng sẽ phức tạp hơn k-means).

Partitioning Around Medoids (PAM) Algorithm là giải thuật phổ biến đuộc sử dụng trong K-medoids

Các bước xử lý K-medoids clustering:

Bước 1: Chọn random k-points làm đại diện cho k-clusters từ n_points. (người ta gọi những điểm này là seed). ^^

Bước 2: Repeat.

  • Từ k-points ta xây dựng k-clusters với các điểm tương tự điểm đại diện nhất (cơ chế giống K-means hôi). ^_^
  • Chọn random một điểm không phải điểm đại diện trong tập dữ liệu làm điểm đại diện tạm thời $c_i$ với hy vọng là điểm đại diện thay thế tốt cho điểm đại diện $o_i$ từ tập k-points.
  • Tính toán tổng cost S dùng để quyết định hoán đổi $c_i text với o_i$.
  • Nếu S<0 thì hoán đổi $c_i text cho o_i$ , S≥0 giữ nguyên $o_i$.

Bước 3: Tiêu chí hội tụ (tương tự như K-means

Độ phức tạp tính toán: $O(k(n-k)²)$

Cả k-means và k-mediods (PAM) đều làm việc không tốt trên dữ liệu lớn ⇒ Vậy có giải pháp nào thay thế để giải thuật có thể làm tốt trên dữ liệu lớn không?

Đó là lý do Clustering LARge Applications (CLARA) được tìm thấy để phần nào giải quyết vấn đề này. Thay vì nó xử lý trên toàn bộ dữ liệu như k-means và k-mediods (PAM) thì nó sẽ sử dụng random sample trên tập dữ liệu. Sau đó trên mỗi mẫu sẽ sử dụng PAM để phân cụm. (Vấn đề chọn mẫu như thế nào để có thể đại diện cho toàn bộ tập dữ liệu cũng là một thách thức không nhỏ cho thuật toán này — trong nhiều trường hợp, một mẫu lớn hoạt động tốt nếu nó được tạo ra để mỗi object có xác suất được chọn vào mẫu là bằng nhau). CLARA xây dựng các nhóm từ nhiều random samples và trả lại nhóm tốt nhất làm đầu ra.

Độ phức tạp tính toán: $O(ks²+k(n-k))$

Trong đó: s là size của sample, k số cluster, n tổng dữ liệu.

Chú ý: Hiệu quả của CLARA phụ thuộc vào chất lượng random sample. Do đó nhược điểm to đùng của CALRA là tính toán trên random sample thay vì trên toàn bộ dữ liệu như PAM vì vậy, nếu tập mẫu bị lệch và không đại diện tốt cho toàn bộ dữ liệu thì kết quả phân cụm có thể là cực kỳ tồi.

How might we improve the quality and scalability of CLARA?

Clustering Large Applications based upon RANdomized Search (CLARANS ): nó đại diện cho việc đánh đổi giữa chi phí và hiểu quả sử dụng samples để đạt được kết quả phân cụm tốt

Đầu tiên nó sẽ chọn random k objects trong tập dữ liệu làm mediods. Sau đó nó sẽ chọn một mediod hiện tại x và một điểm không phải mediod y. Có thể thay thế x bằng y nếu absolute-error không được cải thiện. CLARANS sẽ thực hiện tìm kiếm như vậy l lần. Bộ mediods sau l lần tìm kiếm được gọi là local optimum. CLARANS sẽ lặp lại điều này m lần và trả về local optimal như kết quả cuối cùng.

Thuật toán yêu cầu numlocal (số lần lặp để giải quyết vấn đề), maxneighbor (số lân cận tối đa được kiểm tra) và không dduwowcj kieemr tra của các cụm được tạo thành (k) làm đầu vào.

Sau đó, bắt đầu lặp lại, i được đặt thành 1, trước đó mincost (là chi phí tối ưu) được đặt thành vô hạn và bestnode (medoids tối ưu) được đặt thành bộ giá trị trống.

Bây giờ k điểm dữ liệu ngẫu nhiên được chọn làm medoid hiện tại và các cụm được hình thành bằng cách sử dụng các điểm dữ liệu này (Khoảng cách Euclid có thể được sử dụng để tìm medoid gần nhất để tạo thành cụm).

Sau khi vòng lặp mới này bắt đầu, trong đó j được đặt thành 1. Một medoid hiện tại được chọn ngẫu nhiên và một điểm dữ liệu mediod tạm thời ngẫu nhiên (hàng xóm ngẫu nhiên) được chọn để thay thế bằng medoid hiện tại. Nếu việc thay thế điểm dữ liệu mediod tạm thời mang lại TotalCost thấp hơn so với TotalCost của mediod hiện tại thì việc thay thế sẽ được thực hiện. Nếu việc thay thế được thực hiện thì j không được tăng lên, ngược lại j = j +1.

Khi j> maxneighbor, thì các medoid hiện tại được lấy và Tổng chi phí của chúng được so sánh với mincost. Nếu TotalCost nhỏ hơn mincost, thì Bestnode được cập nhật dưới dạng medoid hiện tại.

i được tăng dần sau đó và nếu nó lớn hơn numlocal, thì Bestnode được đưa ra làm đầu ra, nếu không thì toàn bộ quá trình sẽ được lặp lại.

Cuối cùng chúng ta so sánh một chút về partitioning methods nhé:

https://www.youtube.com/watch?v=GApaAnGx3Fw&ab_channel=OmarSobh

https://medium.com/analytics-vidhya/partitional-clustering-using-clarans-method-with-python-example-545dd84e58b4

https://towardsdatascience.com/machine-learning-birch-clustering-algorithm-clearly-explained-fb9838cbeed9#:~:text=At a high level%2C Balanced,instead of the original dataset.

https://towardsdatascience.com/machine-learning-birch-clustering-algorithm-clearly-explained-fb9838cbeed9#:~:text=At a high level%2C Balanced,instead of the original dataset.

https://core.ac.uk/download/pdf/231160447.pdf

Jiawei_Han_Micheline_Kamber_Jian_Pei_Data_Minib-ok.xyz.pdf



Source link

Leave a Reply

Your email address will not be published. Required fields are marked *

Previous Article

Bellator 281 Results: MVP vs. Storley

Next Article

Cotton (CT) Nearing Weekly Chart Ascending Wedge Support

Related Posts