NGHIÊN CỨU PHÁT HIỆN LUẬT KẾT HỢP HIẾM VÀ ỨNG DỤNG

Trong lĩnh vực khai phá dữ liệu (data mining), luật kết hợp (association rule) được dùng để chỉ mối quan hệ kiểu “điều kiện -> hệ quả” giữa các phần tử dữ liệu (chẳng hạn, sự xuất hiện của tập mặt hàng này “kéo theo” sự xuất hiện của tập mặt hàng khác) trong một tập bao gồm nhiều đối tượng dữ liệu (chẳng hạn, các giao dịch mua hàng). Phát hiện luật kết hợp là phát hiện các mối quan hệ đó trong phạm vi của một tập dữ liệu đã cho. Lý thuyết luật kết hợp được Rakesh Agrawal và cộng sự giới thiệu lần đầu tiên vào năm 1993 và nhanh chóng trở thành một trong những hướng nghiên cứu khai phá dữ liệu quan trọng, đặc biệt trong những năm gần đây. Phát hiện luật kết hợp đã được ứng dụng thành công trong nhiều lĩnh vực kinh tế – xã hội khác nhau như thương mại, y tế, sinh học, tài chính-ngân hàng,…. Hiện tại, nhiều khuynh hướng nghiên cứu và ứng dụng liên quan đến phát hiện luật kết hợp đã và đang tiếp tục được hình thành.

Một trong những vấn đề về phát hiện luật kết hợp hiện đang nhận được nhiều quan tâm của các nhà nghiên cứu là phát hiện luật kết hợp hiếm. Luật kết hợp hiếm (còn được gọi là luật hiếm) là những luật kết hợp ít xảy ra. Mặc dù tần suất xảy ra thấp, nhưng trong nhiều trường hợp, các luật này lại rất có giá trị. Y. S. Koh và N. Rountree trình bầy khái quát về ứng dụng của khai phá luật hiếm, trong đó giới thiệu ví dụ luật kết hợp hiếm “máy pha cà phê” -> “máy xay cà phê” có độ hỗ trợ rất thấp là 0,8% song có độ tin cậy khá cao tới 80% và giá trị bán hai mặt hàng này rất đáng kể. L. Szathmary và cộng sự giới thiệu luật kết hợp hiếm “ăn chay” -> “bệnh tim mạch” trong CSDL điều trị bệnh nhân Stanislas ở Pháp và luật kết hợp hiếm “thuốc hạ lipid trong máu Cerivastatin” -> “tác động xấu khi điều trị”.

Mục tiêu cụ thể của luận án là phát triển vấn đề và đề xuất thuật toán phát hiện luật kết hợp hiếm trên cả hai loại CSDL tác vụ và định lượng, đồng thời ứng dụng ban đầu một phần kết quả nghiên cứu lý thuyết đạt được trong xây dựng mô hình phân tích và dự báo một số vấn đề cụ thể do thực tiễn đặt ra.

Bài toán phát hiện luật kết hợp hiếm cũng được chia làm hai giai đoạn:

Giai đoạn 1: Tìm tất cả các tập mục dữ liệu để sinh ra các luật kết hợp hiếm. Các tập mục dữ liệu này được gọi là tập mục dữ liệu hiếm (hay tập hiếm).

Giai đoạn 2: Với mỗi tập hiếm tìm được ở giai đoạn 1, sinh ra tất cả các luật hiếm có độ tin cậy lớn hơn hoặc bằng độ tin cậy cực tiểu đã được xác định trước.

Trong hai giai đoạn trên thì giai đoạn 1 là khó khăn, phức tạp và tốn nhiều chi phí nhất. Giai đoạn thứ 2 có thể giải quyết đơn giản hơn khi tìm được tất cả các tập hiếm và độ hỗ trợ của chúng.

Tương tự như phát hiện luật kết hợp phổ biến, việc phát hiện luật kết hợp hiếm cũng có một phạm vi rất rộng. Trong luận án này, nghiên cứu sinh tập trung chủ yếu giải quyết giai đoạn 1 của bài toán phát hiện luật kết hợp hiếm. Cụ thể luận án phát triển giải pháp hiệu quả để tìm tập hiếm trên cả CSDL tác vụ và định lượng. Ở Việt Nam, đã có một số luận án tiến sĩ nghiên cứu về luật kết hợp nhưng chưa có một luận án nào nghiên cứu về phát hiện luật kết hợp hiếm.

