Tài liệu Luận văn tìm hiểu các phương pháp phân cụm dữ liệu ứng dụng xây dựng bản đồ phân bố bệnh trên địa bàn tỉnh thái nguyên​

ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN MINH TÚ TÌM HIỂU CÁC PHƢƠNG PHÁP CỤM DỮ LIỆU ỨNG DỤNG XÂY DỰNG BẢN ĐỒ PHÂN BỐ BỆNH TRÊN ĐỊA BÀN TỈNH THÁI NGUYÊN Mã số: 60480101 Ngƣời hƣớng dẫn khoa học: TS. NGUYỄN MINH HẢI LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái Nguyên - 2015 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn LỜI CẢM ƠN Em xin chân thành cảm ơn Trƣờng Đại học Công nghệ Thông tin và Truyền thông – Đại học Thái Nguyên đã tạo điều kiện cho em thực hiện luận văn này. Em xin gửi lời cảm ơn sâu sắc tới thầy giáo TS Nguyễn Hải Minh, trƣởng khoa Công nghệ thông tin – Trƣờng Đại học Công nghệ Thông tin và Truyền thông – Đại học Thái Nguyên đã trực tiếp hƣớng dẫn em trong quá trình thực hiện luận văn. Em cũng xin gửi lời cảm ơn tới các thầy, cô đã có những ý kiến đóng góp bổ ích và đã tạo mọi điều kiện tốt nhất cho em trong suốt thời gian thực hiện luận văn. Xin cảm ơn các bạn học đồng khóa đã thƣờng xuyên động viên, giúp đỡ tôi trong quá trình học tập. Cuối cùng, em xin gửi lời cảm ơn đến gia đình và đồng nghiệp vì sự ủng hộ và động viên đã dành cho em trong suốt quá trình học tập cũng nhƣ thực hiện luận văn này. Thái Nguyên, tháng 11 năm 2015 Học viên Nguyễn Minh Tú Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn LỜI CAM ĐOAN Em xin cam đoan về nội dung đồ án tốt nghiệp với tên đề tài “Tìm hiểu các phƣơng pháp phân cụm dữ liệu ứng dụng xây dựng bản đồ phân bố bệnh trên địa bàn tỉnh Thái Nguyên” không sao chép nội dung từ các luận văn khác, hay các sản phẩm tƣơng tự mà không phải do em làm ra. Sản phẩm luận văn là do chính bản thân em tìm hiểu và xây dựng nên. Nếu có gì sai em xin chịu mọi hình thức kỷ luật của Trƣờng Đại học Công nghệ Thông tin và Truyền thông – Đại học Thái Nguyên. Thái Nguyên, tháng 11 năm 2015 Học viên Nguyễn Minh Tú Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn MỤC LỤC LỜI CẢM ƠN .............................................................................................................. i LỜI CAM ĐOAN ..................................................................................................... iii MỤC LỤC .................................................................................................................. iv DANH MỤC BẢNG .................................................................................................. vi DANH MỤC CÁC HÌNH VẼ...................................................................................vii MỞ ĐẦU ..................................................................................................................... 1 MỘT SỐ KẾT QUẢ NGHIÊN CƢ́U KHÁC ............................................................. 2 CHƢƠNG I. KHAI PHÁ DỮ LIỆU .......................................................................... 3 1.1. Tổng quan khai phá dữ liệu ............................................................................. 3 1.2. Quá trình khám phá tri thức và khai phá dữ liệu ............................................. 3 1.2.1. Quá trình khám phá tri thức ...................................................................... 3 1.2.2. Quá trình khai phá dữ liệu ......................................................................... 6 1.3. Các kỹ thuật trong khai phá dữ liệu ................................................................. 7 1.4. Mô ̣t số thách thƣ́c trong khai phá dƣ̃ liê ̣u ...................................................... 10 CHƢƠNG II. PHÂN CỤM DƢ̃ LIÊU ̣ VÀ CÁC THUẬT TOÁNPHÂN CỤM ...... 12 2.1. Khái niệm phân cụm dữ liệu .......................................................................... 13 2.1.1. Một số định nghĩa .................................................................................... 13 2.1.2. Dữ liệu và độ đo ...................................................................................... 13 2.2. Các yêu cầu đối với phƣơng pháp phân cụm dữ liệu .................................... 14 2.3. Các kỹ thuật phân cụm .................................................................................. 16 2.3.1. Các kỹ thuật phân cụm cơ bản ................................................................ 16 2.3.2. Các kỹ thuật phân cụm khác.................................................................... 17 2.3.3. Một số tiêu chuẩn đánh giá hiệu quả phân cụm ...................................... 23 2.4. Một số thuật toán trong phân cụm dữ liệu ..................................................... 24 2.4.1. Các thuật toán phân cụm phân hoạch ...................................................... 24 2.4.2. Các thuật toán phân cụm phân cấp .......................................................... 32 2.4.3. Các thuật toán phân cụm dựa trên mật độ ............................................... 38 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 2.4.3. Các thuật toán phân cụm dựa vào lƣới .................................................... 42 2.4.4. Các thuật toán phân cụm dựa trên mô hình ............................................. 44 CHƢƠNG 3: XÂY DƢ̣NG BẢN ĐỒ PHÂN BỐ BÊN ̣ H ........................................ 46 3.1. Bài toán phân cụm dữ liệu hồ sơ bệnh án ...................................................... 46 3.2. Dữ liệu và tiêu chí xác định ........................................................................... 46 3.2.1. Một số đặc điểm tập dữ liệu gốc ............................................................. 46 3.2.2. Tiền xử lý dữ liệu gốc ............................................................................. 48 3.3. Lựa chọn phƣơng pháp phân cụm ................................................................. 54 3.4. Kết quả phân cụm dữ liệu mẫu ...................................................................... 55 3.5. Biểu điễn kết quả phân bố bệnh trên bản đồ.................................................. 61 KẾT LUẬN ............................................................................................................... 63 TÀI LIỆU THAM KHẢO ......................................................................................... 65 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn DANH MỤC BẢNG Bảng 3.1: Các loại bệnh và ký hiệu ..........................................................................55 Bảng 3.2: Các khu vực hành chính và ký hiệu..........................................................56 Bảng 3.3: Dữ liệu đầu vào cho phân cụm phân cấp ..................................................56 Bảng 3.4: Biểu diễn kết quả phân cụm chi tiết .........................................................59 Bảng 3.5: Biểu diễn kết quả phân cụm theo tiêu chí bệnh ........................................61 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn DANH MỤC CÁC HÌNH VẼ Hình 1.1: Các giai đoạn trong quá trình khám phá tri thức ........................................4 Hình 1.2: Quá trình khai phá dữ liệu...........................................................................7 Hình 2.1: Ví dụ về phân cụm theo mật độ[4]............................................................18 Hình 2.2: Cấu trúc phân cụm dựa trên lƣới[4] ..........................................................19 Hình 2.3: Ví dụ về phân cụm dựa trên mô hình[4] ...................................................20 Hình 2.4: Cách mà các cụm có thể đƣa ra.................................................................22 Hình 2.5: Thuật toán k-means ...................................................................................25 Hình 2.6: Sự thay đổi tâm cụm trong k-means khi có phần tử ngoại lai ..................28 Hình 2.7: Phân cụm phân cấp tập theo phƣơng pháp “dƣới lên” [4] ........................33 Hình 2.8: Single link .................................................................................................33 Hình 2.9: Complete link ............................................................................................33 Hình 2.10: Các bƣớc cơ bản của AGNES[4] ............................................................35 Hình 2.11: Các bƣớc cơ bản của DIANA[4] ............................................................36 Hình 2.12: Cấu trúc cây CF.......................................................................................37 Hình 2.13: Hình dạng các cụm đƣợc khám phá bởi thuật toán DBSCAN ...............40 Hình 2.14: Sắp xếp cụm trong OPTICS phụ thuộc vào [4].....................................41 Hình 3.1: Sơ đồ khối giải quyết bài toán ..................................................................46 Hình 3.2: Phân tích dữ liệu gốc, thuộc tính “HO TEN” ...........................................49 Hình 3.3: Dữ liệu gốc sau khi loại bỏ thuộc tính thừa và dữ liệu trùng lặp ..............50 Hình 3.4: Phân tích dữ liệu gốc, thuộc tính “QUAN HUYEN” ...............................51 Hình 3.5: Loại bỏ một số giá trị của thuộc tính “QUAN HUYEN” .........................52 Hình 3.6: Dữ liệu trƣớc và sau khi lọc thuộc tính “CHUAN DOAN DAU RA” .....53 Hình 3.7: Cấu và phân bố dữ liệu mẫu......................................................................58 Hình 3.8: Thiết lập tham số thuật toán K-means ......................................................58 Hình 3.9: Kết quả phân cụm chi tiết .........................................................................59 Hình 3.10: Kết quả phân cụm dựa trên loại bệnh .....................................................60 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn Hình 3.11: Bản đồ phân bố bệnh các khu vực ..........................................................62 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 1 MỞ ĐẦU Đề tài tìm hiểu các phƣơng pháp phân cụm dữ liệu, đánh giá ƣu nhƣợc điểm của mỗi phƣơng pháp để tìm ra phƣơng pháp phù hợp áp dụng trên tập dữ liệu mẫu. Kết quả sẽ đƣợc dùng để xây dựng bản đồ phân bố bệnh trên địa bàn tỉnh Thái Nguyên nhằm hỗ trợ công tác lên kế hoạch dự trù cơ sở vật chất, thuốc và các trang thiết bị khác cho các trung tâm y tế của Tỉnh. Thái Nguyên là một tỉnh trung du miền núi thuộc vùng Đông Bắc của Việt Nam với diện tích hơn 3500 km2 và dân số khoảng hơn một triệu ngƣời; bao gồm 9 đơn vị hành chính: Thành phố Thái Nguyên; Thị xã Sông Công và 7 huyện: Phổ Yên, Phú Bình, Đồng Hỷ, Võ Nhai, Định Hóa, Đại Từ, Phú Lƣơng. Trong đó, tổng số gồm 180 xã, trong đó có 125 xã vùng cao và miền núi, còn lại là các xã đồng bằng và trung du.Tỉnh Thái Nguyên có nhiều dân tộc anh em sinh sống. Tuy nhiên, dân cƣ phân bố không đều, vùng cao và vùng núi dân cƣ rất thƣa thớt, trong khi đó ở thành thị và đồng bằng dân cƣ lại dày đặc. Mật độ dân số thấp nhất là huyện Võ Nhai 72 ngƣời/ km2, cao nhất là Thành phố Thái Nguyên với mật độ 1.260 ngƣời/ km2. Do sự khác biệt lớn trong cơ cấu dân số, lối sống, trình độ dân trí nên có những sự khác biệt đáng kể trong các hình thức bệnh trong các khu vực hành chính khác nhau. Nếu các thông tin về hình thức bệnh và các vấn đề sức khỏe trong mỗi khu vực hành chính đƣợc thu thập đầy đủ, nó sẽ có thể sẽ giúp việc phân bổ nguồn lực hiệu quả để phát triển các chính sách y tế công cộng cho các khu vực khác nhau. Luận văn sử dụng các kỹ thuật khai thác dữ liệu để phân tích dữ liệu y tế thuộc Đại học Y Dƣợc Thái Nguyên trongbốn tháng đầu năm 2015. Hy vọng rằng việc sử dụng các công cụ này một cách hiệu quả có thể phân tích và điều tra hình thức bệnh trong khu vực hành chính khác nhau của Thái Nguyên để tiếp tục xây dựng một bản đồ y tế cho tỉnh Thái Nguyên. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 2 MỘT SỐ KẾT QUẢ NGHIÊN CƢ́U KHÁC Ching-Kuo Wei et al. [2] Nghiên cứu này sử dụng các kỹ thuật khai phá dữ liệu điều tra các loại bệnh trong các khu vực hành chính khác nhau và phân tích sự khác nhau giữa các khu vực hành chính để tiếp tục xây dựng một bản đồ phân bố bệnh. Nghiên cứu hy vọng sẽ giúp xây dựng trong tƣơng lai các chiến lƣợc y tế và phân bố các nguồn lực một cách thích hợp. Lavrac [4] đề xuất một số kỹ thuật khai thác dữ liệu có thể đƣợc áp dụng trong y học, và đặc biệt là một số kỹ thuật máy học bao gồm các cơ chế mà làm cho chúng phù hợp hơn cho việc phân tích cơ sở dữ liệu y tế (nguồn gốc của các quy tắc mang tính biểu tƣợng, sử dụng các kiến thức nền, độ nhạy và độ đặc hiệu của giới thiệu gây ra). Tầm quan trọng của thông dịch các kết quả phân tích dữ liệu là thảo luận và minh họa trên các ứng dụng y tế đã chọn. Lavrac et al. [5] đề xuất một phƣơng pháp khai thác dữ liệu và công nghệ trực quan đƣợc sử dụng để hỗ trợ việc ra quyết định liên quan đến sức khỏe cộng đồng tại Slovenia.Mục đích nhằm khai thác cơ sở dữ liệu y tế công cộng để xác định khả năng đáp ứng của các dịch vụ y tế công cộng đối với các khu vực. Các kết quả có thể sử dụng để phát triển các chính sách chăm sóc sức khỏe cơ quan y tế. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 3 CHƢƠNG I. KHAI PHÁ DỮ LIỆU 1.1. Tổng quan khai phá dữ liệu Cùng với sự phát triển mạnh mẽ của công nghệthông tin,lƣợng thông tin của nhân loại đƣợclƣu trữ trên các thiết bị điện tử, các hệ thống thông tin ngày một tăng. Việc ứng dựng công nghệ thông tin mạnh mẽ, sâu rộng trong nhiều lĩnh vực: khoa học, kinh doanh, chứng khoán, thƣơng mại, giao dịch,… đã tích lũy nên nguồn dữ liệu khổng lồ.Sự bùng nổ này đãdẫn tới một yêu cầu cấp thiết là cần có những kỹ thuật và công cụ mới để tựđộng chuyển đổi lƣợng dữ liệu khổng lồ kia thành các tri thức có ích. Do đó, khai phá dữ liệu (Data Mining) và các kỹ thuật phai phá dữ liệu ra đời đã phần nào giải quyết đƣợc đƣợc yêu cầu trên. Trithức đƣợc xem nhƣ là các thông tin tích hợp, bao gồm các sự kiện và mốiquan hệ giữa chúng, đã đƣợc nhận thức, khám phá, hoặc nghiên cứu. Nói cáchkhác, tri thức có thể đƣợc coi là dữ liệu ở mức độ cao của sự trừu tƣợng vàtổng quát. Khám phá tri thức là quá trình tìm ra những tri thức, đó là những mẫu tìm ẩn, trƣớc đó chƣa biết và là thông tin hữu ích đáng tin cậy.Khai phá dữ liệu là một bƣớc trong quá trình khám phá tri thức, gồmcác thuật toán khai thác dữ liệu chuyên dùng dƣới một số qui định về hiệu quảtính toán chấp nhận đƣợc để tìm ra các mẫu hoặc các mô hình trong dữ liệu.Nói cách khác, mục tiêu của khai phá dữ liệu là tìm kiếm các mẫu hoặc môhình tồn tại trong cơ sở dữ liệu (CSDL) nhƣng ẩn trong khối lƣợng lớn dữ liệu. Khám phá tri thức từ CSDL là một quá trình sử dụng các phƣơng pháp và công cụ tin học để khám phá,lựa chọn đƣợc tập con dữ liệu tốt, từ đó phát hiện các mẫu phù hợp với mục tiêu đề ra. Đó chính là tri thức, đƣợc rút ra từ CSDL, thƣờng để phục vụ cho việc giải quyết một loạt nhiệm vụ nhất định trong một lĩnh vực nhất định. 1.2. Quá trình khám phá tri thức vàkhai phá dữ liệu 1.2.1 . Quá trình khám phá tri thức Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 4 Quá trình khám phá tri thức là một quá trình bao gồm nhiều giai đoạnvới nhiều hoạt động tƣơng tác giữa con ngƣời và CSDL thông qua việc hỗ trợ của các phƣơng pháp, thuật toán cũng nhƣ các công cụ tin học. Tri thức đƣợc rút ra từ các CSDL để phục vụ cho việc giải quyết một loạt nhiệm vụ nhất định trong một lĩnh vực nào đó. Do đó quá trình khám phá tri thức cũng mang tính chất hƣớng nhiệm vụ, không phải phát hiện mọi tri thức đƣợc bất kỳ mà phát hiện tri thức nhằm giải quyết tốt vấn đề đặt ra. Hình 1.1: Các giai đoạn trong quá trình khám phá tri thức Quá trình khám phá tri thức gồm sáu giai đoạn[1] nhƣ hình 1.1. Bắt đầu của quá trình là kho dữ liệu thô và kết thúc với tri thức đƣợcchiết xuất ra. Đây là một quátrình rất khó khăn gặp phải rất nhiều vƣớng mắc: quản lý các tập dữ liệu,phải lặp đi lặp lại toàn bộ quá trình, ... 1. Gom dữ liệu: Tập hợp dữ liệu là bƣớc đầu tiên trong quá trìnhkhai phá dữ liệu. Đây là bƣớc đƣợc khai thác trong một cơ sở dữliệu, một kho dữ liệu nguồn thông tin Internet. 2. Trích lọc dữ liệu : Ở giai đoa ̣ n này dữ liệu đƣợc lựa chọn hoặcphân chia theomột số tiêu chuẩn nào đó phục vụ mục đích khaithác. 3. Làm sạch, tiền xử lý và chuẩn bị trƣớc dữ liệu: Dữ liệu cần đƣợc làm sạch để khắc phục đối với trƣờng dữ liệu rỗng, dƣ thừa hoặc dữ liệu không hợp lệ. Giai Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 5 đoạn này là một bƣớc rấtquan trọng trong quá trình khai phá dữ liệu. Một số lỗi thƣờngmắc phải trong khi gom dữ liệu là tính không đủ chặt chẽ.Vì vậy, dữ liệu thƣờng chứa các giá trị vô nghĩa và không có khảnăng kết nối dữ liệu. Giai đoạnnày sẽ tiến hành xử lý những dạng dữ liệu không chặt chẽ nóitrên. Những dữ liệu dạng đƣợc xem nhƣ thông tin dƣ thừa,không có giá trị sẽ đƣợc loại bỏ. Dữ liệu này nếu không đƣợc “làm sạch - tiền xử lý - chuẩn bịtrƣớc” thì sẽ gây nên những kết quả sai lệch nghiêm trọng. Các công việc tiền xử lý dữ liệu bao gồm: - Xử lý dữ liệu bị mất, thiếu: Các dữ liệu thiếu sẽ đƣợc thay thế bằng các giá trị thích hợp. - Khử bỏ trùng lặp: các đối tƣợng dữ liệu trùng lặp sẽ bị loại bỏ. - Giảm nhiễu: dữ liệu nhiễu và các đối tƣợng tách rời khỏi phân bố chung sẽ bị loại bỏ khỏi tập dữ liệu. - Chuẩn hóa: thông thƣờng là chuẩn hóa miền giá trị của dữ liệu cho phù hợp. - Rời rạc hóa: chính là việc biến đổi dữ liệu dạng số về dữ liệu với các giá trị rời rạc. - Trích rút và xây dựng các đặc trƣng mới từ các thuộc tính đã có. - Giảm chiều không gian thuộc tính: là loại bỏ bớt các thuộc tính có chứa ít thông tin. 4. Chuyển đổi dữ liệu: Tiếp theo là giai đoạn chuyển đổi dữ liệu, dữliệu đƣa ra có thể sử dụng và điều khiển đƣợc bởi việc tổ chức lạinó, tức là dữ liệu sẽ đƣợc chuyển đổi về dạng phù hợp với mục đíchkhai phá dữ liệu. 5. Khai phá dữ liệu (KPDL): Đây là bƣớc quan trọng nhất trong tiến trình phát hiện tri thức, là bƣớc mang tính tƣ duy trong khai phádữ liệu. Ở giai đoạn này nhiều thuật toán khác nhau đã đƣợc sử dụng để trích ra các mẫu từ dữ liệu. Thuật toán thƣờng dùng làm nguyên tắc phân loại, nguyên tắc liên kết, ... Kết quả quả giai đoạn này là trích chọn đƣợc các mẫu hoặc các mô hình ẩn dƣới một khối lƣợng lớn dữ liệu. 6. Đánh giá các luật và biểu diễn tri thức: Ở giai đoạn này, các mẫu dữ liệu đƣợc chiết xuất ra bởi phần mềm KPDL. Không phải bất cứ mẫu dữ liệu nào cũng đều hữu ích, đôi khi nó còn bị sai lệch. Vì vậy, cần phải ƣu tiên những tiêu chuẩn Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 6 đánh giá để chiết xuất ra các tri thức (Knowlege) cần chiết xuất ra. Đánh giá sự hữu ích của các mẫu biểu diễn tri thức dựa trên một số phép đo. Sau đó sử dụng các kỹ thuật trình diễn và trực quan hoá dữ liệu để biểu diễn tri thức khai phá đƣợc cho ngƣời sử dụng. Biểu diễn tri thức bao bao gồm việc hiển thị kết quả hoặc dịch kế t quả để hiểu và trình diễn. Trong bƣớc này các tri thức vừa mới khám phá sẽ đƣợc củng cố, kết hợp lại thành một hệ thống, đồng thời giải quyết các xung đột tiềm năng trong các tri thức trƣớc đó. Các mô hình rút ra đƣợc đƣa vào những hệ thống thông tin thực tế dƣới dạng các mô-đun hỗ trợ việc đƣa ra quyết định. Các giai đoạn (bƣớc) của quá trình phát triển tri thức có mỗi quan hệ chặt chẽ với nhau trong bối cảnh chung của hệ thống. Các kỹ thuật trong bƣớc trƣớc có thể ảnh hƣởng đến hiệu quả của các giải thuật trong nhƣỡng bƣớc tiếp theo. Các bƣớc của quá trình khám phá tri thức có thể lặp đi lặp lại một số lần, kết quả thu đƣợc có thể đƣợc lấy trung bình trên tất cả các lần thực hiện. 1.2.2. Quá trình khai phá dữ liệu KPDL là giai đoạn quan trọng nhất trong quá trình khám phátri thức. Về cơ bản, KPDL là về xử lý dữ liệu và nhận biết các mẫu và các xu hƣớng trong thông tin đó để bạn có thể quyết định hoặc đánh giá. Các nguyên tắc KPDL đã đƣợc dùng nhiều năm, nhƣng với sự ra đời của big data (dữ liệu lớn), nó lại càng phổ biến hơn. Big data gây ra một sự bùng nổ về sử dụng nhiều kỹ thuật KPDL hơn, một phần vì kích thƣớc thông tin lớn hơn rất nhiều và vì thông tin có xu hƣớng đa dạng và mở rộng hơn về chính bản chất và nội dung của nó. Với các tập hợp dữ liệu lớn, để nhận đƣợc số liệu thống kê tƣơng đối đơn giản và dễ dàng trong hệ thống vẫn chƣa đủ[6]. Với 30 hoặc 40 triệu bản ghi thông tin khách hàng chi tiết, việc biết rằng 2 triệu khách hàng trong số đó sống tại một địa điểm vẫn chƣa đủ. Bạn muốn biết liệu 2 triệu khách hàng đó có thuộc về một nhóm tuổi cụ thể không và bạn cũng muốn biết thu nhập trung bình của họ để bạn có thể tập trung vào các nhu cầu của khách hàng của mình tốt hơn. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 7 Những nhu cầu đa dạng đã thay đổi cách lấy ra và thống kê dữ liệu đơn giản sang việc KPDL phức tạp hơn. Vấn đề hƣớng tới việc xem xét dữ liệu để giúp xây dựng một mô hình để mô tả các thông tin mà cuối cùng sẽ dẫn đến việc tạo ra báo cáo kết quả. Hình 1.2: Quá trình khai phá dữ liệu - Xác định nhiệm vụ: Xác định chính xác các vấn đề cần giải quyết. - Xác định các dữ liệu liên quan: Dùng để xây dựng giải pháp. - Thu thập và tiền xử lý dữ liệu: Thu thập các dữ liệu liên quan và tiền xử lý chúng sao cho thuật toán KPDL có thể hiểu đƣợc. Đây là một quá trình rất khó khăn, có thể gặp phải rất nhiều các vƣớng mắc nhƣ: dữ liệu phải đƣợc sao ra nhiều bản (nếu đƣợc chiết xuất vào các tệp), quản lý tập các dữ liệu, phải lặp đi lặp lại nhiều lần toàn bộ quá trình (nếu mô hình dữ liệu thay đổi), ... - Thuật toán KPDL: Lựa chọn thuật toán khai phá dữ liệu và thực hiện việc khai phá dữ liệu để tìm đƣợc các mẫu có ý nghĩa, các mẫu này đƣợc biểu diễn dƣới dạng luật kết hợp, cây quyết định...tƣơng ứng mục đích đề ra. 1.3. Các kỹ thuật trong khai phá dữ liệu Có nhiều kỹ thuật khác nhau đƣợc sử dụng để KPDL nhằm thực hiện hai chức năng mô tả và dự đoán. Với mỗi chức năng thì có các kỹ thuật KPDL tƣơng ứng với nó. Không có kỹ thuật nào tốt để có thể áp dụng cho mọi trƣờng hợp [1]. Kỹ thuật KPDL mô tả có nhiệm vụ mô tả tính chất hoặc các đặc tính chung của dữ liệu trong CSDL hiện có. Một số kỹ thuật khai phá trong nhóm này là: phân cụm dữ liệu, tổng hợp, trực quan hóa, phân tích sự phát triển và độ lệch,… Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 8 Kỹ thuật KPDL dự đoán có nhiệm vụ đƣa ra các dự đoán vào việc suy diễn trên CSDL hiện thời. Một số kỹ thuật khai phá trong nhóm này là: phân lớp, hồi quy, cây quyết định, thống kê, mạng nơ-ron, luật kết hợp,… Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 9 a. Cây quyết định Kỹ thuật cây quyết định là một công cụ mạnh và hiệu quả trong việc phân lớp và dự báo. Các đối tƣợng dữ liệu đƣợc phân thành các lớp. Các giá trị của đối tƣợng dữ liệu chƣa biết sẽ đƣợc dự báo, dự đoán. Tri thức đƣợc rút ra dƣới kỹ thuật này thƣờng ở dƣới dạng tƣờng minh, đơn giản, trực quan đối với ngƣời sử dụng. b. Phân lớp dữ liệu và hồi quy Mục tiêu của phân lớp dữ liệu là dự đoán nhãn lớp cho các mẫu dữ liệu. Quá trình gồm hai bƣớc: xây dựng mô hình, dử dụng mô hình để phân lớp dữ liệu. Mô hình đƣợc sử dụng để dự đoán nhãn lớp khi mà độ chính xác của mô hình chấp nhận đƣợc. Phƣơng pháp hồi quy tƣơng tự nhƣ phân lớp dữ liệu. Nhƣng khác ở chỗ nó dùng để dự đoán trƣớc các giá trị liên tục, còn phân lớp dữ liệu dùng để dự đoán các giá trị rời rạc. c. Phân cụm dữ liệu Phân cụm dữ liệu là một kỹ thuật trong Data mining nhằm tìm kiếm, phát hiện các cụm, các mẫu dữ liệu tự nhiên tiềm ẩn và quan trọng trong tập dữ liệu lớn để từ đó cung cấp thông tin, tri thức cho việc ra quyết định. Mục tiêu của phân cụm dữ liệu là nhóm các đối tƣợng tƣơng tự nhau trong tập dữ liệu vào các cụm, sao cho những đối tƣợng thuộc cùng một lớp là tƣơng đồng nhau. d. Khai phá luật kết hợp Mục tiêu của phƣơng pháp này là phát hiện và đƣa ra mỗi liên hệ giữa các giá trị dữ liệu trong CSDL. Đầu ra của giải thuật luật kết hợp là tập luật kết hợp tìm đƣợc. Phƣơng pháp khai phá luật kết hợp gồm có hai bƣớc: - Bƣớc một: Tìm ra tất cả các tập mục phổ biến. Một tập mục phổ biến đƣợc xác định thông qua việc tính độ hỗ trợ và thỏa mãn độ hỗ trợ cực tiểu. - Bƣớc hai: Sinh ra các luật kết hợp mạnh từ tập mục phổ biến, luật phải thỏa mãn độ hỗ trợ và độ tin cậy cực tiểu. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 10 e. Giải thuật di truyền Giải thuật di truyền là quá trình mô phỏng theo tiến hóa của tự nhiên. Ý tƣởng chính của giai đoạn này là dựa vào quy luật di truyền trong biến đổi, chọn lọc tự nhiên và tiến hóa trong sinh học. f. Mạng nơ-ron Đây là một trong những kỹ thuật KPDL đƣợc sử dụng phổ biển hiện nay. Kỹ thuật này phát triển dựa trên nền tảng toán học vững vàng, khả năng huấn luyện trong kỹ thật này mô phỏng hệ thần kinh trung ƣơng của con ngƣời. Kết quả mà mạng nơ-ron học đƣợc có khả năng tạo ra các mô hình dự báo, dự đoán với độ chính xác và độ tin cậy cao. Nó có khả năng phát hiện ra các xu hƣớng phức tạp mà các kỹ thuật thông thƣờng khác khó có thể phát hiện ra đƣợc. Tuy nhiên đây là kỹ thuật tƣơng đối phức tạp và quá trình thực hiện nó gặp rất nhiều khó khăn, đòi hỏi tốn nhiều thời gian, nhiều dữ liệu, nhiều lần kiểm tra thử nghiệm. 1.4. Mô ̣t số thách thƣ́c trong khai phá dƣ̃ liêụ Khám phá tri thức và khai phá dữ liệu liên quan đến nhiều ngành, nhiều lĩnh vực, do đó cũng tồ n ta ̣i nhiề u thách thức và khó khăn: - Các cơ sở dữ liệu lớn hơn rất nhiều: cơ sở dữ liệu với hàng trăm trƣờng và bảng, hàng triệu bản ghi và kích thƣớc lên tới nhiều gigabyte là vấn đề hoàn toàn bình thƣờng. - Số chiều cao : không chỉ thƣờng có một số lƣợng rất lớn các bản ghi trong cơ sở dữ liệu mà còn có một số lƣợng rất lớn các trƣờng (các thuộc tính, các biến) làm cho số chiều của bài toán trở nên cao. Thêm vào đó, nó tăng thêm cơ hội cho một giải thuật khai phá dữ liệu tìm ra các mẫu không hợp lệ. - Thay đổi dữ liệu và tri thức: thay đổi nhanh chóng dữ liệu có thể làm cho các mẫu phát hiện trƣớc đó không hợp lệ. Thêm vào đó, các biến đã đo trong một cơ sở dữ liệu ứng dụng cho trƣớc có thể bị sửa đổi, xóa bỏ hay tăng thêm các phép đo mới. Các giải pháp hợp lý bao gồm các phƣơng pháp tăng trƣởng để cập nhật các mẫu và xử lý thay đổi. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 11 - Dữ liệu thiếu và bị nhiễu: bài toán này đặc biệt nhạy trong các cơ sở dữ liệu thƣơng mại. Các thuộc tính quan trọng có thể bị mất nếu cơ sở dữ liệu không đƣợc thiết kế với sự khám phá bằng trí tuệ. Các giải pháp có thể gồm nhiều chiến lƣợc thống kê phức tạp để nhận biết các biến ẩn và các biến phụ thuộc. - Mối quan hệ phức tạp giữa các trƣờng: các thuộc tính hay giá các giá trị có cấ u trúc phân cấp, các quan hệ giữa các thuộc tính và các phƣơng tiện tinh vi hơn cho việc biểu diễn tri thức về nội dung của một cơ sở dữ liệu sẽ đòi hỏi các giải thuật phải có khả năng sử dụng hiệu quả các thông tin này. Về mặt lịch sử, các giải thuật khai phá dữ liệu đƣợc phát triển cho các bản ghi có giá trị thuộc tính đơn giản, mặc dù các kỹ thuật mới bắt nguồn từ mối quan hệ giữa các biến đang đƣợc phát triển. - Tính dễ hiểu của các mẫu: trong nhiều ứng dụng, điều quan trọng là những gì khai thác đƣợc phải càng dễ hiểu đối với con ngƣời thì càng tốt. Các giải pháp có thể thực hiện đƣợc bao gồm cả việc biểu diễn đƣợc minh họa bằng đồ thị, cấu trúc luật với các đồ thị có hƣớng, biểu diễn bằng ngôn ngữ tự nhiên và các kỹ thuật hình dung ra dữ liệu và tri thức. - Ngƣời dùng tƣơng tác và tri thức sẵn có: nhiều phƣơng pháp khám phá tri thức và các công cụ không tƣơng tác thực sự với ngƣời dùng và không thể dễ dàng kết hợp chặt chẽ với tri thức có sẵn về một bài toán loại trừ theo các cách đơn giản. Việc sử dụng của miền tri thức là quan trọng trong toàn bộ các bƣớc của xử lý khám phá tri thức. Kế t luận Khai phá dữ liệu là lĩnh vực đã và đang trở thành một trong những hƣớng nghiên cứu thu hút đƣợc sự quan tâm của nhiều chuyên gia về công nghệ thông tin. Gần đây, rất nhiều phƣơng pháp và thuật toán mới liên tục đƣợc công bố. Điều này chứng tỏ những lợi ích và khả năng ứng dụng thực tế của khai phá dữ liệu. Chƣơng này đã trình bày một số kiến thức tổng quan về khám phá tri thức, những khái niệm và kiến thức cơ bản nhất về khai phá dữ liệu. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 12 CHƢƠNG II. PHÂN CỤM DƢ̃ LIỆU VÀ CÁC THUẬT TOÁN PHÂN CỤM Phân cụm là một trong những chủ đề đƣợc quan tâm nhiều trong các nghiên cứu KPDL. Phân cụm là quá trình nhóm một tập các đối tƣợng thành các nhóm hay các lớp đối tƣợng “tƣơng tự” nhau. Một cụm là tập các đối tƣợng “giống nhau” hay tƣơng tự nhau. Các đối tƣợng khác cụm là ít hoặc không tƣơng tự nhau. Không giống nhƣ quá trình phân loại, ta thƣờng biết trƣớc tính chất hay đặc điểm của đối tƣợng trong cùng một cụm và dựa vào đó để ấn định một đối tƣợng vào cụm của nó, trong quá trình phân cụm ta không hề biết trƣớc các tính chất của cụm mà dựa vào các mỗi quan hệ của các đối tƣợng để tìm ra sự giống nhau giữa các đối tƣợng dựa vào một độ đo nào đó đặc trƣng cho mỗi cụm. Việc phân cụm dữ liệu không thực hiện độc lập mà thƣờng kết hợp với các phƣơng pháp khác. Một cách phân cụm đƣa ra cũng phải có một phƣơng pháp áp dụng trên các lớp đó để đƣa ra đƣợc ý nghĩa của cụm. Trong lĩnh vực KPDL, các vấn đề nghiên cứu trong phân cụm chủ yếu tập trung vào tìm kiếm các phƣơng pháp phân cụm hiệu quả và tin cậy trong CSDL lớn. Một vấn đề thƣờng gặp trong phân cụm dữ liệu (PCDL) là hầu hết các dữ liệu cần cho PCDL đều có chứa dữ liệu “nhiễu” do nhiều nguyên nhân khác nhau, vì vậy cần xây dựng chiến lƣợc cho bƣớc tiền xử lý nhằm loại bỏ những dữ liệu “nhiễu” trƣớc khi bƣớc vào giai đoạn phân tích PCDL. Ngoài ra, dò tìm phần tử ngoại lai là một trong những hƣớng nghiên cứu quan trọng trong PCDL, chức năng của nó là xác định một nhóm nhỏ các đối tƣợng dữ liệu “khác thƣờng” so với các dữ liệu khác trong CSDL nhằm tránh sự ảnh hƣớng của chúng tới quá trình cũng nhƣ kết quả PCDL. PCDL là một bài toán không hề đơn giản và phải giải quyết nhiều vấn đề cơ bản nhƣ sau: - Biểu diễn dữ liệu. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn