Luận văn Thạc sĩ Khoa học máy tính: Phân lớp dữ liệu hoa Iris sử dụng thuật toán Naive Bayes, RandomForest và KNN (K - Nearest neighbors)

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:73

Thêm vào BST

Báo xấu

61
lượt xem 9
download

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

Mục tiêu nghiên cứu chính của luận văn là khai phá dữ liệu và phát hiện tri thức trong chương này nghiên cứu tổng quan về khái phá dữ liệu và phát hiện tri thức. Bên cạnh đó, một số kĩ thuật khái phá dữ liệu cơ bản cũng được trình bày trong chương này. Đồng thời ứng dụng phân lớp dữ liệu hoa Iris, chương này phát triển và Demo ứng dụng công cụ Weka xây dựng mô hình, kiểm tra và đánh giá mô hình dự doán hoa Iris. Mời các bạn tham khảo!

Chủ đề:

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

Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học máy tính: Phân lớp dữ liệu hoa Iris sử dụng thuật toán Naive Bayes, RandomForest và KNN (K - Nearest neighbors)

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG SENGTHONG XAYAVONG PHÂN LỚP DỮ LIỆU HOA IRIS SỬ DỤNG THUẬT TOÁN NAIVE BAYES, RANDOMFOREST VÀ KNN (K - NEAREST NEIGHBORS) LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH Thái Nguyên – 2020
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG SENGTHONG XAYAVONG PHÂN LỚP DỮ LIỆU HOA IRIS SỬ DỤNG THUẬT TOÁN NAIVE BAYES, RANDOMFOREST VÀ KNN (K - NEAREST NEIGHBORS) LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH Chuyên ngành: KHOA HỌC MÁY TÍNH Mã số: 84 8 01 01 Người hướng dẫn khoa học: TS. Nguyễn Văn Núi Thái Nguyên – 2020
I LỜI CAM ĐOAN Họ và tên học viên: Sengthong Xayavong Lớp cao học: CK17A Trường Đại học Công nghệ thông tin và Truyền thông – Đại học Thái Nguyên. Chuyên ngành: Khoa học máy tính Tên đề tài luận văn: PHÂN LỚP DỮ LIỆU HOA IRIS SỬ DỤNG THUẬT TOÁN NAIVE BAYES, RANDOMFOREST VÀ KNN (K - NEAREST NEIGHBORS). Học viên xin cam đoan đây là công trình nghiên cứu của bản than học viện. Các kết quả nghiên cứu và các kết luận trong luận văn là trung thực, không sao chép từ bất kỳ một nguồn nào và dưới bất kỳ hình thức nào. Trong quá trình làm học viên có tham khảo các tài liệu liên quan nhằm khẳng định thêm sự tin cậy và cấp thiết của đề tài. Việc tham khảo các nguồn tài liệu đã được thực hiện trích dẫn và ghi nguồn tài liệu tham khảo đúng quy định. Thái Nguyên, ngày 08 tháng 10 năm 2020 Tác giả luận văn Sengthong xayavong
II LỜI CẢM ƠN Tôi xin gửi lời cảm ơn sâu sắc tới TS. Nguyễn Văn Núi, Trường Đại học Công nghệ Thông tin và Truyền thông, người thầy đã dành nhiều thời gian tận tình chỉ bảo, hướng dẫn, giúp đỡ tôi trong suốt quá trình tìm hiểu, nghiên cứu. Thầy là người định hướng và đưa ra nhiều góp ý quý báu trong quá trình tôi thực hiện luận văn. Tôi xin chân thành cảm ơn các thầy, cô ở khoa Công nghệ thông tin – trường Đại học Công nghệ Thông tin và Truyền thông đã cung cấp cho tôi những kiến thức và tạo cho tôi những điều kiện thuận lợi trong suốt quá trình tôi học tập tại trường. Tôi cũng bày tỏ lòng biết ơn về sự giúp đỡ của lãnh đạo cơ quan, đồng nghiệp đã cung cấp dữ liệu, tài liệu và cho tôi những lời khuyên quý báu. Tôi xin cảm ơn gia đình, người thân, bạn bè và các thành viên trong nhóm nghiên cứu luôn động viên và tạo mọi điều kiện tốt nhất cho tôi. Tôi xin chân thành cảm ơn! Thái Nguyên, ngày 08 tháng 10 năm 2020 Tác giả luận văn Sengthong Xayavong
III MỤC LỤC LỜI CAM ĐOAN ...................................................................................................... I LỜI CẢM ƠN .......................................................................................................... II DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT .......................................... VI DANH MỤC CÁC BẢNG ....................................................................................VII DANH MỤC HÌNH ............................................................................................. VIII MỞ ĐẦU ....................................................................................................................1 Chương 1: Tổng quan về khai phá dữ liệu và phát hiện tri thức .........................3 1.1 Giới thiệu tổng quan ........................................................................................3 1.1.1 Giới thiệu chung về khám phá tri thức và khai phá dữ liệu ........................3 1.1.2 Quá trình khám phá tri thức ........................................................................3 1.1.3 Khai phá dữ liệu ..........................................................................................5 1.1.4 Quá trình của khai phá dữ liệu ....................................................................6 1.1.5 Ứng dụng của khai phá dữ liệu ...................................................................7 1.2 Một số kỹ thuật khai phá dữ liệu cơ bản .......................................................7 1.2.1 Luật kết hợp (Association Rules).................................................................7 1.2.2 Khai thác mẫu tuần tự (Sequential / Temporal patterns) ............................7 1.2.3 Phân cụm dữ liệu (Clustering) ....................................................................8 1.2.4 Phân nhóm- đoạn (Clustering / Segmentation) ...........................................8 1.2.5 Hồi quy (Regression) ..................................................................................9 1.2.6 Tổng hợp hóa (Summarization) ...................................................................9 1.2.7 Mô hình hóa sự phụ thuộc (dependency modeling) ....................................9 1.2.8 Phát hiện sự biến đổi và độ lệch (Change and deviation detection) .........10 1.3. Một số so sánh giữa khai phá dữ liệu và các phương pháp cơ bản khác 10 1.3.1. So sánh với phương pháp hệ chuyên gia ..................................................10 1.3.2. So sánh với phương pháp phân loại thống kê ..........................................11 1.3.3. So sánh với phương pháp học máy ..........................................................12 1.3.4 So sánh với phương pháp học sâu .............................................................14 Chương 2: Một số kỹ thuật phân lớp dữ liệu .......................................................16 2.1 Tổng quan về phân lớp dữ liệu ....................................................................16 2.2. Phân lớp dữ liệu Naive Bayes .....................................................................19
IV 2.2.1 Định nghĩa thuật toán Naïve Bayes..........................................................19 2.2.3 Đặc điểm của thuật toán Naïve Bayes .......................................................22 2.2.4 Ứng dụng của thuật toán Naïve Bayes ......................................................23 2.3 Phân lớp dữ liệu RandomForest .................................................................24 2.3.1 Định nghĩa thuật toán Ramdomforest .......................................................24 2.3.2 Đặc điểm của Random Forest ...................................................................27 2.3.3 Mô hình phân lớp với Random Forest ......................................................29 2.3.4 Ứng dụng thuật toán Ramdom Forest .......................................................29 2.4. Phân lớp dữ liệu KNN (K-nearest neighbor) ............................................29 2.4.1 Định nghĩa thuât toán KNN ......................................................................29 2.4.2 Mô tả thuật toán K-NN..............................................................................31 2.4.3 Đặc điểm của thuật toán KNN .................................................................33 2.4.4 Ứng dụng thuật toán K-NN ......................................................................33 2.5. Một số thuật toán phân lớp dữ liệu khác...................................................34 2.5.1 Cây quyết định ứng dụng trong phân lớp dữ liệu......................................34 2.5.2 Phân lớp với máy vector hỗ trợ (SVM) .....................................................34 Chương 3: Ứng dụng phân lớp dữ liệu hoa Iris ...................................................35 3.1. Giới thiệu về hoa Iris và bài toán phân lớp hoa Iris..................................35 3.1.1. Giới thiệu về tập dữ liệu hoa Iris ..............................................................35 3.1.2 Sử dụng tập dữ liệu....................................................................................36 3.1.3 Tập dữ liệu.................................................................................................36 3.1.4 Định nghĩa bài toán phân lớp hoa Iris ......................................................41 3.2. Thu thập và tiền xử lý dữ liệu......................................................................41 3.2.1. Làm sạch dữ liệu ......................................................................................42 3.2.2. Chọn lọc dữ liệu .......................................................................................42 3.2.3. Chuyển đổi dữ liệu ...................................................................................43 3.2.4. Rút gọn dữ liệu .........................................................................................43 3.3. Giới thiệu về công cụ Weka, cấu hình và ứng dụng phân lớp hoa Iris...43 3.3.1 Khái niệm ..................................................................................................43 3.3.2 Ưu điểm của Weka ....................................................................................44 3.3.3 Những tính năng vượt trội của Weka ........................................................45
V 3.3.4 Kiến trúc thư viện Weka ...........................................................................45 3.3.5 Các môi trường chức năng chính của Weka .............................................46 3.3.6 Định dạng dữ liệu của weka ......................................................................48 3.4. Áp dụng các thuật toán Naive Bayes, RandomForest và KNN trong phân lớp dự đoán hoa Iris ............................................................................................49 3.4.1 Áp dụng thuật toán Naive Bayes trong phân lớp dự đoán hoa Iris ...........50 3.4.2 Áp dụng thuật toán RandomForest trong phân lớp dự đoán hoa Iris ........53 3.4.3 Áp dụng thuật toán KNN trong phân lớp dự đoán hoa Iris .......................56 3.5 Đánh giá mô hình phân lớp dữ liệu Hoa IRIS ............................................59 3.5.1 Đánh giá hiệu năng mô hình sử dụng phương pháp đánh giá chéo (k-fold cross-validation) .................................................................................................59 3.5.2 Đánh giá mô hình sử dụng phương pháp Hold-out ...................................59 3.5.3 Kết luận thực nghiệm phân lớp dữ liệu IRIS ............................................60 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN .............................................................61 TÀI LIỆU THAM KHẢO ......................................................................................62
VI DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT TT Chữ viết tắt Ý nghĩa 1. KPDL Khai phá dữ liệu 2. CSDL Cơ sở dữ liệu 3. KNN K-nearest neighbor 4. KDD Knowledge Discovery in Database 5. RF Ramdom Forest 6. SVM Support Vector Machines 7. NBC Naive Bayes Classification
VII DANH MỤC CÁC BẢNG Bảng 1:Thông tin loài Setosa .......................................................................... 36 Bảng 2:Thông tin loài Iris-Versicolor ............................................................. 38 Bảng 3: thông tin Loài Iris-Virginica.............................................................. 39 Bảng 4: tổng kết thống kê Giá trị của hoa Iris ................................................ 42 Bảng 5: ý nghĩa các môi trường chính trên Weka 3.8.4 ................................. 46 Bảng 6: ý nghĩa các môi trường Explorer trên Weka 3.8.4 ............................ 48 Bảng 7: Tổng hợp đánh giá các thật toán chia tập dữ liệu thành 10 phần (chọn fold=10) ........................................................................................................... 59 Bảng 8: Tổng hợp kết quả đánh giá hiệu năng phân lớp, dự đoán của mô hình bằng phương pháp kiểm thử độc lập ............................................................... 60
VIII DANH MỤC HÌNH Hình 1. 1:Quá trình khám phá tri thức ........................................................................5 Hình 1. 2:Quá trình khai phá dữ liệu...........................................................................6 Hình 1. 3: Lược đồ hệ chuyên gia .............................................................................11 Hình 2. 1: Bài toán phân lớp .....................................................................................16 Hình 2. 2: Quá trình phân lớp dữ liệu - (a) Bước xây dựng mô hình phân lớp ........18 Hình 2. 3: Quá trình phân lớp dữ liệu - (b1) Ước lượng độ chính xác của mô hình 19 Hình 2. 4:Quá trình phân lớp dữ liệu - (b2) Phân lớp dữ liệu mới ...........................19 Hình 2. 5:Mô hình rừng ngẫu nhiên ..........................................................................25 Hình 2. 6:Các bước phân lớp với Random Forest ....................................................27 Hình 2. 7:Mô hình phân lớp với Random Forest ......................................................29 Hình 2. 8: Bản dổ của KNN nhiễu k =1 ....................................................................31 Hình 2. 9: Minh họa của KNN ..................................................................................32 Hình 3. 1: Minh họa về iris flower dataset ................................................................35 Hình 3. 2: Loài chim Mecca được chọn là biểu tượng của ứng dụng Weka ............43 Hình 3. 3: môi trường chính của Weka .....................................................................46 Hình 3. 4 : Sơ đồ tổng thể Mô hình phân lớp dự đoán hoa Iris trong luận văn ........50 Hình 3. 5:Cấu hình tham số cho thuật toán Naive Bayes .........................................51 Hình 3. 6: Kết quả phân lớp dữ liệu cho thuật toán Naive Bayes Tập luyện tập 66% (Tập kiểm chứng 34%) ..............................................................................................52 Hình 3. 7:Kết quả phân lớp dữ liệu cho thuật toán Naive Bayes chia tập dữ liệu thành 10 phần (chọn fold=10) ...................................................................................53 Hình 3. 8:Cấu hình tham số cho thuật toán Ramdomforest ......................................54 Hình 3. 9: Kết quả phân lớp dữ liệu cho thuật toán Ramdomforest Tập luyện tập 66% (Tập kiểm chứng 34%) .....................................................................................55 Hình 3. 10:Kết quả phân lớp dữ liệu cho thuật toán Ramdomforest chia tập dữ liệu thành 10 phần (chọn fold=10) ...................................................................................56 Hình 3. 11:Cấu hình tham số cho thuật toán k-Nearest Neighbors ..........................57
IX Hình 3. 12: Kết quả phân lớp dữ liệu cho thuật toán K-NN Tập luyện tập 66% (Tập kiểm chứng 34%) ......................................................................................................58 Hình 3. 13:Kết quả phân lớp dữ liệu cho thuật toán k-Nearest Neighbors chia tập dữ liệu thành 10 phần (chọn fold=10) ............................................................................58
1 MỞ ĐẦU Sự phát triển của công nghệ thông tin và việc ứng dụng công nghệ thông tin ở hầu hết các lĩnh vực trong nhiều năm qua cũng đồng nghĩa với lượng dữ liệu đã được thu thập và lưu trữ ngày càng lớn. Các hệ quản trị cơ sở dữ liệu truyền thống cũng chỉ khai thác được một lượng thông tin nhỏ không còn đáp ứng đầy đủ những yêu cầu, những thách thức mới. Do vậy một khuynh hướng mới được ra đời đó là kỹ thuật phát hiện tri thức trong cơ sở dữ liệu. Xin giới thiệu một cách tổng quan về phát hiện tri thức và khai phá dữ liệu cùng một số kỹ thuật cơ bản để trong khai phá dữ liệu để phát hiện tri thức và một số ứng dụng trong thực tế nhằm hỗ trợ cho tiến trình ra quyết định. Kỹ thuật phát hiện tri thức và khai phá dữ liệu đã và đang được nghiên cứu, ứng dụng trong nhiều lĩnh vực khác nhau ở các nước trên thế giới, kỹ thuật này tương đối còn mới mẻ tuy nhiên cũng đang được nghiên cứu và dần đưa vào ứng dụng. Bước quan trọng nhất của quá trình này là Khai phá dữ liệu (Data Mining), giúp người sử dụng thu được những tri thức hữu ích từ những CSDL hoặc các nguồn dữ liệu khổng lồ khác. Rất nhiều doanh nghiệp và tổ chức trên thế giới đã ứng dụng kĩ thuật khai phá dữ liệu vào hoạt động sản xuất kinh doanh của mình và đã thu được những lợi ích to lớn. Nhưng để làm được điều đó, sự phát triển của các mô hình toán học và các giải thuật hiệu quả là chìa khoá quan trọng. Vì vậy, trong luận văn này, tác giả sẽ đề cập tới hai kỹ thuật thường dùng trong Khai phá dữ liệu, đó là Phân lớp (Classification). Trong quá trình hoạt động, con người tạo ra nhiều dữ liệu nghiệp vụ. Các tập dữ liệu được tích lũy có kích thước ngày càng lớn, và có thể chứa nhiều thông tin ẩn dạng những quy luật chưa được khám phá. Chính vì vậy, một nhu cầu đặt ra là cần tìm cách trích rút từ tập dữ liệu đó các luật về phân lớp dữ liệu hay dự đoán những xu hướng dữ liệu tương lai. Những quy tắc nghiệp vụ thông minh được tạo ra sẽ phục vụ đắc lực cho các hoạt động thực tiễn, cũng như phục vụ đắc lực cho quá trình nghiên cứu khoa học. Công nghệ phân lớp và dự đoán dữ liệu ra đời để đáp ứng mong muốn đó.
2 Công nghệ phân lớp dữ liệu đã, đang và sẽ phát triển mạnh mẽ trước những khao khát tri thức của con người. Trong những năm qua, phân lớp dữ liệu đã thu hút sự quan tâm các nhà nghiên cứu trong nhiều lĩnh vực khác nhau như học máy (machine learning), hệ chuyên gia (expert system), thống kê (statistics)... Công nghệ này cũng ứng dụng trong nhiều lĩnh vực thực tế như: thương mại, nhà băng, maketing, nghiên cứu thị trường, bảo hiểm, y tế, giáo dục... Nhiều kỹ thuật phân lớp đã được đề xuất như: Phân lớp : phân lớp dữ liệu hoa iris, phân lớp Bayesian (Bayesian classifier), phân lớp Khàng xóm gần nhất (K-nearest neighbor classifier), mạng nơron, phân tích thống kê,…Trong các kỹ thuật đó, cây quyết định được coi là công cụ mạnh, phổ biến và đặc biệt thích hợp cho data mining. Trong các mô hình phân lớp, thuật toán phân lớp là nhân tố chủ đạo. Do vậy cần xây dựng những thuật toán có độ chính xác cao, thực thi nhanh, đi kèm với khả năng mở rộng được để có thể thao tác với những tập dữ liệu ngày càng lớn. Bố cục của luận văn có nội dụng chính 3 chương : Chương 1: Tổng quan về khai phá dữ liệu và phát hiện tri thức trong chương này nghiên cứu tổng quan về khái phá dữ liệu và phát hiện tri thức. Bên cạnh đó, một số kĩ thuật khái phá dữ liệu cơ bản cũng được trình bày trong chương này. Chương 2: Một số kỹ thuật phân lớp dữ liệu trong chương này trình bày tổng quan về phân lớp dữ liệu và 3 phương pháp : Naïve Bayes, Ramdom Forrest và KNN. Chương 3: Ứng dụng phân lớp dữ liệu hoa Iris, chương này Phát triển và Demo ứng dụng cung cụ Weka xây dựng mô hình, kiểm tra và đánh giá mô hình dự doán hoa Iris.
3 Chương 1: Tổng quan về khai phá dữ liệu và phát hiện tri thức 1.1 Giới thiệu tổng quan 1.1.1 Giới thiệu chung về khám phá tri thức và khai phá dữ liệu Nếu cho rằng, điện tử và truyền thông chính là bản chất của khoa học điện tử, thì dữ liệu, thông tin, và tri thức hiện đang là tiêu điểm của một lĩnh vực mới để nghiên cứu và ứng dụng, đó là khám phá tri thức và khai phá dữ liệu. Thông thường, chúng ta coi dữ liệu như là một chuỗi các bits, hoặc các số và các ký hiệu hay là các “đối tượng” với một ý nghĩa nào đó khi được gửi cho một chương trình dưới một dạng nhất định. Các bits thường được sử dụng để đo thông tin, và xem nó như là dữ liệu đã được loại bỏ phần tử thừa, lặp lại, và rút gọn tới mức tối thiểu để đặc trưng một cách cơ bản cho dữ liệu. Tri thức được xem như là các thông tin tích hợp, bao gồm các sự kiện và mối quan hệ giữa chúng, đã được nhận thức, khám phá, hoặc nghiên cứu. Nói cách khá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 hay phát hiện tri thức trong CSDL là một quy trình nhận biết các mẫu hoặc các mô hình trong dữ liệu với các tính năng: Phân tích, tổng hợp, hợp thức, khả ích và có thể hiểu được. Khai phá dữ liệu là một bước trong quá trình khám phá tri thức, gồm các giải thuật 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 CSDL nhưng ẩn trong khối lượng lớn dữ liệu. 1.1.2 Quá trình khám phá tri thức Quy trình khám phá tri thức tiến hành qua 6 giai đoạn, xem hình 1.1: 1. Gom dữ liệu: Tập hợp dữ liệu là bước đầu tiên trong quá trình khai 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 và thậm chí các dữ liệu từ các nguồn ứng dụng Web.
4 2. Trích lọc dữ liệu: Ở giai đọan này dữ liệu được lựa chọn hoặc phân chia theo một số tiêu chuẩn nào đó phục vụ mục đích khai thác, ví dụ chọn tất cả những em học sinh có điểm Trung bình học kỳ lớn hơn 8.0 và có giới tính nữ. 3. Làm sạch, tiền xử lý và chuẩn bị trước dữ liệu: Giai đoạn thứ ba này là giai đoạn hay bị sao lãng, nhưng thực tế nó là một bước rất quan trọng trong quá trình khai phá dữ liệu. Một số lỗi thường mắc phải trong khi gom dữ liệu là tính không đủ chặt chẽ, logíc. 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. Ví dụ : Điểm Trung bình = 12.4. Giai đoạn này sẽ tiến hành xử lý những dạng dữ liệu không chặt chẻ nói trên. Những dữ liệu dạng này được xem như thông tin dư thừa, không có giá trị. Bởi vậy, đây là một quá trình rất quan trọng vì 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. 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ại nó, tức là dữ liệu sẽ được chuyển đổi về dạng phù hợp cho việc khai phá bằng cách thực hiện các thao tác nhóm hoặc tập hợp. 5. Khai phá dữ liệu: Đây 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à nguyên tắc phân loại, nguyên tắc kết, v.v... 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 khai phá dữ liệu. 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 đá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.
5 Hình 1. 1:Quá trình khám phá tri thức 1.1.3 Khai phá dữ liệu KPDL là một khái niệm ra đời vào những năm cuối của thập kỷ 80. Nó bao hàm một loạt các kỹ thuật nhằm phát hiện ra các thông tin có giá trị tiềm ẩn trong các tập dữ liệu lớn (các kho dữ liệu). Về bản chất, KPDL liên quan đến việc phân tích các dữ liệu và sử dụng các kỹ thuật để tìm ra các mẫu hình có tính chính quy (regularities) trong tập dữ liệu. Năm 1989, Fayyad, Piatestsky-Shapiro và Smyth đã dùng khái niệm Phát hiện tri thức trong cơ sở dữ liệu (Knowledge Discovery in Database – KDD) để chỉ toàn bộ quá trình phát hiện các tri thức có ích từ các tập dữ liệu lớn. Trong đó, KPDL là một bước đặc biệt trong toàn bộ tiến trình, sử dụng các giải thuật đặc biệt để chiết xuất ra các mẫu (pattern) (hay các mô hình) từ dữ liệu. Khai phá dữ liệu là một tiến trình sử dụng các công cụ phân tích dữ liệu khác nhau để khám phá ra các mẫu dưới nhiều góc độ khác nhau nhằm phát hiện ra các mối quan hệ giữa các dữ kiện, đối tượng bên trong CSDL, kết quả của việc khai phá là xác định các mẫu hay các mô hình đang tồn tại bên trong, nhưng chúng nằm ẩn khuất ở các CSDL. Để từ đó rút trích ra được các mẫu, các mô hình hay các thông tin và tri thức từ các CSDL.
6 1.1.4 Quá trình của khai phá dữ liệu Khai phá dữ liệu là một giai đoạn quan trọng trong quá trình khám phá tri thức. Về bản chất là giai đoạn duy nhất tìm ra được thông tin mới, thông tin tiềm ẩn có trong cơ sở dữ liệu chủ yếu phục vụ cho mô tả và dự đoán. Mô tả dữ liệu là tổng kết hoặc diễn tả những đặc điểm chung của những thuộc tính dữ liệu trong kho dữ liệu mà con người có thể hiểu được. Dự đoán là dựa trên những dữ liệu hiện thời để dự đoán những quy luật được phát hiện từ các mối liên hệ giữa các thuộc tính của dữ liệu trên cơ sở đó chiết xuất ra các mẫu, dự đoán được những giá trị chưa biết hoặc những giá trị tương lai của các biến quan tâm. Thống kê tóm tắt 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 thành dạng sao cho thuật toán khai phá dữ liệu 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), v.v.. - Thuật toán khai phá dữ liệu: 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 với ý nghĩa của nó.
7 1.1.5 Ứng dụng của khai phá dữ liệu KPDL có nhiều ứng dụng trong thực tế, một số ứng dụng điển hình như:  Bảo hiểm, tài chính và thị trường chứng khoán: phân tích tình hình tài chính và dự báo giá của các loại cổ phiếu trong thị trường chứng khoán. Danh mục vốn và giá, lãi suất, dữ liệu thẻ tín dụng, phát hiện gian lận.  Điều trị y học và chăm sóc y tế: một số thông tin về chẩn đoán bệnh lưu trong các hệ thống quản lý bệnh viện. Phân tích mối liên hệ giữa triệu chứng bệnh, chẩn đoán và phương pháp điều trị (chế độ dinh dưỡng, thuốc,…).  Sản xuất và chế biến: qui trình, phương pháp chế biến và xử lý xử cố Text mining & Web mining: phân lớp văn bản và các trang web, tóm tắt văn bản.  Lĩnh vực khoa học: quan sát thiên văn, dữ liệu gene, dữ liệu sinh vật học, tìm kiếm, so sánh các hệ gene và thông tin di truyền, mối liên hệ gene và các bệnh di truyền.  Lĩnh vực khác: viễn thông, môi trường, thể thao, âm nhạc, giáo dục… 1.2 Một số kỹ thuật khai phá dữ liệu cơ bản 1.2.1 Luật kết hợp (Association Rules) Luật kết hợp là dạng luật biểu diễn tri thức ở dạng tương đối đơn giản. Mục tiêu của phương pháp này là phát hiện và đưa ra các mối liên hệ giữa các giá trị dữ liệu trong CSDL. Mẫu đầu ra của giải thuật KPDL là tập luật kết hợp tìm được. Tuy luật kết hợp là một dạng luật khá đơn giản nhưng lại mang rất nhiều ý nghĩa. Thông tin mà dạng luật này đem lại rất có lợi trong các hệ hỗ trợ ra quyết định.Tìm kiếm được những luật kết hợp đặc trưng và mang nhiều thông tin từ CSDL tác nghiệp là một trong những hướng tiếp cận chính của lĩnh vực khai phá dữ liệu. 1.2.2 Khai thác mẫu tuần tự (Sequential / Temporal patterns) Tương tự như khai thác luật kết hợp nhưng có thêm tính thứ tự và tính thời gian. Một luật mô tả mẫu tuần tự có dạng tiêu biểu X Y phản ánh sự xuất hiện của biến cố X sẽ dẫn đến việc xuất hiện kế tiếp biến cố Y. Hướng tiếp cận này có tính dự báo cao.
8 1.2.3 Phân cụm dữ liệu (Clustering) 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. Phân cụm dữ liệu là sự phân chia một cơ sở dữ liệu lớn thành các nhóm dữ liệu với trong đó các đối tượng tương tự như nhau. Trong mỗi nhóm, một số chi tiết có thể không quan tâm đến để đổi lấy dữ liệu đơn giản hóa. Hay ta có thể hiểu “Phân cụm dữ liệu là quá trình tổ chức các đối tượng thành từng nhóm mà các đối tượng ở mỗi nhóm đều tương tự nhau theo một tính chất nào đó, những đối tượng không tương tự tính chất sẽ ở nhóm khác”. Phân cụm dữ liệu là quá trình nhóm một tập các đối tượng tương tự nhau trong tập dữ liệu vào các cụm sao cho các đối tượng thuộc cùng một cụm là tương đồng còn các đối tượng thuộc các cụm khác nhau sẽ không tương đồng. Phân cụm dữ liệu là một ví dụ của phương pháp học không có thầy. Không giống như phân lớp dữ liệu, phân cụm dữ liệu không đòi hỏi phải định nghĩa trước các mẫu dữ liệu huấn luyện. Vì thế, có thể coi phân cụm dữ liệu là một cách học bằng quan sát, trong khi phân lớp dữ liệu là học bằng ví dụ . . . Ngoài ra phân cụm dữ liệu còn có thể được sử dụng như một bước tiền xử lí cho các thuật toán khai phá dữ liệu khác như là phân loại và mô tả đặc điểm, có tác dụng trong việc phát hiện ra các cụm. 1.2.4 Phân nhóm- đoạn (Clustering / Segmentation) Mục tiêu chính của việc phân nhó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 nhóm sao cho mức độ tương tự giữa các đối tượng trong cùng một nhóm là lớn nhất và mức độ tương tự giữa các đối tượng nằm trong các nhóm khác nhau là nhỏ nhất. Các nhóm có thể tách nhau hoặc phân cấp gối lên nhau và số lượng các nhóm là chưa biết trước. Một đối tượng có thể vừa thuộc nhóm này, nhưng cũng có thể vừa thuộc nhóm khác. Không giống như phân lớp dữ liệu, phân nhóm dữ liệu không đòi hỏi phải định nghĩa trước các mẫu dữ liệu huấn luyện. Vì thế, có thể coi phân nhóm dữ liệu là một cách học bằng quan sát (learning by observation), trong khi phân lớp dữ liệu là học bằng ví dụ (learning by example).
9 Trong phương pháp này bạn sẽ không thể biết kết quả các nhóm thu được sẽ như thế nào khi bắt đầu quá trình. Vì vậy, thông thường cần có một chuyên gia về lĩnh vực đó để đánh giá các nhóm thu được. Phân nhóm còn được gọi là học không có giám sát (unsupervised learning). Phân nhóm dữ liệu được sử dụng nhiều trong các ứng dụng về phân đoạn thị trường, phân đoạn khách hàng, nhận dạng mẫu, phân loại trang Web, … Ngoài ra phân nhóm dữ liệu còn có thể được sử dụng như một bước tiền xử lý cho các thuật toán KPDL khác. 1.2.5 Hồi quy (Regression) Hồi quy là việc học một hàm ánh xạ từ một mẫu dữ liệu thành một biến dự đoán có giá trị thực. Nhiệm vụ của hồi quy tương tự như phân lớp, điểm khác nhau chính là ở chỗ thuộc tính để dự báo là liên tục chứ không rời rạc. Việc dự báo các giá trị số thường được làm bởi các phương pháp thống kê cổ điển chẳng hạn như hồi quy tuyến tính. Tuy nhiên phương pháp mô hình hóa cũng có thể được sử dụng như cây quyết định. 1.2.6 Tổng hợp hóa (Summarization) Là công việc liên quan đến các phương pháp tìm kiếm một mô tả tập con dữ liệu. Kỹ thuật mô tả khái niệm và tổng hợp hóa thường áp dụng trong việc phân tích dữ liệu có tính thăm dò và báo cáo tự động. Nhiệm vụ chính là sản sinh ra các mô tả đặc trưng cho một lớp. Mô tả loại này là một kiểu tổng hợp, tóm tắt các đặc tính chung của tất cả hay hầu hết các mục của một lớp. Các mô tả đặc trưng thể hiện theo luật có dạng sau: “Nếu một mục thuộc về lớp đã chỉ trong tiền đề thì mục đó có tất cả các thuộc tính đã nêu trong kết luận”. 1.2.7 Mô hình hóa sự phụ thuộc (dependency modeling) Là việc tìm kiếm một mô hình mô tả sự phụ thuộc giữa các biến, thuộc tính theo hai mức. Mức cấu trúc của mô hình mô tả (thường dưới dạng đồ thị), trong đó, các biến phụ thuộc bộ phận vào các biến khác. Và mức định lượng mô hình mô tả mức độ phụ thuộc. Những phụ thuộc này thường được biểu thị dưới dạng theo luật “nếu - thì” - nếu tiền đề đúng thì kết luận đúng. Về nguyên tắc, cả tiền đề và kết luậnđều có thể là sự kết hợp logic của các giá trị thuộc tính. Trên thực tế, tiền đề