Bài giảng Nhập môn khai phá dữ liệu - Chương 6: Phân cụm dữ liệu và hệ thống tư vấn

BÀI GIẢNG KHAI PHÁ DỮ LIỆU

CHƯƠNG 6. PHÂN CỤM DỮ LiỆU và

HỆ THỐNG TƯ VẤN

PGS. TS. Hà Quang Thụy

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

ĐẠI HỌC QUỐC GIA HÀ NỘI

HÀ NỘI, 09-2018

http://uet.vnu.edu.vn/~thuyhq/

1

Nội dung

Phâ n cụm: Giới thiệu

Mô hì nh phâ n cụm: phẳng, phâ n cấp, theo mật độ và theo mô hì nh

Gá n nhã n cụm và đánh giá phâ n cụm

Hệ thống tư vấn: Giới thiệu

Kỹ thuật tư vấn: Khá i quá t và cụ thể

Đánh giá hệ thống tư vấn

Charu C. Aggarwal, Chandan K. Reddy. Data Clustering: Algorithms and

Applications. CRC Press 2014.

Israë l Cé sar Lerman. Foundations and Methods in Combinatorial and Statistical Data

2

Analysis and Clustering. Springer-Verlag London, 2016

Giới thiệu. Ví dụ về phâ n khúc khá ch hàng

⚫ Vꢀng đꢁi cá nhân khách hàng

▪ Khách hàng: là các giai đoꢂn sống thay đổi theo thꢁi gian

▪ Công ty: Khꢃi nghiệp, phát triển/sát nhập, chấm dꢄt

▪ Cá nhân: tốt nghiệp trung học, tốt nghiệp đꢂi học, nhận công việc

làm, xây dꢅng gia đꢆnh, sinh con, thay đổi nơi cư tru

▪ quan trọng để tiếp thị và quản lý quan hệ khách hàng

▪ Vꢇ dụ: chuyển nha, sinh con, v.v.

▪ Một số loꢂi doanh nghiệp được tổ chꢄc xung quanh tꢈng giai

́, v.v.

̀

đoꢂn sống: mꢉ và bꢊ, áo cưới, v.v.

⚫ Thách thꢄc

▪ Thách thꢄc: xác định các sꢅ kiện trong cuộc sống kịp thꢁi

▪ Nhiều sꢅ kiện chꢋ xảy một lꢌn, hoặc rất hiếm khi xảy ra

▪ Sự kiện giai đoꢂn cuộc sống: không thể đoán trước và kiểm soát

3

Một khung nhꢀn vꢁng đꢂi khꢃch hꢄng

⚫ Các giai đoꢂn

▪ ꢍng viên tiềm năng

▪ ꢍng viên triển vong

▪ Khách hàng mới

▪ Khách hàng được ghi nhận: Giá trị thấp, giá trị cao tiềm năng, giá

trị cao

▪ Khách hàng cꢎ: tꢅ nguyện hoặc cưꢏng bꢄc

▪ Tập khꢃch hꢄng giꢃ trị cao, cao tiềm năng, cao: phân khúc KH

4

Khung nhꢀn hꢄnh trꢀnh KH: thang giꢃ trị

Đối sánh

▪ ꢍng viên tiềm năng

▪ ꢍng viên triển vọng

▪ Khách hàng mới

~ ꢍng viên nghi vấn

~ ꢍng viên tiềm năng

~ Khách hàng mới

~ Khách hàng lặp lꢂi

▪ Khách hàng gia

́

trị thấp

trị cao tiềm năng ~ Khách hàng đa sô

trị cao ~ Khách hàng vận động

́

5

Hai lꢅi ꢆch quan trꢇng phân khúc KH

⚫ Giảm chi phꢇ tiếp thị

▪ Cải tiến duy trꢆ KH: giảm chi phꢇ tiếp thị

▪ Vꢇ dụ: chi phꢇ thu hꢐt KH mới gấp 20 lꢌn duy trꢆ KH hiện cꢑ

▪ Chi phꢇ phục vụ KH hiện thꢁi: giảm theo thꢁi gian

▪ Quản lý QHKH tꢅ động hꢑa hoàn toàn: rất ꢇt chi phꢇ

⚫ Hiểu KH sâu sꢒc hơn

▪ Nhiệm kꢓ dài hơn: hiểu biết tốt hơn lꢔn nhau

▪ Cty hiểu kỹ kꢓ vọng cꢕa KH, KH hiểu cái gꢆ Cty cung cấp được

