CHƯƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU 1. Khai phá dữ liệu 1. Mục tiêu của khai phá dữ liệu Theo J. Kamber [19], quá trình tiến hóa của lĩnh vực công nghệ CSDL được mô tả như Hình 1.1, trong đó công nghệ KPDL được coi là dạng tiến hóa mới của công nghệ CSDL bắt đầu từ cuối những năm 1980 và không ngừng được phát triển về bề rộng và chiều sâu.
Tập hợp dữ liệu và khởi tạo CSDL (tới cuối những năm 1960) - Xử lý file thô sơ Hệ quản trị CSDL (những năm 1970 và những năm đầu 1980) - Hệ thống CSDL phân cấp và mạng - Công cụ mô hình dữ liệu: Mô hình quan hệ thực thể - Phương pháp đánh chỉ số và truy nhập: cây B+, hàm băm - Ngôn ngữ hỏi SQL … - Giao diện người dùng, nhập liệu và kết xuất - Xử lý truy vấn, tối ưu truy vấn - Quản lý giao dịch: khôi phục, điều khiển tương tranh - Xử lý giao dịch trực tuyến (OLTP) Hệ CSDL mở rộng Kho dữ liệu và khai phá dữ Hệ CSDL dựa trên (những năm giữa 1980 liệu Web đến nay) (những năm cuối 1980 đến nay) (những năm 1990 đến - Mô hình dữ liệu mở - Kho dữ liệu và OLAP nay) rộng: quan hệ mở rộng, - Khai phá dữ liệu và phát hiện - Hệ CSDL dựa trên quan hệ - đối tượng, suy tri thức: phân lớp, phân cụm, XML luận kết hợp, phân tích mẫu, phân - Sự tích hợp với sự - Ứng dụng mở rộng: tích ngoại lai … phục hồi thông tin không gian, thời gian, đa - Ứng dụng khai phá dữ liệu - Dữ liệu và sự tích phương tiện, tích cực, mở rộng: khai phá dữ liệu dòng, hợp thông tin khoa học, cơ sở tri thức khai phá text, khai phá web… Thế hệ mới của dữ liệu tích hợp và các hệ thống thông tin (2000 - ) Hình 1. Sự tiến hoá công nghệ CSDL LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 11 Những thập kỷ gần đây đã chứng kiến một sự gia tăng đáng kể lượng thông tin hoặc dữ liệu được lưu trữ trong các thiết bị điện tử (như là đĩa cứng, CD- ROM, băng từ, v. Sự tích lũy dữ liệu này xảy ra với một tốc độ bùng nổ. Người ta ước đoán rằng, lượng thông tin trên toàn cầu tăng gấp đôi sau khoảng hai năm và theo đó số lượng cũng như kích cỡ của các CSDL cũng tăng lên một cách nhanh chóng [3].
Theo Fayyad, Piatetsky-Shapiro, Smyth [15], việc nghiên cứu phát triển lĩnh vực KPDL và KDD (Knowledge Discovery in Databases: KDD) là nhằm giải quyết tình trạng “ngập tràn thông tin mà thiếu thốn tri thức”. Một số số liệu thống kê dưới đây được đưa ra vào năm 2006 [17] đã minh chứng cho tình trạng "ngập tràn thông tin" là hiện nay tồn tại nhiều kho dữ liệu không những đã trở nên khổng lồ mà hàng ngày khối lượng của chúng còn được tăng trưởng với tốc độ cao. Về dữ liệu web, điển hình là Alexa sau 7 năm đã có 500 TB, Google đã lưu trữ hơn 4 tỷ trang Web với dung lượng nhiều trăm TB, IBM Web Fountain với hơn 160 TB, Internet Archive xấp xỉ 300 TB v. Về CSDL, điển hình là Max Planck Institute for Meteorology có tới hơn 220 TB, Yahoo! có hơn 100TB còn AT&T có gần 100 TB.
Theo ước lượng của UC Berkeley 2003 thì có tới 5 exabytes (5 triệu terabytes) dữ liệu mới được khởi tạo trong năm 2002. Mục đích của việc thu thập và lưu trữ các kho dữ liệu khổng lồ được liệt kê trên đây không ngoài mục đích KPDL nhằm phát hiện các tri thức mới có ích cho hoạt động của con người trong tập hợp các dữ liệu đã thu thập được [1]. Những công cụ KPDL có thể dự đoán các xu thế tương lai trên cơ sở phân tích dữ liệu hoạt động của doanh nghiệp, do đó cho phép các tổ chức doanh nghiệp đưa ra được các quyết định kịp thời được định hướng bởi tri thức mà KPDL đem lại. Tính tự động trong phân tích dữ liệu khiến nó chiếm ưu thế hơn hẳn so với các phân tích thông thường dựa trên kinh nghiệm hay các sự kiện trong quá khứ của các hệ thống hỗ trợ ra quyết định trước đây.
Trên cơ sở đó cũng đồng thời trả lời được nhiều vấn đề trong kinh doanh mà trước đây khó có thể thực hiện vì cần rất nhiều thời gian và công sức để xử lý. Với các ưu điểm trên, KPDL đã chứng tỏ được tính hữu dụng của nó trong môi trường kinh doanh đầy tính cạnh tranh ngày nay và được ứng dụng rộng rãi trong nhiều lĩnh vực như: thương mại, tài chính, y học, giáo dục, viễn thông … Định hướng và mục tiêu chính của KPDL là kết xuất tri thức từ dữ liệu. Do đó, ở mức cao - tổng quát, ta có thể coi mục đích chính của quá trình KPDL là LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 12 mô tả (description) và dự đoán (prediction) [2]. Dự đoán dùng một số biến hoặc trường trong CSDL để dự đoán hoặc về giá trị chưa biết hoặc về giá trị sẽ có trong tương lai của các biến.
Mô tả hướng tới việc tìm ra các mẫu mô tả dữ liệu. Dự đoán và mô tả có tầm quan trọng khác nhau đối với các thuật toán KPDL. Ở mức chi tiết - cụ thể, dự báo và mô tả được thể hiện thông qua các bài toán cụ thể như mô tả khái niệm, quan hệ kết hợp, phân cụm, phân lớp, hồi quy, mô hình phụ thuộc, phát hiện biến đổi và độ lệch và một số bài toán cụ thể khác. Khái niệm khai phá dữ liệu Lĩnh vực KPDL và KDD đã cuốn hút các phương pháp, thuật toán và kỹ thuật từ nhiều chuyên ngành nghiên cứu khác nhau như học máy, thu nhận mẫu, CSDL, thống kê, trí tuệ nhân tạo, thu nhận tri thức trong hệ chuyên gia… nhằm hướng tới cùng một mục tiêu thống nhất là trích lọc ra được các tri thức từ dữ liệu trong các CSDL khổng lồ.
Tính phong phú và đa dạng đó đã dẫn đến một thực trạng là tồn tại một số quan niệm khác nhau về lĩnh vực nghiên cứu gần gũi nhất với lĩnh vực này - KDD. Với những gì đã trình bày ở trên, chúng ta có thể hiểu một cách sơ lược rằng KPDL là quá trình tìm kiếm những thông tin (tri thức) hữu ích, tiềm ẩn và mang tính dự báo trong các tập dữ liệu lớn. Như vậy, chúng ta nên gọi quá trình này là phát hiện tri thức. Tuy nhiên các nhà khoa học trong lĩnh vực này đồng ý với nhau rằng hai thuật ngữ trên là tương đương và có thể thay thế cho nhau.
Họ lý giải rằng, mục đích chính của quá trình phát hiện tri thức là thông tin và tri thức có ích, nhưng đối tượng mà chúng ta phải xử lý rất nhiều trong suốt quá trình đó lại chính là dữ liệu. Mặt khác, khi chia các bước trong quá trình khám phá tri thức, một số nhà nghiên cứu lại cho rằng, KPDL chỉ là một bước trong quá trình khám phá tri thức. Như vậy, khi xét ở mức tổng quan thì hai thuật ngữ này là tương đương nhau, nhưng khi xét cụ thể thì KPDL được xem là một bước trong quá trình khám phá tri thức [3]. Phát hiện tri thức trong CSDL (đôi khi còn được gọi là KPDL) là một quá trình không tầm thường nhận ra những mẫu có giá trị, mới, hữu ích tiềm năng và hiểu được trong dữ liệu [15].
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 13 Là lĩnh vực nghiên cứu và triển khai được phát triển nhanh chóng và rộng lớn, lại được rất nhiều nhóm nghiên cứu tại nhiều địa điểm khác nhau trên thế giới đồng thời quan tâm, cho nên tồn tại rất nhiều cách tiếp cận khác nhau đối với lĩnh vực KDD. Vì lý do đó mà trong nhiều tài liệu, các nhà khoa học trên thế giới đã sử dụng nhiều thuật ngữ khác nhau mà chúng được coi là mang cùng nghĩa với KDD như chiết lọc tri thức (knowledge extraction), phát hiện thông tin (information discovery), thu hoạch thông tin (information harvesting), khai quật dữ liệu (data archaeology) và xử lý mẫu dữ liệu (data pattern processing) Khái niệm 1. Khai phá dữ liệu là một bước trong quá trình phát hiện tri thức trong CSDL, thi hành một thuật toán KPDL để tìm ra các mẫu từ dữ liệu theo khuôn dạng thích hợp [15]. Ngoài ra, theo B.
Các bước chính của quá trình phát hiện tri thức trong CSDL Toàn bộ quá trình KDD thường được chia thành các bước sau đây [3]. 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, data repositories) ban đầu theo một số tiêu chí nhất định. Tiền xử lý dữ liệu (data preprocessing): đây là giai đoạn làm sạch dữ liệu và cấu hình lại, ở đây một số kỹ thuật được áp dụng để đối phó với LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 14 tính không đầy đủ, nhiễu, và không phù hợp của dữ liệu. Bước này cũng cố gắng để giảm dữ liệu bằng cách sử dụng chức năng tổng hợp và nhóm, các phương pháp nén dữ liệu, histograms, lấy mẫu, v.
Ngoài ra, các kỹ thuật rời rạc hoá dữ liệu (Bining, rời rạc hóa dựa vào histograms, dựa vào entropy, dựa vào phân khoảng, .v) có thể được sử dụng để làm giảm số lượng các giá trị cho một thuộc tính liên tục. Sau bước này, dữ liệu được làm sạch , hoàn chỉnh, thống nhất. Quá trình phát hiện tri thức trong CSDL 3. Biến đổi dữ liệu (data transformation): trong bước này, dữ liệu được chuyển dạng hoặc hợp nhất thành dạng thích hợp cho KPDL.
Biến đổi dữ liệu có thể liên quan đến việc làm mịn và chuẩn hóa dữ liệu. Sau bước này, dữ liệu đã sẵn sàng cho bước KPDL. Khai phá dữ liệu (data mining): đây được xem là bước quan trọng nhất trong quá trình KDD. Nó áp dụng một số kỹ thuật KPDL (chủ yếu là từ học máy và các lĩnh vực khác) để khai phá, trích chọn được những mẫu (patterns) thông tin, những mối liên hệ (relationships) đặc biệt trong dữ liệu.
Biểu diễn và đánh giá tri thức (knowledge representation & evaluation): những mẫu thông tin và mối liên hệ trong dữ liệu đã được khai phá ở bước trên được chuyển dạng và biểu diễn ở một 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. LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Kiến trúc một hệ thống khai phá dữ liệu Kiến trúc điển hình của một hệ KPDL được trình bày trong hình 1.