Clustering Algorithms: A Real-world Case

R Data Science Series

Introduction

Nhóm thuật toán phân cụm (Clustering Algorithms) là nhóm thuật toán học không giám sát (unsupervised machine learning algorithm) thường được sử dụng để nhóm các quan sát thành k nhóm khác nhau (MacQueen, 1967) sao cho các quan sát thuộc cùng một nhóm là đồng nhất với nhau nhất có thể. Ý tưởng của thuật toán này và cơ sở toán của nó có thể tham khảo trang 386 cuốn An Introduction to Statistical Learning.

Trong post này chúng ta sẽ áp dụng hai thuật toán phân cụm là K-means clustering và Hierarchical clustering với bộ dữ liệu IBM Watson Telco Customer Churn Data. Bộ dữ liệu này có thể download tại đây. Mô tả về bộ dữ liệu này tại đây.

Mục tiêu của chúng ta là phân cụm nhóm khách hàng từ bỏ sử dụng dịch vụ của công ti để từ đó làm cơ sở khắc họa chân dung của những nhóm khách hàng này và đưa ra những giải pháp phục vụ cho một số chiến lược kinh doanh của công ti chẳng hạn.

K-means clustering

Trước hết load bộ dữ liệu, sử dụng chỉ các numeric features rồi lấy ra những khách hàng đã từ bỏ sử dụng dịch vụ:

#=========================
#    K-means clustering
#=========================

# Load data: 
rm(list = ls())

library(tidyverse)

read_csv("https://raw.githubusercontent.com/treselle-systems/customer_churn_analysis/master/WA_Fn-UseC_-Telco-Customer-Churn.csv") -> all_data

# Filter customers churned: 

all_data %>% 
  filter(Churn == "Yes") %>% 
  select(tenure, MonthlyCharges, TotalCharges, customerID) -> raw_data

Là một nhóm thuật toán dựa trên khoảng cách nên K-means clustering rất nhạy với outliers. Để loại bỏ/hạn chế ảnh hưởng của các outliers chúng ta có thể sử dụng chuẩn hóa 0-1 cho tất cả các features:

# Customer ID: 

churned_ID <- raw_data$customerID

# Scale 0-1 numeric features: 

raw_data %>% 
  select(-customerID) %>% 
  mutate_all(function(x) {(x - min(x)) / (max(x) - min(x))}) -> data_scaled

Thuật toán K-means clustering đòi hỏi rằng phải xác định trước số cụm K. Chúng ta có thể tìm số cụm tối ưu bằng Elbow method như sau:

# Calculate WSS from a range of k: 
wss2 <- sapply(1:10, function(k){kmeans(data_scaled, k, nstart = 50)$tot.withinss})

# Plot k vs WSS: 
u2 <- data.frame(k = 1:10, WSS = wss2)

u2 %>% 
  ggplot(aes(k, WSS)) + 
  geom_line() + 
  geom_point() + 
  geom_point(data = u2 %>% filter(k == 4), color = "red", size = 3) + 
  scale_x_continuous(breaks = seq(1, 10, by = 1)) + 
  labs(title = "Figure 1: The Optimal Number of Clusters, Elbow Method", x = "Number of Clusters (K)") + 
  theme(panel.grid.minor = element_blank())

Tốc độ giảm của WSS chậm hẳn lại nếu k vượt 4. Do vậy k tối ưu được lựa chọn sẽ là 4. Chúng ta thực hiện phân cụm với k = 4:

# k = 4: 
set.seed(123)
km.res4 <- kmeans(data_scaled, 4, nstart = 50)

Xác định quan sát thuộc về cụm nào cho bộ dữ liệu ban đầu:

raw_data %>% 
  mutate(cluster = paste0("Group", km.res4$cluster)) -> data_clustered2

Hình ảnh hóa 4 cụm khách hàng (Figure 2):

# Plot customer groups: 
library(factoextra)

fviz_cluster(km.res4, 
             data = data_scaled,
             palette = "jco", 
             ellipse.type = "euclid", 
             star.plot = TRUE,
             repel = TRUE) + 
  labs(title = "Figure 2: Customer Clusters by K-means Clustering", 
       caption = "Source: IBM Watson Telco Customer Churn Data") + 
  theme_minimal() + 
  theme(axis.text = element_blank()) + 
  theme(plot.margin = unit(rep(0.5, 4), "cm")) + 
  theme(legend.position = "top")

Table 1 mô tả chân dung của 4 nhóm khách hàng này:

