Tài liệu Phương pháp luật kết hợp và ứng dụng

-1- MỞ ĐẦU Trong những năm gần đây, sự phát triển mạnh mẽ của công nghệ thông tin đã làm cho khả năng thu thập và lưu trữ thông tin của các hệ thống thông tin tăng nhanh một cách nhanh chóng. Bên cạnh đó, việc tin học hóa một cách ồ ạt và nhanh chóng các hoạt động sản xuất, kinh doanh cũng như nhiều lĩnh vực hoạt động khác đã tạo ra cho chúng ta một lượng dữ liệu cần lưu trữ khổng lồ. Hàng triệu cơ sở dữ liệu đã được sử dụng trong các hoạt động sản xuất, kinh doanh, quản lý..., trong đó có nhiều cơ sở dữ liệu cực lớn cỡ Gigabyte, thậm chí là Terabyte. 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. Từ đó, các kỹ thuật khai phá dữ liệu đã trở thành một lĩnh vực thời sự của nền CNTT thế giới hiện nay nói chung và Việt Nam nói riêng. Khai phá dữ liệu đang được áp dụng một cách rộng rãi trong nhiều lĩnh vực kinh doanh và đời sống khác nhau: Marketing, tài chính, ngân hàng và bảo hiểm, giáo dục, y tế, an ninh, internet… Rất nhiều tổ chức và công ty lớn trên thế giới đã áp dụng kỹ thuật khai phá dữ liệu vào các hoạt động sản xuất kinh doanh của mình và thu được những lợi ích to lớn. Khai phá luật kết hợp là một kỹ thuật quan trọng của KPDL được đề xuất vào năm 1993 và phát triển mạnh mẽ trong những năm gần đây. Những nghiên cứu về luật kết hợp gần đây tập trung xây dựng các thuật toán khai phá luật kết hợp mới, hiệu quả hoặc cải tiến, phát triển các thuật toán hiệu quả hơn từ các thuật toán đã có. Mục đích nghiên cứu của đề tài là tìm hiểu về các kỹ thuật khai phá dữ liệu; các vấn đề liên quan đến khai phá luật kết hợp nhằm 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 và áp dụng chúng vào bài toán hỗ trợ tư vấn học tập tại Trường Cao đẳng Công nghiệp Cao su cho đề tài của mình. -2- Mục tiêu nghiên cứu của đề tài: - Tổng kết các kiến thức cơ bản nhất liên quan đến phát hiện luật kết hợp và tìm kiếm tri thức từ dữ liệu. - Dựa trên lý thuyết đã tổng kết được, đi sâu vào tìm hiểu, nghiên cứu phương pháp luật kết hợp và thử nghiệm chương trình dựa trên thuật toán Apriori. Ý nghĩa khoa học của đề tài: - Đây là phương pháp được nhiều nhà khoa học nghiên cứu và đã có nhiều đóng góp trong thực tiễn. - Có thể coi đề tài là một tài liệu tham khảo khá đầy đủ, rõ ràng về các kiến thức cơ bản trong phương pháp phát hiện luật kết hợp. Phạm vi nghiên cứu: Các kiến thức cơ bản nhất về phương pháp phát hiện luật kết hợp trên cơ sở làm luận văn thạc sỹ. Các kết quả nghiên cứu đạt được: - Tổng kết các kiến thức cơ bản nhất của phương pháp khai phá luật kết hợp. - Luận văn có thể trở thành một tài liệu tham khảo cho những người muốn tìm hiểu về khai phá dữ liệu và phương pháp khai phá luật kết hợp. - Kết quả thử nghiệm dựa trên thuật toán Apriori. Luận văn bao gồm 4 chương, với các nội dung: Chương 1: Trình bày cơ sở lý thuyết về khai phá dữ liệu. Chương 2: Trình bày về luật kết hợp, trong đó trình bày về các khái niệm, định nghĩa, tính chất của luật kết hợp. Chương 3: Trình bày một số kỹ thuật khai thác luật kết hợp. Chương 4: Sử dụng phần mềm WEKA tìm luật kết hợp, viết chương trình demo hỗ trợ tư vấn học tập tại Trường Cao đẳng Công nghiệp Cao Su. -3- CHƯƠNG 1: CƠ SỞ LÝ THUYẾT VỀ KHAI PHÁ DỮ LIỆU 1.1. Khai phá dữ liệu: 1.1.1. Mục tiêu của khai phá dữ liệu: - Theo J. Han va M. Kamber [10], 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. - 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, CDROM, băng từ, v..v). Sự tích lũy dữ liệu này xảy ra với một tốc độ bung 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 [5]. Theo Fayyad, Piatetsky-Shapiro, Smyth [8], việc nghiên cứu phát triển lĩnh vực KPDL và KDD (Knowledge Discovery in Databases) 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 [9] đã 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 hàng trăm TB, IBM Web Fountain với hơn 160 TB, Internet Archive xấp xỉ 300 TB, ... 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 -4- 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 [3]. 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 (những năm giữa 1980 đến nay) - Mô hình dữ liệu mở rộng: Quan hệ mở rộng, quan hệ - đối tượng, suy luận - Ứng dụng mở rộng: Không gian, thời gian, đa phương tiện, tích cực, khoa học, cơ sở tri thức Kho dữ liệu và khai phá dữ liệu (những năm cuối 1980 đến nay) - Kho dữ liệu và OLAP - Khai phá dữ liệu và phát hiện tri thức: Phân lớp, phân cụm, kết hợp, phân tích mẫu, phân tích ngoại lai … - Ứng dụng KPDL mở rộng: Khai phá dữ liệu dòng, khai phá text, khai phá web… Hệ CSDL dựa trên Web (những năm 1990 đến nay) - Hệ CSDL dựa trên XML - Sự tích hợp với sự phục hồi thông tin - Dữ liệu và sự tích hợp thông tin 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.1. Sự tiến hóa công nghệ CSDL - 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 -5- 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á trinh KPDL là mô tả (description) và dự đoán (prediction) [4]. 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 tim 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. 1.1.2. Khái niệm khai phá dữ liệu: - Lĩnh vực KPDL và KDD đa 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 -6- 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 la tương đương và có thể thay thế cho nhau. Họ lý giải rằng, mục đích chính của quá trinh 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á trinh 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 [8]. Khái niệm 1.1. 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 [8]. - 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). -7- Khái niệm 1.2. 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 [8]. - Ngoài ra, theo B.Kovalerchuk và E.Vityaev [6], Friedman đã tổng hợp một số quan niệm sau đây liên quan về khái niệm "Khai phá dữ liệu": + Quá trình không tầm thường để nhận biết từ dữ liệu ra các mẫu có giá trị, mới, hữu dụng và hiểu được (Fayyad). + Quá trình trích lọc các thông tin chưa biết trước, có thể nhận thức được, có thể tác động được từ CSDL lớn và sử dụng chúng để tạo ra quyết định công tác (Zekulin) + Tập các phương pháp được dùng trong quá trình phát hiện tri thức nhằm tường minh các quan hệ và các mẫu chưa biết trước chứa trong dữ liệu (Ferruzza) + Quá trình hỗ trợ quyết định khi tìm kiếm những mẫu thông tin chưa biết và hữu ích từ CSDL lớn (Parsaye) 1.1.3. 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 [5]. 1. 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. 2. 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 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, ... 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, …) có thể được sử dụng để làm giảm số lượng các giá trị cho một -8- 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. Hình 1.2. 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 nay, dữ liệu đã sẵn sàng cho bước KPDL. 4. 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. 5. 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. -9- 1.1.4. 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.3. [10]. - Trong kiến trúc này, các nguồn dữ liệu cho các hệ thống KPDL bao gồm hoặc CSDL, hoặc Kho dữ liệu, hoặc World Wide Web, hoặc kho chứa dữ liệu kiểu bất kỳ khác, hoặc tổ hợp các kiểu đã liệt kê nói trên. Cơ sở tri thức, bao chứa các tri thức hiện có về miền ứng dụng, được sử dụng trong thành phần KPDL để làm tăng tính hiệu quả của thành phần này. Một số tham số của thuật toán KPDL tương ứng sẽ được tinh chỉnh theo tri thức miền sẵn có từ cơ sở tri thức trong hệ thống. Cơ sở tri thức còn được sử dụng trong việc đánh giá các mẫu đã khai phá được xem chúng có thực sự hấp dẫn hay không, trong đó có đối chứng với các tri thức đã có trong cơ sở tri thức. Nếu mẫu khai phá được thực sự hấp dẫn thì được bổ sung vào cơ sở tri thức để phục vụ cho hoạt động tiếp theo của hệ thống. Như vậy, nguồn tri thức bổ sung vào cơ sở tri thức ở đây không chỉ từ lập luận lôgic theo các hệ toán lôgic để có tri thức mới, không chỉ do con người hiểu biết thêm về thế giới khách quan để bổ sung vào mà còn tri thức được phát hiện một cách tự động từ nguồn dữ liệu. - KPDL là một bước chính trong quá trình phát hiện tri thức từ số lượng lớn dữ liệu đã lưu trữ trong CSDL, kho dữ liệu hoặc các nơi lưu trữ khác. Kết quả của bước này là những mẫu đáng quan tâm được đưa đến cho người dùng hoặc lưu giữ như là tri thức mới trong cơ sở tri thức. - Kiến trúc của hệ thống KPDL có thể có các thành phần chính sau [10]: - 10 - Giao diện người dùng Đánh giá mẫu khai phá được Cơ sở tri thức Thành phần khai phá dữ liệu Phục vụ CSDL/Kho dữ liệu Làm sạch, tích hợp và chọn lựa dữ liệu CSDL Kho dữ liệu World Wide Web Các kiểu kho thông tin khác Hình 1.3. Kiến trúc điển hình của hệ thống khai phá dữ liệu + CSDL, kho dữ liệu, WorldWideWeb, kho chứa dữ liệu khác: Đây là một hoặc một tập CSDL, kho dữ liệu, World Wide Web, hoặc kho chứa dữ liệu kiểu bất kỳ khác, hoặc tổ hợp các kiểu đã liệt kê nói trên. Các kỹ thuật làm sạch dữ liệu và tích hợp dữ liệu có thể được thực hiện trên dữ liệu. + Phục vụ CSDL/Kho dữ liệu: Có trách nhiệm lấy dữ liệu liên quan dựa trên yêu cầu của người KPDL. + Cơ sở tri thức: Đây là tri thức miền được sử dụng để hướng dẫn việc tìm kiếm hoặc đánh giá sự thú vị của các mẫu thú vị. Tri thức này có thể bao gồm các mức phân cấp khái niệm, được sử dụng để tổ chức các thuộc tính hoặc giá trị thuộc tính thành các cấp trừu tượng. Tri thức như độ tin cậy của người sử dụng, có thể được sử dụng để đánh giá độ thú vị của mẫu cũng có thể - 11 - được bao gồm. Các ví dụ khác của tri thức miền là các ràng buộc thú vị bổ sung hoặc ngưỡng, và siêu dữ liệu (ví dụ, mô tả dữ liệu từ nhiều nguồn không đồng nhất). + Thành phần khai phá dữ liệu: Đây là thành phần cần thiết đối với hệ thống KPDL, bao gồm một tập các chức năng như mô tả, phân tích tính kết hợp và tính tương quan, phân lớp, dự báo, phân tích cụm, phân tích ngoại lai, và phân tích sự tiến hóa. + Đánh giá mẫu: Thành phần này thường sử dụng các độ đo và tương tác với thành phần KPDL để tập trung tìm kiếm các mẫu thú vị. Nó có thể sử dụng các ngưỡng để lọc ra các mẫu phát hiện được. Ngoài ra, thành phần đánh giá mẫu có thể được tích hợp với thành phần KPDL, phụ thuộc vào các phương pháp KPDL được sử dụng. + Giao diện người dùng: Thành phần này là thành phần giao tiếp giữa người sử dụng và hệ thống KPDL, cho phép người dùng tương tác với hệ thống bằng cách xác định một truy vấn hoặc một nhiệm vụ KPDL, cung cấp thông tin để giúp tập trung tìm kiếm, thăm dò và KPDL dựa trên kết quả KPDL trung gian. Ngoài ra, thành phần này cho phép người dùng tìm các lược đồ CSDL và kho dữ liệu hoặc các cấu trúc dữ liệu, đánh giá các mẫu khai phá được, và trực quan hoá các mẫu trong các dạng khác nhau. 1.2. Hướng tiếp cận và kỹ thuật chính trong khai phá dữ liệu: 1.2.1. Hướng tiếp cận và kỹ thuật chính trong khai phá dữ liệu: - 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 KPDL. Chúng có thể được phân loại theo chức năng, các loại tri thức, loại dữ liệu được khai phá, hoặc bất cứ điều gì phù hợp tiêu chuẩn [10]. Dưới đây là một số cách tiếp cận chính. - 12 - + Phân lớp và dự báo: Phương pháp này cố gắng sắp xếp một đối tượng nhất định vào một lớp thích hợp trong số các lớp đã biết. Số lượng các lớp và tên của nó chắc chắn được biết đến. Ví dụ, chúng ta có thể phân lớp hoặc dự đoán các khu vực địa lý theo dữ liệu thời tiết và khí hậu. Phương pháp này thường sử dụng các kỹ thuật và khái niệm điển hình trong học máy như cây quyết định, k-min, mạng thần kinh nhân tạo, máy hỗ trợ vector, ... Phân lớp còn được gọi là học có giám sát. + Luật kết hợp (association rules): Là dạng luật biểu diễn tri thức ở dạng khá đơn giản. Ví dụ “80% sinh viên đăng ký học CSDL thì có tới 70% trong số họ đăng ký học phân tích thiết kế các hệ thống thông tin”. Hướng tiếp cận này được ứng dụng nhiều trong các lĩnh vực kinh doanh, tài chính, thị trường chứng khoán, y học, tin sinh học, giáo dục … + Phân cụm & phân đoạn: Phương pháp này cố gắng sắp xếp các đối tượng theo từng cụm nhưng số lượng và tên của các cụm chưa được biết trước. Phân cụm và phân đoạn được gọi là học không có giám sát. + Khai phá mẫu theo thứ tự/theo thời gian (sequential/temporal patterns mining): Cũng tương tự như KPDL bằng luật kết hợp nhưng có thêm tính thứ tự và tính thời gian. Hướng tiếp cận này được ứng dụng nhiều trong lĩnh vực tài chính và thị trường chứng khoán bởi vì chúng có tính dự báo cao. + Mô tả khái niệm (concept description & summarization): Mục tiêu chính của phương pháp này là tìm các đặc trưng và tính chất của các khái niệm. Điển hình nhất cho bài toán này là các bài toán như tổng quát hóa, tóm tắt các đặc trưng dữ liệu ràng buộc…Tóm tắt văn bản là một ví dụ điển hình. 1.2.2. Kiểu dữ liệu trong khai phá dữ liệu: Về nguyên lý chung, nguồn dữ liệu được sử dụng để tiến hành KPDL nhằm phát hiện tri thức là rất phong phú và đa dạng, trong đó điển hình nhất là CSDL quan hệ, kho dữ liệu, CSDL giao dịch, các hệ thống dữ liệu và thông tin mở rộng khác [3]. - 13 - - Cở sở dữ liệu quan hệ: Tính phổ biến của hệ thống CSDL quan hệ hiện nay tạo ra một hệ quả tự nhiên quy định CSDL quan hệ là một nguồn đầu vào điển hình nhất, được quan tâm trước hết của KPDL. Hơn nữa, một trong những mẫu được quan tâm là mẫu về các loại “quan hệ” mà với bản chất của mình, hệ thống CSDL tiềm ẩn các mẫu dạng như thế. Như đã biết trong lý thuyết CSDL, hệ thống CSDL thường bao gồm một tập các bảng (hai chiều dọc va ngang). Hệ thống CSDL quan hệ còn bao gồm một mô hình ngữ nghĩa mà thông thường là mô hình thực thể - quan hệ. - Kho dữ liệu: + Kho dữ liệu là một kết quả xuất hiện trong quá trình tiến hoá các hệ hỗ trợ quyết định. Quá trình phát hiện tri thức trong CSDL tiếp nhận đầu vào là các hệ thống CSDL, các nhà kho tổ chức dữ liệu từ các nguồn và các dữ liệu mô tả. + Các nghiên cứu và triển khai liên quan tới kho dữ liệu chỉ dẫn khuynh hướng hiện tại của các hệ thống thông tin quản lý phổ biến là nhằm vào việc thu thập, làm sạch dữ liệu giao dịch và tạo cho chúng độ linh hoạt khi tìm kiếm trực tuyến. Đồng thời với sự phát triển của công nghệ kho dữ liệu, các hệ thống tích hợp các nguồn dữ liệu cả dữ liệu trong quá khứ lẫn dữ liệu tác nghiệp đã được xây dựng. Nhiều hệ thống KPDL có đầu vào từ siêu dữ liệu cung các dữ liệu nguồn trong các kho dữ liệu. - Cơ sở dữ liệu giao dịch: Một lớp bài toán KPDL phổ biến là khai phá quan hệ kết hợp, trong đó điển hình là bài toán khai phá luật kết hợp, được xuất phát từ việc xem xét các CSDL giao dịch. Dữ liệu giao dịch chính là dữ liệu nguyên thuỷ xuất hiện trong định nghĩa về luật kết hợp cùng với các độ đo của luật như độ hỗ trợ va độ tin cậy. Khi mở rộng dữ liệu từ dữ liệu giao dịch sang dữ liệu vô hướng, hoặc dữ liệu phức tạp hơn có trong các CSDL quan hệ, các giải pháp khai phá - 14 - luật kết hợp được cải tiến để thích ứng với sự biến đổi này. Các giải pháp ứng dụng lý thuyết tập mờ và lý thuyết tập thô tương ứng với việc mở rộng miền dữ liệu cần khai phá đã được tiến hành trong nhiều công trình nghiên cứu. - Các hệ thống dữ liệu mở rộng: Trong quá trình phát triển, các phương pháp và thuật toán KPDL thích hợp đối với các CSDL mở rộng và các kiểu kho chứa dữ liệu được đề xuất. Các phương pháp và thuật toán này phù hợp với các CSDL trong CSDL hướng đối tượng, CSDL không gian - thời gian, CSDL tạm thời, dữ liệu chuỗi thời gian, CSDL Text, CSDL đa phương tiện, CSDL hỗn tạp, CSDL kế thừa và Word Wide Web. 1.2.3. Một số phương pháp khai phá dữ liệu: - Có rất nhiều các phương pháp KPDL, mỗi phương pháp có những đặc điểm riêng và phù hợp với một lớp các bài toán với các dạng dữ liệu và miền dữ liệu nhất định. Dưới đây là một số phương pháp thường được dùng [6]. + Phương pháp quy nạp + Cây quyết định và luật + Khai phá luật kết hợp + Các phương pháp phân lớp và hồi quy phi tuyến + Phân nhóm và phân đoạn + Các phương pháp dựa trên mẫu + Khai phá dữ liệu văn bản. + Mạng nơ-ron + Giải thuật di truyền. + Mô hình phụ thuộc dựa trên đồ thị xác suất. + Mô hình học quan hệ - 15 - - Các thuật toán KPDL tự động vẫn mới chỉ ở giai đoạn phát triển ban đầu. Người ta vẫn chưa đưa ra được một tiêu chuẩn nào trong việc quyết định sử dụng phương pháp nào và trong trường hợp nào thì có hiệu quả. - Hầu hết các phương pháp KPDL đều mới đối với lĩnh vực kinh doanh. Hơn nữa lại có rất nhiều kỹ thuật, mỗi kỹ thuật được sử dụng cho nhiều bài toán khác nhau. Mỗi phương pháp đều có điểm mạnh va điểm yếu của nó, nhưng hầu hết các điểm yếu đều có thể khắc phục được. Vì vậy, cần tìm cách áp dụng mỗi kỹ thuật thật đơn giản, dễ sử dụng để không cảm thấy những phức tạp vốn có của kỹ thuật đó. - Để so sánh các kỹ thuật cần phải có một tập lớn các quy tắc và các phương pháp thực nghiệm tốt. Thường thì các quy tắc này không được sử dụng khi đánh giá các kỹ thuật mới nhất. Vì vậy mà những yêu cầu cải thiện độ chính xác không phải lúc nào cũng thực hiện được. - Nhiều công ty đa đưa ra những sản phẩm sử dụng kết hợp nhiều kỹ thuật KPDL khác nhau với hy vọng nhiều kỹ thuật thì sẽ tốt hơn. Nhưng thực tế cho thấy không phải như vậy, nhiều kỹ thuật chỉ thêm nhiều rắc rối và gây nhiều khó khăn cho việc so sánh giữa các phương pháp và các sản phẩm. Theo nhiều đánh giá cho thấy khi đã hiểu được các kỹ thuật và nghiên cứu tính giống nhau giữa chúng, người ta thấy rằng nhiều kỹ thuật lúc đầu có vẻ khác nhau nhưng thực chất thì chúng lại giống nhau. Tuy nhiên đánh giá này cũng chỉ để tham khảo vì cho đến nay KPDL vẫn còn là kỹ thuật mới chứa nhiều tiềm năng mà người ta chưa khai thác hết. 1.3. Ứng dụng của khai phá dữ liệu: 1.3.1. Ưu thế của khai phá dữ liệu: KPDL thực chất không có gì mới mà hoàn toàn dựa trên các phương pháp cơ bản đã biết. Vậy KPDL có gì khác so với các phương pháp đó và tại sao KPDL lại có ưu thế hơn hẳn chúng? Các phân tích sau sẽ giải đáp những câu hỏi này [4]. - 16 - - Học máy (machine learning): + Tuy phương pháp học máy đã được cải tiến để có thể phù hợp với mục đích KPDL, nhưng sự khác biệt giữa thiết kế, các đặc điểm của CSDL đã làm nó trở nên không phù hợp với mục đích này, mặc dù đến nay phần lớn các phương pháp KPDL vẫn dựa trên nền tảng cơ sở của phương pháp học máy. + Trong các hệ quản trị CSDL, một CSDL là một tập hợp dữ liệu được tích hợp một cách logic, được lưu trong một hay nhiều tệp, và được tổ chức để lưu trữ, sửa đổi và lấy thông tin một cách hiệu quả và dễ dang. Trong học máy, thuật ngữ CSDL chủ yếu đề cập tới một tập các mẫu (instance hay example) được lưu trong một tệp. Các mẫu thường là các vector thuộc tính có độ dài cố định, thông tin về tên thuộc tính và dãy giá trị của chúng đôi khi cũng được lưu lại như trong từ điển dữ liệu. Một thuật toán học còn sử dụng tập dữ liệu và các thông tin kèm theo tập dữ liệu đó làm đầu vào và đầu ra biểu thị kết quả của việc học. + Với so sánh CSDL thông thường và CSDL trong học máy như trên, có thể thấy là học máy có khả năng áp dụng cho CSDL, bởi vì không phải học trên tập các mẫu mà học trên tệp các bản ghi của CSDL. Tuy nhien KDD làm tăng thêm các khó khăn vốn đã là điển hình trong học máy và đã vượt quá khả năng của học máy. Trong thực tế CSDL thường động, không đầy đủ, bị nhiễu và lớn hơn nhiều so với các tập dữ liệu học máy điển hình. Các yếu tố này làm cho hầu hết các thuật toán học máy trở nên không hiệu quả trong hầu hết các trường hợp. Vì vậy trong KPDL cần tập trung rất nhiều công sức vào việc vượt qua những vấn đề này trong CSDL. - Phương pháp hệ chuyên gia: Các hệ chuyên gia cố gắng nắm bắt các tri thức thích hợp với một bài toán nào đó. Các kỹ thuật thu thập giúp cho việc lấy tri thức từ chuyên gia con người. Mỗi phương pháp đó là một cách suy diễn các luật từ các ví dụ và giải pháp đối với bài toán chuyên gia đưa ra. Phương pháp này khác với KPDL ở - 17 - chỗ các ví dụ của chuyên gia thường ở mức chất lượng cao hơn rất nhiều so với các dữ liệu trong CSDL và chúng thường chỉ bao quát được các trường hợp quan trọng. Hơn nữa, các chuyên gia sẽ xác nhận tính có giá trị và hữu dụng của các mẫu phát hiện được. Cũng như với các công cụ quản trị CSDL, ở phương pháp này đòi hỏi có sự tham gia của con người trong việc phát hiện tri thức. - Phát kiến khoa học: KPDL rất khác với phát kiến khoa học ở chỗ những khai phá trong CSDL ít có chủ tâm và có điều khiển hơn. Các dữ liệu khoa học có từ thực nghiệm nhằm loại bỏ một số tác động của các tham số để nhấn mạnh độ biến thiên của một hay một số tham số đích. Tuy nhiên, các CSDL thương mại thường ghi lại một số lượng thừa thông tin về các dự án của họ để đạt được một số mục đích về mặt tổ chức. Sự dư thừa này có thể là hiển hiện hay ẩn chứa trong các mối quan hệ dữ liệu. Hơn nữa các nhà khoa học có thể tạo lại các thí nghiệm và có thể tìm ra rằng các thiết kế ban đầu không thích hợp. Trong khi đó các nhà quản lý CSDL hầu như không thể xa xỉ đi thiết kế lại các trường dữ liệu và thu thập lại dữ liệu. - Phương pháp thống kê: + Mặc dù các phương pháp thông kê cung cấp một nền tảng lý thuyết vững chắc cho các bài toán phân tích dữ liệu nhưng chỉ có tiếp cận thống kê thuần tuý thôi thì chưa đủ. Thứ nhất, các phương pháp thống kê chuẩn không phù hợp đối với các kiểu dữ liệu có cấu trúc trong rất nhiều CSDL. Thứ hai, các phương pháp thống kê hoàn toàn bị dữ liệu điều khiển, nó không sử dụng tri thức sẵn có về lĩnh vực. Thứ ba, các kết quả của phân tích thống kê có thể sẽ rất nhiều và khó có thể làm rõ được. Cuối cùng các phương pháp thống kê cần có sự hướng dẫn của người dùng để xác định phân tích dữ liệu như thế nào và ở đâu. - 18 - + Sự khác nhau cơ bản giữa KPDL và thống kê là ở chỗ KPDL là một phương tiện được dùng bởi người dùng cuối chứ không phải là các nhà thống kê. KPDL tự động hoá quá trình thống kê một cách hiệu quả, vì vậy làm nhẹ bớt công việc của người dùng cuối, tạo ra một công cụ dễ sử dụng hơn. Như vậy, nhờ có KPDL, việc dự đoán và kiểm tra rất vất vả trước đây có thể được đưa lên máy tính, được tính, dự đoán và kiểm tra một cách tự động. 1.3.2. Ứng dụng của KPDL: Mặc dù KPDL là một xu hướng nghiên cứu tương đối mới, nhưng thu hút nhiều nhà nghiên cứu bởi vì các ứng dụng thực tế của nó trong nhiều lĩnh vực. Sau đây là một số ứng dụng tiêu biểu: - Phân tích dữ liệu và hỗ trợ ra quyết định: Ứng dụng này là phổ biến trong thương mại, tài chính và thị trường chứng khoán, … - Y tế: Tìm kiếm sự liên quan tiềm năng giữa các triệu chứng, chẩn đoán, và phương pháp điều trị (dinh dưỡng, toa thuốc, bác sĩ phẫu thuật, …). - Khai phá text và web: Tóm tắt tài liệu, khôi phục văn bản và tìm kiếm văn bản, phân lớp văn bản và siêu văn bản. - Tin sinh học: Tìm kiếm và so sánh thông tin di truyền điển hình hoặc đặc biệt như bộ gen và DNA, các mối quan hệ ngầm giữa một số gen và một số bệnh di truyền, …. - Tài chính và thị trường chứng khoán: Kiểm tra dữ liệu để trích xuất thông tin dự đoán cho giá của các loại cổ phiếu. - Những ứng dụng khác (Viễn thông, bảo hiểm y tế, thiên văn học, chống khủng bố, thể thao, …). 1.3.3. Phân loại các hệ thống khai phá dữ liệu: KPDL là một công nghệ tri thức liên quan đến nhiều lĩnh vực nghiên cứu khác như CSDL, học máy, trí tuệ nhân tạo, trực quan hoá dữ liệu và tri thức, … Chúng ta có thể phân loại các hệ thống KPDL theo các tiêu chí khác nhau như sau: - 19 - - Phân loại dựa trên loại dữ liệu được khai phá: Các hệ thống KPDL làm việc với CSDL quan hệ, kho dữ liệu , CSDL giao dịch, CSDL hướng đối tượng, CSDL không gian và thời gian, CSDL đa phương tiện, CSDL văn bản và web, … - Phân loại dựa trên loại tri thức khai phá được: Các hệ thống KPDL có thể phân loại dựa theo loại tri thức mà chúng khai phá được, nghĩa là dựa vào các chức năng khai phá như mô tả, tóm tắt, luật kết hợp, phân lớp, dự báo, phân cụm, … - Phân loại dựa trên loại kỹ thuật được sử dụng: Các công cụ KPDL như các hệ thống xử lý phân tích trực tuyến (OLAP), sử dụng kỹ thuật học máy (cây quyết định, mạng nơron nhân tạo, k-min, thuật toán gen, máy hỗ trợ vector, tập thô, tập mờ, ...), trực quan hoá dữ liệu, … - Phân loại dựa trên các lĩnh vực hệ thống KPDL được ứng dụng: Các hệ thống KPDL được sử dụng trong các lĩnh vực khác nhau như: Thương mại (ngành công nghiệp bán lẻ), viễn thông, tin sinh học, điều trị y tế, tài chính và thị trường chứng khoán, bảo hiểm y tế, … 1.3.4. Xu hướng trong khai phá dữ liệu: Sự đa dạng của dữ liệu, các nhiệm vụ KPDL, và các cách tiếp cận KPDL đặt ra nhiều thách thức trong vấn đề nghiên cứu KPDL. Sự phát triển của các hệ thống và phương pháp KPDL hiệu quả, việc xây dựng các môi trường KPDL tương tác và tích hợp, việc thiết kế các ngôn ngữ KPDL, và việc ứng dụng các kỹ thuật KPDL để giải quyết các vấn đề ứng dụng lớn là nhiệm vụ quan trọng đối với các nhà nghiên cứu KPDL, hệ thống KPDL và các nhà phát triển ứng dụng. Phần này đề cập đến một số vấn đề đang thu hút sự chú ý của các nhà nghiên cứu KPDL. - OLAM (khai phá phân tích trực tuyến) - một sự kết hợp của CSDL, kho dữ liệu, và khai phá dữ liệu. Ngày nay, các hệ quản trị CSDL như Oracle, MS SQL Server, IBM DB2 có tích hợp chức năng OLAP và kho dữ liệu để tạo - 20 - điều kiện cho người sử dụng trong việc khôi phục và phân tích dữ liệu. Các nhà nghiên cứu trong lĩnh vực này hy vọng sẽ vượt qua được những giới hạn hiện tại bằng cách phát triển hệ thống OLAM đa mục đích để hỗ trợ dữ liệu giao dịch cho hoạt động kinh doanh hàng ngày cũng như các phân tích dữ liệu cho việc ra quyết định [10]. - Các hệ thống khai thác dữ liệu có thể khai phá các loại khác nhau của tri thức từ loại dữ liệu khác nhau [6] [10]. - Làm thế nào để tăng cường hiệu suất, độ chính xác, khả năng mở rộng, và tích hợp của các hệ thống khai thác dữ liệu? Làm thế nào để giảm độ phức tạp tính toán? Làm thế nào để cải thiện khả năng xử lý dữ liệu không đầy đủ, không phù hợp, và nhiễu? Ba câu hỏi trên vẫn còn cần được tập trung trong tương lai [10]. - Tận dụng tri thức nền hoặc tri thức từ những người dùng (các chuyên gia hoặc chuyên viên) để nâng cấp hiệu suất của các hệ thống khai thác dữ liệu [6]. - Khai thác dữ liệu song song và phân tán là một xu hướng nghiên cứu thú vị bởi vì nó sử dụng các hệ thống tính toán mạnh mẽ để giảm thời gian phản ứng. Đây là điều cần thiết bởi vì ngày càng cần nhiều các ứng dụng thời gian thực trong thế giới cạnh tranh ngày nay [7]. - Ngôn ngữ truy vấn khai thác dữ liệu (DMQL): Các nhà nghiên cứu trong lĩnh vực này cố gắng thiết kế một ngôn ngữ truy vấn chuẩn cho khai thác dữ liệu. Ngôn ngữ này sẽ được sử dụng trong các hệ thống OLAM như SQL được sử dụng rộng rải trong CSDL quan hệ [10]. - Trực quan hoá và trình diễn tri thức cũng được xem xét để thể hiện tri thức trong các dạng mà con người dễ sử dụng và có thể đọc được. Tri thức có thể được biểu diễn trong các biểu thức trực quan hơn do cấu trúc dữ liệu đa chiều hoặc đa mức.