Nghiên cứu phát hiện luật kết hợp hiếm và ứng dụng

Nội dung bài viết

Lý do chọn đề tài

Trong lĩnh vực khai phá dữ liệu (data mining), luật kết hợp (association rule) được dùng để chỉ mối quan hệ kiểu “điều kiện Æ hệ quả” giữa các phần tử dữ liệu (chẳng hạn, sự xuất hiện của tập mặt hàng này “kéo theo” sự xuất hiện của tập mặt hàng khác) trong một tập bao gồm nhiều đối tượng dữ liệu (chẳng hạn, các giao dịch mua hàng). Phát hiện luật kết hợp là phát hiện các mối quan hệ đó trong phạm vi của một tập dữ liệu đã cho. Lý thuyết luật kết hợp được Rakesh Agrawal và cộng sự giới thiệu lần đầu tiên vào năm 1993 [13] và nhanh chóng trở thành một trong những hướng nghiên cứu khai phá dữ liệu quan trọng, đặc biệt trong những năm gần đây. Phát hiện luật kết hợp đã được ứng dụng thành công trong nhiều lĩnh vực kinh tế – xã hội khác nhau như thương mại, y tế, sinh học, tài chính-ngân hàng,…[18, 23, 25, 44, 69, 86, 87]. Hiện tại, nhiều khuynh hướng nghiên cứu và ứng dụng liên quan đến phát hiện luật kết hợp đã và đang tiếp tục được hình thành.

Một trong những vấn đề về phát hiện luật kết hợp hiện đang nhận được nhiều quan tâm của các nhà nghiên cứu là phát hiện luật kết hợp hiếm [26, 47, 49, 50, 53, 58, 66, 68, 80]. Luật kết hợp hiếm (còn được gọi là luật hiếm) là những luật kết hợp ít xảy ra. Mặc dù tần suất xảy ra thấp, nhưng trong nhiều trường hợp, các luật này lại rất có giá trị. Trong [49], Y. S. Koh và N. Rountree trình bầy khái quát về ứng dụng của khai phá luật hiếm, trong đó giới thiệu ví dụ luật kết hợp hiếm “máy pha cà phê” Æ “máy xay cà phê” có độ hỗ trợ rất thấp là 0,8% song có độ tin cậy khá cao tới 80% và giá trị bán hai mặt hàng này rất đáng kể. L. Szathmary và cộng sự [76] giới thiệu luật kết hợp hiếm “ăn chay” Æ “bệnh tim mạch” trong CSDL điều trị bệnh nhân Stanislas ở Pháp và luật kết hợp hiếm “thuốc hạ lipid trong máu Cerivastatin” Æ “tác động xấu khi điều trị”.

Phần lớn các thuật toán phát hiện luật kết hợp hiện nay thường thực hiện tìm các luật có độ hỗ trợ và độ tin cậy cao. Việc ứng dụng các thuật toán này để tìm các luật kết hợp hiếm (có độ hỗ trợ thấp) là không hiệu quả do phải đặt ngưỡng độ hỗ trợ cực tiểu rất nhỏ, nên số lượng các tập phổ biến tìm được sẽ khá lớn (trong khi chỉ có một phần trong các tập tìm được có độ hỗ trợ nhỏ hơn ngưỡng độ hỗ trợ cực tiểu minSup) và như vậy chi phí cho việc tìm kiếm sẽ tăng lên. Nhằm khắc phục những khó khăn này, các thuật toán phát hiện luật kết hợp hiếm được phát triển. Hai khuynh hướng phát hiện luật kết hợp hiếm được quan tâm nhiều nhất là:

(i) Sử dụng ràng buộc phần hệ quả của luật. Các phương pháp này đưa ra danh sách các mục dữ liệu sẽ xuất hiện trong một phần của luật và được sử dụng làm điều kiện khi sinh luật. Tuy nhiên, cách tiếp cận này chỉ hiệu quả khi biết trước thông tin về các mục dữ liệu, chẳng hạn phải xác định trước được mục dữ liệu nào sẽ xuất hiện trong phần hệ quả của luật [22, 56, 66].