Về nghiên cứu lý thuyết, luận án tập trung xác định một số dạng luật kết hợp hiếm Sporadic trên cả CSDL tác vụ và CSDL định lượng, đồng thời phát triển các thuật toán phát hiện các tập dữ liệu hiếm tương ứng cho các dạng luật hiếm này.

Đối với bài toán phát hiện luật kết hợp hiếm trên CSDL tác vụ, luận án theo hướng tiếp cận đi tìm các tập không phổ biến đóng cho các luật kết hợp hiếm thay vì việc đi tìm tất cả các tập không phổ biến như các nghiên cứu về luật hiếm trước đây. Cơ sở của hướng tiếp cận này của luận án dựa trên các tính chất sau đây: (1) Tập tất cả các tập hiếm cực đại và tập tất cả các tập hiếm đóng cực đại là bằng nhau; (2) Các luật kết hợp hiếm được sinh ra từ các tập hiếm và từ các tập hiếm cực đại là như nhau. Tiếp cận nói trên là tương đồng với tư tưởng của thuật toán CHARM [94], là một trong những thuật toán hiệu quả nhất để phát hiện luật kết hợp mạnh trên CSDL tác vụ. Tập các tập không phổ biến đóng là nhỏ hơn tập các tập không phổ biến, vì vậy, việc chỉ phải tìm tập hiếm đóng không những hạn chế được chi phí mà còn hạn chế được các luật hiếm dư thừa. Luận án phát triển ba thuật toán tìm các tập mục hiếm cho ba dạng luật kết hợp hiếm trên CSDL tác vụ là: thuật toán MCPSI (Mining Closed Perfectly Sporadic Itemsets) phát hiện tập mục Sporadic tuyệt đối hai ngưỡng, thuật toán MCISI (Mining Closed Imperfectly Sporadic Itemsets) phát hiện tập mục Sporadic không tuyệt đối hai ngưỡng và thuật toán NC-CHARM (Negative Constrains – CHARM) phát hiện tập dữ liệu với ràng buộc mục âm. Cả ba thuật toán trên đây được phát triển theo hướng bổ sung, phát triển các giải pháp cho phát hiện luật kết hợp Sporadic dựa theo cách tiếp cận và ý tưởng của thuật toán CHARM.

Đối với bài toán phát hiện luật kết hợp hiếm trên CSDL định lượng, luận án theo hướng tiếp cận tương tự như phát hiện luật kết hợp mạnh trên CSDL định lượng là sử dụng lý thuyết tập mờ để chuyển CSDL định lượng về CSDL mờ và thực hiện phát hiện luật hiếm trên CSDL mờ này. Tương tự như đối với luật kết hợp mạnh, việc ứng dụng tập mờ sẽ giúp biểu diễn luật kết hợp hiếm tự nhiên hơn, gần gũi hơn với người sử dụng và nhất là khắc phục được vấn đề “điểm biên gãy” trong phân khoảng các thuộc tính định lượng. Hai dạng luật kết hợp Sporadic cho CSDL định lượng đã được luận án đề xuất là luật kết hợp Sporadic tuyệt đối hai ngưỡng mờ và luật kết hợp Sporadic không tuyệt đối hai ngưỡng mờ [4]. Luận án đã phát triển hai thuật toán tìm tập hiếm cho hai dạng luật này. Thuật toán MFPSI (Mining Fuzzy Perfectly Sporadic Itemsets) phát hiện tập mục Sporadic tuyệt đối hai ngưỡng mờ được phát triển theo tư tưởng của thuật toán Apriori, còn thuật toán MFISI (Mining Fuzzy Imperfectly Sporadic Itemsets) phát hiện tập mục Sporadic không tuyệt đối hai ngưỡng mờ được phát triển theo tư tưởng của thuật toán của chúng tôi tìm tập hiếm cho luật Sporadic không tuyệt đối trên CSDL tác vụ.

Tải về miễn phí bản đầy đủ luận văn tại địa chỉ:

https://www.file-upload.com/pqz37h9vng7q

Tác giả

CÙ THU THỦY

Chuyên ngành

Hệ thống thông tin

Mã số

62 48 05 01

Người hướng dẫn khoa học

PGS. TS. Đỗ Văn Thành, PGS. TS. Hà Quang Thụy

Đánh giá

Chưa có đánh giá nào.

Hãy là người đầu tiên đánh giá “NGHIÊN CỨU PHÁT HIỆN LUẬT KẾT HỢP HIẾM VÀ ỨNG DỤNG”

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *