Bài giảng Khai phá dữ liệu - Chương 4: Phân cụm dữ liệu

Chia sẻ: Nguyễn Thị Hiền Phúc | Ngày: | Loại File: PPTX | Số trang:47

Thêm vào BST

Báo xấu

88
lượt xem 9
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng cung cấp cho người học các kiến thức: Phân cụm dữ liệu. Hi vọng đây sẽ là một tài liệu hữu ích dành cho các bạn sinh viên đang theo học môn dùng làm tài liệu học tập và nghiên cứu.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Khai phá dữ liệu - Chương 4: Phân cụm dữ liệu

TRƯỜNG ĐẠI HỌC HÀNG HẢI VIỆT NAM KHOA CÔNG NGHỆ THÔNG TIN BÀI GIẢNG MÔN HỌC KHAI PHÁ DỮ LIỆU CH ƯƠN G 4 : P HÂ N C ỤM D Ữ LIỆU Gi ản g v iê n : Th S . N g u y ễn V ươn g Th ịn h B ộ m ô n : H ệ t h ốn g t h ô n g t in H ải P h ò n g ,
Th ô n g t in v ề g i ản g v iê n Họ và tên Nguyễn Vương Thịnh Đơn vị công tác Bộ môn Hệ thống thông tin – Khoa Công nghệ thông tin Học vị Thạc sỹ Chuyên ngành Hệ thống thông tin Cơ sở đào tạo Trường Đại học Công nghệ - Đại học Quốc Gia Hà Nội Năm tốt nghiệp 2012 Điện thoại 0983283791 Email thinhnv@vimaru.edu.vn Website cá nhân http://scholar.vimaru.edu.vn/thinhnv 2
Th ô n g t in v ề h ọc p h ần Tên học phần Khai phá dữ liệu Tên tiếng Anh Data Mining Mã học phần 17409 Số tín chỉ 03 tín chỉ Số tiết lý thuyết 39 tiết (13 tuần x 03 tiết/tuần) Số tiết thực hành 10 tiết (05 tuần x 02 tiết/tuần) Bộ môn phụ trách Hệ thống thông tin P H ƯƠN G P HÁP H ỌC TẬP, N GHIÊN CỨU v N g h e g i ản g , t h ảo lu ận , t ra o đ ổi v ới g i ản g v iê n t rê n l ớp . P H ƯƠTNựG P n g HÁP h iê n Đ c ứ ÁNu tH GIÁ à i li ệu v à là m b à i t ập ở n h à . v v S V p h ải t h a m d ự ít n h ất 7 5 % t h ời g ia n . v Có 0 2 b à i k i ểm t ra v i ết g i ữa h ọc p h ần ( X = X2 = ( L1 + L2 ) /2 ) . 3 v Th i k ết t h ú c h ọc p h ần b ằn g h ìn h t h ức t r ắc n g h i ệm k h á c h q u a n t rê n m á y t ín h ( Z = 0 . 5 X + 0 . 5 Y) .
Tài liệu tham khảo 1. Jiawei Han and Micheline Kamber, D a t a Min in g Co n c e p t s a n d Te c h n iq u e s , Elsevier Inc, 2006. 2. Ian H. Witten, Eibe Frank, D a t a Min in g – P ra c t ic a l Ma c h in e Le a rn in g To o ls a n d Te c h n iq u e s ( t h e s e c o n d e d it io n ) , Elsevier Inc, 2005 (sử dụng kèm với công cụ Weka). 3. Elmasri, Navathe, Somayajulu, Gupta, Fu n d a m e n t a ls o f D a t a b a s e S y s t e m s ( t h e 4 t h Ed it io n ) , Pearson Education Inc, 2004. 4. Hà Quang Thụy, Phan Xuân Hiếu, Đoàn Sơn, Nguyễn Trí Thành, Nguyễn Thu Trang, Nguyễn Cẩm Tú, Giá o t rìn h Kh a i p h á d ữ li ệu We b , NXB Giáo dục, 2009 4
5
Cô n g c ụ p h ần m ềm h ỗ t rợ P h ần m ềm We k a đ ược p h á t t ri ển b ởi n h ó m n g h iê n c ứu c ủa t r ườn g Đ ại h ọc Wa ik a t o ( N e w Ze a la n d ) t ừ n ă m 1 9 9 9 . Có t h ể d o w n lo a d v ề t ại đ ịa c h ỉ: h t t p ://w w w . c s . w a ik a t o . a c . n z /m l/w e k a /d o w n lo a d in g . h t m l 6
CHƯƠNG 4: PHÂN CỤM DỮ LIỆU 4.1. KHÁI NIỆM VỀ PHÂN CỤM DỮ LIỆU 4.2. ĐỘ ĐO SỬ DỤNG TRONG PHÂN CỤM 4.3. PHÂN CỤM DỮ LIỆU VỚI GIẢI THUẬT K-MEANS (Phân cụm từ trên xuống) 4.4. PHÂN CỤM DỮ LIỆU VỚI GIẢI THUẬT HAC (Phân cụm từ dưới lên) 4.5. SO SÁNH GIẢI THUẬT K-MEANS VÀ HAC 4.6. PHÂN CỤM DỮ LIỆU VỚI PHẦN MỀM WEKA 7
4.1. KHÁI NIỆM VỀ PHÂN CỤM DỮ LIỆU 4.1.1. Phân cụm dữ liệu (clustering) là gì?  Phân cụm dữ liệu là quá trình phân chia các đối tượng dữ liệu (bản ghi) vào các nhóm (cụm) sao cho các đối tượng thuộc về cùng một cụm thì có các đặc điểm “tương tự” nhau (“gần” nhau) và các đối tượng thuộc về các cụm khác nhau thì có các đặc điểm “khác” nhau (“xa” nhau). Đại lượng nào xác định sự “tương tự” và “khác” nhau giữa các đối tượng?  Khác với phân lớp, phân cụm được xem quá trình học không có giám sát (unsupervised learning). Dữ liệu được phân vào các cụm mà không cần có tập mẫu học (training sample). 8
4.1.2. Ứng dụng của phân cụm dữ liệu Phân cụm dữ liệu có thể ứng dụng trong nhiều lĩnh vực:  Nghiên cứu thị trường (Marketing): Xác định các nhóm khách hàng (khách hàng tiềm năng, khách hàng lớn, phân loại và dự đoán hành vi khách hàng,…) sử dụng sản phẩm hay dịch vụ của công ty để giúp công ty có chiến lược kinh doanh hiệu quả hơn.  Sinh học (Biology): Phân nhóm động vật và thực vật dựa vào các thuộc tính của chúng.  Quản lý thư viện (Libraries): Theo dõi độc giả, sách, dự đoán nhu cầu của độc giả…  Tài chính, Bảo hiểm (Finance and Insurance): Phân nhóm các đối tượng sử dụng bảo hiểm và các dịch vụ tài chính, dự đoán xu hướng 9 (trend) của khách hàng, phát hiện gian lận tài chính (identifying
4 . 2 . Đ Ộ Đ O S Ử D ỤN G TRON G P HÂN • CỤ Để xác định tính chất tương M giữa các đối tượng dữ liệu, đồng người ta thường sử dụng khái niệm “khoảng cách” (distance). • Hai đối tượng có “khoảng cách” càng nhỏ thì càng “tương tự” (giống) nhau và có “khoảng cách” càng lớn thì càng “khác” nhau. Xét hai đ ối tượng dữ liệu (bản ghi) ri và rj , mỗi đối tượng có n thuộc tính: ri = ( xi1 , xi 2 ,..., xin ) rj = ( x j1 , x j 2 ,..., x jn ) Khoảng cách Euclid (Euclidean Distance): d (ri , rj ) = ( xi1 − x j1 ) 2 + ( xi 2 − x j 2 ) 2 + ... + ( xin − x jn ) 2 Kh o ản g c á c h Ma n h a t t a n (Manhattan Distance): d (ri , rj ) = xi1 − x j1 + xi 2 − x j 2 + ... + xin − x jn 10
4.3. PHÂN CỤM VỚI GIẢI THUẬT KMEANS 4.3.1. Khái niệm về trọng tâm cụm Xét cụm dữ liệu Cj gồm m đối tượng thuộc cụm: C j = { r1 , r2 , r3 ,..., rm } Mỗi đối tượng có n thuộc tính: ri = ( xi1 , xi 2 , xi 3 ,..., xin ) (1 i m) Trọng tâm cụm (mean/centroid) là đối tượng mj được xác định: �1 m 1 m 1 m � m j = � �xi1 , �xi 2 ,..., �xin � �m i =1 m i =1 m i =1 � Ví dụ: Cho cụm C1 = {r1, r2, r3} với r1 = (1, 2, 1), r2 = (1, 3, 2), r3 = (1, 1, 3). r 1 Trọng � 1 + 1cụm tâm + 1 2là:+ 3 + 1 1 + 2 + 3 � m1 = � , , �= ( 1, 2, 2 ) m1 � 3 3 3 � r r C1 2 3 11
4.3.2. Nội dung giải thuật K-means Input: Tập dữ liệu D gồm m đối tượng dữ liệu (bản ghi): r1, r2,…, rm . Số lượng cụm k. Output: k cụm dữ liệu. Begin Chọn ngẫu nhiên k đối tượng làm trọng tâm cho k cụm; Repeat Gá n m ỗi đ ối t ượn g ri c h o c ụm m à k h o ản g c á c h t ừ đ ối t ượn g đ ến t rọn g t â m c ụm là n h ỏ n h ất t ro n g s ố k c ụm ; Xá c đ ịn h lại t rọn g t â m c h o m ỗi c ụm d ựa t rê n c á c đ ối t ượn g đ ược g á n c h o c ụm ; Until (Kh ô n g c ò n s ự t h a y đ ổi); End; 12 (xem “Fundamentals of Database Systems – 4th Edition” trang 680)
r r 2 1 m1 m2 m3 C1 C2 C3 d(r1,m1)
4.3.3. Điều kiện dừng của giải thuật K-means Có hai kết cục có thể xảy ra đối với giải thuật K-means: Giải thuật hội tụ: không còn sự phân chia lại các đối tượng giữa các cụm, hay trọng tâm các cụm là không đổi. Lúc đó tổng các tổng khoảng cách nội tại từ các đối tượng thuộc cụm đến trọng tâm cụm là cực tiểu: k J = ��d ( ri , m j ) min j =1 ri C j Đây là điều kiện dừng “lý tưởng”. J Jm i n n 14
Giải thuật không hội tụ: trọng tâm của các cụm cứ liên tục thay đổi. Lúc đó có 3 lựa chọn: q Dừng giải thuật khi số lượng vòng lặp vượt quá một ngưỡng nào đó định trước. q Dừng giải thuật khi giá trị J nhỏ hơn một ngưỡng nào đó định trước. J JH Jmin nH nmi n n q Dừng giải thuật khi hiệu giá trị của J trong hai vòng lặp liên tiếp nhỏ hơn một ngưỡng nào đó định trước: |Jn+1 – Jn|
BÀI TẬP ÁP D ỤN G Bài tập số 1: Cho tập dữ liệu D như sau: X1 X2 r1 1 2 r2 2 2 r3 2 3 r4 3 3 r5 3 4 r6 2 4 Hãy phân cụm tập dữ liệu D với k = 2. 16
Chọn m1 = r1 = (1, 2), m2 = r6 = (2, 4) . Lần lặp 1: r2 = (2, 2) d(r2, m1) = |2 - 1| + |2 - 2| = 1, d(r2, m2) = |2 - 2| + |2 - 4| = 2 ⟹ r2 ∈ C1 r3 = (2, 3) d(r3, m1) = |2 - 1| + |3 - 2| = 2, d(r3, m2) = |2 - 2| + |3 - 4| = 1 ⟹ r3 ∈ C2 r4 = (3, 3) d(r4, m1) = |3 - 1| + |3 - 2| = 3, d(r4, m2) = |3 - 2| + |3 - 4| = 2 ⟹ r4 ∈ C2 r5 = (3, 4) d(r5, m1) = |3 - 1| + |4 - 2| = 4, d(r5, m2) = |3 - 2| + |4 - 4| = 1 ⟹ r5 ∈ C2 Ta thu được 2 cụm: C1 = {r1, r2} và C2 = {r3, r4 , r5 , r6} Cập nhật trọng tâm cụm: �1+2 2+2 � m1= � , �= ( 1.5,1) �2 2 � �2+3+3+2 3+3+4+4 � m2 = � , = ( 2.5,3.5 ) � � 4 4 � 17
Với m1 = (1.5, 2), m2 = (2.5, 3.5) Lần lặp 2: r1 = (1, 2) d(r1, m1) = |1 - 1.5| + |2 - 2| = 0.5, d(r1, m2) = |1 - 2.5| + |2 - 3.5| = 3 ⟹ r1 ∈ C1 r2 = (2, 2) d(r2, m1) = |2 - 1.5| + |2 - 2| = 0.5, d(r2, m2) = |2 - 2.5| + |2 - 3.5| = 2 ⟹ r2 ∈ C1 r3 = (2, 3) d(r3, m1) = |2 - 1.5| + |3 - 2| = 1.5, d(r3, m2) = |2 - 2.5| + |3 - 3.5| = 1 ⟹ r3 ∈ C2 r4 = (3, 3) d(r4, m1) = |3 - 1.5| + |3 - 2| = 2.5, d(r4, m2) = |3 - 2.5| + |3 - 3.5| = 1 ⟹ r4 ∈ C2 r5 = (3, 4) d(r5, m1) = |3 - 1.5| + |4 - 2| = 3.5, d(r5, m2) = |3 - 2.5| + |4 - 3.5| = 1 ⟹ r5 ∈ C2 18 r6 = (2, 4)
X X 2 2 5 5 r r r r 4 6 5 4 6 5 r r r r 3 3 3 4 3 4 r r r r 1 2 2 1 2 2 1 1 0 1 2 3 4 5 X 0 1 2 3 4 5 X 1 1 19
Bài tập số 2: Cho tập dữ liệu D như sau: X1 X2 A 1 1 B 2 1 C 4 3 D 5 4 Hãy phân cụm tập dữ liệu D với k = 2. 20