(ii) Sử dụng đường ranh giới để phân chia tập không phổ biến với tập phổ biến và chỉ phát hiện luật kết hợp hiếm từ những tập (được gọi là tập hiếm) thuộc không gian các tập không phổ biến [49, 50, 58, 75, 76, 80]. Tuy đạt được những kết quả nhất định nhưng hướng nghiên cứu này vẫn còn nhiều hạn chế như: do phải sinh ra tất cả các tập không phổ biến nên chi phí cho không gian nhớ là rất cao, và xẩy ra tình trạng dư thừa nhiều luật kết hợp được sinh ra từ các tập hiếm tìm được.

Cả hai hướng nghiên cứu nói trên tập trung chủ yếu vào vấn đề phát hiện luật kết hợp hiếm trên CSDL tác vụ và vẫn chưa được giải quyết triệt để.

Vấn đề phát hiện luật kết hợp hiếm trên CSDL định lượng mới chỉ được đề cập lần đầu trong [58] và cũng chỉ nhằm phát hiện luật kết hợp hiếm từ các tập chỉ chứa các mục dữ liệu không phổ biến. Tuy nhiên, tập hiếm không chỉ gồm các mục dữ liệu không phổ biến mà còn là sự kết hợp giữa một số mục dữ liệu không phổ biến với mục dữ liệu phổ biến hay sự kết hợp giữa những mục dữ liệu phổ biến. Như vậy, vấn đề phát hiện luật kết hợp hiếm trên CSDL định lượng hiện cũng chưa được giải quyết đầy đủ.

Luận án này sẽ tiếp nối những nghiên cứu trước đó nhằm giải quyết những hạn chế được nêu ra ở trên.

Mục tiêu cụ thể và phạm vi nghiên cứu của luận án

Mục tiêu cụ thể của luận án là phát triển vấn đề và đề xuất thuật toán phát hiện luật kết hợp hiếm trên cả hai loại CSDL tác vụ và định lượng, đồng thời ứng dụng ban đầu một phần kết quả nghiên cứu lý thuyết đạt được trong xây dựng mô hình phân tích và dự báo một số vấn đề cụ thể do thực tiễn đặt ra.

Bài toán phát hiện luật kết hợp hiếm cũng được chia làm hai giai đoạn:

Giai đoạn 1: Tìm tất cả các tập mục dữ liệu để sinh ra các luật kết hợp hiếm. Các tập mục dữ liệu này được gọi là tập mục dữ liệu hiếm (hay tập hiếm).

Giai đoạn 2: Với mỗi tập hiếm tìm được ở giai đoạn 1, sinh ra tất cả các luật hiếm có độ tin cậy lớn hơn hoặc bằng độ tin cậy cực tiểu đã được xác định trước.

Trong hai giai đoạn trên thì giai đoạn 1 là khó khăn, phức tạp và tốn nhiều chi phí nhất. Giai đoạn thứ 2 có thể giải quyết đơn giản hơn khi tìm được tất cả các tập hiếm và độ hỗ trợ của chúng.

Tương tự như phát hiện luật kết hợp phổ biến, việc phát hiện luật kết hợp hiếm cũng có một phạm vi rất rộng. Trong luận án này, nghiên cứu sinh tập trung chủ yếu giải quyết giai đoạn 1 của bài toán phát hiện luật kết hợp hiếm. Cụ thể luận án phát triển giải pháp hiệu quả để tìm tập hiếm trên cả CSDL tác vụ và định lượng. Ở Việt Nam, đã có một số luận án tiến sĩ nghiên cứu về luật kết hợp [9, 10, 12] nhưng chưa có một luận án nào nghiên cứu về phát hiện luật kết hợp hiếm.

Ý nghĩa khoa học và thực tiễn của luận án

Về mặt khoa học, luận án đề xuất hướng tiếp cận phát hiện luật kết hợp hiếm trên CSDL tác vụ dựa trên không gian tập dữ liệu hiếm đóng. Nhờ đó, đã nâng cao hiệu quả của việc phát hiện luật kết hợp hiếm vì không gian các tập dữ liệu hiếm và đóng là nhỏ hơn không gian các tập dữ liệu hiếm. Luận án sử dụng lý thuyết tập mờ trong vấn đề phát hiện luật kết hợp hiếm trên CSDL định lượng.

