Cluster Analysis
Clustering hay phân cụm là một kỹ thuật quan trọng trong Pattern Analysis để xác định các nhóm riêng biệt trong dữ liệu. Dữ liệu trong thực tế luôn nhiều hơn ba chiều (three-dimensional) vì vậy cần thực hiện các phương pháp giảm chiều dữ liệu (dimensionality reduction/ dimension reduction) như PCA hoặc Laplacian Eigenmaps trước khi áp dụng kỹ thuật clustering.
Giảm chiều dữ liệu là sự biến đổi dữ liệu từ không gian chiều (cao) thành không gian chiều (thấp) đồng thời giữ lại một số thuộc tính có ý nghĩa của dữ liệu gốc, có ý tưởng gần với chiều nội tại (intrinsic dimension). Phân tích dữ liệu trong không gian chiều (cao) có thể gặp nhiều khó khăn vì nhiều lý do, dữ liệu thô thường có tính thưa thớt (sparse matrix) khó tính toán, hơn nữa các thuật toán mất rất nhiều thời gian để xử lý dữ liệu.
Thuật toán K-Means
Trong bài viết này mình tôi giới thiệu về thuật toán K-Means Clustering đây là một dạng thuật toán phân tích cụm phổ biến do MacQueen đề xuất trong lĩnh vực thống kê năm 1967. Bài báo khoa học mang tên Some Methods for Classification and analysis of multivariate observations - J. MacQueen (1967), đây là một thuật toán thống kê cổ điển.
Về lý thuyết và cơ chế toán học bên trong của thuật toán K-Means có thể tham khảo bài viết của tiến sĩ Vũ Hữu Tiệp (PhD) trên trang machine learning cơ bản K-means Clustering xem tại mục 2 Phân tích toán học, anh viết khá dễ hiểu và có kèm theo bài thực hành bằng ngôn ngữ lập trình Python.
Nhắc lại một chút về lý thuyết: Ý tưởng của thuật toán K-Means là tạo ra \(k\) cụm dữ liệu \({C_1, C_2, C_3, ..., C_k}\) từ một tập dữ liệu chứa \(n\) đối tượng trong không gian \(d\) chiều \(X_i = (x_{i1}, x_{i2}, ..., x_{id})\) \((i=\overline{1,n})\), sao cho hàm tiêu chuẩn: \(E=\sum_{i=1}^k\sum_{x \in C_i}D^2(x-m_i)\) đạt giá trị tối thiểu. Trong đó \(m_i\) là tâm cụm của \(C_i\), \(D\) là khoàng cách giữa hai đối tượng.
Tâm của một cụm là một vector, trong đó giá trị của mỗi phần tử của nó là trung bình công của các thành phần tương ứng của các đối tượng vector dữ liệu cụm đang xét. Độ đo khoảng cách D giữa các giữa các đối tượng dữ liệu (measures of distance) có rất nhiều phương pháp như: Euclidean distance, squared euclidean distance, manhattan distance, Minkowski distance, pearson correlation distance, binary data, … trong đó phương pháp Euclidean distance là phương pháp thường được sử dụng nhất, bởi vì đây là mô hình khoảng cách dễ lấy đạo hàm và xác định các cực trị tối thiệu. Hàm tiêu chuẩn và độ đo khoảng cách có thể được xác định cụ thể tùy vào ứng dụng hoặc quan điểm của người dùng.
Hình 1: Euclidean distance cho không gian 3 chiều
Các bước tiến hành thuật toán K-Means:
Input: Tập dữ liệu chứa n đối tượng, số cụm k Output: Tâm các cụm \(C_i(i= \overline{1,k})\) và hạm tiêu chuẩn E đạt giá trị tối thiểu.
Bước 1: Chọn k tâm \({[m_j]}_{j=1}^k\) ban đầu trong không gian \(R^d\) (\(d\) là số chiều của dữ liệu). Việc lựa chọn này có thể là ngẫu nhiên hoặc theo kinh nghiệm.
Bước 2: Đối với mỗi điểm \(X_i (1 <= i <= n)\), tính toán khoảng cách của nó tới mỗi tâm \(m_j, j=1,k\). Sau đó tìm tâm gần nhất đối với mỗi điểm.
Bước 3: Đối với mỗi \(j=1,k\), cập nhật tâm cụm \(m_j\) bằng cách xác định trung bình cộng vector đối tượng dữ liệu
Bước 4: Lặp các bước 2 và 3 đến khi các tâm của cụm không thay đổi.
Thụât toán K-Means tuần tự trên có độ phức tạp tính toán là: \(\large{O((3nkd)\tau} \large{T^{flop}} )\) Trong đó: \(n\) là số đối tượng dữ liệu, \(k\) là số cụm dữ liệu, \(d\) là số chiều, \(\tau\) là số vòng lặp, \(\large {T^{flop}}\) là thời gian để thực hiện một phép tính cơ sở như phép tính nhân, chia, … Như vậy, do K-Means phân tích phân cụm đơn giản nên có thể áp dụng đối với tập dữ liệu lớn. Tuy nhiên, nhược điểm của K-means là chỉ áp dụng với dữ liệu có thuộc tính số và khám ra các cụm có dạng hình cầu, K-means còn rất nhạy cảm với nhiễu và các phần tử ngoại lai trong dữ liệu. Chất lượng phân cụm dữ liệu của thuật toán K-means phụ thuộc nhiều vào các tham số đầu vào như: số cụm \(k\) và \(k\) tâm khởi tạo ban đầu. Trong trường hợp, các tâm khởi tạo ban đầu mà quá lệch so với các tâm cụm tự nhiên thì kết quả phân cụm của K-Means là rất thấp, nghĩa là các cụm dữ liệu được khám phá rất lệch so với các cụm trong thực tế. Trên thực tế người ta chưa có một giải pháp tối ưu nào để chọn các tham số đầu vào, giải pháp thường được sử dụng nhất là thử nghiệm với các giá trị đầu vào \(k\) khác nhau rồi sau đó chọn giải pháp tốt nhất.
Để diễn giải và minh hoạt một cách đơn giản hơn có thể tóm lượt thuật toán K-Means trong không gian 2 chiều như sau (nội dung này tôi lấy tại wikipedia)
Bước 1: ví dụ chúng ta có hàng loạt các giá trị quan sát như hình trên, đầu tiên ta xác định giá trị k phân cụm cần thiết,trong trường hợp này ta đang chọn k = 3 cụm, máy tính sẽ ngẫu nhiên hóa 3 giá trị trung bình, ta có 3 điểm biểu thị qua màu đỏ, xanh lá cây, xanh nước biển
Bước 2: Tìm các giá trị quan sát sao cho gần với giá trị trung bình, như hình trên ta phân biệt được 3 nhóm hiện tại khá rõ ràng và những giá trị quan sát nào gần với giá trị centroid ban đầu máy tính ngẫu nhiên hóa
Bước 3: Tiếp tục tính các giá trị trung bình mới dựa trên các giá trị quan sát, chú ý giai vị trí trung tâm của các cụm lúc này đã thay đổi
Bước 4: Lặp lại bước 2 và 3 đến khi tâm của cụm không thay đổi
Ví dụ ta có tập dataset gồm các giá trị: {2, 4, 1, 10, 15, 30, 40, 12, 3, 25}, ta xác định k cluster = 2 nhóm.
Iteration 1: Gọi M1, M2 là 2 giá trị trung bình ngẫu nhiên (centroids), M1 = 4, M2 = 12. Lúc này ta sẽ có 2 trung tâm cụm C1 = {4}, C2 = {12}. Tính khoảng cách D1, D2 giữa các giá so với trung tâm cụm. Ta có các giá trị 2 phân cụm C1 = {2, 4, 1, 3} vì gần với giá trị {4}, C2 = {10, 15, 30, 40, 12, 25}
Iteration 2: Ta sẽ tính giá trị trung bình của C1 và C2, cụ thể
M1 = mean(2, 4, 1, 3) = 2.5
M2 = mean(10, 15, 30, 40, 12, 25) = 22
Ta cập nhật hóa khoảng cách, lúc này ta có 2 phân cụm mới như sau:
C1 = {2, 4, 1, 3, 10, 12} C2 = {15, 30, 40, 25}
- Iteration 3: tiếp tục thực hiện như vậy cho đến khi có cluster sau cùng
Thực hành phân nhóm khách hàng với K-Means
Trong bài thực hành này tôi sẽ sử dụng R để tiến hành phân cụm dữ liệu, dữ liệu thực hành lấy từ Github có tên Mall Customer Segmentation Data, có thể download tại đây
Nội dung dữ liệu như sau thông qua thông tin thẻ thành viên của khách hàng ở trung tâm mua sắm, bạn có một số dữ liệu cơ bản về khách hàng của mình như ID khách hàng, tuổi, giới tính, thu nhập hàng năm và điểm chi tiêu. Ví dụ vấn đề đặt ra: bạn là quản lý mới tại trung tâm mua sắm hoặc với vai trò là quản lý Marketing và mong muốn của bạn là muốn hiểu về các đối tượng khách hàng của mình, và phân nhóm các khách hàng có chung các đặc điểm nhất định, xác định nhóm khách hàng mục tiêu để MKT team có thể lập các chiến lược và kế hoạch tiếp cận phù hợp.
Như vậy làm thế nào để phân khúc khách hàng thông qua thuật toán Machine Learning (K-Means Clustering) một cách đơn giản nhất.
Tôi sẽ thực hành quy trình phân tích thông qua 5 bước cơ bản sau đây:
- Data Preparation (Chuẩn bị dữ liệu để phân tích)
- Visualization of distance matrix (trực quan hóa dữ liệu bằng ma trận khoảng cách)
- Determination of k (xác định giá trị k tối ưu)
- Computation k-means (tính giá trị trung bình centroids của mỗi cluster)
- Validation (kiểm định phân nhóm)
Đầu tiên Khai báo các thư viện cần thiết trong R
library(dplyr)
library(psych)
library(tidyverse)
library(psych)
library(broom)
library(ggplot2)
library(DataExplorer)
library(ggthemes)
library(plotly)
library(correlation)
library(GGally)
library(readr)
library(plotly)
library(scatterplot3d)
#Các thư viện chính trong phân tích cụm
library(cluster)
library(factoextra)
library(NbClust)Tạo dataset có tên df thông qua đọc link chứa file Mall_Customers.csv
df <- read.csv('https://raw.githubusercontent.com/SteffiPeTaffy/machineLearningAZ/master/Machine%20Learning%20A-Z%20Template%20Folder/Part%204%20-%20Clustering/Section%2025%20-%20Hierarchical%20Clustering/Mall_Customers.csv')
head(df)## CustomerID Genre Age Annual.Income..k.. Spending.Score..1.100.
## 1 1 Male 19 15 39
## 2 2 Male 21 15 81
## 3 3 Female 20 16 6
## 4 4 Female 23 16 77
## 5 5 Female 31 17 40
## 6 6 Female 22 17 76Dữ liệu bao gồm các biến:
CustomerID: Unique ID assigned to the customer
Genre: Gender of the customer
Age: Age of the customer
Annual Income (k$): Annual Income of the customer
Spending Score (1-100): Score assigned by the mall based on customer behavior and spending nature
Triển khai quy trình
1.Data preparation
df %>% names()## [1] "CustomerID" "Genre" "Age"
## [4] "Annual.Income..k.." "Spending.Score..1.100."dim(df)## [1] 200 5Thực hiện đổi tên các biến giúp các mã code trở nên gọn gàng hơn
df <- rename(df,
Id = CustomerID,
Age = Age,
Gender = Genre,
Income = Annual.Income..k..,
SpendingScore = Spending.Score..1.100.)
head(df)## Id Gender Age Income SpendingScore
## 1 1 Male 19 15 39
## 2 2 Male 21 15 81
## 3 3 Female 20 16 6
## 4 4 Female 23 16 77
## 5 5 Female 31 17 40
## 6 6 Female 22 17 76df %>% glimpse()## Rows: 200
## Columns: 5
## $ Id <int> 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 1~
## $ Gender <chr> "Male", "Male", "Female", "Female", "Female", "Female", ~
## $ Age <int> 19, 21, 20, 23, 31, 22, 35, 23, 64, 30, 67, 35, 58, 24, ~
## $ Income <int> 15, 15, 16, 16, 17, 17, 18, 18, 19, 19, 19, 19, 20, 20, ~
## $ SpendingScore <int> 39, 81, 6, 77, 40, 76, 6, 94, 3, 72, 14, 99, 15, 77, 13,~Dữ liệu gồm 5 cột, 200 dòng, định dạng các biến Id, Age, Income, SpendingScore là biến số nguyên (int) tức là Integer là định dạng số học, có thể thực hiện các phép tính toán. Biến Gender có định dạng kiểu chuỗi (chr) character và có đặc tính phân loại theo giới tính.
Tôi sẽ tạo ra biến mới đặt tên là G có định dạng kiểu int, quy ước Male = 1, Female = 0 vì đối với K-Means khi tiến hành phân cụm chỉ có thể thực hiện trên kiểu dữ liệu định dạng số học.
df$G <- as.integer(# Chuyển sang dạng kiểu <int>
(ifelse(
df$Gender=="Male", 1, 0) # Quy ước Male: 1 & Female: 0
)
)
head(df)## Id Gender Age Income SpendingScore G
## 1 1 Male 19 15 39 1
## 2 2 Male 21 15 81 1
## 3 3 Female 20 16 6 0
## 4 4 Female 23 16 77 0
## 5 5 Female 31 17 40 0
## 6 6 Female 22 17 76 0Kiểm tra lại với hàm str() lúc này ta có 5 biến kiểu int trong đó có biến G vừa tạo và Gender là biến phân loại.
str(df)## 'data.frame': 200 obs. of 6 variables:
## $ Id : int 1 2 3 4 5 6 7 8 9 10 ...
## $ Gender : chr "Male" "Male" "Female" "Female" ...
## $ Age : int 19 21 20 23 31 22 35 23 64 30 ...
## $ Income : int 15 15 16 16 17 17 18 18 19 19 ...
## $ SpendingScore: int 39 81 6 77 40 76 6 94 3 72 ...
## $ G : int 1 1 0 0 0 0 0 0 1 0 ...colSums(is.na(df)
)## Id Gender Age Income SpendingScore
## 0 0 0 0 0
## G
## 0df %>% describe()## vars n mean sd median trimmed mad min max range skew
## Id 1 200 100.50 57.88 100.5 100.50 74.13 1 200 199 0.00
## Gender* 2 200 1.44 0.50 1.0 1.43 0.00 1 2 1 0.24
## Age 3 200 38.85 13.97 36.0 37.94 16.31 18 70 52 0.48
## Income 4 200 60.56 26.26 61.5 59.64 24.46 15 137 122 0.32
## SpendingScore 5 200 50.20 25.82 50.0 50.31 29.65 1 99 98 -0.05
## G 6 200 0.44 0.50 0.0 0.42 0.00 0 1 1 0.24
## kurtosis se
## Id -1.22 4.09
## Gender* -1.95 0.04
## Age -0.71 0.99
## Income -0.15 1.86
## SpendingScore -0.86 1.83
## G -1.95 0.04Sử dụng biểu đồ tương quan đa biến, xem xét đặc tính phân bố dữ liệu của nhóm khách hàng Nam/ Nữ và mối tương quan giữa các biến thông qua chỉ số tương quan Pearson.
ggpairs(df,
columns = 3:5,
mapping = ggplot2::aes(color = Gender))
Ta sẽ xem kỹ hơn về phân bố dữ liệu Dưới đây là biểu đồ histogram cho thấy tần suất phân bố khác nhau giữa các giá trị theo từng biến số Age, Income và Spending Score.
plot_histogram(df[-1])
df %>% ggplot(aes(x=Income,
fill=Gender)) +
geom_density(alpha = 0.8) +
labs(x = "Income",
y = "Density") +
ggtitle("Gender vs Income")
df %>% ggplot(aes(Age,
Gender)) +
geom_boxplot(outlier.colour = "orange") +
geom_jitter(positiion = position_jitter(width = 0.5,
height = 0.5),
alpha = 1,
color = "blue") +
labs(x = "AGE",
y = "GENDER") +
ggtitle("Gender vs Age") 
df %>% ggplot(aes(Income, Gender)) +
geom_boxplot(outlier.colour = "orange") +
geom_jitter(positiion = position_jitter(width = 0.1,
height = 0),
alpha = 1,
color="blue") +
labs(x = "INCOME",
y = "GENDER")
df %>% ggplot(aes(Age,
Income)) +
geom_point(color="blue") +
geom_smooth() +
facet_grid(~Gender) +
ggtitle("Income vs Age") 
df %>% ggplot(aes(Age,
SpendingScore)) +
geom_point(color="blue") +
geom_smooth() +
facet_grid(~Gender) +
ggtitle("Spending Score vs Age") 
df$zn_age <- scale(df[3])
df$zn_income <- scale(df[4])
df$zn_spendingscore <- scale(df[5])
names(df)## [1] "Id" "Gender" "Age" "Income"
## [5] "SpendingScore" "G" "zn_age" "zn_income"
## [9] "zn_spendingscore"2.Viz of distance matrix
Tính chỉ số Hopkins
#Hopkins statistics
df_gct <- get_clust_tendency(df[c(7:9)],
n=100,
graph = T)
df_gct$hopkins## [1] 0.6689417#Matrix Distance
df_gct$plot
3.Determination of k
Xác định k cụm bằng phương pháp Elbow Method
fviz_nbclust(scale(df[c(7:9)]),
kmeans, # Sử dụng thuật toán K-Means
method = 'wss') +
geom_vline(xintercept = 4,
linetype = 2)+
labs(subtitle = "Elbow method")
Xác định k cụm bằng phương pháp Gap Statistic
fviz_nbclust(df[c(7:9)],
kmeans,
nstart = 25,
method ='gap_stat',
nboot = 100) +
geom_vline(xintercept = 4, linetype = 2) +
labs(subtitle = "Gap Statistic method")## Warning in check_font_path(italic, "italic"): 'italic' should be a length-one
## vector, using the first element
4.Computation k-means
df_clust <- kmeans(df[c(7:9)],
centers = 4,
nstart = 25)
summary(df_clust)## Length Class Mode
## cluster 200 -none- numeric
## centers 12 -none- numeric
## totss 1 -none- numeric
## withinss 4 -none- numeric
## tot.withinss 1 -none- numeric
## betweenss 1 -none- numeric
## size 4 -none- numeric
## iter 1 -none- numeric
## ifault 1 -none- numericdf_clust## K-means clustering with 4 clusters of sizes 38, 65, 57, 40
##
## Cluster means:
## zn_age zn_income zn_spendingscore
## 1 0.03711223 0.9876366 -1.1857814
## 2 1.08344244 -0.4893373 -0.3961802
## 3 -0.96008279 -0.7827991 0.3910484
## 4 -0.42773261 0.9724070 1.2130414
##
## Clustering vector:
## [1] 3 3 3 3 3 3 2 3 2 3 2 3 2 3 2 3 3 3 2 3 3 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2
## [38] 3 2 3 2 3 2 3 2 3 2 3 3 3 2 3 3 2 2 2 2 2 3 2 2 3 2 2 2 3 2 2 3 3 2 2 2 2
## [75] 2 3 2 2 3 2 2 3 2 2 3 2 2 3 3 2 2 3 2 2 3 3 2 3 2 3 3 2 2 3 2 3 2 2 2 2 2
## [112] 3 1 3 3 3 2 2 2 2 3 1 4 4 1 4 1 4 2 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4
## [149] 1 4 1 4 1 4 1 4 1 4 1 4 2 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4 1
## [186] 4 1 4 1 4 1 4 1 4 1 4 1 4 1 4
##
## Within cluster sum of squares by cluster:
## [1] 44.01863 74.83280 61.43215 23.91544
## (between_SS / total_SS = 65.8 %)
##
## Available components:
##
## [1] "cluster" "centers" "totss" "withinss" "tot.withinss"
## [6] "betweenss" "size" "iter" "ifault"fviz_cluster(df_clust,
df[c(7:9)],
palette = c("#2E9FDF", "#00AFBB", "#E7B800", "#0000FF"),
geom = "point",
ellipse.type = "convex",
ggtheme = theme_bw())## Warning in check_font_path(italic, "italic"): 'italic' should be a length-one
## vector, using the first element
tidy(df_clust)## # A tibble: 4 x 6
## zn_age zn_income zn_spendingscore size withinss cluster
## <dbl> <dbl> <dbl> <int> <dbl> <fct>
## 1 0.0371 0.988 -1.19 38 44.0 1
## 2 1.08 -0.489 -0.396 65 74.8 2
## 3 -0.960 -0.783 0.391 57 61.4 3
## 4 -0.428 0.972 1.21 40 23.9 4augment(df_clust, df) %>%
ggplot(aes(Age,
SpendingScore,
color =.cluster
)) +
geom_point(alpha = 2) 
augment(df_clust, df) %>%
ggplot(aes(Age,
SpendingScore,
color =.cluster
)) +
facet_grid(~Gender) +
geom_point(alpha = 2) ## Warning in check_font_path(italic, "italic"): 'italic' should be a length-one
## vector, using the first element
augment(df_clust, df) %>%
ggplot(aes(Income,
Age,
color =.cluster
)) +
geom_point(alpha = 2) ## Warning in check_font_path(italic, "italic"): 'italic' should be a length-one
## vector, using the first element
augment(df_clust, df) %>%
ggplot(aes(Income,
Age,
color =.cluster
)) +
facet_grid(~Gender) +
geom_point(alpha = 2) ## Warning in check_font_path(italic, "italic"): 'italic' should be a length-one
## vector, using the first element
Trực quan hóa 3 chiều dữ liệu đối với 4 cluster
# Visualizations of 4 clusters
fig <- augment(df_clust, df) %>% plot_ly(x= ~Income, y= ~Age, z= ~SpendingScore, color = ~.cluster, colors = c('#BF382A', '#0C4B8E', "#BBBBBB", "#00FF00")) %>%
add_markers() %>%
layout(scene = list(
xaxis = list(title="Annual Income"),
yaxis = list(title="Age"),
zaxis = list(title="Spending Score")))
fig5.Validation
Trong bước 5 này tôi sẽ dùng chỉ số Silhouette làm cơ sở để đánh giá việc phân cụm có thực sự tốt không ?
Một cách ngắn gọn phương pháp Silhouette sẽ cho chúng ta biết những điểm dữ liệu hay những quan sát nào nằm gọn bên trong cụm (tốt) hay nằm ngoài rìa cụm (không tốt) để đánh giá hiệu quả phân cụm.
\[Silhouette = \frac{1}{n}\sum_{i=1}^n \frac{b(i)-a(i)}{max(a(i), b(i))}\] Silhouette đo lường khoảng cách của một điểm dữ liệu trong cụm đến Centroid, điểm trung tâm của cụm, và khoảng cách của chính điểm đó đến điểm trung tâm của cụm gần nhất (hoặc đến các điểm trung tâm của các cụm còn lại và chọn ra khoảng cách ngắn nhất).
Giả sử có 2 cluster A và B được tìm thấy dựa trên K-means clustering
- \(b_i\) là khoảng cách từ điểm \(i\) trong cluster A đến điểm trung tâm của cluster B
- \(a_i\) là khoảng cách từ điểm \(i\) trong cluster A đến điểm trung tâm của cluster A
Theo công thức trên \(max(b_i, a_i)\) tức lấy chọn giá trị lớn nhất giữa \(a_i\) và \(b_i\). Nếu chỉ số Silhouette tiến về -1, tức khoảng cách điểm \(i\) so với điểm trung tâm trong chính cụm nó được phân xa hơn so với điểm trung tâm của cụm còn lại, vậy khả năng điểm \(i\) lúc này bị phân sai cụm. Có thể xét ngược lại. Do đó, \(b_i – a_i\) càng cao càng tốt, đạt \(max = b_i\) khi \(a_i = 0\). Nếu một cluster được đánh giá chất lượng, là các điểm trong cluster sẽ có Silhouette tiến về 1
Điểm trung bình Silhouette trong trường hợp này = 0.4 cho thấy dữ liệu phân cụm chưa thực sự tốt (chú ý cluster thứ 2), điểm trung bình nằm trong khoảng 0.25 đến 0.5, trường hợp này cần thêm kiến thức chuyên môn, kinh nghiệm để đánh giá thêm khả năng cluster trong thực tế.
sil = silhouette(df_clust$cluster,
dist(df[c(7:9)]))
fviz_silhouette(sil)## cluster size ave.sil.width
## 1 1 38 0.34
## 2 2 65 0.38
## 3 3 57 0.37
## 4 4 40 0.55