Hướng dẫn dùng heirarchical clustering python - using python clustering phân cấp
Chiến lược hợp nhất sẽ bắt đầu biểu diễn mỗi quan sát là một cụm đơn lẻ. Gỉa định chúng ta có \(N\) quan sát, thuật toán cần thực hiện \(N-1\) bước để hợp nhất hai nhóm có khoảng cách gần nhất lại với nhau và đồng thời giảm số lượng cụm trước khi chúng đạt được tới node gốc gồm toàn bộ các quan sát. Như vậy câu hỏi đặt ra đó là:\(N\) quan sát, thuật toán cần thực hiện \(N-1\) bước để hợp nhất hai nhóm có khoảng cách gần nhất lại với nhau và đồng thời giảm số lượng cụm trước khi chúng đạt được tới node gốc gồm toàn bộ các quan sát. Như vậy câu hỏi đặt ra đó là: Show
Nội dung chính
Nội dung chính
Khi nào thì thuật toán sẽ dừng? Hình minh hoạ bên dưới về chiến lược hợp nhất sẽ được sử dụng để làm rõ điều này:: Hình minh hoạ các bước được thực hiện trên thuật toán phân cụm phân cấp sử dụng chiến lược hợp nhất đối với 6 điểm dữ liệu \(\{A, B, C, D, E, F\}\). Chấm tròn thể hiện cho các điểm dữ liệu, chấm tròn có dấu x ở giữa là tâm của các cụm. Các đường elipse bao ngoài thể hiện cho các điểm được phân về cùng một cụm. Ở bên phải dưới cùng của mỗi hình là đồ thị dendrogram thể hiện sự gộp nhóm. Hình 2: Hình minh hoạ các bước được thực hiện trên thuật toán phân cụm phân cấp sử dụng chiến lược hợp nhất đối với 6 điểm dữ liệu \(\{A, B, C, D, E, F\}\). Chấm tròn thể hiện cho các điểm dữ liệu, chấm tròn có dấu x ở giữa là tâm của các cụm. Các đường elipse bao ngoài thể hiện cho các điểm được phân về cùng một cụm. Ở bên phải dưới cùng của mỗi hình là đồ thị dendrogram thể hiện sự gộp nhóm.
Step 5: Gộp cả 2 cụm \(\{A, B, C\}\) và \(\{D, E, F\}\) ta thu được cụm cuối cùng là node gốc bao trùm toàn bộ dữ liệu. 14.2. Khoảng cách giữa hai cụm?¶Như vậy chúng ta đã hình dung ra chiến lược nhóm cụm rồi chứ? Chung qui lại xuất phát từ node lá, thuật toán gộp dần thành các cụm theo chiều từ dưới lên trên. Sau đó sẽ thực hiện truy hồi việc gộp cụm (cụm ở đây có thể gồm một điểm hoặc nhiều điểm). Khoảng cách giữa hai cụm được đo lường thông qua một thước đo sẽ được làm rõ hơn ở bên dưới, trong ví dụ này chính là khoảng cách trong không gian euclidean giữa tâm của mỗi cụm. Trong đó tâm cụm được xác định bằng trung bình cộng của các quan sát bên trong cụm.không trùng nhau là \(\mathcal{S}_1 = \{ \mathbf{x}_i^{(1)}\}_{i=1}^{N_1}\) và \(\mathcal{S}_2 = \{ \mathbf{x}_j^{(2)} \}_{j=1}^{N_2}\). Khoảng cách giữa hai cụm chính là sự khác biệt giữa chúng. Có những phương pháp giúp xác định khoảng cách giữa hai cụm như sau:
\[d(\mathbf{m}_1,\mathbf{m}_2) = d(\mathbf{m}_2,\mathbf{m}_1) = \sqrt{(m_{1}^{(1)} -m_1^{(2)})^2 + (m_2^{(1)} - m_2^{(2)})^2 + \cdots + (m_n^{(1)} -m_n^{(2)})^2} = \sqrt{\sum_{i=1}^{n} (m_i^{(1)}-m_i^{(2)})^2} \] Thuật toán ward linkage cũng chỉ được sử dụng trong điều kiện giả định các quan sát nằm trong không gian euclidean. Tiếp theo ta sẽ chứng minh công thức mức độ suy giảm phương sai theo khoảng cách giữa hai tâm cụm. Giả sử \(\mathbf{m}, \mathbf{m}_1, \mathbf{m}_2\) lần lượt là trung bình của tâm cụm cha \(\{\mathcal{S}_1, \mathcal{S}_2\}\), và hai cụm con \(\mathcal{S}_1\) và \(\mathcal{S}_2\). Khi đó thước đo khoảng cách ward linkage có công thức như sau:\(\mathbf{m}, \mathbf{m}_1, \mathbf{m}_2\) lần lượt là trung bình của tâm cụm cha \(\{\mathcal{S}_1, \mathcal{S}_2\}\), và hai cụm con \(\mathcal{S}_1\) và \(\mathcal{S}_2\). Khi đó thước đo khoảng cách ward linkage có công thức như sau: \[\begin{split}\begin{eqnarray}d(\mathcal{S}_1, \mathcal{S}_2) & = & \sum_{\mathbf{x}_i \in \mathcal{S_1} \cup \mathcal{S}_2} \| \mathbf{x}_i-\mathbf{m} \|^2 - \sum_{\mathbf{x}_i \in \mathcal{S}_1} \| \mathbf{x}_i - \mathbf{m}_1\|^2 - \sum_{\mathbf{x}_i \in \mathcal{S}_2} \| \mathbf{x}_i - \mathbf{m}_2\|^2 \\ & = & \frac{N_1 N_2}{N_1 + N_2} \| \mathbf{m}_1 - \mathbf{m}_2 \|^2 \\ & = & \frac{N_1 N_2}{N_1 + N_2} d(\mathbf{m}_1, \mathbf{m}_2) \tag{1} \end{eqnarray}\end{split}\] Ta có thể chứng minh công thức \((1)\) như sau:\((1)\) như sau: \[\begin{split}\begin{eqnarray}d(\mathcal{S}_1, \mathcal{S}_2) & = & \sum_{\mathbf{x}_i \in \mathcal{S_1} \cup \mathcal{S}_2} \| \mathbf{x}_i-\mathbf{m} \|^2 - \sum_{\mathbf{x}_i \in \mathcal{S}_1} \| \mathbf{x}_i - \mathbf{m}_1\|^2 - \sum_{\mathbf{x}_i \in \mathcal{S}_2} \| \mathbf{x}_i - \mathbf{m}_2\|^2 \\ & = & \sum_{\mathbf{x}_i \in \mathcal{S}_1}[ \| \mathbf{x}_i - \mathbf{m}\|^2 - \| \mathbf{x}_i - \mathbf{m}_1\|^2] + \sum_{\mathbf{x}_i \in \mathcal{S}_2}[ \| \mathbf{x}_i - \mathbf{m}\|^2 - \| \mathbf{x}_i - \mathbf{m}_2\|^2] \\ & = & \sum_{\mathbf{x}_i \in \mathcal{S}_1} (2 \mathbf{x}_i - \mathbf{m} - \mathbf{m}_1)(\mathbf{m}_1-\mathbf{m}) + \sum_{\mathbf{x}_i \in \mathcal{S}_2} (2 \mathbf{x}_i - \mathbf{m} - \mathbf{m}_2)(\mathbf{m}_2-\mathbf{m}) \\ & = & (2 \underbrace{\sum_{\mathbf{x}_i \in \mathcal{S}_1}\mathbf{x}_i}_{N_1 \mathbf{m}_1} - N_1 \mathbf{m} - N_1 \mathbf{m}_1)(\mathbf{m}_1-\mathbf{m}) + (2 \underbrace{\sum_{\mathbf{x}_i \in \mathcal{S}_2} \mathbf{x}_i}_{N_2\mathbf{m}_2} - N_2\mathbf{m} - N_2\mathbf{m}_2)(\mathbf{m}_2-\mathbf{m})\\ & = & N_1 (\mathbf{m}_1 - \mathbf{m})^2+N_2(\mathbf{m}_2-\mathbf{m})^2 \\ & = & N_1 (\mathbf{m}_1 - \frac{N_1\mathbf{m}_1 + N_2\mathbf{m}_2}{N_1 + N_2})^2+N_2(\mathbf{m}_2-\frac{N_1\mathbf{m}_1 + N_2\mathbf{m}_2}{N_1 + N_2})^2 \\ & = & \frac{N_1N_2}{N_1 + N_2} \|\mathbf{m}_1 - \mathbf{m}_2\|^2 \end{eqnarray}\end{split}\] Công thức \((1)\) cho thấy việc phân cụm luôn khiến phương sai dữ liệu giảm. Tuy nhiên mức độ suy giảm nhiều hay ít sẽ phụ thuộc và khoảng cách tâm (centroids) giữa hai cụm. Nếu hai tâm cách xa nhau thì giá trị giảm của phương sai sau khi phân cụm càng lớn. Trái lại nếu tâm giữa hai cụm càng sát nhau, các cụm có xu hướng chồng lấn và không rõ ràng thì sau khi phân chia phương sai của cụm giảm không đáng kể. Trường hợp này tiếp tục phân chia cũng không có nhiều ý nghĩa, thậm chí có thể phá vỡ qui luật phân phối tổng quát của một cụm. Mức độ suy giảm phương sai cũng tỷ lệ thuận với khoảng cách giữa hai tâm được tính theo trung bình. Trường hợp này tâm còn gọi là centroids để phân biệt với clusteroids được giới thiệu bên dưới.\((1)\) cho thấy việc phân cụm luôn khiến phương sai dữ liệu giảm. Tuy nhiên mức độ suy giảm nhiều hay ít sẽ phụ thuộc và khoảng cách tâm (centroids) giữa hai cụm. Nếu hai tâm cách xa nhau thì giá trị giảm của phương sai sau khi phân cụm càng lớn. Trái lại nếu tâm giữa hai cụm càng sát nhau, các cụm có xu hướng chồng lấn và không rõ ràng thì sau khi phân chia phương sai của cụm giảm không đáng kể. Trường hợp này tiếp tục phân chia cũng không có nhiều ý nghĩa, thậm chí có thể phá vỡ qui luật phân phối tổng quát của một cụm. Mức độ suy giảm phương sai cũng tỷ lệ thuận với khoảng cách giữa hai tâm được tính theo trung bình. Trường hợp này tâm còn gọi là centroids để phân biệt với clusteroids được giới thiệu bên dưới. Trong nhiều trường hợp khi dữ liệu không tồn tại trong không gian euclidean (non-euclidean) thì chúng ta không thể tính toán được tâm của từng cụm theo trung bình toàn bộ các điểm trong cụm. Khi đó tâm cụm sẽ được xác định là một điểm nằm trong cụm sao cho có trung bình khoảng cách tới những điểm khác trong cùng cụm là nhỏ nhất. Như vậy ta đã thay thế trung bình bằng một điểm dữ liệu thực tế, những điểm này còn được gọi là clustroids. Ngoài phương pháp Ward linkage, để đo lường sự không tương đồng giữa các cụm còn có những phương pháp sau đây:
\[d(\mathcal{S}_1, \mathcal{S}_2) = \min_{\mathbf{x}_i \in \mathcal{S}_1, \mathbf{x}_j \in \mathcal{S}_2}d(\mathbf{x}_i^{(1)}, \mathbf{x}_j^{(2)})\] Phương pháp này còn được gọi dưới một tên khác là nearest-neighbor. Tức là đo lường khoảng cách cụm thông qua 2 điểm gần nhau nhất thuộc mỗi cụm.
\[d(\mathcal{S}_1, \mathcal{S}_2) = \max_{\mathbf{x}_i \in \mathcal{S}_1, \mathbf{x}_j \in \mathcal{S}_2}d(\mathbf{x}_i^{(1)}, \mathbf{x}_j^{(2)})\]
\[d(\mathcal{S}_1, \mathcal{S}_2) = \frac{1}{N_1 N_2}\sum_{i=1}^{N_1} \sum_{j=1}^{N_2}d(\mathbf{x}_i^{(1)}, \mathbf{x}_j^{(2)})\] Cả bốn phương pháp ward linkage, sinlge linkage, complete linkage, group average đều giúp tạo ra một thước đo về sự không tương đồng hay chính là khoảng cách giữa hai cụm. Khi giữa các cụm có sự tách biệt thể hiện qua phân phối dữ liệu và đường biên phân chia rõ rệt thì kết quả trả về \(d(\mathcal{S}_1, \mathcal{S}_2)\) đều thu được lớn và trái lại. Tuy nhiên phương pháp single linkage và complete linkage thường bị ảnh hưởng bởi những điểm dữ liệu outliers. Chẳng hạn hai cụm rất cách xa nhau nhưng do hai điểm outliers của chúng lại rất gần nhau có thể trả về một khoảng cách theo single linkage rất bé. Một tình huống khác, khi hai cụm rất gần nhau nhưng do hai điểm outliers của chúng rất xa nên khoảng cách được đo theo complete linkage lại rất lớn. trong khi đó ward linkage và group average ít bị ảnh hưởng bởi outliers hơn. Tuy nhiên ward linkage lại chỉ có thể hoạt động khi các điểm dữ liệu tồn tại trong không gian euclidean.\(d(\mathcal{S}_1, \mathcal{S}_2)\) đều thu được lớn và trái lại. Tuy nhiên phương pháp single linkage và complete linkage thường bị ảnh hưởng bởi những điểm dữ liệu outliers. Chẳng hạn hai cụm rất cách xa nhau nhưng do hai điểm outliers của chúng lại rất gần nhau có thể trả về một khoảng cách theo single linkage rất bé. Một tình huống khác, khi hai cụm rất gần nhau nhưng do hai điểm outliers của chúng rất xa nên khoảng cách được đo theo complete linkage lại rất lớn. trong khi đó ward linkage và group average ít bị ảnh hưởng bởi outliers hơn. Tuy nhiên ward linkage lại chỉ có thể hoạt động khi các điểm dữ liệu tồn tại trong không gian euclidean. 14.3. Chiến lược phân chia (divisive)¶Chiến lược phân chia chưa được nghiên cứu và phát triển rộng rãi trong các bài toán phân cụm như hợp nhất. Trong sklearn cũng chưa có module phát triển cho phương pháp này. Nó được giới thiệu lần đầu trong một tài liệu của Gersho và Grey, 1992 về kĩ thuật nén. Chiến lược phân chia sẽ bắt đầu từ một cụm gồm toàn bộ các quan sát bên trong cụm và sau đó phân chia đệ qui những cụm đang tồn tại thành hai cụm con tại mỗi bước theo hướng top-down. Đầu tiên thuật toán sẽ chọn ra một điểm từ toàn bộ tập dữ liệu \(\mathcal{S}\) sao cho điểm này thoả mãn điều kiện trung bình khoảng cách từ điểm đó tới toàn bộ những điểm còn lại là nhỏ nhất. Chúng ta đưa điểm này vào tập \(\mathcal{S}_1\), tập còn lại gồm \(N-1\) điểm là tập \(\mathcal{S}_2\). Tiếp theo ta sẽ thực hiện các lượt phân chia sao cho mỗi một lượt lựa chọn ra một điểm \(\mathbf{x}_i\) từ tập \(\mathcal{S}_2\) đưa sang \(\mathcal{S}_1\). Điểm này cần thoả mãn hai điều kiện:\(\mathcal{S}\) sao cho điểm này thoả mãn điều kiện trung bình khoảng cách từ điểm đó tới toàn bộ những điểm còn lại là nhỏ nhất. Chúng ta đưa điểm này vào tập \(\mathcal{S}_1\), tập còn lại gồm \(N-1\) điểm là tập \(\mathcal{S}_2\). Tiếp theo ta sẽ thực hiện các lượt phân chia sao cho mỗi một lượt lựa chọn ra một điểm \(\mathbf{x}_i\) từ tập \(\mathcal{S}_2\) đưa sang \(\mathcal{S}_1\). Điểm này cần thoả mãn hai điều kiện:
\[\mathbf{x}_i = \arg \max_{\mathbf{x}_i} \frac{1}{|\mathcal{S}_1|-1} \sum_{j=1, j \neq i}^{|\mathcal{S}_1|} d(\mathbf{x}_i, \mathbf{x}_j)\]
\[d(\mathbf{x}_i, \mathcal{S}_1) \geq d(\mathbf{x}_i, \mathcal{S}_2)\] Trong đó: \[d(\mathbf{x}_i, \mathcal{S}_k) = \min_{\mathbf{x}_j, \mathbf{x}_j \in \mathcal{S}_k} d(\mathbf{x}_i, \mathbf{x}_j)\] Qúa trình chuyển cụm sẽ kết thúc khi không còn điểm nào thoả mãn hai điều kiện trên. Khi đó chúng ta lại thực hiện đệ qui lại quá trình trên trên từng tập \(\mathcal{S}_1\) và \(\mathcal{S}_2\).\(\mathcal{S}_1\) và \(\mathcal{S}_2\). Chúng ta cùng diễn giải lại quá trình này thông qua hình minh hoạ bên dưới: Hình 3: Hình minh hoạ phương pháp phân chia trong thuật toán phân cụm phân cấp. Ở bước 1 chúng ta sẽ lựa chọn ra điểm \(C\) là điểm đầu tiên thuộc cụm mới dựa trên khoảng cách so với các điểm còn lại là xa nhất. Sau bước 1 ta thu được tập \(\mathcal{S}_1 = \{ C \}\) và \(\mathcal{S}_2 = \{A, B, D, E, F\}\). Tại bước 2 lựa chọn trong số các điểm thuộc \(\mathcal{S}_2\) ra điểm mà có khoảng cách xa nhất so với những điểm còn lại sao cho điểm này gần với \(C\) hơn so với các điểm thuộc tập \(\mathcal{S}_2\), đó chính là diểm \(A\). Di chuyển điểm này sang \(\mathcal{S}_1\). Bước 3 chúng ta lại tiếp tục thực hiện như vậy và lựa chọn được điểm \(B\) để đưa sang \(\mathcal{S}_1\). Ở bước thứ 4 ta sẽ dừng quá trình chuyển cụm cho các điểm thuộc \(\mathcal{S}_2\) vì thuật toán đã đạt sự hội tụ về hai cụm. Khi đó ta lại tiếp tục tiến hành đệ qui thuật toán trên từng cụm con. Hình minh hoạ phương pháp phân chia trong thuật toán phân cụm phân cấp. Ở bước 1 chúng ta sẽ lựa chọn ra điểm \(C\) là điểm đầu tiên thuộc cụm mới dựa trên khoảng cách so với các điểm còn lại là xa nhất. Sau bước 1 ta thu được tập \(\mathcal{S}_1 = \{ C \}\) và \(\mathcal{S}_2 = \{A, B, D, E, F\}\). Tại bước 2 lựa chọn trong số các điểm thuộc \(\mathcal{S}_2\) ra điểm mà có khoảng cách xa nhất so với những điểm còn lại sao cho điểm này gần với \(C\) hơn so với các điểm thuộc tập \(\mathcal{S}_2\), đó chính là diểm \(A\). Di chuyển điểm này sang \(\mathcal{S}_1\). Bước 3 chúng ta lại tiếp tục thực hiện như vậy và lựa chọn được điểm \(B\) để đưa sang \(\mathcal{S}_1\). Ở bước thứ 4 ta sẽ dừng quá trình chuyển cụm cho các điểm thuộc \(\mathcal{S}_2\) vì thuật toán đã đạt sự hội tụ về hai cụm. Khi đó ta lại tiếp tục tiến hành đệ qui thuật toán trên từng cụm con. 14.4. Điều kiện dừng của thuật toán phân cụm¶Qúa trình phân cụm theo cả hai chiến lược phân chia và hợp nhất đều thu được một đồ thị dendrogram dạng cây nhị phân. Mỗi một node trong cây nhị phân sẽ xác định một cụm dữ liệu. Nhưng làm thế nào để xác định khi nào sẽ ngừng tiếp tục phân chia hoặc hợp nhất đối với một node để tạo thành kết quả phân cụm khái quát. Bên dưới là những phương pháp chính giúp xác định quá trình dừng phân cụm:
14.5. Độ phức tạp của thuật toán phân cụm phân cấp¶Trong thuật toán phân cụm phân cấp tại mỗi bước chúng ta cần phải tính khoảng cách cho từng cặp điểm trong cùng một cụm và cặp điểm thuộc hai cụm là hai tập vách ngăn (partition set). Như vậy độ phức tạp tính toán sẽ là \(O(N^2)\) trên mỗi bước, trong đó \(N\) là số lượng quan sát. Chúng ta lặp lại \(N\) bước cho từng điểm dữ liệu nên độ phức tạp tính toán của thuật toán sẽ là \(O(N^3)\). Đây là một chi phí tính toán không hề nhỏ đối với những bộ dữ liệu lớn. Do đó chúng ta chỉ nên áp dụng thuật toán phân cụm phân cấp đối với những bộ dữ liệu nhỏ kích thước dưới vài chục nghìn quan sát.\(O(N^2)\) trên mỗi bước, trong đó \(N\) là số lượng quan sát. Chúng ta lặp lại \(N\) bước cho từng điểm dữ liệu nên độ phức tạp tính toán của thuật toán sẽ là \(O(N^3)\). Đây là một chi phí tính toán không hề nhỏ đối với những bộ dữ liệu lớn. Do đó chúng ta chỉ nên áp dụng thuật toán phân cụm phân cấp đối với những bộ dữ liệu nhỏ kích thước dưới vài chục nghìn quan sát. Ngoài ra khi triển khai thuật toán, nếu khéo léo sử dụng ưu tiên queue thì có thể giảm độ phức tạp xuống \(O(N^2\log N)\). Tuy nhiên hiệu quả về chi phí tính toán (computational complexity) thường đánh đổi bằng sự gia tăng chi phí lưu trữ (space complexity). Trường hợp này chi phí lưu trữ vẫn rất tốn kém đối với những bộ dữ liệu vượt quá kích thước lưu trữ của bộ nhớ.\(O(N^2\log N)\). Tuy nhiên hiệu quả về chi phí tính toán (computational complexity) thường đánh đổi bằng sự gia tăng chi phí lưu trữ (space complexity). Trường hợp này chi phí lưu trữ vẫn rất tốn kém đối với những bộ dữ liệu vượt quá kích thước lưu trữ của bộ nhớ. 14.6. Thực hành phân cụm phân cấp¶Đầu tiên chúng ta cần import các packages cần thiết được sử dụng trong bài toán phân loại. Trong sklearn, thuật toán phân cụm phân cấp được phát triển dựa trên chiến lược hợp nhất thông qua class sklearn.cluster.AgglomerativeClustering. import pandas as pd from sklearn.cluster import AgglomerativeClustering from sklearn.preprocessing import MinMaxScaler import scipy.cluster.hierarchy as shc import matplotlib.pyplot as plt import matplotlib.patheffects as PathEffects import seaborn as sns import numpy as np Để minh hoạ thuật toán phân cụm, chúng ta sử dụng dữ liệu shopping data. Bộ dữ liệu này mô tả hành vi mua sắm của những khách hàng theo giới tính, độ tuổi, thu nhập hàng năm và điểm số mua sắm của họ. data = pd.read_csv("https://raw.githubusercontent.com/phamdinhkhanh/datasets/cf391fa1a7babe490fdd10c088f0ca1b6d377f59/shopping-data.csv", header=0, index_col=0) print(data.shape) data.head()
Để đơn giản hoá, chúng ta chỉ sử dụng hai thông tin chính là thu nhập và điểm mua sắm để xây dựng mô hình. Trước tiên cần biểu đồ hoá dữ liệu shopping để nhận biết khái quát qui luật của các cụm. # Lấy ra thu nhập va điểm shopping X = data.iloc[:, 2:4].values print(X.shape) # Biểu đồ hoá các điểm dữ liệu trên đồ thị scatter plot plt.figure(figsize=(12, 8)) plt.scatter(X[:,0], X[:,1], lw=0, s=40) plt.xlabel('Annual Income k$') plt.ylabel('Spending Score') plt.title('Distribution of Shopping Dataset') Text(0.5, 1.0, 'Distribution of Shopping Dataset') Ta nhận thấy sự phân bố của dữ liệu có thể được chia thành 5 cụm khác nhau. Trong đó có 1 cụm ở trung tâm và 4 cụm còn lại nằm ở 4 góc. Trước khi tiến hành xây dựng mô hình phân cụm, chúng ta cần chuẩn hoá giữ liệu để loại bỏ sự khác biệt về mặt đơn vị giữa các chiều. Phương pháp chuẩn hoá được áp dụng là MinMaxScaler. std = MinMaxScaler() X_std = std.fit_transform(X) 14.6.1. Biểu đồ dendrogram¶Trong phương pháp phân cụm phân cấp, biểu đồ dendrogram có thể giúp xác định được số lượng cụm được phân chia hợp lý. Bằng cách vẽ một đường thẳng nằm ngang tương ứng với một mức độ khác biệt của các cụm, ta có thể xác định được có bao nhiêu cụm được phân chia có level nằm bên dưới đoạn thẳng này. Số lượng các điểm dữ liệu trong từng cụm cũng được thể hiện trong biểu đồ. Mức độ khác biệt giữa các cụm sẽ được thể hiện qua độ cao của các node. Một biểu đồ mà có các cụm bên dưới nằm thấp hơn so với các cụm bên trên thì thường là những bộ dữ liệu mà phương pháp phân cụm phân cấp đã xác định được qui luật phân cụm tổng quát. Tiếp theo ta sẽ vẽ biểu đồ dendrogram để nhận biết các cụm cần phân chia. Để vẽ biểu đồ này chúng ta sử dụng package data = pd.read_csv("https://raw.githubusercontent.com/phamdinhkhanh/datasets/cf391fa1a7babe490fdd10c088f0ca1b6d377f59/shopping-data.csv", header=0, index_col=0) print(data.shape) data.head()1. Phương pháp được sử dụng để xác định các cụm là Ward linkage. plt.figure(figsize=(20, 7)) plt.title("Customer Dendograms") dend = shc.dendrogram(shc.linkage(X, method='ward')) plt.axhline(200, linestyle='--') plt.xlabel('sample indice') plt.ylabel('dissimilarity metric cluster') Text(0, 0.5, 'dissimilarity metric cluster') Trong biểu đồ dendogram mà bạn nhìn thấy ở trên, trục hoành (horizontal axis) là thứ tự index của các quan sát trong bộ dữ liệu gốc, trục tung (vertical axis) thể hiện mức độ khác biệt giữa các cụm được tính toán thông qua thước đo sự khác biệt, trong biểu đồ trên chính là khoảng cách cụm được tính theo phương pháp Ward linkage. Nhìn vào đồ thị dendrogram ta có thể dễ dàng xác định được rằng với cùng một giá trị mức độ khác biệt là 200 thì chúng ta có thể tạo thành 5 cụm phân biệt. 14.6.2. Xây dựng mô hình phân cụm phân cấp hợp nhất¶Để xây dựng biểu đồ phân cụm phân cấp theo phương pháp hợp nhất chúng ta sử dụng class sklearn.cluster.AgglomerativeClustering. Trong class này chúng ta cần khai báo các thông tin: AgglomerativeClustering( n_clusters=2, affinity='euclidean', compute_full_tree='auto', linkage='ward', distance_threshold=None, compute_distances=False) Trong đó data = pd.read_csv("https://raw.githubusercontent.com/phamdinhkhanh/datasets/cf391fa1a7babe490fdd10c088f0ca1b6d377f59/shopping-data.csv", header=0, index_col=0) print(data.shape) data.head()2 là số lượng cụm cần phân chia. data = pd.read_csv("https://raw.githubusercontent.com/phamdinhkhanh/datasets/cf391fa1a7babe490fdd10c088f0ca1b6d377f59/shopping-data.csv", header=0, index_col=0) print(data.shape) data.head()3 là phương pháp tính khoảng cách giữa các quan sát. Đây có thể là bất kì độ đo khoảng cách nào, trong đó 5 khoảng cách thông dụng nhất là data = pd.read_csv("https://raw.githubusercontent.com/phamdinhkhanh/datasets/cf391fa1a7babe490fdd10c088f0ca1b6d377f59/shopping-data.csv", header=0, index_col=0) print(data.shape) data.head()4. data = pd.read_csv("https://raw.githubusercontent.com/phamdinhkhanh/datasets/cf391fa1a7babe490fdd10c088f0ca1b6d377f59/shopping-data.csv", header=0, index_col=0) print(data.shape) data.head()5 là phương pháp áp dụng để tính khoảng cách giữa các cụm bao gồm data = pd.read_csv("https://raw.githubusercontent.com/phamdinhkhanh/datasets/cf391fa1a7babe490fdd10c088f0ca1b6d377f59/shopping-data.csv", header=0, index_col=0) print(data.shape) data.head()6 trong đó mặc định là data = pd.read_csv("https://raw.githubusercontent.com/phamdinhkhanh/datasets/cf391fa1a7babe490fdd10c088f0ca1b6d377f59/shopping-data.csv", header=0, index_col=0) print(data.shape) data.head()7. Bên dưới chúng ta sẽ cùng khởi tạo một thuật toán phân cụm với 5 cụm, sử dụng khoảng các cụm là data = pd.read_csv("https://raw.githubusercontent.com/phamdinhkhanh/datasets/cf391fa1a7babe490fdd10c088f0ca1b6d377f59/shopping-data.csv", header=0, index_col=0) print(data.shape) data.head()8 và phương pháp tính khoảng cách giữa các điểm là data = pd.read_csv("https://raw.githubusercontent.com/phamdinhkhanh/datasets/cf391fa1a7babe490fdd10c088f0ca1b6d377f59/shopping-data.csv", header=0, index_col=0) print(data.shape) data.head()9. from sklearn.cluster import AgglomerativeClustering cluster = AgglomerativeClustering(n_clusters=5, affinity='euclidean', linkage='ward') labels = cluster.fit_predict(X_std) Vẽ biểu đồ các cụm trong không gian hai chiều data = pd.read_csv("https://raw.githubusercontent.com/phamdinhkhanh/datasets/cf391fa1a7babe490fdd10c088f0ca1b6d377f59/shopping-data.csv", header=0, index_col=0) print(data.shape) data.head()0 14.7. Tổng kết¶Như vậy qua bài naỳ bạn đã nắm được ý tưởng đằng sau thuật toán phân cụm phân cấp. Đây là thuật toán dựa trên chiến lược phân chia (divisive) hoặc hợp nhất (agglomerative) các cụm theo sơ đồ của đồ thị dendrogram. Thuật toán sẽ bao gồm \(N\) bước, tại mỗi bước ta sẽ tìm cách gộp hoặc tách một điểm vào một cụm dựa trên khoảng cách của nó với những điểm còn lại. Thuật toán sẽ dừng cho đến khi đạt ngưỡng về số lượng cụm hoặc đạt ngưỡng về chất lượng của một cụm như đường kính, bán kính, mật độ điểm.\(N\) bước, tại mỗi bước ta sẽ tìm cách gộp hoặc tách một điểm vào một cụm dựa trên khoảng cách của nó với những điểm còn lại. Thuật toán sẽ dừng cho đến khi đạt ngưỡng về số lượng cụm hoặc đạt ngưỡng về chất lượng của một cụm như đường kính, bán kính, mật độ điểm. Mặc dù là thuật toán khá hiệu quả nhưng phân cụm phân cấp lại có chi phí tính toán khá lớn, lên tới \(O(N^3)\). Do đó chỉ nên áp dụng phương pháp này đối với những bộ dữ liệu có kích thước vừa phải. Để củng cố lại kiến thức về thuật toán phân cụm phân cấp chúng ta hãy cùng làm những bài tập bên dưới.\(O(N^3)\). Do đó chỉ nên áp dụng phương pháp này đối với những bộ dữ liệu có kích thước vừa phải. Để củng cố lại kiến thức về thuật toán phân cụm phân cấp chúng ta hãy cùng làm những bài tập bên dưới. 14.8. Bài tập¶
14.9. Tài liệu tham khảo¶
How to do hierarchical clustering in Python?How to Do Hierarchical Clustering in Python ? 5 Easy Steps Only Step 1: Import the necessary Libraries for the Hierarchical Clustering. Here we are importing dendrogram, linkage,... Step 2: Import the libraries for the Data Visualization. The first line np.set_printoptions (precision=4,suppress=True ... What is divisive hierarchical clustering?Divisive hierarchical clustering: tất cả các đối tượng/điểm là một cụm, việc phân cụm là thực hiện chia tách cụm lớn thành các cụm nhỏ hơn (top–down). ... Không sử dụng được tâm của các cụm để tính toán như trong không gian Euclid. What is clustering in Python machine learning?By Jason Brownlee on April 6, 2020 in Python Machine Learning. Last Updated on August 20, 2020. Clustering or cluster analysis is an unsupervised learning problem. It is often used as a data analysis technique for discovering interesting patterns in data, such as groups of customers based on their behavior. There are many clustering algorithms ... What is a hierarchical clustering in machine learning?Hierarchical Clustering uses the distance based approach between the neighbor datapoints for clustering. Each data point is linked to its nearest neighbors. There are two ways you can do Hierarchical clustering Agglomerative that is bottom-up approach clustering and Divisive uses top-down approaches for clustering. |