Luận án có tính thực tiễn vì đã đề cập việc ứng dụng luật kết hợp cùng với mô hình hồi quy chuyển tiếp trơn để xây dựng mô hình phân tích và dự báo kinh tế.

Đóng góp của luận án

Về nghiên cứu lý thuyết, luận án tập trung xác định một số dạng luật kết hợp hiếm Sporadic trên cả CSDL tác vụ và CSDL định lượng, đồng thời phát triển các thuật toán phát hiện các tập dữ liệu hiếm tương ứng cho các dạng luật hiếm này.

Đối với bài toán phát hiện luật kết hợp hiếm trên CSDL tác vụ, luận án theo hướng tiếp cận đi tìm các tập không phổ biến đóng cho các luật kết hợp hiếm thay vì việc đi tìm tất cả các tập không phổ biến như các nghiên cứu về luật hiếm trước đây. Cơ sở của hướng tiếp cận này của luận án dựa trên các tính chất sau đây: (1) Tập tất cả các tập hiếm cực đại và tập tất cả các tập hiếm đóng cực đại là bằng nhau; (2) Các luật kết hợp hiếm được sinh ra từ các tập hiếm và từ các tập hiếm cực đại là như nhau. Tiếp cận nói trên là tương đồng với tư tưởng của thuật toán CHARM [94], là một trong những thuật toán hiệu quả nhất để phát hiện luật kết hợp mạnh trên CSDL tác vụ. Tập các tập không phổ biến đóng là nhỏ hơn tập các tập không phổ biến, vì vậy, việc chỉ phải tìm tập hiếm đóng không những hạn chế được chi phí mà còn hạn chế được các luật hiếm dư thừa. Luận án phát triển ba thuật toán tìm các tập mục hiếm cho ba dạng luật kết hợp hiếm trên CSDL tác vụ là: thuật toán MCPSI (Mining Closed Perfectly Sporadic Itemsets) phát hiện tập mục Sporadic tuyệt đối hai ngưỡng [32], thuật toán MCISI (Mining Closed Imperfectly Sporadic Itemsets) phát hiện tập mục Sporadic không tuyệt đối hai ngưỡng [33] và thuật toán NC-CHARM (Negative Constrains – CHARM) phát hiện tập dữ liệu với ràng buộc mục âm [2]. Cả ba thuật toán trên đây được phát triển theo hướng bổ sung, phát triển các giải pháp cho phát hiện luật kết hợp Sporadic dựa theo cách tiếp cận và ý tưởng của thuật toán CHARM.

Đối với bài toán phát hiện luật kết hợp hiếm trên CSDL định lượng, luận án theo hướng tiếp cận tương tự như phát hiện luật kết hợp mạnh trên CSDL định lượng là sử dụng lý thuyết tập mờ để chuyển CSDL định lượng về CSDL mờ và thực hiện phát hiện luật hiếm trên CSDL mờ này. Tương tự như đối với luật kết hợp mạnh, việc ứng dụng tập mờ sẽ giúp biểu diễn luật kết hợp hiếm tự nhiên hơn, gần gũi hơn với người sử dụng và nhất là khắc phục được vấn đề “điểm biên gãy” trong

phân khoảng các thuộc tính định lượng. Hai dạng luật kết hợp Sporadic cho CSDL định lượng đã được luận án đề xuất là luật kết hợp Sporadic tuyệt đối hai ngưỡng mờ [3] và luật kết hợp Sporadic không tuyệt đối hai ngưỡng mờ [4]. Luận án đã phát triển hai thuật toán tìm tập hiếm cho hai dạng luật này. Thuật toán MFPSI (Mining Fuzzy Perfectly Sporadic Itemsets) phát hiện tập mục Sporadic tuyệt đối hai ngưỡng mờ [3] được phát triển theo tư tưởng của thuật toán Apriori [16], còn thuật toán MFISI (Mining Fuzzy Imperfectly Sporadic Itemsets) phát hiện tập mục Sporadic không tuyệt đối hai ngưỡng mờ [4] được phát triển theo tư tưởng của thuật toán của chúng tôi tìm tập hiếm cho luật Sporadic không tuyệt đối trên CSDL tác vụ [33].