▪ Quan hệ sâu sꢒc hơn, tin cậy và cam kết hai bên phát triển hơn

▪ dꢀng doanh thu và lợi nhuận tꢈ khách hàng trꢃ nên an toàn hơn

▪ tháng 31-36 quꢌn áo trꢅc tuyến 67%, tꢂp hꢑa 23% tháng 0-6

▪ Mô hꢆnh hành trꢆnh bậc thang giá trị: Cty hiểu vị trꢇ hiện thꢁi KH

▪ Phꢌn chi tiêu cꢕa KH tăng lên

6

Trung thꢄnh KH

⚫ Giới thiệu

▪ Trung thành KH với Cty

▪ Hai tiếp cận xác định & đo lưꢁng: hành vi và thái độ

⚫ Trung thành hành vi

▪ tham chiếu đến hành vi mua sản phꢖm cꢕa KH

▪ Hai khꢇa cꢂnh trung thành hành vi: (i) vꢔn tꢇch cꢅc mua sản

phꢖm; (ii) Công ty vꢔn duy trꢆ được chi tiêu cꢕa KH

▪ Danh mục mua các nhà CC tꢅa nhau: c/tiêu KH quan trọng hơn

▪ Ba độ đo hành vi trung thành

▪ Mua hàng gꢌn đây (Recency of purchases: R): (Nghịch đảo)

Thꢁi gian trôi qua kể tꢈ lꢌn mua cuối cùng

▪ Tꢌn số mua hàng (Frequency of purchases: F): Số lượng mua

trong khoảng thꢁi gian xác định.

▪ giá trị tiền mua hàng (Monetary value of purchases: M): Giá trị

tiền mua hàng trong khoảng thꢁi gian xác định.

7

Bài toá n phâ n khúc khá ch hàng

⚫ Giới thiệu

▪ Phꢂm vi: Tập khách hàng hiện thꢁi trong CS KH

▪ Dữ liệu: Dữ liệu mua sản phꢖm công ty cꢕa KH

▪ Định hướng: Ba nhꢑm KH như đã đề cập

⚫ Bài toán phân cụm liên quan

▪ Tập dữ liệu KH và ba thuộc tꢇnh trung thành RFM

▪ Mục tiêu: Tꢆm ba nhꢑm KH giá trị thấp (KH đa số), KH tiềm năng

cꢑ giá trị (KH trung thành), KH giá trị cao (KH vận động)

▪ Không cꢑ thông tin mô tả về ba nhꢑm KH này: học máy không

giám sát

▪ Bài toán Phân cụm tập DL KH với ba thuộc tꢇnh RFM thành ba

cụm; thông tin mô tả tꢈng cụm.

8

Hꢇc mꢃy không giꢃm sꢃt  tối ưu hóa

⚫ Bꢄi toꢃn hꢇc không giꢃm sꢃt

▪ Cho I là tập dữ liệu I={<i>},

▪ Cho tập G là tập các ánh xꢂ g: I→Z với Z là tập số nguyên

▪ Cho một độ đo “tốt” trên tập các ánh xꢂ G

▪ Tꢆm hàm f: I→Z đạt độ đo “tốt nhất” trên tập G.

▪ Trưꢁng hợp đơn giản:

▪ G = {g là một phân hoꢂch cꢕa I: g={I₁,I₂,…, I_g} và I=I_j}}

▪ tꢆm f là phân hoạch tốt nhất

9

Loại KPDL Mô tả: phân cụm

Phân cụm, vꢇ dụ phân cụm khách hàng theo RF

1^J8^ul_^{y 1}B^2,a²e⁰²s¹ens, Bart_ Bravo, Cristiꢃn_ Verbeke, Wouter. Profit-driven business analyt¹ic⁰s:

a practitioner's guide to transforming big data into added value. Wiley, 2018

Giới thiệu: bꢄi toꢃn phân cụm

⚫ Bài toán

❑ Tập dữ liệu D = {d_i}

❑ Phân các dữ liệu thuộc D thành các cụm

▪ Các dữ liệu trong một cụm: “tương tꢅ” nhau (gꢌn nhau)

▪ Dữ liệu hai cụm: “không tương tꢅ” nhau (xa nhau)

❑ Đo “tương tꢅ” (gꢌn) nhau ?

▪ Tiên đề phân cụm: Nếu ngưꢁi dùng lꢅa chọn một đối tượng d thꢆ họ

cꢎng lꢅa chọn các đối tượng cùng cụm với d

