Chương I : TỔNG QUAN I. ðẶT VẤN ðỀ Ngày nay, công nghệ thông tin ñã trở thành một trong những ñộng lực quan trọng của sự phát triển. Với khả năng số hóa mọi thông tin (số, ñồ thị, văn bản, hình ảnh, âm thanh, tiếng nói,…), máy tính ñã trở thành một công cụ thông minh, nó ñược sử dụng ñể xử lý thông tin với nhiều dạng thông tin thuộc nhiều lĩnh vực khác nhau trong ñời sống như: kinh doanh, y học,… Bên cạnh ñó, cùng với sự phát triển của công nghệ lưu trữ dữ liệu phục vụ trong công việc lưu trữ các thông tin liên quan ñến nhiều mặt của cuộc sống: kinh doanh, buôn bán, … ñã góp phần cải thiện cuộc sống và làm giảm bớt ñi việc lưu trữ thông tin dựa trên văn bản. ðó chính là tiền ñề cho sự ra ñời của nền kinh tế mới – nền kinh tế số ( hay có thể gọi là nền kinh tế tri thức, nền kinh tế dựa trên tri thức).
Nền kinh tế ñấy ñã và ñang làm cho sự phát triển thông tin lưu trữ ngày càng nhiều, và khả năng linh hoạt của các phần mềm phải ñảm ñương nhiều công việc trong việc lựa chọn thông tin. Và trong những năm 1980, một số nhà nghiên cứu ñã ñưa một số kỹ thuật nhằm giải quyết các vấn ñề trên, và ñược gọi là kỹ thuật khai phá dữ liệu (data mining). Các kỹ thuật khai phá dữ liệu ñã ñược các công ty kinh doanh các sản phẩm liên quan ñến thông tin ñã ứng dụng như: - Duyệt web, tìm kiếm các thông tin trên Google, Google luôn ñưa ra các gợi ý, có lẽ bạn sẽ nghĩ: nó ñã ñọc ñược những suy nghĩ của mình! Mà ña phần các gợi ý ñấy gần như là các thông tin mà bạn cần tìm kiếm. Vì sao Google biết mình cần tìm thông tin ñấy? - Facebook, nhắc ñến Facebook bạn sẽ nghĩ ñến một cộng ñồng với số lượng thông tin cá nhân ñược lưu trữ với số lượng lớn, phải nói là rất lớn.
Khi bạn muốn kết bạn trên cộng ñồng ấy, Facebook luôn ñưa ra những gợi ý về những người bạn cho bạn kết bạn. Và những người bạn ấy gần như bạn ñã quen biết ngoài cuộc sống ñời thường. Bạn nghĩ tại sao nó có thể làm như vậy? - Một ví dụ khác, ñó là việc tìm và mua 1 quyển sách trên cửa hàng sách trực tuyến khổng lồ Amazon. Khi lựa chọn một quyển sách, nó luôn ñưa ra cho bạn các lựa chọn về những quyến sách mà 90% là bạn cần mua.
Vậy tại sao nó hiểu bạn nhiều như thế? Và câu hỏi cuối cùng, việc xử lý thông tin của nó ra sao? Tất cả những câu hỏi ñấy là một ứng dụng cụ thể của khai phá dữ liệu và khám phá tri thức. Vậy khai phá dữ liệu là gì? I. LỊCH SỬ GIẢI QUYẾT VẤN ðỀ “ Data mining là quá trình thăm dò, lựa chọn và mô hình hóa khối lượng lớn dữ liệu ñể tìm ra những quy luật hoặc các mối quan hệ chưa biết ñầu tiên với mục ñích là ñể có ñược kết quả rõ ràng và hữu ích cho các chủ sở hữu của cơ sở dữ liệu.” SVTH: Quách Luyl ða Trang 7 .com NGHIÊN CỨU KHAI MỎ DỮ LIỆU VÀ KHÁM PHÁ TRI THỨC Qua quá trình phát triển, ñịnh nghĩa về khai phá dữ liệu ngày càng ñược mở rộng, và dần dần hoàn thiện: - Khai phá dữ liệu là quá trình khám phá thông tin hữu dụng trong các kho dữ liệu khổng lồ một cách tự ñộng. Các kỹ thuật khai phá dữ liệu ñược triển khai dựa trên các cơ sở dữ liệu lớn nhằm tìm kiếm các mẫu hay các quy luật (pattern) mới và hữu dụng mà chưa từng ñược biết trước ñó.
Ví dụ: “Những sinh viên học giỏi các môn Toán rời rạc, Lập trình, Cấu trúc dữ liệu và Cơ sở dữ liệu thì sẽ học giỏi môn khai phá dữ liệu” - Khai phá dữ liệu là quá trình tìm kiếm các mẫu mới, những thông tin, tri thức có ích, tiềm ẩn và mang tính dự ñoán trong khối lượng dữ liệu lớn. Các kỹ thuật khai phá dữ liệu cũng cung cấp các khả năng phán ñoán (dự ñoán) kết quả của các quan sát trong hiện tại và quá khứ. Khai phá dữ liệu không chỉ khám phá các thông tin hữu dụng trong các cơ sở dữ liệu (databases) hay kho dữ liệu (data respostories) mà còn liên quan ñến các lĩnh vực truy xuất thông tin (information retrieval). Ví dụ: Sử dụng hệ quản trị cơ sở dữ liệu ñể tìm kiếm các mẫu tin hoặc sử dụng các công cụ tìm kiếm trên Internet ñể tìm kiếm các trang web hoặc thông tin ñược lưu trữ ở các trang web cụ thể nào ñó.
Data mining là 1 phần hoàn chỉnh của lĩnh vực khám phá tri thức (Knowledge Discovery). Nó là toàn bộ quá trình chuyển dữ liệu thô sang thông tin hữu dụng. Quá trình này gồm nhiều bước tiền xử lý dữ liệu ñến hậu xử lý kết quả của quá trình khai phá. Thống kê tóm tắt Xác Xác Thu Giải ñịnh thập và thuật ñịnh Mẫu nhiệm dữ tiền xử khai vụ liệu lý dữ phá liên liệu Dữ liệu trực tiếp Hình I-2.
Quá trình khai phá dữ liệu Các khó khăn trong việc khai thác tri thức từ dữ liệu: a) Tính qui mô: Với sự phát triển trong việc tạo ra dữ liệu cũng như thu thập dữ liệu, các tập hợp dữ liệu ñuợc lưu trữ ngày càng lớn (gigabytes, terabytes,petabytes) và ngày càng trở nên thông dụng. Các thuật toán khai phá dữ liệu phải có khả năng phân tích ñược các tập dữ liệu ñó. Nhiều kỹ thuật khai phá dữ liệu triển khai các chiến lược nghiên cứu ñặc biệt nhằm quản lý các vấn ñề trong nghiên cứu tăng theo cấp SVTH: Quách Luyl ða Trang 8 .com NGHIÊN CỨU KHAI MỎ DỮ LIỆU VÀ KHÁM PHÁ TRI THỨC số nhân. Tính qui mô (scalability) yêu cầu phương pháp cài ñặt của cấu trúc dữ liệu mới nhằm truy xuất ñược các mẩu tin một cách hiệu quả.
Ví dụ: Các thuật toán “xử lý dữ liệu ngoài bộ nhớ (RAM)” (out-of-core) rất cần thiết khi xử lý các tập dữ liệu lớn hơn dung lượng của bộ nhớ. Tính qui mô có thể ñược cải tiến bằng cách sử dụng các dữ liệu mẫu (samples), sử dụng các giải thuật song song và phân tán. b) Tính ña thuộc tính: Xử lý các tập dữ liệu có hàng trăm hay hàng nghìn thuộc tính ngày càng trở nên phổ biến. Trong lĩnh vực tin học cho sinh học, dữ liệu về gen có thể bao gồm hàng ngàn thuộc tính.
Các tập dữ liệu với các thành phần dữ liệu theo thời gian hay còn ñược gọi là dữ liệu tuần tự (temporal/ spatial components) cũng có xu hướng có rất nhiều thuộc tính. Ví dụ: Tập dữ liệu chứa các thông tin về ñịa chất ở nhiều khu vực khác nhau ñược thu thập lặp ñi lặp lại nhiều lần, số lượng các thuộc tính có thể tăng dần theo thời gian. Các kỹ thuật phân tích dữ liệu truyền thống ñược thiết kế cho dữ liệu có ít thuộc tính không thể áp dụng cho trường hợp dữ liệu có nhiều thuộc tính. c) Dữ liệu không thuần nhất và phức tạp: Các phương pháp phân tích dữ liệu truyền thống áp dụng cho các tập hợp dữ liệu chứa các thuộc tính có cùng kiểu dữ liệu (có thể là liên tục hay rời rạc).
Khi việc sử dụng khai phá dữ liệu trong kinh doanh, trong khoa học và trong y học ngày càng tăng thì cần có các kỹ thuật phân tích dữ liệu có thể áp dụng ñược cho các thuộc tính không thuần nhất (heterogeneous attributes). Bên cạnh ñó, cũng phải áp dụng ñược cho các dữ liệu phức tạp. Ví dụ: Các kiểu dữ liệu truyền thống bao gồm: tập hợp các trang web lưu văn bản và liên kết bán cấu trúc, các dữ liệu về DNA trong không gian 3 chiều, dữ liệu về thời tiết (nhiệt ñộ, áp suất, ñộ ẩm) tại nhiều vùng trên thế giới. Các kỹ thuật ñược phát triển cho khai phá dữ liệu cần phải quan tâm ñến mối quan hệ trong dữ liệu như: mối quan hệ về nhiệt ñộ theo thời gian, sự liên thông giữa các ñồ thị, quan hệ giữa các thành phần trong dữ liệu bán cấu trúc và XML.
d) Sở hữu và phân bố dữ liệu: Có khi dữ liệu cần ñược phân tích ñược lưu trữ ở nhiều nơi khác nhau và ñược sở hữu bởi nhiều cơ quan khác nhau. Các khó khăn này ñòi hỏi phải phát triển các kỹ thuật khai phá dữ liệu theo dạng phân tán. Vấn ñề cần quan tâm là “làm sao hạn chế lưu lượng truyền tải dữ liệu khi thực hiện các thuật toán phân tán?”, “làm sao hợp nhất dữ liệu từ các nguồn gốc khác nhau một cách hiệu quả nhất?”, “làm sao ñảm bảo tính an toàn và bảo mật?”,… e) Việc phân tích dữ liệu không theo cách truyền thống: Cách tiếp cận dữ liệu theo phương pháp thống kê truyền thống dựa trên cách ñặt giả thuyết và kiểm tra giả thuyết cần rất nhiều công sức ñể kiểm tra các giả thuyết. Các công việc phân tích dữ liệu hiện tại ñòi hỏi phải ñặt và kiểm tra hàng nghìn giả ñịnh một cách tuần tự.
Quá trình phát triển các kỹ thuật khai phá dữ liệu ñã ñược thúc ñẩy bởi sự mong ñợi một quá trình ñặt và kiểm tra giả ñịnh một cách hoàn toàn tự ñộng. Hơn nữa, dữ liệu ñược phân tích trong khai phá dữ SVTH: Quách Luyl ða Trang 9 .com NGHIÊN CỨU KHAI MỎ DỮ LIỆU VÀ KHÁM PHÁ TRI THỨC liệu là dữ liệu ngẫu nhiên nên các phương pháp phân tích truyền thống không thể áp dụng cho các tập dữ liệu phức tạp và mang tính ngẫu nhiên. PHẠM VI CỦA ðỀ TÀI ðề tài ñi sâu nghiên cứu về quá trình khai phá dữ liệu và khám phá tri thức từ dữ liệu. Qua việc nghiên cứu có thể tìm hiểu thêm về các kỹ thuật cơ bản trong việc tiền xử lý dữ liệu, các kỹ thuật khai phá dữ liệu cơ bản và từ ñó có ñược những kiến thức trong việc tìm hiểu một công cụ khai phá dữ liệu, xây dựng demo khai phá dữ liệu dựa trên một số thuật toán của cây quyết ñịnh và luật kết hợp.
Từ quá trình nghiên cứu và thực tiễn ñể có thể thấy ñược các vấn ñề thách thức trong lĩnh vực khai phá dữ liệu. Sử dụng cơ sở lý thuyết ñã nghiên cứu ñể cài ñặt chuơng trình sinh luật kết hợp và cây quyết ñịnh là 2 kỹ thuật cơ bản của quá trình khai phá dữ liệu. PHƯƠNG PHÁP NGHIÊN CỨU Dựa trên việc tìm hiểu các tư liệu trong lĩnh vực khai phá dữ liệu, từ ñó rút ra ñược những kết quả của quá trình tiền xử lý dữ liệu, một số kỹ thuật khai phá dữ liệu cơ bản cùng với các thuật toán của nó.