library(kableExtra) # For presenting table. 

data_clustered2 %>% 
  group_by(cluster) %>% 
  summarise(avg_ten = mean(tenure), avg_m_charges = mean(MonthlyCharges), total_charges = sum(TotalCharges), N = n()) %>% 
  mutate(per_obs = N / sum(N)) %>% 
  mutate(per_charges = total_charges / sum(total_charges)) %>% 
  mutate_if(is.numeric, function(x) {round(x, 2)}) -> des1

des1 %>% 
  kbl(caption = "Table 1: Customer Characteristics, K-means", escape = TRUE) %>%
  kable_classic(full_width = FALSE, html_font = "Cambria")

Table 1: Customer Characteristics, K-means

cluster	avg_ten	avg_m_charges	total_charges	N	per_obs	per_charges
Group1	6.49	82.87	452332.4	820	0.44	0.16
Group2	32.72	84.43	993167.2	371	0.20	0.35
Group3	57.40	99.57	1302633.1	228	0.12	0.46
Group4	6.79	38.10	114794.3	450	0.24	0.04

Căn cứ vào Table 1 chúng ta có thể thấy Group3 là nhóm khách hàng đã từng mang lại giá trị nhất cho công ti. Nhóm này có 228 khách hàng, chiếm chỉ 12% tổng số khách hàng đã rời bỏ nhưng mang về 46% tổng doanh thu. Đây cũng là nhóm khách hàng gắn bố lâu dài nhất với công ti với thời gian sử dụng dịch vụ trung bình là gần 56 tháng, tiêu dùng lớn với phí dịch vụ bình quân hàng tháng là gần 100$. Để một tập khách hàng đáng giá như vậy rời bỏ thì công ti có lẽ cần tìm hiểu nguyên nhân tại sao để từ đó ngăn chặn/hạn chế việc mất thêm những khách hàng tốt.

Table 1 cũng chỉ ra rằng Group2 là nhóm khách hàng tốt thứ hai. Còn Group1 là nhóm khách hàng mang lại ít giá trị nhất cho công ti và đây cũng là nhóm khách hàng chiếm số lượng lớn nhất.

Giả sử công ti muốn lôi kéo những khách hàng đã rời bỏ này trở lại bằng cách, ví dụ, gọi điện đề xuất cho khách hàng những ưu đãi nào đó, như giảm cho họ 5% phí thanh toán hàng tháng chẳng hạn. Mặt khác, giả sử rằng nguồn lực thời gian và nhân lực hạn chế nên công ti chỉ có khả năng cover/gọi điện chỉ cho 100 khách hàng thì đương nhiên vẫn ưu tiên chăm sóc Group3 trước. Tuy nhiên nhóm này có tới 220 khách hàng nên cách tiếp cận đơn giản nhất cho việc lựa chọn là sắp xếp 228 khách hàng này theo tiêu chí tổng phí thanh toán (hoặc phí trung bình tháng) và chỉ vớt 100 khách hàng đầu tiên. Cụ thể những khách hàng này có ID được xác định như sau:

data_clustered2 %>% 
  mutate(customerID = churned_ID) %>% 
  filter(cluster == "Group3") %>% 
  arrange(-MonthlyCharges) %>% 
  slice(1:100) %>% 
  pull(customerID) -> group3_top100_ID

# The first-potential customers: 
head(group3_top100_ID)

## [1] "8199-ZLLSA" "2889-FPWRM" "2302-ANTDP" "9053-JZFKV" "1444-VVSGW"
## [6] "0201-OAMXR"

Sau khi xác định được 100 khách hàng đáng giá nhất để lôi kéo trở lại này, công ti có thể kết hợp với các thông tin khác nữa về khách hàng (như giới tính, tuổi, nghề nghiệp) để đưa ra các actions lôi kéo hiệu quả hơn.

Kế tiếp là công ti cần đánh giá/ước lượng tác động về mặt doanh thu tháng (hoặc tổng doanh thu) sẽ là như thế nào nếu thực hiện chính sách lôi kéo trở lại những khách hàng này bằng chính sách giảm giá 5%. Giả sử như bộ phận chăm sóc khách hàng của công ti, dựa trên những hiểu biết và kinh nghiệm, chỉ ra rằng nếu thực hiện chính sách giảm giá như vậy thì tỉ lệ thành công sẽ là 20%. Tức là nếu gọi điện/email cho 10 khách hàng thì sẽ có 2 khách hàng sẵn sàng quay trở lại sử dụng dịch vụ của công ti. Chúng ta có thể ước lượng doanh thu mà công ti sẽ thu lại được với giả định rằng hành vi tiêu dùng của họ vẫn tuân theo các pattern như đã từng bằng Monte Carlo Simulation (5000 lần) như sau:

# Discount rate 5%: 
discount_rate <- 0.05

# Function calculates total revenue: 

calculate_charges20 <- function(j) {
  
  set.seed(j)
  
  data_clustered2 %>% 
  mutate(customerID = churned_ID) %>% 
  filter(cluster == "Group3") %>% 
  arrange(-MonthlyCharges) %>% 
  slice(1:100) %>% 
  sample_n(20) %>% 
  pull(TotalCharges) %>% 
  sum() -> charges_20
  
  return(charges_20*(1 - discount_rate))
  
}

sapply(1:5000, calculate_charges20) -> charges_20_simulation

df_income <- data.frame(income = charges_20_simulation)

df_income %>% 
  ggplot(aes(income)) + 
  geom_density(alpha = 0.3, fill = "blue", color = "blue") + 
  geom_histogram(aes(y = ..density..), fill = "red", color = "red", alpha = 0.3) + 
  geom_vline(xintercept = mean(df_income$income), color = "green", size = 1.1) + 
  theme(text = element_text(size = 10)) + 
  theme(axis.text.y = element_blank()) + 
  scale_x_continuous(labels = scales::dollar) + 
  labs(x = NULL, y = NULL, 
       title = "Figure 3: Total Charges from 20 Customers", 
       subtitle = "Monte Carlo Simulation, 5000 Interactions", 
       caption = "Data Source: IBM Data")

Figure 3 cho thấy rằng nếu:

• Tỉ lệ thành công khi lôi kéo trở lại khách hàng đã rời bỏ là 20%.
• Hành vi tiêu dùng của những khách hàng này vẫn lặp lại pattern như đã từng.
• Tỉ lệ chiết khấu là 5%

Thì có thể nói gần như chắc chắn rằng tổng doanh thu mà công ti có thể có được nằm đâu đó trong khoảng 100.000 đến 140.000$.

Hierarchical clustering

Thuật toán K-means clustering đòi hỏi rằng số cụm k cần phải xác định trước. K này có thể được tìm dựa trên Elbow method như trên. Hierarchical clustering là một thuật toán linh hoạt hơn vì nó không đòi hỏi phải xác định trước k:

#===========================
#  Hierarchical clustering
#===========================

# Compute distances: 
dd <- dist(data_scaled, method = "euclidean")

# Perform hierarchical clustering: 
hc <- hclust(dd, method = "ward.D2")

Chúng ta có thể hình ảnh hóa những khách hàng rời bỏ này thành, ví dụ, 4 cụm khác nhau như Figure 4:

# Create a draft of dendrogram by using fviz_dend() function: 

fviz_dend(hc, 
          k = 4,   
          cex = 0.5, 
          rect = TRUE, 
          rect_fill = TRUE, 
          horiz = FALSE, 
          show_labels = FALSE, 
          palette = "jco", 
          rect_border = "jco", 
          color_labels_by_k = TRUE) -> basic_plot

# Decorate the draft: 

basic_plot + 
  theme_gray() + 
  theme(plot.margin = unit(rep(0.5, 4), "cm")) + 
  labs(title = "Figure 4: Customer Clusters by Hierarchical Clustering", 
       caption = "Source: IBM Watson Telco Customer Churn Data") + 
  theme(axis.ticks.x = element_blank()) + 
  theme(axis.text.x = element_blank())

Chúng ta cũng có thể “khắc họa - mô tả” chân dung của 4 nhóm khách hàng một cách tương tự:

# Cut tree into 4 groups: 
sub_grp <- cutree(hc, k = 4)

raw_data %>% 
  mutate(cluster = paste0("Group", sub_grp)) -> data_clusteredHC

data_clusteredHC %>% 
  group_by(cluster) %>% 
  summarise(avg_ten = mean(tenure), avg_m_charges = mean(MonthlyCharges), total_charges = sum(TotalCharges), N = n()) %>% 
  mutate(per_obs = N / sum(N)) %>% 
  mutate(per_charges = total_charges / sum(total_charges)) %>% 
  mutate_if(is.numeric, function(x) {round(x, 2)}) -> des2

