1. Trang Chủ
  2. Cơ sở dữ liệu
  3. Bài giảng Nhập môn khai phá dữ liệu: Chương 6 - PGS. TS. Hà Quang Thụy

Bài giảng Nhập môn khai phá dữ liệu: Chương 6 - PGS. TS. Hà Quang Thụy

Chương 6 - Phân cụm dữ liệu và hệ thống tư vấn. Những nội dung chính trong chương này gồm có: 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. 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/

Thể loại Tài liệu miễn phí Cơ sở dữ liệu

Số trang 55

Ngày tạo 10/10/2021 6:10:07 PM +00:00

Loại tệp PDF

Kích thước 1.39 M

Tên tệp

Tải Bài giảng Nhập môn khai phá dữ liệu: Chương 6 - PG... (.pdf)

Xem mẫu

  1. 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
  2. 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
  3. 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ư trú, v.v. ▪ quan trọng để tiếp thị và quản lý quan hệ khách hàng ▪ Ví dụ: chuyển nhà, sinh con, v.v. ▪ Một số loại doanh nghiệp được tổ chức xung quanh từng giai đoạn sống: mẹ và 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
  4. 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
  5. Khung nhìn hành trình KH: thang giá trị Đối sánh ▪ Ứng viên tiềm năng ~ Ứng viên nghi vấn ▪ Ứng viên triển vọng ~ Ứng viên tiềm năng ▪ Khách hàng mới ~ Khách hàng mới ▪ Khách hàng giá trị thấp ~ Khách hàng lặp lại ▪ Khách hàng giá trị cao tiềm năng ~ Khách hàng đa số 5 ▪ Khách hàng giá trị cao ~ Khách hàng vận động
  6. 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
  7. 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
  8. 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
  9. 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={}, ▪ 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={I1,I2,…, Ig} và I=Ij}} ▪ tìm f là phân hoạch tốt nhất 9
  10. 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 18_Baesens, July 12, 2021 Bart_ Bravo, Cristián_ Verbeke, Wouter. Profit-driven business analytics: 10 a practitioner's guide to transforming big data into added value. Wiley, 2018
  11. Giới thiệu: bài toán phân cụm ⚫ Bài toán ❑ Tập dữ liệu D = {di} ❑ 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
  12. 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
  13. 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
  14. 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
  15. 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
  16. 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
  17. 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 17 ❑ Có thể dùng độ đo khoảng cách thay cho độ đo tương tự
  18. 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 ci. ❖ Tính lại ci mớ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.
  19. 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
  20. 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
nguon tai.lieu . vn
Tin học văn phòng Đồ họa - Thiết kế - Flash Quản trị Web Cơ sở dữ liệu Quản trị mạng Kỹ thuật lập trình Hệ điều hành Phần cứng An ninh - Bảo mật Chứng chỉ quốc tế Thủ thuật máy tính Điện - Điện tử Kinh tế học Hoá học Xã hội học Môi trường