▪ Khai thác “cách chọn lꢅa” cꢕa ngưꢁi dùng

▪ Đưa ra một số độ đo “tương tꢅ” theo biểu diễn dữ liệu

⚫ Một số nội dung liên quan

❑ Xây dꢅng độ đo tương tꢅ

❑ Khai thác thông tin bổ sung

❑ Số lượng cụm cho trước, số lượng cụm không cho trước

11

Sơ bộ tiếp cận phân cụm

⚫ Phân cụm mô hꢆnh và phân cụm phân vùng

❑ Mô hꢆnh: Kết quả là mô hꢆnh biểu diễn các cụm dữ liệu

❑ Vùng: Danh sách cụm và vùng dữ liệu thuộc cụm

⚫ Phân cụm đơn định và phân cụm xác suất

❑ Đơn định: Mỗi dữ liệu thuộc duy nhất một cụm

❑ Xác suất: Danh sách cụm và xác suất một dữ liệu thuộc vào các

cụm

⚫ Phân cụm phẳng và phân cụm phân cấp

❑ Phẳng: Các cụm dữ liệu không giao nhau

❑ Phân cấp: Các cụm dữ liệu cꢑ quan hệ phân cấp cha- con

⚫ Phân cụm theo lô và phân cụm tăng

❑ Lô: Tꢂi thꢁi điểm phân cụm, toàn bộ dữ liệu đã cꢑ

❑ Tăng: Dữ liệu tiếp tục được bổ sung trong quá trꢆnh phân cụm

12

Cꢃc phương phꢃp phân cụm

⚫ Các phương pháp phổ biến

❑ Phân vùng, phân cấp, dꢅa theo mật độ, dꢅa theo lưới, dꢅa theo mô

hꢆnh, và phân cụm mꢁ

⚫ Phân cụm phân vùng (phân cụm phẳng)

❑ Xây dꢅng tꢈng bước phân hoꢂch các cụm và đánh giá chꢐng theo các

tiêu chꢇ tương ꢄng

❑ Tiếp cận: tꢈ dưới lên (gộp dꢌn), tꢈ trên xuống (chia dꢌn)

❑ Độ đo tương tꢅ / khoảng cách

❑ K-mean, k-mediod, CLARANS, …

❑ Hꢂn chế: Không điều chꢋnh được lỗi

⚫ Phân cụm phân cấp

❑ Xây dꢅng hợp (tách) dꢌn các cụm tꢂo cấu trꢐc phân cấp và đánh giá

theo các tiêu chꢇ tương ꢄng

❑ Độ đo tương tꢅ / khoảng cách

❑ HAC: Hierarchical agglomerative clustering

❑ CHAMELEON, BIRRCH và CURE, …

13

Cꢃc phương phꢃp phân cụm

⚫ Phân cụm dꢅa theo mật độ

❑ Hàm mật độ: Tꢆm các phꢌn tử chꢇnh tꢂi nơi cꢑ mật độ cao

❑ Hàm liên kết: Xác định cụm là lân cận phꢌn tử chꢇnh

❑ DBSCAN, OPTICS…

⚫ Phân cụm dꢅa theo lưới

❑ Sử dụng lưới các ô cùng cꢏ: tuy nhiên cụm là các “ô” phân cấp

❑ Tꢂo phân cấp ô lưới theo một số tiêu chꢇ: số lượng đối tượng trong ô

❑ STING, CLIQUE, WaweCluster…

⚫ Phân cụm dꢅa theo mô hꢆnh

❑ Giải thiết: Tồn tꢂi một số mô hꢆnh dữ liệu cho phân cụm

❑ Xác định mô hꢆnh tốt nhất phù hợp với dữ liệu

❑ MCLUST…

⚫ Phân cụm mꢁ

❑ Giả thiết: không cꢑ phân cụm “cꢄng” cho dữ liệu và đối tượng cꢑ thể

thuộc một số cụm

❑ Sử dụng hàm mꢁ tꢈ các đối tượng tới các cụm

❑ FCM (Fuzzy CMEANS),…

14

Một số độ đo cơ bản

⚫ Độ đo tương đồng

❑ Biểu diễn: vector n chiều

❑ Giá trị nhị phân: Ma trận kề, độ đo

Jaccard

❑ Giá trị rꢁi rꢂc [0,m]: Chuyển m giá

trị thành nhị phân, độ đo Jaccard

❑ Giá trị thꢅc : độ đo cosin hai

vector

⚫ Độ đo khác biệt

❑ Đối ngꢔu độ đo tương đồng

