Đăng ký Đăng nhập
Trang chủ Hoàn thiện bộ nhớ tri thức của hệ chuyên gia dựa vào khai phá luật kết hợp...

Tài liệu Hoàn thiện bộ nhớ tri thức của hệ chuyên gia dựa vào khai phá luật kết hợp

.PDF
63
315
132

Mô tả:

LỜI CẢM ƠN Trước tiên tôi xin gửi lời cảm ơn đến thầy PGS, TS, NCNC Lê Huy Thập đã định hướng và nhiệt tình hướng dẫn, giúp đỡ tôi rất nhiều về mặt chuyên môn trong quá trình làm luận văn. Tôi xin gửi lời cảm ơn đến các thầy, các cô đã dạy dỗ và truyền đạt những kinh nghiệm quý báu cho chúng tôi trong suốt hai năm học cao học tại trường Đại học sư phạm Hà Nội 2. Tôi xin cảm ơn bạn bè, đồng nghiệp và gia đình, những người luôn gần gũi, động viên, chia sẻ cùng tôi trong suốt thời gian làm luận văn tốt nghiệp. Hà Nội, ngày 06 tháng 12 năm 2013 Học viên Nguyễn Thị Duyên LỜI CAM ĐOAN Tôi xin cam đoan thông tin trích dẫn trong luận văn đã được chỉ rõ nguồn gốc. Hà Nội, ngày 06 tháng 12 năm 2013 Học viên Nguyễn Thị Duyên DANH MỤC CÁC TỪ VIẾT TẮT CSDL : Cơ sở dữ liệu HCG : Hệ chuyên gia KPDL : Khai phá dữ liệu DANH SÁCH HÌNH VẼ Hình 1.1. Quá trình phát hiện tri thức từ CSDL .............................................. 9 Hình 1.2. Sơ đồ quá trình Khai phá dữ liệu bằng mạng ................................ 16 Hình 1.3. Mẫu kết quả với kỹ thuật mạng neuron ......................................... 16 Hình 2.1. Phạm vi của giá trị CF .................................................................. 41 Hình 2.2. Liên kết thực thể ........................................................................... 44 Hình 2.3. Liên kết thực thể .......................................................................... 46 Hình 3.1. Giao diện chính của Demo ............................................................ 52 Hinh 3.2. Giao diện khi cập nhật thông tin bảng quan hệ.............................. 53 Hình 3.3. Kết quả sau quá trình khai phá luật kết hợp .................................. 53 Hình 3.4. Tập luật mới được sinh ra ............................................................. 54 Hình 3.5. Mô tả tập luật cần được chuyên gia đánh giá lại ........................... 54 DANH SÁCH BẢNG BIỂU Bảng 1.1. Các loại vấn đề do HCG giải .......................................................... 4 Bảng 2.1. Các mặt hàng và nhãn .................................................................. 35 Bảng 2.2. Các giao dịch................................................................................ 36 Bảng 2.3. C1 ................................................................................................. 36 Bảng 2.4. F1.................................................................................................. 36 Bảng 2.5. C2 ................................................................................................. 36 Bảng 2.6. C2 ................................................................................................. 36 Bảng 2.7. C2 ................................................................................................. 37 Bảng 2.8. F2.................................................................................................. 37 Bảng 2.9. C3 ................................................................................................. 37 Bảng 2.10. C3 ............................................................................................... 37 Bảng 3.1. Mô tả tập các sự kiện được sử dụng trong Demo .......................... 50 Bảng 3.2. Tập luật trong bộ nhớ tri thức ....................................................... 50 MỤC LỤC MỞ ĐẦU ....................................................................................................... 1 1. Lí do chọn đề tài ......................................................................................... 1 2. Mục đích nghiên cứu (Các kết quả cần đạt được) ....................................... 1 3. Nhiệm vụ nghiên cứu ............................................................................... 1 4. Đối tượng và phạm vi nghiên cứu .............................................................. 1 5. Phương pháp nghiên cứu ............................................................................ 1 6. Giả thiết khoa học ...................................................................................... 2 7. Nội dung .................................................................................................... 2 8. Kết luận ...................................................................................................... 2 CHƢƠNG 1: TỔNG QUAN ........................................................................ 3 1.1. Hệ chuyên gia .......................................................................................... 3 1.1.1. Khái niệm Hệ chuyên gia ............................................................ 3 1.1.2. Các lĩnh vực ứng dụng của Hệ chuyên gia ................................. 3 1.1.3. Các đặc tính của Hệ chuyên gia ................................................. 4 1.2. Khai phá dữ liệu ...................................................................................... 7 1.2.1. Tổ chức và Khai phá dữ liệu truyền thống .................................. 7 1.2.2. Bước phát triển tiếp theo của việc tổ chức và khai thác các cơ sở dữ liệu ............................................................................................................ 7 1.2.3. Khai phá dữ liệu và quá trình phát hiện tri thức ......................... 8 1.2.4. Các dạng cơ sở dữ liệu có thể khai thác ................................... 10 1.2.5. Các thành phần của giải thuật Khai phá dữ liệu ....................... 11 1.2.6. Một số phương pháp Khai phá dữ liệu phổ biến ....................... 11 1.2.7. Ứng dụng của KPDL ................................................................ 18 1.2.8. Khai phá luật kết hợp và ứng dụng ........................................... 20 1.3. Kết luận ................................................................................................. 20 CHƢƠNG 2. KHAI PHÁ LUẬT KẾT HỢP TRONG BỘ NHỚ TRI THỨC CỦA HỆ CHUYÊN GIA ............................................................... 22 2.1. Bộ nhớ tri thức của hệ chuyên gia ......................................................... 22 2.1.1. Bộ nhớ tri thức ........................................................................ 22 2.1.2. Cách biểu diễn các luật trong nhớ tri thức .............................. 22 2.2. Phương pháp tìm luật kết hợp trong Khai phá dữ liệu ............................ 24 2.2.1. Luật kết hợp .............................................................................. 25 2.2.2. Một số tính chất liên quan đến các hạng mục phổ biến ............. 27 2.2.3. Bài toán khai phá luật kết hợp ................................................. 28 2.2.4. Một số hướng tiếp cận trong KPLKH ....................................... 29 2.2.5. Thuật toán Apriori để xác định các tập phổ biến và xây dựng luật kết hợp ......................................................................................................... 31 2.3. Các phương pháp suy luận trong hệ chuyên gia ..................................... 37 2.3.1. Suy luận Bayes ......................................................................... 38 2.3.2. Suy luận không chắc chắn trong hệ chuyên gia ....................... 39 2.4.3. Đề xuất hoàn thiện bộ nhớ tri thức ........................................... 42 2.4. Hoàn thiện bộ nhớ tri thức dựa vào khai phá luật kết hợp .................... 42 2.4.1. Dạng quan hệ khi thể hiện bằng O-A-V .................................... 44 2.4.2. Dạng quan hệ khi thể hiện bằng luật ........................................ 46 2.5. Kết luận và hướng phát triển ................................................................ 49 CHƢƠNG 3: ỨNG DỤNG BỔ SUNG LUẬT TRONG BỘ NHỚ TRI THỨC ......................................................................................................... 50 3.1. Lập trình ứng dụng đề tài tại siêu thị Điện máy ..................................... 50 3.1.1. Dữ liệu ..................................................................................... 50 3.1.2. Các công cụ phát triển Demo .................................................. 51 3.2. Các giao diện và kết quả của chương trình ứng dụng ............................. 52 KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN ................................................. 55 TÀI LIỆU THAM KHẢO.......................................................................... 56 1 MỞ ĐẦU 1. Lí do chọn đề tài Bộ nhớ tri thức của HCG là các luật, các sự kiện và các phương pháp suy luận,…Tuy nhiên mức độ đầy đủ luật và khả tín đến đâu thường là tùy thuộc vào nhiều yếu tố như: để tìm ra các luật kết hợp trong khai phá dữ liệu, cơ bản dựa vào độ hỗ trợ Sup (Suport) và độ tin cậy Conf (Confidence), nhưng những tham số này phải được xác định qua kinh nghiệm hay qua phương pháp chuyên gia. Dù bằng cách nào thì độ khả tín của các luật cũng ở mức độ tham khảo nào đó. Để tăng độ tin cậy vào các luật đã tìm được chúng ta có thể dùng phương pháp hỗ trợ thêm của hệ chuyên gia. Từng chuyên đề trên thì thế giới và Việt Nam đã có sự quan tâm nghiên cứu, nhưng sự kết hợp giữa hai chuyên đề theo cách nêu ra trên thì chưa. Chúng ta sẽ dùng phương pháp bổ sung nhân tố chắc chắn CF cho cả các sự kiện, luật,… để chỉ ra độ khả tín cho các luật kết hợp đã nhận được bằng phương pháp khai phá luật kết hợp. 2. Mục đích nghiên cứu (Các kết quả cần đạt đƣợc) Dùng suy luận không chắc chắn để hỗ trợ khai phá luật kết hợp. Ứng dụng đề tài tại siêu thị điện máy. 3. Nhiệm vụ nghiên cứu Nghiên cứu khai phá dữ liệu trên CSDL các luật trong bộ nhớ tri thức. Từ đó bổ sung các luật chưa có. 4. Đối tƣợng và phạm vi nghiên cứu Khai phá dữ liệu. Hệ chuyên gia. 5. Phƣơng pháp nghiên cứu Phương pháp tìm luật kết hợp trong khai phá dữ liệu. Các phương pháp suy luận trong HCG. 2 6. Giả thiết khoa học Dùng HCG, Trí tuệ nhân tạo,… để hỗ trợ khi nâng cao và mở rộng đề tài. 7. Nội dung Luận văn được trình bày gồm 3 chương: Chương 1. Tổng quan 1.1. Hệ chuyên gia 1.2. Khai phá dữ liệu 1.3. Kết luận Chương 2. Khai phá luật kết hợp trong bộ nhớ tri thức của hệ chuyên gia 2.1. Bộ nhớ tri thức của hệ chuyên gia 2.2. Phương pháp tìm luật kết hợp trong khai phá dữ liệu 2.3. Các phương pháp suy luận trong Hệ chuyên gia 2.4. Hoàn thiện bộ nhớ tri thức dựa vào khai phá luật kết hợp 2.5. Kết luận và hướng phát triển Chương 3. Ứng dụng bổ sung luật trong bộ nhớ tri thức 3.1. Lập trình ứng dụng đề tài tại siêu thị Điện máy 3.2. Các giao diện và kết quả của chương trình ứng dụng 8. Kết luận  Luận văn “Hoàn thiện bộ nhớ tri thức của hệ chuyên gia dựa vào khai phá luật kết hợp”.  Demo chương trình ứng dụng.  Dùng HCG, Trí tuệ nhân tạo,… để hỗ trợ khi nâng cao và mở rộng đề tài. 3 CHƢƠNG 1: TỔNG QUAN 1.1. Hệ chuyên gia 1.1.1. Khái niệm Hệ chuyên gia Chuyên gia lĩnh vực: Là một người hoặc một nhóm người có kiến thức sâu về chuyên ngành và có kĩ năng giải các vấn đề (về chuyên ngành đó) một cách có hiệu quả. Hệ chuyên gia (HCG): Là một hệ thống phần mềm dựa trên tri thức, nó mô hình hóa các tri thức của chuyên gia, nhóm chuyên gia và dùng tri thức này để giải quyết vấn đề phức tạp thuộc lĩnh vực đó. Hay Hệ chuyên gia là một hệ thống bao gồm máy tính và chương trình được dùng để mô phỏng và bắt chước cách giải vấn đề của chuyên gia. Các khối cơ bản của HCG: Một HCG bao gồm hai khối cơ bản. i. Khối tri thức cơ sở, dùng để lưu các tri thức bao gồm các sự kiện, các quan hệ và các luật,…. ii. Khối suy luận hay mô tơ suy luận là bộ xử lí được mô hình hóa theo cách lập luận và xử lý của HCG. Mô tơ nhận thông tin về sự kiện, so sánh chúng với các kiến thức đã có trong khối tri thức cơ sở rồi rút ra kết luận hay bình luận. Như vậy mô tơ cần có kĩ thuật về suy luận. 1.1.2. Các lĩnh vực ứng dụng của Hệ chuyên gia Tính đến thời điểm này, hàng trăm HCG đã được xây dựng và công bố thường xuyên trong các tạp chí, sách báo và hội thảo khoa học. Ngoài ra còn các HCG được sử dụng trong các công ty, các tổ chức quân sự mà không được công bố vì lí do bảo mật. 4 Dưới đây là một số lĩnh vực ứng dụng diện rộng của các HCG : Lĩnh vực Ứng dụng diện rộng Chuẩn đoán Lập luận dựa trên những chứng cứ quan sát được. Truyền đạt Dạy học kiểu thông minh sao cho sinh viên có thể hỏi và được trả lời. Giải thích Giải thích những dữ liệu thu nhận được. Kiểm tra So sánh dữ liệu thu lượm được với chuyên môn để đánh giá hiệu quả. Lập kế hoạch Lập kế hoạch sản xuất theo yêu cầu. Dự đoán Dự đoán hậu quả từ một tình huống xảy ra. Chữa trị Chỉ định cách thụ lý một vấn đề. Điều khiển Điều khiển một quá trình, đòi hỏi diễn giải, chẩn đoán, kiểm tra, lập kế hoạch, dự đoán và chữa trị. Bảng 1.1. Các loại vấn đề do HCG giải 1.1.3. Các đặc tính của Hệ chuyên gia 1.1.3.1. Tri thức và các lập luận a) Cơ sở tri thức Cơ sở tri thức của chuyên gia lĩnh vực là các kiến thức sẵn có (hay kinh nghiệm giải quyết vấn đề) được dùng để giải quyết vấn đề đã cho thuộc lĩnh vực đó. Cơ sở tri thức của HCG là bộ nhớ tri thức lĩnh vực. b) Phương tiện giải thích Bộ nhớ làm việc trong HCG chứa các sự kiện (cùng với kết luận nếu có) liên quan đến vấn đề cần quan tâm. Nó giống như bộ nhớ làm việc trong mô hình giải quyết vấn đề của HCG. Bộ nhớ làm việc là một bộ phận trong HCG, nó chứa các sự kiện, các lập luận đã có để suy luận ra quyết định vấn đề đang xem xét. 5 Cách trao đổi với HCG: - Người sử dụng HCG nhập sự kiện cần thiết vào trong HCG thông qua giao diện sử dụng. - Hệ thống so sánh các sự kiện đã nhập vào ở bộ nhớ làm việc với các tri thức trong bộ nhớ tri thức để suy luận ra sự kiện mới. Hệ thống lại nhập sự kiện mới này vào bộ nhớ làm việc để tiếp tục suy luận và quá trình sẽ được lặp lại. Như vậy bộ nhớ làm việc chứa các thông tin do người sử dụng đưa vào hoặc do hệ thống suy luận ra, các thông tin này được gọi là thông tin ngữ cảnh. Định nghĩa hệ thống dựa trên tri thức: Là hệ thống phần mềm, trong đó các tri thức vấn đề được lưu trữ trong cơ sở tri thức, sau đó được xử lí và đánh giá nhờ bộ phận giải vấn đề. c) Mô tơ suy luận HCG mô hình hóa quá trình lập luận của chuyên gia trong khối motor suy luận hay motor suy diễn. Định nghĩa motor suy luận: Motor suy luận là một bộ phận trong HCG cho phép so sánh các sự kiện trong bộ nhớ làm việc với các tri thức về lĩnh vực trong bộ nhớ tri thức, để rút ra kết luận vấn đề đang được xem xét. Motor suy luận dựa vào các sự kiện trong bộ nhớ làm việc và tri thức về lĩnh vực trong cơ sở tri thức, để rút ra sự kiện mới hoặc một quyết định. Như vậy motor suy luận cần tìm ra các luật rồi so sánh phần giả thiết của luật với các sự kiện trong bộ nhớ làm việc từ đó đưa ra quyết định chính là phần kết luận của luật. Khi phát hiện thấy so sánh khớp, kết luận của luật sẽ là thông tin mới. d) Khối giải thích Khối này lưu các khả năng giải thích các suy luận của nó. Thông qua khối giải thích, HCG giải thích cho người sử dụng hiểu tại sao nó đặt câu hỏi, và cách suy luận để đi đến kết luận mà nó đưa ra. 6 e) Giao diện Giao diện là nơi giao tiếp giữa HCG và người sử dụng, thông tin được trao đổi thông qua kiểu ngôn ngữ tự nhiên: Hỏi và đáp, truy vấn, .... Người ta dùng các loại giao diện như đồ họa, thực đơn, …. 1.1.3.2. Các đặc tính của HCG a) Tách tri thức ra khỏi điều khiển Cơ sở tri thức và motor suy luận là hai khối tách rời. Khối cơ sở tri thức chứa các tri thức chuyên gia về lĩnh vực, khối motor là cơ chế giải quyết vấn đề. Việc tách như vậy rất tốt trong HCG, nó làm cho việc giải quyết vấn đề và đưa ra kết luận sẽ khách quan không bị nhiễu hay xung đột với các luật trong bộ nhớ tri thức. b) Tri thức chuyên gia Tri thức giải vấn đề trong HCG là tri thức thu thập từ các chuyên gia. c) Tập trung nguồn chuyên gia Mỗi chuyên gia chỉ có khả năng giải quyết vấn đề trong lĩnh vực chuyên môn nhất định. Vì vậy, HCG cần có tri thức từ nhiều chuyên gia (nhiều nguồn). d) Xử lí tri thức bằng các kí hiệu Tri thức giải bài toán trong HCG được mã hóa bằng kí hiệu và xử lý những kí hiệu này trên cơ sở lập luận logic. e) Xử lí tri thức với heuristic Người chuyên gia có rất nhiều kinh nghiệm có thể giải quyết vấn đề trong lĩnh vực chuyên môn của họ bằng kinh nghiệm. Phương pháp này được gọi là xử lí tri thức với heuristic. f) Xử lí tri thức không chắc chắn Hơn 80% ứng dụng trong thực tế không thể giải quyết được bằng phương pháp lập luận chắc chắn. HCG có thể giải quyết những ứng dụng này nhờ vào phương pháp xử lí không chắc chắn. 7 g) Bài toán giải được HCG chỉ giải được bài toán mà người chuyên gia giải được. h) Mức phức tạp vừa phải Không nên thiết kế một HCG để giải quyết vấn đề quá đơn giản và cũng không nên mong đợi HCG có thể giải quyết vấn đề quá phức tạp ngoài khả năng giải quyết vấn đề của người chuyên gia. i) Chấp nhận sai lầm Người chuyên gia giải quyết vấn đề đôi lúc cũng mắc phải sai lầm, vì thế ta phải chấp nhận một số rủi ro khi sử dụng HCG. 1.2. Khai phá dữ liệu 1.2.1. Tổ chức và Khai phá dữ liệu truyền thống Với sự phát triển mạnh mẽ của công nghệ điện tử tạo ra các bộ nhớ có dung lượng lớn, bộ xử lý tốc độ cao cùng với các hệ thống mạng viễn thông, người ta đã xây dựng các hệ thống thông tin nhằm tự động hóa mọi hoạt động kinh doanh của mình. Điều này đã làm cho dữ liệu tăng lên không ngừng. Vì vậy, nhiều hệ quản trị CSDL mạnh với các công cụ phong phú và thuận tiện đã được nghiên cứu nhằm mục đích giúp con người khai thác có hiệu quả tri thức từ các nguồn dữ liệu. Các hệ quản trị CSDL truyền thống (SQL) chưa đáp ứng được các nhu cầu về KPDL, tức là chưa nêu bật được ý nghĩa của dữ liệu đầu vào mà mới chỉ cung ứng được các công cụ truy vấn hay tìm kiếm thông tin. 1.2.2. Bước phát triển tiếp theo của việc tổ chức và khai thác các cơ sở dữ liệu Để lấy được những thông tin có tính “tri thức” trong khối dữ liệu khổng lồ, người ta đã đi tìm những kỹ thuật có khả năng hợp nhất các dữ liệu từ các hệ thống giao dịch khác nhau, chuyển đổi thành một tập hợp các CSDL ổn định, có chất lượng, chỉ được sử dụng riêng cho một vài mục đích nào đó. Các kỹ thuật này được gọi là kỹ thuật tạo, sử dụng kho dữ liệu (data warehousing). 8 1.2.3. Khai phá dữ liệu và quá trình phát hiện tri thức 1.2.3.1. Quá trình phát hiện tri thức Quá trình phát hiện tri thức là một quá trình hoạt động tương tác giữa con người với hệ thống thông qua các công cụ tin học để thực hiện các bước cơ bản sau: - Xác định chính xác vấn đề cần giải quyết, lĩnh vực ứng dụng và nhiệm vụ đặt ra, xác định các tri thức đã có và các mục tiêu của người sử dụng. - Xây dựng một tập dữ liệu đích thông qua việc chọn một tập dữ liệu từ CSDL với các giá trị biến và các mẫu được quan tâm. Trên tập dữ liệu đó, ta thực hiện quá trình phát hiện tri thức. - Làm sạch và tiền xử lý dữ liệu. - Thu gọn và rút bớt số chiều của dữ liệu để tập trung vào những thuộc tính chủ chốt đối với việc phát hiện tri thức. - Chọn nhiệm vụ KPDL dựa vào mục tiêu của quá trình phát hiện tri thức: Xếp loại, phân nhóm hay hồi quy,…. - Chọn thuật toán KPDL thích hợp và thực hiện việc KPDL để tìm được các mẫu hình (pattern) có ý nghĩa dưới dạng biểu diễn tương ứng (luật xếp loại, cây quyết định, luật sản xuất, biểu thức hồi quy, đồ thị,…). 9 Sơ đồ tổng quát quá trình phát hiện tri thức như sau: Xác định bài toán Thu thập và tiền xử lí dữ liệu Khai phá dữ liệu triết xuất tri thức Phát biểu kết quả và đánh giá triết xuất tri thức Sử dụng tri thức và phát hiện được triết suất tri thức Hình 1.1. Quá trình phát hiện tri thức từ CSDL 1.2.3.2. Mẫu Sự tương tác giữa con người và hệ thống nhằm mục đích xây dựng được các mẫu có ý nghĩa. Các mẫu cần có đặc điểm như sau: - Độ mới có thể được đo tương ứng với độ thay đổi trong dữ liệu (bằng cách so sánh các giá trị hiện tại với các giá trị trước đó hoặc các giá trị mong muốn). - Được đo dựa vào tri thức (mối liên hệ giữa phương pháp mới và phương pháp cũ như thế nào). Thường thì độ mới của mẫu được đánh giá bằng một hàm logic hoặc một hàm đo độ mới, độ bất ngờ của mẫu. 1.2.3.3. Khai phá dữ liệu Nếu phát hiện tri thức là toàn bộ quá trình chiết xuất tri thức từ các CSDL thì KPDL là giai đoạn chủ yếu của quá trình đó. Như trên đã trình bày, khâu KPDL là bước tiếp sau khâu tinh lọc và tiền xử lý dữ liệu trong quá trình phát hiện tri thức. Có nghĩa là việc khai thác được thực hiện trên các mẫu sau quá trình tinh lọc trên một mẫu theo mục đích nhất định của người sử dụng chứ không phải trên toàn bộ CSDL. Các công việc của KPDL: 10 - Tìm mô hình phù hợp với tập dữ liệu. - Tìm kiếm các mẫu từ tập dữ liệu theo mô hình đó. 1.2.4. Các dạng cơ sở dữ liệu có thể khai thác - CSDL 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 các ngành viễn thông, tài chính và ngân hàng do hầu hết các hệ quản trị CSDL đều hỗ trợ dạng CSDL quan hệ như Oracle, MS SQL Server, IBM DB2, MS Access,v.v… - CSDL đ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. - CSDL 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 bưu chính cũng như trong ngành tài chính, ngân hàng. - CSDL 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í, thời gian gửi tiền của các khách hàng trong ngân hàng, thời gian cho vay…. - CSDL đa phương tiện (Multimedia databases): Là dạng dữ liệu âm thanh (audio), hình ảnh (video), Text & 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 ngành bưu điện. Các kĩ thuật Khai phá dữ liệu: Phân lớp dữ liệu (classification); Phân cụm dữ liệu (clustering); Hồi quy (regression). 11 1.2.5. Các thành phần của giải thuật Khai phá dữ liệu Giải thuật KPDL bao gồm 3 thành phần chính như sau: Biểu diễn mô hình; Đánh giá mô hình; Tìm kiếm mô hình. Biểu diễn mô hình: Mô hình được biểu diễn bằng một ngôn ngữ nào đó để mô tả các mẫu có thể khai thác được. Nếu sự mô tả bị hạn chế thì sẽ không thể “học” được hoặc không thể có được các mẫu có thể tạo ra một mô hình chính xác cho dữ liệu. Đánh giá mô hình: Đánh giá xem một mẫu có đáp ứng được các tiêu chuẩn của quá trình phát hiện tri thức hay không. Việc đánh giá chính xác dự đoán dựa trên đánh giá chéo. Việc đánh giá chất lượng liên quan đến độ chính xác dự đoán, độ mới, khả năng sử dụng, khả năng hiểu được của mô hình. Cả hai chuẩn thống kê và chuẩn logic đều có thể được sử dụng để đánh giá mô hình. Tìm kiếm tham số và mô hình: Phương pháp tìm kiếm mô hình bao gồm hai thành phần: - Tìm kiếm tham số: Giải thuật cần tìm kiếm các tham số để tối ưu hóa các tiêu chuẩn đánh giá mô hình với các dữ liệu quan sát được và với một mô tả mô hình đã định. - Tìm kiếm mô hình: Tìm kiếm mô hình xảy ra giống như một vòng lặp qua phương pháp tìm kiếm tham số: Mô tả mô hình bị thay đổi tạo nên một họ các mô hình. Với mỗi một mô tả mô hình, phương pháp tìm kiếm tham số được áp dụng để đánh giá chất lượng mô hình. Các phương pháp tìm kiếm mô hình thường sử dụng các kỹ thuật tìm kiếm heuristic. 1.2.6. Một số phương pháp Khai phá dữ liệu phổ biến 1.2.6.1. Phương pháp suy diễn/quy nạp a) Phương pháp suy diễn Phương pháp suy diễn dựa trên các sự kiện chính xác để suy ra các tri thức mới từ các thông tin cũ. Mẫu chiết xuất được bằng cách sử dụng phương pháp này thường là các luật suy diễn. 12 b) Phương pháp quy nạp Phương pháp quy nạp suy ra các thông tin được sinh ra từ CSDL. Có nghĩa là nó tự tìm kiếm, tạo mẫu và sinh ra tri thức chứ không phải bắt đầu với các tri thức đã biết trước. Các thông tin mà phương pháp này đem lại là các thông tin hay các tri thức cấp cao diễn tả về các đối tượng trong CSDL. Phương pháp này liên quan đến việc tìm kiếm các mẫu trong CSDL. Trong KPDL, quy nạp được sử dụng trong cây quyết định và tạo luật. 1.2.6.2. Cây quyết định và luật a) Cây quyết định Cây quyết định là một mô tả tri thức dạng đơn giản nhằm phân các đối tượng dữ liệu thành một số lớp nhất định. Các nút của cây được gán nhãn là tên các thuộc tính, các cạnh được gán các giá trị của các thuộc tính, các lá mô tả các lớp khác nhau. Các đối tượng được phân lớp theo các đường đi trên cây, qua các cạnh tương ứng với các giá trị của thuộc tính của đối tượng tới lá. b) Tạo luật Các luật được tạo ra nhằm suy diễn một số mẫu dữ liệu có ý nghĩa về mặt thống kê. Các luật có dạng NẾU P THÌ Q, với P là mệnh đề đúng với một phần trong CSDL, Q là mệnh đề dự đoán. Cây quyết định và luật có ưu điểm là hình thức mô tả đơn giản, mô hình suy diễn khá dễ hiểu đối với người sử dụng. Tuy nhiên, giới hạn của nó là mô tả cây và luật chỉ có thể biểu diễn được một số dạng chức năng và vì vậy giới hạn về cả độ chính xác của mô hình. Đối với quy mô lớn, người ta dựa trên các phương pháp đánh giá mô hình theo xác suất với các mô hình mức độ phức tạp khác nhau. Các phương pháp tìm kiếm “tham lam”, liên quan đến việc tăng hay rút gọn các luật và các cấu trúc cây, chủ yếu được sử dụng để khai thác không gian siêu mũ (superexponnential space) của các mô hình. Cây và luật chủ yếu được sử dụng cho 13 việc mô hình hóa dự đoán, phân lớp và hồi quy. Chúng cũng có thể được áp dụng cho việc tóm tắt và mô hình hóa các mô tả. 1.2.6.3. Các phương pháp phân lớp và hồi quy phi tuyến Các phương pháp này bao gồm một họ các kỹ thuật dự đoán tạo ra các luật kết hợp tuyến tính và phi tuyến của các hàm cơ bản (hàm dấu, hàm tuyến tính đơn, hàm đa thức) phù hợp với giá trị biến đầu vào. Các phương pháp thuộc loại này như mạng neuron truyền thống, phương pháp sai số bình phương chuẩn (standard squared error), các hàm entropy (cross entropy loss function)…. Xét về mặt đánh giá mô hình, mạng neuron có kích thước tương đối và có khả năng mô phỏng bất kỳ hàm nào gần đúng với một độ chính xác mong muốn. Tuy nhiên, để tìm một mạng có kích thước tối ưu cho một tập dữ liệu lại là một công việc khá phức tạp và chưa chắc đã có thể tìm được kết quả của kích thước. Các phương pháp sai số bình phương chuẩn (standard squared error) và các hàm entropy (cross entropy loss function) được sử dụng để học khi phân lớp và hồi quy (các hàm khả năng logarit ). Phương pháp Lan truyền ngược sai số là một phương pháp tìm kiếm tham số thực hiện việc giảm số chiều gradient trong không gian tham số (ở đây là các trọng số) để tìm một giá trị cực đại cục bộ của hàm xác suất bắt đầu từ các giá trị khởi tạo ngẫu nhiên. Các phương pháp hồi quy phi tuyến tuy dễ biểu diễn nhưng khó có thể xây dựng thành các luật. 1.2.6.4. Phân cụm và phân đoạn (clustering and segmentation) Kỹ thuật phân cụm và phân đoạn là những kỹ thuật phân chia dữ liệu sao cho mỗi phần hoặc mỗi cụm giống nhau theo một tiêu chuẩn xác định. Mối quan hệ thành viên của các cụm có thể dựa trên mức độ giống nhau của các thành viên và từ đó xây dựng nên các luật ràng buộc giữa các thành viên
- Xem thêm -

Tài liệu liên quan