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

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.
Nội dung trích xuất từ tài liệu:
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 TINBÀI GIẢNG MÔN HỌCKHAI PHÁ DỮ LIỆU CH ƯƠN G4 :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 ảiP 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/thinhnv2 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 GP HÁP H ỌCTẬP, N GHIÊN CỨU v N g h e g i ản g , t h ảo lu ận , t ra o đ ổiv ớig i ản g v iê n t rê n l ớp . P H ƯƠTNựGP n g HÁP h iê nĐ c ứ ÁNu tHGIÁ à ili ệu v à là m b à it ập ởn h à . v v S Vp h ảit h a m d ự ít n h ất 7 5 %t h ờig 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àiliệuthamkhảo1. 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ụngkèmvớicôngcụ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 45 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 l6 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 WEKA7 4.1.KHÁINIỆMVỀPHÂNCỤMDỮ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ướng9 (trend) của khách hàng, phát hiện gian lận tài chính (identifying 4 . 2 . Đ ỘĐ OS ỬD ỤN GTRON GP 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éthaiđ ốitượngdữliệu(bảnghi)rivàrj,mỗiđốitượngcónthuộctính: ri = ( xi1 , xi 2 ,..., xin ) rj = ( x j1 , x j 2 ,..., x jn ) KhoảngcáchEuclid(EuclideanDist ...