Luận văn Một số kỹ thuật đánh giá luật dựa trên lý thuyết tập thô

1 Chương 1. GIỚI THIỆU 1.1. KHAI PHÁ DỮ LIỆU Phát hiện tri thức trong cơ sở dữ liệu (KDD-Knowledge Discovery in Database) là quá trình tìm kiếm những thông tin ẩn có giá trị từ tập dữ liệu lớn, là quá trình hoạt động tương tác giữa con người và cơ sở dữ liệu với sự hỗ trợ của công cụ tin học để chọn ra những tri thức có ích phục vụ cho một mục đích nhất định trong một lĩnh vực nhất định. Khai phá dữ liệu (Data Mining) là một trong những hoạt động của quá trình phát hiện tri thức, là kỹ thuật chính giúp ta lấy được các tri thức hữu ích, quan trọng. Quá trình phát hiện tri thức có thể được biểu diễn bằng Hình 1.1: Hình 1.1. Quá trình phát hiện tri thức Hiện nay trên thế giới đã có nhiều ngành công nghiệp sử dụng kỹ thuật khai phá dữ liệu để phục vụ cho các hoạt động kinh doanh của mình và bước đầu thành công như ngành tài chính, y học, bảo hiểm, sản xuất… Mặc dù kỹ thuật khai phá dữ liệu hiện nay vẫn còn nhiều vấn đề nổi cộm nhưng với những tri thức mà nó đem lại cũng đã chứng tỏ khai phá dữ liệu có một tiềm năng to lớn trong việc tạo ra những lợi nhuận đáng kể trong nền kinh tế. Các hướng tiếp cận khai phá dữ liệu phổ biến đang được nghiên cứu và sử dụng hiện nay: mạng nơron, kỹ thuật phân cụm và phân đoạn, phương pháp Xác định mục tiêu 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á Sử dụng tri thức đã phát hiện được 2 láng giềng gần nhất, giải thuật di truyền, phương pháp phát hiện luật kết hợp… Trong đó, các hướng tiếp cận khai phá luật kết hợp: luật kết hợp nhị phân, luật kết hợp mờ, luật kết hợp nhiều mức, luật kết hợp tiếp cận theo hướng tập thô, luật kết hợp với các thuộc tính được đánh trọng số… Luận văn này tập trung vào kỹ thuật phát hiện luật kết hợp theo hướng tiếp cận tập thô trong quá trình khai phá dữ liệu, tiếp theo đó giới thiệu những kỹ thuật đánh giá luật dựa trên cơ sở lý thuyết tập thô để rút trích những luật quan trọng và có ích để tri thức phát hiện được thật sự có ý nghĩa cho ứng dụng. 1.2. LUẬT KẾT HỢP Luật kết hợp là lĩnh vực quan trọng trong khai phá dữ liệu, là kỹ thuật khai phá dữ liệu khá đơn giản nhưng thiết thực. Phát hiện luật kết hợp giúp ta tìm ra được các mối liên quan của các thành phần trong dữ liệu. Chẳng hạn, từ việc phân tích dữ liệu bán hàng của siêu thị, ta có thể phát hiện thói quen mua hàng của khách hàng như: khi khách hàng mua bánh mì thì hầu như họ sẽ mua sữa. Luật kết hợp có thể được sử dụng để tìm hiểu các thói quen này của khách hàng, giúp gia tăng số lượng hàng bán được trong siêu thị bằng cách sắp xếp những mặt hàng liên quan với nhau một cách hợp lý. Một luật kết hợp được xem là có ý nghĩa nếu độ hỗ trợ và độ tin cậy của luật cao hơn ngưỡng hỗ trợ minSup và ngưỡng tin cậy minConf do người dùng định nghĩa. Một ví dụ nhỏ: từ tập dữ liệu bán hàng của siêu thị ta phát hiện luật kết hợp bread→ cheese với độ hỗ trợ là 80% và độ tin cậy 60% (minSup=50%, minConf=50%); điều này có nghĩa: trong số các khách hàng mua hàng ở siêu thị thì có 80% khách hàng vừa mua bread vừa mua cheese và trong số các khách hàng có mua bread thì có 60% khách hàng mua cheese. 1.3. LÝ THUYẾT TẬP THÔ Phát hiện luật theo hướng tiếp cận của lý thuyết tập thô được phát triển bởi Zdzislaw Pawlak vào đầu những năm 1980[12] là một trong những phương pháp đang được nhiều nhà khoa học nghiên cứu và sử dụng trong quá trình khai phá tri thức từ dữ liệu. Dữ liệu thực tế thường không đầy đủ, dư thừa, hoặc 3 không chính xác, gây ảnh hưởng không tốt đến quá trình khai phá dữ liệu. Ý tưởng “rút gọn” trong lý thuyết tập thô được sử dụng cho phép loại bỏ những thông tin dư thừa mà vẫn giữ được đầy đủ ý nghĩa của tập dữ liệu đang xét, mục tiêu chính là lựa chọn các thuộc tính cốt yếu và cần thiết trong cơ sở dữ liệu. Dựa vào đó, việc phát hiện luật vẫn đạt hiệu quả cao nhất mà chỉ cần sử dụng tập con của tập thuộc tính điều kiện thay vì toàn bộ tập thuộc tính điều kiện. 1.4. ĐÁNH GIÁ LUẬT Một vấn đề đáng quan tâm của quá trình phát sinh luật kết hợp là số lượng luật kết hợp tìm được thường khá lớn, gây khó khăn trong việc xác định luật nào thực sự hữu ích và đáng tin cậy. Một giải pháp cho vấn đề này là sử dụng các độ đo hữu ích (Interesting Measures)[11] như độ tin cậy, độ hỗ trợ, Lift, 2χ , Laplace, Conviction,…. Độ đo sự hữu ích của luật được chia làm hai loại chính: độ đo khách quan (Object Measure) – là độ đo tùy thuộc vào cấu trúc của mô hình và dữ liệu sẵn có trong quá trình phát hiện luật, độ đo chủ quan (Subject Measure) – là độ đo tùy thuộc vào sự chọn lựa mô hình do người sử dụng quyết định. Nhóm tác giả Jiye Li cũng đã đề xuất một số độ đo dựa vào lý thuyết tập thô: độ đo Tầm quan trọng của luật (Rule Importance Measure - RIM)[6] là độ đo khách quan được định nghĩa tương tự độ đo hữu ích dùng để đánh giá mức độ quan trọng của luật, độ đo Xem luật như thuộc tính (Rule-as-Attribute Measure - RAM)[7] cũng là độ đo khách quan dùng để chọn ra những luật quan trọng nhất từ tập luật, và độ đo Tầm quan trọng cải tiến (Enhanced Rule Importance Measure - ERIM)[9] là sự kết hợp hai độ đo chủ quan và khách quan được định nghĩa dựa vào trọng số của các thuộc tính điều kiện. Trong luận văn này, tôi có nhận xét về hạn chế của độ đo ERIM và đề xuất 2 độ đo mới: độ đo WAERIM (Weight Average Based Enhanced Rule Importance Measure) và độ đo AIERIM (Attributes Importance Degree Based Rule Importance Measure). Tiếp theo, tôi so sánh khả năng đánh giá luật giữa 2 độ đo luận văn đề xuất với các độ đo hữu ích và với các độ đo mà nhóm tác giả 4 Jiye Li đã đề xuất bằng các ứng dụng thực tế trên các nguồn dữ liệu từ UCI và trên nguồn dữ liệu cho vay ngân hàng (BankLoan). 1.5. TÓM LẠI Luận văn giới thiệu các cách tiếp cận để đánh giá luật kết hợp dựa trên cơ sở lý thuyết tập thô: độ đo RIM, độ đo RAM, độ đo ERIM, độ đo WAERIM, độ đo AIERIM và chứng minh hiệu quả đánh giá luật của các độ đo này bằng ứng dụng thực tế. Các phần tiếp theo của luận văn được tổ chức như sau: Chương 2: Kiến thức nền tảng về lý thuyết tập thô và kiến thức cơ bản về luật kết hợp, ứng dụng lý thuyết tập thô vào quá trình phát sinh luật. Chương 3: Các phương pháp đánh giá luật sử dụng các độ đo, giới thiệu một số độ đo dựa trên cơ sở lý thuyết tập thô và đề xuất hai độ đo mới. Chương 4: Cài đặt các độ đo, dùng các nguồn dữ liệu thực tế để so sánh khả năng đánh giá luật giữa các độ đo này. Cuối cùng là phần Kết luận và hướng phát triển trong tương lai.