des2 %>% 
  kbl(caption = "Table 2: Customer Characteristics, Hierarchical", escape = TRUE) %>%
  kable_classic(full_width = FALSE, html_font = "Cambria")

Table 2: Customer Characteristics, Hierarchical

cluster	avg_ten	avg_m_charges	total_charges	N	per_obs	per_charges
Group1	6.26	39.12	118011.1	456	0.24	0.04
Group2	7.52	83.19	554407.6	869	0.46	0.19
Group3	35.35	84.51	924316.4	322	0.17	0.32
Group4	57.80	98.16	1266191.9	222	0.12	0.44

Group4 là cụm khách hàng giá trị nhất đã rời bỏ công ti theo kết quả của thuật toán Hierarchical clustering. Cụ thể đây đã từng là nhóm khách hàng trung thành nhất, chi tiêu nhiều nhất. Nhóm này có tất cả 222 khách hàng, chiếm 12% tổng số khách hàng đã rời bỏ nhưng chiếm tới 44% doanh thu. Kết quả này cũng rất sát với kết quả phân cụm từ thuật toán K-means mà ta đã biết. Trong tình huống này của bộ dữ liệu thì không thấy có sự khác biệt đáng kể về kết quả giữa hai thuật toán phân cụm. Tương tự, sử dụng các kết quả của thuật toán phân cụm Hierarchical clustering vẫn tương tự như đã trình bày ở trên.

Some Extensions

Ngoài hai thuật toán phân cụm được sử dụng phổ biến ở trên thì cũng còn một số thuật toán phân cụm khác nữa. Đáng chú ý trong số đó là PAM và CLARA. Cả hai thuật toán phân loại này khắc phục những nhược điểm của K-means clustering cũng như khả năng áp dụng cho những bộ dữ liệu kích thước lớn. Cả hai thuật toán này đều có trong gói cluster. Dưới đây là R codes cho hai thuật toán này (không hiển thị kết quả):

#===================
#  PAM Algorithm
#===================

library(cluster)

pamResult <- pam(data_scaled, k = 4)

raw_data %>% 
  mutate(cluster = paste0("Group", pamResult$clustering)) -> data_clusteredPAM

data_clusteredPAM %>% 
  group_by(cluster) %>% 
  summarise(avg_ten = mean(tenure), avg_m_charges = mean(MonthlyCharges), total_charges = sum(TotalCharges), N = n()) %>% 
  mutate(per_obs = N / sum(N)) %>% 
  mutate(per_charges = total_charges / sum(total_charges)) -> des3


#===================
#  CLARA Algorithm
#===================

# https://paginas.fe.up.pt/~ec/files_1112/week_06_Clustering_part_II.pdf
# https://en.wikibooks.org/wiki/Data_Mining_Algorithms_In_R/Clustering/CLARA

claraResult <- clara(data_scaled, k = 4, sampsize = 1000)

raw_data %>% 
  mutate(cluster = paste0("Group", claraResult$clustering)) -> data_clusteredCLARA

data_clusteredCLARA %>% 
  group_by(cluster) %>% 
  summarise(avg_ten = mean(tenure), avg_m_charges = mean(MonthlyCharges), total_charges = sum(TotalCharges), N = n()) %>% 
  mutate(per_obs = N / sum(N)) %>% 
  mutate(per_charges = total_charges / sum(total_charges)) -> des4

Final Notes

• Post này giới thiệu việc áp dụng hai thuật toán phâm cụm được sử dụng phổ biến là K-means và Hierarchical clustering cho bộ dữ liệu IBM Watson Telco Customer Churn Data cũng như ứng dụng/sử dụng kết quả phân cụm cho các mục tiêu của công ti.

• Việc sử dụng kết quả của thuật toán phân cụm trong thực tế là phức tạp hơn vì còn phải tính đến nhiều yếu tố cũng như bối cảnh và đòi hỏi cụ thể của công ti. Post này không thể cover hết những tình huống đó.

• Ngoài hai thuật toán K-means và Hierarchical clustering chúng ta cũng còn có thể sử dụng những thuật toán thay thế khác như PAM và CLARA.

References

1. Customer and Business Analytics: Applied Data Mining for Business Decision Making Using R.
2. Hands-On Data Science for Marketing: Improve your marketing strategies with machine learning using Python and R.
3. Marketing Data Science: Modeling Techniques in Predictive Analytics with R and Python.
4. An Introduction to Statistical Learning.
5. Hands-On Machine Learning with R.