Về triển khai ứng dụng, luận án đã đề xuất kết hợp vấn đề phát hiện luật kết hợp mẫu âm trong công nghệ thông tin và mô hình hồi quy chuyển tiếp trơn phi tuyến trong kinh tế lượng để xây dựng mô hình phân tích và dự báo chỉ số giá tiêu dùng CPI và chỉ số chứng khoán Việt Nam. Kết quả dự báo kiểm định theo mô hình được xây dựng theo cách tiếp cận này cho thấy chất lượng dự báo được cải thiện rõ rệt, độ chính xác của kết quả dự báo so với thực tiễn là khá cao [1, 7, 36].

Cấu trúc của luận án

Tiếp nối phần mở đầu này, nội dung chính của luận án được bố cục thành 4 chương và phần kết luận. Hình 0.1 trình bày phân bố các chủ đề phát hiện luật kết hợp được đề cập trong bốn chương nội dung của luận án.

Các chủ đề nghiên cứu trong các hình chữ nhật với đường biên kép là các kết quả đóng góp chính của luận án. Các chương luận án là tổng hợp nội dung các bài báo công bố các kết quả nghiên cứu được thực hiện trong luận án (chương 2 với [2, 32-33], chương 3 với [3-4], chương 4 với [1, 7, 36]).

Phần kết luận tổng hợp các kết quả đạt được cũng như nêu lên một số hạn chế của luận án, và đồng thời trình bầy một số định hướng nghiên cứu trong tương lai.

Link tải tài liệu: https://tii.la/H9jbpUPRaJ

Lưu ý: Link tải có chứa quảng cáo được rút gọn bằng Shrinkearn.com

Mật khẩu mở tệp PDF: sharetailieu.net

Nghiên cứu chế tạo và khảo sát tính chất vật liệu Polyme Nanocompozit trên cơ sở Polyaniline và Graphit

Nghiên cứu công nghệ chế tạo và tính chất của giả vật liệu Metamaterial

Nghiên cứu chế tạo vật liệu sắt điện BaTiO3 và tổ hợp BaTiO3/Fe3O4 có cấu trúc micro-nano bằng phương pháp thủy phân nhiệt

Tiếp cận các ứng dụng giao thức truyền thông không dây MiWi PRO

Nghiên cứu chế tạo và khảo sát tính chất vật liệu Polyme Nanocompozit trên cơ sở Polyaniline và Graphit

Nghiên cứu công nghệ chế tạo và tính chất của giả vật liệu Metamaterial

Nghiên cứu chế tạo vật liệu sắt điện BaTiO3 và tổ hợp BaTiO3/Fe3O4 có cấu trúc micro-nano bằng phương pháp thủy phân nhiệt

Tiếp cận các ứng dụng giao thức truyền thông không dây MiWi PRO

Lý do chọn đề tài

Mục tiêu cụ thể và phạm vi nghiên cứu của luận án

Ý nghĩa khoa học và thực tiễn của luận án

Đóng góp của luận án

Cấu trúc của luận án

LEAVE A REPLY Cancel reply

Mới Nhất

Nghiên cứu chế tạo và khảo sát tính chất vật liệu Polyme Nanocompozit trên cơ sở Polyaniline và Graphit

Nghiên cứu công nghệ chế tạo và tính chất của giả vật liệu Metamaterial

Nghiên cứu chế tạo vật liệu sắt điện BaTiO3 và tổ hợp BaTiO3/Fe3O4 có cấu trúc micro-nano bằng phương pháp thủy phân nhiệt

Tiếp cận các ứng dụng giao thức truyền thông không dây MiWi PRO

Nâng cao độ chính xác định vị robot bằng phương pháp tổng hợp dữ liệu cảm biến lập mã quang với bộ lọc Kalman...

Cùng Chuyên Mục

Đọc Nhiều Nhất

Áp dụng OSGi trong việc xây dựng hệ thống dựa thành...

Kiến trúc hướng dịch vụ và ứng dụng điện toán đám...

Nghiên cứu tính khả kiểm thử của ứng dụng trên nền...

Kiểm thử đơn vị cho hệ thống

Phát triền phần mềm cho người học tại Đại học Quốc...

Các kỹ thuật phân cụm trong khai phá dữ liệu sử...