❑ Thuộc tꢇnh nhị phân: đối cꢄng,

không đối xꢄng

❑ Giá trị rꢁi rꢂc: hoặc tương tꢅ trên

hoặc dꢂng đơn giản (q thuộc tꢇnh

giống nhau)

❑ Giá trị thꢅc: Khoảng cách

Manhattan, Euclide, Mincowski

❑ Tꢇnh xác định dương, tꢇnh đối

xꢄng, tꢇnh bất đẳng thꢄc tam giác

15

Một số độ đo cơ bản

⚫ Vꢇ dụ về độ khác biệt

❑ CSDL xꢊt nghiệm bệnh

nhân

❑ Quy về giá trị nhị phân:

M/F, Y/N, N/P

❑ Lập ma trận khác biệt cho

tꢈng cặp đối tượng.

❑ Vꢇ dụ, cặp (Nam, Vân):

a=2, b=1, c=1, d=3

D(Nam, Vân)

=(1+1)/(2+1+1)=0.5

16

3. Thuât toꢃn K-mean gꢃn cứng

⚫ Một số lưu ý

❑ Điều kiện dꢈng

▪ Sau bước 2 khô ng có sꢅ thay đổi cụm

▪ Điều kiện dꢈng cưꢏng bꢄc

❖ Khống chế số lꢌn lặp

❖ Giá trị mục tiêu đꢕ nhỏ

❑ Vấn đề chọn tập đꢂi diện ban đꢌu ꢃ bước Khꢃi động

❑ Có thể dùng độ đo khoảng cá ch thay cho độ đo tương tꢅ

17

a. Thuât toꢃn K-mean gꢃn cứng

⚫ Một số lưu ý (tiếp) và vꢇ dụ

❑ Trong bước 2: các trọng tâm cꢑ thể không thuộc S

❑ Thꢅc tế: số lꢌn lặp  50

❑ Thi hành k-mean với dữ liệu trên đĩa

▪ Toàn bộ dữ liệu quá lớn: không thể ꢃ bộ nhớ trong

▪ Với mỗi vꢀng lặp: duyệt CSDL trên đĩa 1 lꢌn

❖ Tꢇnh được độ tương tꢅ cꢕa d với các c_i.

❖ Tꢇnh lꢂi c_imới: bước 2.1 khꢃi động (tổng, bộ đếm); bước 2.2

cộng và tăng bộ đếm; bước 2.3 chꢋ thꢅc hiện k phꢊp chia.

18

Bing Liu (2007), Web Data Mining: Exploring Hyperlinks, Contents, and Usage Data, Spinger, 2007.

Thuât toꢃn K-mean

⚫ Ưu điểm

❑ Đơn giản, dễ sử dụng

❑ Hiệu quả về thꢁi gian: tuyến tꢇnh O(tkn), t số lꢌn lặp, k số cụm, n

là số phꢌn tử

❑ Một thuật toán phân cụm phổ biến nhất

❑ Thưꢁng cho tối ưu cục bộ. Tối ưu toàn cục rất khꢑ tꢆm

⚫ Nhược điểm

❑ Phải “tꢇnh trung bꢆnh được”: dữ liệu phân lớp thꢆ dꢅa theo tꢌn số

❑ Cꢌn cho trước k : số cụm

❑ Nhꢂy cảm với ngoꢂi lệ (cách xa so với đꢂi đa số dữ liệu cꢀn lꢂi):

ngoꢂi lệ thꢅc tế, ngoꢂi lệ do quan sát sai (làm sꢂch dữ liệu)

❑ Nhꢂy cảm với mꢔu ban đꢌu: cꢌn phương pháp chọn mꢔu thô tốt

❑ Không thꢇch hợp với các tập dữ liệu không siêu-ellip hoặc siêu

cꢌu (các thành phꢌn con không ellip/cꢌu hꢑa)

Bing Liu (2007), Web Data Mining: Exploring Hyperlinks, Contents, and Usage Data, Spinger, 2007.

19

Thuâ t toá n K-mean

Trái: Nhꢂy cảm với chọn mꢔu ban đꢌu

Phải: Không thꢇch hợp với bộ dữ liệu không siêu ellip/cꢌu hꢑa

Bing Liu (2007), Web Data Mining: Exploring Hyperlinks, Contents, and Usage Data, Spinger, 2007.

20

Bài giảng Nhập môn khai phá dữ liệu - Chương 6: Phân cụm dữ liệu và hệ thống tư vấn - Hà Quang Thụy