Luận văn Thạc sĩ Khoa học máy tính: Phát hiện mối quan hệ trong cơ sở dữ liệu và ứng dụng trong y học

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

Thêm vào BST

Báo xấu

22
lượt xem 3
download

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

Nội dụng của luận văn này là tìm hiểu các phương pháp khai thác dữ liệu dựa trên ngôn ngữ truy vấn SQL và chọn tiếp cận K-way join làm trọng tâm. Dựa trên cách tiếp cận này chúng ta sẽ phân tích và đánh giá các cải tiến cho K-way join, đề xuất phương pháp phát sinh và rút gọn luật kết hợp dựa trên tập luật mẫu. Mời các bạn cùng 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át hiện mối quan hệ trong cơ sở dữ liệu và ứng dụng trong y học

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG VY ĐẠI NGHĨA PHÁT HIỆN MỐI QUAN HỆ TRONG CƠ SỞ DỮ LIỆU VÀ ỨNG DỤNG TRONG Y HỌC 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
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG VY ĐẠI NGHĨA PHÁT HIỆN MỐI QUAN HỆ TRONG CƠ SỞ DỮ LIỆU VÀ ỨNG DỤNG TRONG Y HỌC Chuyên ngành: Khoa học máy tính Mã số: 60 48 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. Đỗ Trung Tuấn Thái Nguyên - 2015 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
i Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
ii Lời cảm ơn Trước tiên, tôi xin được gửi lời cảm ơn đến tất cả quý thầy cô đã giảng dạy trong chương trình Cao học do Trường Đại học Công nghệ thông tin và truyền thông tổ chức, những người đã truyền đạt cho tôi những kiến thức hữu ích về khoa học máy tính làm cơ sở cho tôi thực hiện tốt luận văn này. Tôi xin chân thành cảm ơn PGS. TS. Đỗ Trung Tuấn đã tận tình hướng dẫn cho tôi trong thời gian thực hiện luận văn. Mặc dù trong quá trình thực hiện luận văn có giai đoạn không được thuận lợi nhưng những gì Thầy đã hướng dẫn, chỉ bảo đã cho tôi nhiều kinh nghiệm trong thời gian thực hiện đề tài. Tôi cũng xin gửi lời cảm ơn đến tất cả các Thầy Cô đang làm việc tại Phòng khám đa khoa trường Cao đẳng Y tế Phú Thọ đã tận tình giúp đỡ trong việc thu thập thông tin, lấy số liệu về bệnh và thuốc làm cơ sở dữ liệu cho luận văn. Sau cùng tôi xin gửi lời biết ơn sâu sắc đến các anh chị trong lớp và gia đình đã luôn tạo điều kiện tốt nhất cho tôi trong suốt quá trình học cũng như thực hiện luận văn. Do thời gian có hạn và kinh nghiệm nghiên cứu khoa học chưa nhiều nên luận văn còn nhiều thiếu sót, rất mong nhận được ý kiến góp ý của Thầy/Cô và các anh chị học viên. Phú Thọ, tháng 7 năm 2015 Học viên Vy Đại Nghĩa Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
iii Lời cam đoan Tôi cam đoan những kế t quả trong luâ ̣n văn là của viê ̣c tìm hiể u, có trích dẫn và tham chiế u đế n các nguồn tư liê ̣u tin cậy. Nội dung luận văn không sao chép từ các kế t quả của các luâ ̣n văn, luận án khác. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
iv MỤC LỤC Lời cảm ơn .................................................................................................................. i Lời cam đoan ........................................................................................................... iii MỤC LỤC ................................................................................................................. iv DANH MỤC CÁC TỪ VIẾT TẮT........................................................................... vi DANH MỤC CÁC BẢNG, HÌNH VẼ .....................................................................vii MỞ ĐẦU .................................................................................................................... 1 CHƯƠNG 1 ................................................................................................................ 6 TỔNG QUAN VỀ PHÁT HIỆN MỐI QUAN HỆ GIỮA CÁC DỮ LIỆU TRONG CƠ SỞ DỮ LIỆU ....................................................................................................... 6 1. 1. Mục tiêu của việc phát hiện mối quan hê ̣ giữa các dữ liệu ......................... 6 1. 2. Các bước chính của quá trình khai phá tri thức .......................................... 6 1. 3. Các dạng dữ liệu có thể khai phá ............................................................... 7 1. 4. Các hướng tiếp cận chính trong khai phá dữ liệu ....................................... 8 1. 5. Phân loại và ứng dụng các hệ thống khai phá dữ liệu ............................... 11 1. 5. 1. Phân loại các hệ thống khai phá dữ liệu ....................................... 11 1. 5. 2. Ứng dụng của khai phá dữ liệu .................................................... 12 1. 6. Kết luận chương ...................................................................................... 12 CHƯƠNG 2 .............................................................................................................. 13 MỘT SỐ MỐI QUAN HỆ DỮ LIỆU ĐƯỢC PHÁT HIỆN THÔNG QUA NGÔN NGỮ TRUY VẤN .................................................................................................... 13 2. 1. Luật kết hợp ............................................................................................ 13 2. 1. 1. Các khái niệm cơ bản................................................................... 13 2. 1. 2. Bài toán khai phá luật kết hợp ...................................................... 16 2. 2. Khai thác tập phổ biến dựa trên ngôn ngữ truy vấn .................................. 17 2. 2. 1. Ngôn ngữ truy vấn ....................................................................... 17 2. 2. 2. Tìm tập phổ biến bằng K-way join ............................................... 20 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
v 2. 2. 3. Kết quả thử nghiệm 3 phương pháp đếm độ hỗ trợ....................... 27 2. 2. 4. Phân tích các cải tiến của thuật toán k-way join ........................... 32 2. 2. 5. Phát sinh luật kết hợp................................................................... 38 2. 2. 6. Rút ngọn luật kết hợp................................................................... 42 2. 3. Kết luận chương ...................................................................................... 49 CHƯƠNG 3 .............................................................................................................. 51 ỨNG DỤNG TRONG TÍNH TOÁN THỬ NGHIỆM ............................................ 51 3. 1. Các bài toán............................................................................................. 51 3. 1. 1. Bài toán tìm luật kết hợp dạng X Y .......................................... 51 3. 1. 2. Bài toán tìm độ hỗ trợ và độ tin cậy của luật ................................ 52 3. 1. 3. Bài toán đánh giá độ tin cậy của luật theo ngưỡng ....................... 53 3. 1. 5. Giải pháp giúp thực hiện các bài toán .......................................... 54 3. 2. Chương trình thử nghiệm ........................................................................ 56 3. 2. 1. Cơ sở dữ liệu của bài toán............................................................ 57 3. 2. 2. Kết quả khai phá dữ liệu khi thực hiện các bài toán ..................... 58 3. 3. Kết luận chương ...................................................................................... 65 KẾT LUẬN .............................................................................................................. 67 PHỤ LỤC ................................................................................................................. 68 TÀI LIỆU THAM KHẢO ....................................................................................... 76 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
vi DANH MỤC CÁC TỪ VIẾT TẮT ADO Active X Data Object ANSI Chuẩn quốc gia Hoa Kì Client/ server Khách/ chủ confidence Độ tin cậy CSDL Cơ sở dữ liệu DB2 Tên hệ quản trị cơ sở dữ liệu của IBM DBMS Hệ quản trị cơ sở dữ liệu HQTCSDL Hệ quản trị cơ sở dữ liệu ISO Tổ chức tiêu chuẩn hóa quốc tế MOLAP multidimensional OLAP OLAP Online Analysis Processing ORACLE Tên công ty ORACLE, tên hệ quản trị cơ sở dữ liệu ROLAP Relational OLAP SQL Ngôn ngữ truy vấn support Độ hỗ trợ, trợ giúp Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
vii DANH MỤC CÁC BẢNG, HÌNH VẼ Hình. Thí dụ về xử lí dữ liệu y tế tại trường Cao đẳng Y tế Phú Thọ............................ 2 Hình 1. 1: Các bước trong quá trình khai phá tri thức................................................... 6 Hình 1. 2: Các kiến trúc khai phá tích hợp với cơ sở dữ liệu ........................................ 9 Hình 1. 3: Kiến trúc gắn kết lỏng ................................................................................. 9 Hình 1. 4: Kiến trúc thủ tục nội và hàm do người dùng định nghĩa ............................ 10 Hình 1. 5: Kiến trúc dựa trên truy vấn SQL ............................................................... 10 Hình 2. 1: Minh họa luật kết hợp ............................................................................... 16 Bảng 2. 1: Cấu trúc bảng ban đầu .............................................................................. 20 Bảng 2. 2: Cấu trúc bảng dùng để khai khác .............................................................. 21 Hình 2. 2: Tiến trình phát sinh tập ứng viên Ck .......................................................... 23 Hình 2. 2: Đếm độ hỗ trợ bằng cách tiếp cận K-way Join........................................... 24 Hình 2. 3: Biểu đồ hình cây cho Sub Query Qi ........................................................... 26 Hình 2. 4: Đồ thị thời gian thực thi của 3 thuật toán khi minsup=10% và D=100000 . 28 Hình 2. 5: Đồ thị thời gian thực thi 3 thuật toán khi minsup=10% và D=50000 ......... 29 Hình 2. 7: Đồ thị thời gian thực thi của 3 thuật toán khi minsup=10% và D=10000 ... 29 Hình 2. 6: Đồ thị tổng hợp thời gian thực thi của 3 thuật toán khi minsup lớn ............ 29 Hình 2. 7: Đồ thị thời gian thực thi 3 thuật toán khi minsup=5% và D=100000 ......... 30 Hình 2. 8: Đồ thị thời gian thực thi 3 thuật toán khi minsup=5% và D=50000 ........... 30 Hình 2. 9: Đồ thị thời gian thực thi 3 thuật toán khi minsup=5% và D=10000 ........... 30 Hình 2. 10: Đồ thị tổng hợp thời gian thực thi 3 thuật toán khi minsup trung bình ..... 31 Hình 2. 11: Đồ thị thời gian thực thi 3 thuật toán khi minsup = 1% và D = 100000.... 31 Hình 2. 12: Đồ thị thời gian thực thi 3 thuật toán khi minsup = 1% và D= 50000 ...... 32 Hình 2. 13: Đồ thị thời gian thực thi của 3 thuật toán khi minsup =1% và D=10000 .. 32 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
viii Hình 2. 154: Đồ thị tổng hợp thời gian thực thi của 3 thuật toán khi minsup nhỏ ....... 32 Bảng 2. 3: Cơ sở dữ liệu ban đầu D ........................................................................... 44 Bảng 2. 4: Cơ sở dữ liệu sau khi chuyển đổi .............................................................. 44 Bảng 2. 5: Kết quả F1 ................................................................................................. 45 Bảng 2. 6: Kết quả F2 ................................................................................................. 46 Bảng 2. 7: Kết quả C3 ................................................................................................ 46 Bảng 2. 8: Kết quả Comb3 ......................................................................................... 47 Bảng 2. 9: Kết quả F3 ................................................................................................. 47 Bảng 2. 10: Kết quả C4 .............................................................................................. 48 Bảng 2. 11: Kết quả Comb4........................................................................................ 49 Bảng 2. 12: Kết quả F4 ............................................................................................... 49 Bảng 2. 13. Kết quả ................................................................................................... 49 Bảng 3. 1. Cấu trúc bảng dữ liệu ban đầu ................................................................... 55 Bảng 3. 2. Cấu trúc bảng dùng để khai phá dữ liệu .................................................... 56 Hình 3. 1. Mẫu đơn thuốc của Phòng khám đa khoa Trường cao đẳng Y Phú Thọ ..... 57 Hình 3. 2. Minh họa cấu trúc dữ liệu ban đầu............................................................. 58 Hình 3. 3. Cấu trúc dữ liệu dùng để khai phá ............................................................. 58 Hình 3. 4. Tính độ hỗ trợ và độ tin cậy của luật {Cefalecin} => {Paracetamol} ......... 61 Hình 3. 5. Tính độ hỗ trợ và độ tin cậy của một luật {Decolgen}=>{Vitamin C} ....... 61 Hình 3.6. Đánh giá độ tin cậy của luật {Decolgen}=>{Vitamin B1} .......................... 65 Hình 3.7. Đánh giá độ tin cậy của luật {Cefalecin}=>{Vitamin C}............................ 65 Hình PL1: Minh họa dữ liệu đầu vào ......................................................................... 68 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
1 MỞ ĐẦU 1. Lý do chọn đề tài Theo [1] người ta thấy với sự phát triển rất mạnh mẽ về công nghệ lưu trữ, và khả năng đáp ứng của máy tính đã cho phép ta lưu trữ và xử lý khối lượng dữ liệu khổng lồ. Hầu hết các tổ chức, cơ quan đang lưu trữ dữ liệu theo thời gian. Kết quả là, sau một thời gian dài, lượng dữ liệu ngày càng nhiều. Tuy nhiên, những nhà quản lý lại chưa chú tâm lắm về giá trị tiềm ẩn bên trong khối dữ liệu này. Những tri thức có ích ẩn bên trong đó không dễ dàng để lấy hay rút trích ra. Ngày này, tính cạnh trạnh trên thị trường rất cao, đòi hỏi người ra quyết định cần phải đưa ra quyết định, chính sách một cách thận trọng, chính xác và hiệu quả. Những thông tin để giúp cho họ đạt hiệu quả hơn trong việc ra quyết định có thể được phân tích, rút trích từ những dữ liệu lưu trữ hiện tại (dữ liệu thô). Khai phá dữ liệu sẽ giúp ta giải quyết được vấn đề trên. Công việc khai phá sẽ phân tích, rút trích một cách tự động thông tin trong khối dữ liệu lớn nhằm tóm tắt dữ liệu theo cách mới để tiện cho người dùng khai phá, tìm ra các mẫu mới, những mối liên hệ và những dự đoán, xu hướng thông tin trong tương lai. Về cơ bản, khai phá dữ liệu 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 khai phá dữ liệu đã được dùng nhiều năm rồi, 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. Những nhu cầu hướng kinh doanh này đã thay đổi cách lấy ra và thống kê dữ liệu đơn giản sang việc khai phá dữ liệu phức tạp hơn. Vấn đề kinh doanh 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 cuộc sẽ dẫn đến việc tạo ra báo cáo kết quả. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
2 Các yêu cầu về nghiệp vụ y tế Xác định nguồn dữ liệu y tế Xác định khuôn dạng dữ liệu Lặp lại Xây dựng mô hình dữ liệu y tế Xây dựng c u t c dữ liệu y tế, phù hợp với hỏi dữ liệu Phát hiện t i thức, mối quan hệ giữa dữ liệu y tế Hình. Thí dụ về xử lí dữ liệu y tế tại trường Cao đẳng Y tế Phú Thọ Quá trình phân tích dữ liệu, khám phá dữ liệu và xây dựng mô hình dữ liệu thường lặp lại khi bạn tập trung vào và nhận ra các thông tin khác nhau để bạn có thể trích ra. Bạn cũng phải hiểu cách thiết lập quan hệ, ánh xạ, kết hợp và phân cụm thông tin đó với dữ liệu khác để tạo ra kết quả. Quá trình nhận ra dữ liệu nguồn và các định dạng nguồn, rồi ánh xạ thông tin đó tới kết quả đã cho của chúng tôi có thể thay đổi sau khi bạn phát hiện ra các yếu tố và các khía cạnh khác nhau của dữ liệu. Khai phá dữ liệu không phải là tất cả về các công cụ hay phần mềm cơ sở dữ liệu mà bạn đang sử dụng. Bạn có thể thực hiện khai phá dữ liệu bằng các hệ thống cơ sở dữ liệu bình thường và các công cụ đơn giản, bao gồm việc tạo và viết phần mềm riêng của bạn hoặc sử dụng các gói phần mềm bán ngoài cửa hàng. Khai phá dữ liệu phức tạp được hưởng lợi từ kinh nghiệm trong quá khứ và các thuật toán đã định nghĩa với phần mềm và các gói phần mềm hiện có, với các công cụ nhất định để thu được một mối quan hệ hoặc uy tín lớn hơn bằng các kỹ thuật khác nhau. Liên quan đến xử lí dữ liệu trong các bài toán với dữ liệu lớn, trên các hệ quản trị cơ sở dữ liệu như Oracle, DB2, người ta đã sử du ̣ng tiếp cận nối K-way join [10] để tăng tốc độ xử lí dữ liệu, và để thuận tiện cho việc phát hiện các mối quan Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
3 hê ̣ giữa các dữ liệu, chẳng hạn như luật kết hợp. Do đó, tôi đã chọn đề tài về xử lí dữ liệu y tế, trong cơ sở dữ liệu về y tế tại trường Cao đẳng Y tế Phú Thọ áp dụng ki ̃ thuâ ̣t của tiếp cận K-way join để phát hiện các mối quan hê ̣. Trong luận văn này, tôi sử dụng ngôn ngữ truy vấn SQL và chọn cách tiếp cận K-way join làm trọng tâm để đưa ra được các tri thức về thuốc theo nhiều bệnh lý khác nhau nhằm hỗ trợ cho y, bác sỹ và người quản lý trong công việc khám chữa bệnh, kinh doanh dược. . . . Dựa trên bài toán đề ra, tôi đã tính toán một bài toán thực tế lấy dữ liệu từ các đơn thuốc của phòng khám trường Cao đẳng Y tế Phú Thọ, đơn thuốc mẫu trong các tài liệu giáo trình của nhà trường theo các bệnh khác nhau. . . 2. Tính thực tiễn của đề tài Y học là môn khoa học không ngừng phát triển. Tiếp cận và cập nhật hóa thông tin y học từ những cơ sở dữ liệu, để nâng cao chất lượng chăm sóc sức khỏe cho nhân dân là điều không thể thiếu trong thực hành lâm sàng. Với sự phát triển mạnh mẽ của ngành Công nghệ thông tin, một trong những ngành mũi nhọn của nhiều quốc gia trên thới giới. Sự phát triển vượt bậc đó là kết quả tất yếu của việc ứng dụng của nó trong nhiều lĩnh vực khác nhau trong cuộc sống như: giáo dục, y tế, kinh tế, khoa học, xây dựng nó đã trở thành một phần không thể thiếu được trong cuộc sống hàng ngày của con người. Trong kỷ nguyên bùng nổ thông tin, việc áp dụng các phương pháp tìm kiếm thông tin từ những nguồn dữ liệu khác nhau là nhu cầu thiết thực cho toàn xã hội. Trong các phương pháp tìm kiếm thông tin đó, khai phá dữ liệu để tìm ra tri thức, phục vụ đời sống xã hội là một phương pháp mới, đang được các nhà nghiên cứu khoa học quan tâm. Tuy nhiên, khai phá dữ liệu trong lĩnh vực y học ở nước ta quả thật còn rất ít, gặp nhiều khó khăn, do hiện nay nhiều bệnh viện ở nước ta chưa có bệnh án điện tử. Việc khai phá trong lĩnh vực này thực sự mang lại nhiều ý nghĩa cho y học để hỗ trợ cho các bác sĩ kê đơn, chẩn đoán bệnh sớm và điều trị bệnh có hiệu quả, giảm bớt tử vong cũng như chi phí điều trị, đây là một nhu cầu thiết thực trong các bệnh viện. Xuất phát từ những thực tế Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
4 trên, tôi đã chọn đề tài “Phát hiện mối quan hệ trong cơ sở dữ liệu và ứng dụng trong y học” để nghiên cứu cho luận văn thạc sĩ của mình. 3. Mục tiêu nghiên cứu Mục tiêu và nội dụng của luận văn này là tìm hiểu các phương pháp khai thác dữ liệu dựa trên ngôn ngữ truy vấn SQL và chọn tiếp cận K-way join làm trọng tâm. Dựa trên cách tiếp cận này chúng ta sẽ phân tích và đánh giá các cải tiến cho K-way join, đề xuất phương pháp phát sinh và rút gọn luật kết hợp dựa trên tập luật mẫu. 4. Đối tượng và phạm vi nghiên cứu  Tìm hiểu các khái niệm cơ bản về luật kết hợp, các cách tiếp cận khai phá dữ liệu, đặc biệt là cách tiếp cận K-way join  Đề xuất phương pháp phát sinh và rút gọn luật kết hợp trên tập luật mẫu  Tính toán thử nghiệm để đưa ra các tri thức về thuốc cho trường Cao đẳng Y tế Phú Thọ, so sánh và đánh giá hiệu năng, độ tối ưu của cách tiếp cận K-way join với các cách tiếp cận khác. 5. Phương pháp nghiên cứu  Tìm hiểu các tài liệu về các vấn đề liên quan.  Tham gia thảo luận và trình bày xemina.  Tính toán thử nghiệm. 6. Bố cục luận văn Luận văn bao gồm: mục lục, phần mở đầu, phụ lục.  Chương I: Tổng quan về phát hiện mối quan hệ giữa các dữ liệu trong cơ sở dữ liệu.  Chương II: Một số mối quan hệ dữ liệu được phát hiện thông qua ngôn ngữ truy vấn  Chương III: Ứng dụng trong tính toán thử nghiệm. Kết luận và hướng phát triển. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
6 CHƯƠNG 1 TỔNG QUAN VỀ PHÁT HIỆN MỐI QUAN HỆ GIỮA CÁC DỮ LIỆU TRONG CƠ SỞ DỮ LIỆU 1. 1. Mục tiêu của việc phát hiện mối quan hê ̣ giữa các dữ liệu Mục tiêu của việc khai khác dữ liệu có các nhiệm vụ chính như sau [2]:  Khám phá dữ liệu, khám phá mẫu, và dự đoán mẫu nhằm khám phá tri thức trong kho dữ liệu;  Rút trích các thông tin có giá trị tiềm ẩn trong kho dữ liệu;  Phân tích tự động trong kho dữ liệu;  Biểu diễn dữ liệu để thân thiện với người dùng hơn;  Dự báo các thông tin mới dựa trên dữ liệu hiện tại để từ đó hỗ trợ, và ra quyết định. 1. 2. Các bước chính của quá trình phát hiện tri thức Quá trình phát hiện tri thức được chia thành các bước như sau [1, 2]: Hình 1. 1: Các bước trong quá trình khai phá tri thức  Trích chọn dữ liệu (data selection): Là bước trích chọn những tập dữ liệu cần được khai phá từ các tập dữ liệu lớn (databases, data warehouses).  Tiền xử lý dữ liệu (data preprocessing): Là bước làm sạch dữ liệu (xử lý dữ liệu không đầy đủ, dữ liệu nhiễu, dữ liệu không nhất quán, . . . ), rút Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
7 gọn dữ liệu (sử dụng các phương pháp thu gọn dữ liệu, histograms, lấy mẫu, . . . ), rời rạc hoá dữ liệu (dựa vào histograms, entropy, phân khoảng, . . . ). Sau bước này, dữ liệu sẽ nhất quán, đầy đủ, được rút gọn, và được rời rạc hoá.  Biến đổi dữ liệu (data transformation): Là bước chuẩn hoá và làm mịn dữ liệu để đưa dữ liệu về dạng thuận lợi nhất nhằm phục vụ cho các kỹ thuật khai thác ở bước sau.  Khai phá dữ liệu (data mining): Đây là bước quan trọng và tốn nhiều thời gian nhất của quá trình khám phá tri thức, áp dụng các kỹ thuật khai phá (phần lớn là các kỹ thuật của học máy) để khai phá, trích chọn được các mẫu (pattern) thông tin, các mối liên hệ đặc biệt trong dữ liệu.  Đánh giá và biểu diễn tri thức (knowledge representation & evaluation): Dùng các kỹ thuật hiển thị dữ liệu để trình bày các mẫu thông tin (tri thức) và mối liên hệ đặc biệt trong dữ liệu đã được khai phá ở bước trên biểu diễn theo dạng gần gũi với người sử dụng như đồ thị, cây, bảng biểu, luật, . . . Đồng thời bước này cũng đánh giá những tri thức khám phá được theo những tiêu chí nhất định. Trong giai đoạn khai phá dữ liệu, có thể cần sự tương tác của người dùng để điều chỉnh và rút ra các tri thức cần thiết nhất. Các tri thức nhận được cũng có thể được lưu và sử dụng lại. 1. 3. Các dạng dữ liệu có thể khai phá Khai phá dữ liệu có khả năng chấp nhận một số kiểu dữ liệu khác nhau điển hình như sau [3, 4]:  Cơ sở dữ liệu quan hệ (relational databases): Là các dữ liệu tác nghiệp được tổ chức theo mô hình dữ liệu quan hệ rất phổ biến trong hệ thống quản lý và quán lý bán hàng nói riêng, do hầu hết các hệ quản trị cơ sở dữ liệu đều hỗ trợ dạng cơ sở dữ liệu quan hệ như Oracle, MS SQL Server, IBM DB2, MS Access, . . . Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
8  Cơ sở dữ liệu đa chiều (multidimention structures, data warehouses, data mart): Là các kho dữ liệu được tập hợp và chọn lọc từ nhiều nguồn dữ liệu khác nhau. Dạng dữ liệu này chủ yếu phục vụ cho quá trình phân tích cũng như khai phá tri thức và hỗ trợ quá trình ra quyết định.  Cơ sở dữ liệu giao tác (transactional databases): Đây cũng là dạng dữ liệu tác nghiệp có các bản ghi thường là các giao tác. Dạng dữ liệu này cũng phổ biến hiện nay trong đó có ngành thương mại.  Cơ sở dữ liệu quan hệ – hướng đối tượng (object relational databases): Là dạng dữ liệu lai giữa hai mô hình quan hệ và hướng đối tượng.  Dữ liệu không gian và thời gian (spatial, temporal, and time-series data): Là dạng dữ liệu có tích hợp thuộc tính về không gian như dữ liệu bản đồ mạng cáp điện thoại hoặc thời gian như dữ liệu cước điện thoại, phát hành báo chí.  Cơ sở dữ liệu đa phương tiện (Multimedia database): Là dạng dữ liệu âm thanh (audio), hình ảnh (video), văn bản và WWW, . . . Dạng dữ liệu này đang rất phổ biến trên Internet và lưu tại các web server của các đơn vị trực thuộc doanh nghiệp hoặc tổ chức. 1. 4. Các hướng tiếp cận chính trong khai phá dữ liệu Một số hướng tiếp cận chính của khai phá dữ liệu được phân chia theo chức năng hay lớp các bài toán khác nhau [2, 4]:  Phân lớp và dự đoán (classification & prediction): Xếp đối tượng vào một trong các lớp đã biết trước. Ví dụ: phân lớp loại cước hoặc loại dịch vụ dựa trên số máy bị gọi của cuộc gọi, phân lớp khu vực dựa trên số máy chủ gọi, phân lớp giờ cao điểm, thấp điểm dựa trên giờ bắt đầu đàm thoại. . . . Phân lớp là một lĩnh vực rất quan trọng trong khai phá dữ liệu. Phân lớp còn được gọi là học có giám sát (supervised learning), hướng tiếp cận này thường sử dụng một số kỹ thuật của học máy như cây quyết định (decision tree), mạng nơ ron nhân tạo (neural network). . . Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
9 Trong việc khai phá dữ liệu, một số kiến trúc đã được đề xuất cho việc tích hợp tiến trình khai phá với hệ quản trị cơ sở dữ liệu (HQTCSDL). Những kiến trúc này được biểu diễn như sau: Hình 1. 2: Các kiến trúc khai thác tích hợp với cơ sở dữ liệu  Sự gắn kết lỏng hay khai phá dựa trên việc lưu trữ (Loose coupling or Cache based mining): Đây là kiến trúc dạng Client/Server. Phần khai phá được xem là ứng dụng phía server. Theo kiến trúc này, đầu tiên dữ liệu được đọc từ database bằng cursor, sau đó nó sẽ đưa vào nhân khai phá (mining kernel). Khai phá xong sẽ đưa kết quả vào cơ sở dữ liệu. Điều này dẫn đến hiệu năng chậm. Kiến trúc được mô tả như hình vẽ bên dưới: Hình 1. 3: Kiến trúc gắn kết lỏng  Thủ tục nội và hàm do người dùng định nghĩa (Stored procedure and user defined functions): Theo kiến trúc này, công việc khai phá được xem như là một ứng dụng trên máy chủ cơ sở dữ liệu. Các xử lý được thực thi trên cùng không gian địa chỉ là HQTCSDL. Thuật toán khai phá được viết Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
10 dưới dạng thủ tục nội (stored procedure) nên việc lập trình khá uyển chuyển, và có thể tái sử dụng. Hình 1. 4: Kiến trúc thủ tục nội và hàm do người dùng định nghĩa  Cách tiếp cận dựa trên SQL (SQL based approach): Theo kiến trúc này, sử dụng các câu truy vấn SQL để khai phá. Bộ xử lý tối ưu của HQTCSDL (query optimizer) được dùng để tối ưu các truy vấn phức tạp, những truy vấn xử lý với thời gian dài dựa trên ngữ nghĩa. Khai phá được tính xử lý song song những câu truy vấn SQL. Hình 1. 5: Kiến trúc dựa trên truy vấn SQL  Cách tiếp cận tích hợp (Intergrated approach): Đây là kiến trúc chặt chẽ nhất, không có giới hạn giữa việc truy vấn, OLAP, hay khai phá. Các toán tử khai phá hay SQL được mở rộng cho việc khai phá được tối ưu dựa trên hệ thống bên trong mà không có sự tác động của người dùng.  Khai phá mẫu tuần tự (sequential/temporal patterns): Tương tự như khai phá 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.  Phân cụm (clustering/segmentation): Sắp xếp các đối tượng theo từng cụm (số lượng và tên của cụm chưa được biết trước). Các đối tượng được Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
11 gom cụm sao cho mức độ tương tự giữa các đối tượng trong cùng một cụm là lớn nhất và mức độ tương tự giữa các đối tượng nằm trong các cụm khác nhau là nhỏ nhất. Phân cụm còn được gọi là học không có giám sát (unsupervised learning). 1. 5. Phân loại và ứng dụng các hệ thống khai phá dữ liệu 1. 5. 1. Phân loại các hệ thống khai phá dữ liệu Phân loại khai phá dữ liệu dựa trên các tiêu chí khác nhau [3]:  Phân loại dựa trên kiểu dữ liệu được khai phá: Cơ sở dữ liệu quan hệ, kho dữ liệu, cơ sở dữ liệu giao tác, cơ sở dữ liệu hướng đối tượng, cơ sở dữ liệu không gian, cơ sở dữ liệu đa phương tiện, cơ sở dữ liệu văn bản. . .  Phân loại dựa trên dạng tri thức được khám phá: Tóm tắt và mô tả, luật kết hợp, phân lớp, phân cụm, khai phá chuỗi. . .  Phân loại dựa trên lĩnh vực được áp dụng: Thương mại, viễn thông, tài chính, y học, web mining, . . .  Phân loại dựa trên kỹ thuật được áp dụng: Phân tích trực tuyến (Online Analytial Processing - OLAP), học máy (cây quyết định, mạng nơ ron nhân tạo, K-Means, giải thuật di truyền, tập thô, tập mờ. . . ). Thông thường sử dụng tập mờ là thích hợp cho việc tìm ra và hiểu được sự liên quan của các mô hình dữ liệu chưa đầy đủ, tạp nhiễu, thông tin hỗn tạp và tác động của con người, và từ đó có thể cung cấp giải pháp xấp xỉ nhanh hơn. Mạng nơ ron có khả năng tổng quát, không giới hạn, mạnh và học tốt trong môi trường dữ liệu giàu (data-rich). thuật toán di truyền cung cấp khả năng tìm các thuật toán để chọn mẫu từ các dữ liệu hỗn tạp dựa trên một số hàm tiêu chuẩn/ mục tiêu thường dùng. Tập thô thì phù hợp cho tìm ra các mẫu khác nhau của tình trạng không rõ ràng trong dữ liệu. Một số yêu cầu khai phá dữ liệu cần phải áp dụng phương pháp tính toán mềm (Tính toán mềm là sự kết hợp của các phương pháp logic mờ, thuật toán di truyền, khám phá tri thức, mạng nơ ron, tính toán neuro- fuzzy, tập thô, rút ra luật. ) Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn