Khai phá luật kết hợp đa cấp và ứng dụng ở trường Đại học Quảng Bình
Hiện nay, với sự phát triển không ngừng của xã hội, một thách thức đặt ra cho sinh viên các trường đại học là khả năng tự nghiên cứu, tìm tòi kiến thức bằng nhiều kênh thông tin và bằng các phương pháp khác nhau, trong đó việc học hỏi qua sách báo ở trung tâm học liệu hoặc thư viên trường là cách mà nhiều sinh viên đang sử dụng để thực hiện điều đó.
Vì vậy, một vấn đề đặt ra là làm sao để các trung tâm học liệu hoạt động hiệu quả nhất, làm sao để sinh viên có thể mượn sách ở trung tâm học liệu một cách khoa học nhất, làm sao để biết sinh viên khoa nào, bộ môn nào hay lên trung tâm học liệu, cuốn sách nào được sinh viên mượn thường xuyên từ đó biết được nguyên nhân sinh viên các khoa, bộ môn nào ít lên trung tâm học liệu, cuốn sách nào không được mượn thường xuyên để có cách điều chỉnh hợp lý, đáp ứng cao nhất nhu cầu đọc sách của sinh viên.
Khai phá dữ liệu hiện nay đã trở thành một hướng nghiên cứu chính trong lĩnh vực khoa học máy tính và công nghệ tri thức. Hàng loạt nghiên cứu, đề xuất trong lĩnh vực này đã được ứng dụng và thử nghiệm thành công vào đời sống. [3]
Khai phá dữ liệu là quá trình khám phá thông tin ẩn được tìm thấy trong các cơ sở dữ liệu, là giai đoạn quan trọng nhất trong quá trình khám phá tri thức từ cơ sở dữ liệu, hay cũng có thể gọi là quá trình trích rút tri thức từ dữ liệu, các tri thức này hỗ trợ trong việc ra quyết định trong khoa học và kinh doanh. [3]
Hướng tiếp cận luật kết hợp là một trong những vấn đề được nhiều người quan tâm trong lĩnh vực khai phá dữ liệu, bởi sự đơn giản và dễ hiểu của nó. Mục đích của nó là tìm ra các luật tiềm ẩn trong cơ sở dữ liệu. Khai phá luật kết hợp đa cấp là sự mở rộng khám phá luật kết hợp ở mức đơn với một cấu trúc phân lớp trên những dữ liệu được lưu trữ
Xuất phát từ thực trạng đó, tôi đã chọn đề tài “Khai phá luật kết hợp đa cấp và ứng dụng ở trường Đại học Quảng Bình” làm đề tài luận văn của mình.
2. Mục tiêu nghiên cứu
Nghiên cứu về khai phá luật kết hợp đa cấp và ứng dụng vào khai dữ liệu ở trung tâm học liệu trường Đại học Quảng Bình.
3. Đối tượng và phạm vi nghiên cứu
- Đối tượng:
- Luật kết hợp đa cấp.
- Thuật toán khai phá luật kết hợp đa cấp.
- Dữ liệu về thông tin mượn sách của sinh viên ở Trung tâm học liệu trường Đại học Quảng Bình.
- Phạm vi nghiên cứu:
- Nghiên cứu thuật toán khai phá luật kết hợp đa cấp.
- Ứng dụng thuật toán khai phá luật kết hợp đa cấp vào khai phá dữ liệu ở trung tâm học liệu trường Đại học Quảng Bình.
- Nghiên cứu lý thuyết:
- Tổng hợp và nghiên cứu các tài liệu liên quan luật kết hợp đa cấp và khai phá luật kết hợp đa cấp.
- Thu thập, thống kê số liệu từ nguồn dữ liệu lưu trữ ở trường Đại học Quảng Bình.
- Nghiên cứu thuật toán khai phá luật kết hợp đa cấp.
- Nghiên cứu thực nghiệm:
- Nghiên cứu ngôn ngữ lập trình để cài đặt thuật toán mô phỏng trên một cơ sở dữ liệu cụ thể.
- Đánh giá kết quả đạt được.
- Tổng quan về khai phá luật kết hợp.
- Khai phá luật kết hợp đa cấp.
- Ứng dụng quản lý trung tâm học liệu.
6. Tổng quan tài liệu nghiên cứuCHƯƠNG 1
KHAI PHÁ LUẬT KẾT HỢP
1.1. LUẬT KẾT HỢP
1.1.1. Giới thiệu
1.1.2. Các khái niệm cơ bản
1.1.3. Phân loại luật kết hợp
1.1.4. Khai phá luật kết hợp
1.2. KHAI PHÁ LUẬT KẾT HỢP BẰNG THUẬT TOÁN APRIORI
1.2.1. Tìm tập mục phổ biến bằng thuật toán Apriori
1.2.2. Cách sinh luật từ tập mục phổ biến
1.3. MỘT SỐ THUẬT TOÁN KHÁC ĐỂ KHAI PHÁ LUẬT KẾT HỢP
1.3.1. Thuật toán khai phá luật kết hợp tuần tự
1.3.2. Thuật toán khai phá luật kết hợp song song
1.3.3. Thuật toán khai phá luật kết hợp phân tán
1.3.4. Thuật toán khai phá luật kết hợp đa mức với tập mục thường xuyên sử dụng phương pháp dựa trên cây
FP-Tree
1.4. KẾT CHƯƠNG 1
KHAI PHÁ LUẬT KẾT HỢP ĐA CẤP
2.1. LUẬT KẾT HỢP ĐA CẤP
2.1.1. Khái quát về luật kết hợp đa cấp
Các nghiên cứu trước đây của việc khám phá dữ liệu thường tập trung trong khám phá những tri thức tại mức khái niệm đơn. Tuy nhiên, trong thế giới thực tại luôn tồn tại những sự phân cấp dữ liệu hay phân lớp các khái niệm với nhau. Do đó những tri thức được khám phá cũng được phân biệt theo mức độ cũa mẫu dữ liệu được khám phá. Tri thức được xem tại mức nguyên thủy nếu những mẫu chỉ liên quan đến dữ liệu bên trong cơ sở dữ liệu. Còn những tri thức được xem là ở mức tổng quát nếu những mẫu liên quan đến những khái niệm mức cao, thông thường là sự trừu tượng hạy sự tổng quát của các khái niệm tại mức nguyên thủy trong dữ liệu gốc. [1]
Đối với nhiều ứng dụng, thì đó là sự khác nhau để tìm ra các luật kết hợp mạnh giữa các mục dữ liệu ở mức nguyên thủy hoặc mức tổng quát. Các luật kết hợp mạnh được phát hiện ở mức cao có thể đại diện cho kiến thức thông thường. Các hệ thống khai phá dữ liệu phải cung cấp khả năng cho các luật kết hợp ở nhiều mức khác nhau.
[1] Có thể nói việc khai phá luật kết hợp đa cấp là sự mở rộng khai phá luật kết hợp ở mức độ đơn với một cấu trúc phân lớp (taxonomy) trên những dữ liệu được lưu trữ. Trong đó cấu trúc phân lớp này được xây dựng dựa trên các tiêu chuẩn như sự trừu tượng, tổng quát hóa, hay sự phân loại trên các dữ liệu
Một hệ thống cấu trúc phân lớp là một dãy tuần tự từ các tập khái niệm mức thấp đến tập khái niệm mức cao hơn. Dữ liệu có thể được tổng quát hóa bằng cách thay thế các khái niệm mức thấp bởi các khái niệm mức cao hơn hoặc xa hơn. Các mức trong hệ thống phân lớp được đánh dấu từ trên xuống dưới hoặc từ dưới lên trên.
2.1.2. Sự cải tiến của luật kết hợp đa cấp so với luật kết hợp đơn
Các luật được tạo ra từ khai phá luật kết hợp với khái niệm phân cấp được gọi là luật kết hợp đa cấp. [4]
2.1.3. Phương pháp để khai phá luật kết hợp đa cấp
– Sử dụng độ hỗ trợ tối thiểu đồng nhất cho tất cả các cấp: Cùng độ hỗ trợ tối thiểu được sử dụng khi khai thác ở mỗi cấp trừu tượng.
Khi thống nhất độ hỗ trợ tối thiểu, các thủ tục tìm kiếm là đơn giản. Phương pháp này cũng đơn giản khi mà người dùng được yêu cầu xác định chỉ với một độ hỗ trợ tối thiểu. Một kỹ thuật tối ưu hóa có thể được thông qua bằng cách tìm kiếm tránh kiểm tra các tập mục phổ biến có chứa bất kỳ mục nào mà cha của nó không có độ hỗ trợ tối thiểu.
Cấp 1
Minsup=30%
Cấp 2
Minsup=30%
Hình 2.1. Khai phá luật kết hợp đa cấp với độ hỗ trợ đồng nhất
Tuy nhiên, các phương pháp tiếp cận các cấp có độ hỗ trợ đồng nhất có một số khó khăn. Không chắc chắn mục ở mức trừu tượng cấp thấp hơn sẽ xảy ra thường xuyên như những mức trừu tượng ở cấp cao hơn. Nếu độ hỗ trợ đặt quá cao, nó có thể bỏ qua một số kết hợp có ý nghĩa ở mức trừu tượng xảy ra ở các cấp thấp. Nếu độ hỗ trợ đặt quá thấp, nó có thể tạo ra nhiều kết hợp không hợp lý ở mức độ trừu tượng cấp cao. Điều này cung cấp động lực cho các phương pháp sau.
– Giảm độ hỗ trợ tối thiểu ở mức thấp hơn:
Cấp 1
Minsup=30%
Cấp 2
Minsup=15%
Hình 2.2. Khai phá luật kết hợp đa cấp với độ hỗ trợ giảm dần
+ Giảm độ hỗ trợ – Độc lập theo từng cấp: Đây là việc tìm kiếm đầy đủ theo chiều rộng, nơi mà việc xác định tập mục thường xuyên được bỏ qua. Mỗi nút được kiểm tra, bất kể cha của nó có phải là tập mục phổ biến không.
+ Giảm dộ hỗ trợ – Vượt mức đơn: Một mục ở cấp thứ i được kiểm tra nếu và chỉ nếu nút của nó tại cấp i-1 là phổ biến. Nếu một nút là phổ biến thì nút đó sẽ được kiểm tra, nếu không, con cháu của nó được cắt bỏ.
Cấp 1
Minsup=65%
Cấp 2
Minsup=30%
Hình 2.3. Khai phá luật kết hợp đa cấp với độ hỗ trợ giảm dần có sử dụng vượt mức đơn
+ Giảm độ hỗ trợ – vượt mức k- tập mục: Một k tập mục ở cấp thứ i được kiểm tra nếu và chỉ nếu nó tương ứng với k- tập mục cha ở cấp i-1 là phổ biến.
Cấp 1
Minsup=30%
Cấp 2
Minsup=15%
Hình 2.4. Khai phá luật kết hợp đa mức với mức độ hỗ trợ giảm dần có sử dụng vượt mức theo k- tập mục
2.2. THUẬT TOÁN KHAI PHÁ LUẬT KẾT HỢP ĐA CẤP DỰA TRÊN MA TRẬN LOGIC
2.2.1. Định nghĩa và mệnh đề
Định nghĩa 1: Ma trận logic: Là một ma trận mà trong ma trận đó chỉ có hai giá trị là “0” và “1”.
Định nghĩa 2: Phép toán logic AND: là phép toán được xác định như sau:
0 and 0 = 0; 0 and 1 = 0; 1 and 0 = 0; 1 and 1 = 1
Bảng 2.1. Bảng chân lý của phép toán logic AND
| A | B | A and B |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
2.2.2. Chi tiết thuật toán MLBM
Đầu vào: Tập I, tập giao tác D, tập mục mã hóa ở các cấp khái niệm khác nhau, ngưỡng minsup từng cấp khái niệm.
Đầu ra: Tất cả tập mục phổ biến ở các cấp khái niệm khác nhau.
Thuật toán [6]:
Bước 1: Mã hóa cây phân cấp sử dụng một dãy số và ký hiệu *.
Bước 2: Thiết lập H = 1, với H được sử dụng để lưu trữ số cấp được xử lý và H{1,2,3,…}
Bước 3: Chuyển đổi cơ sở dữ liệu thành ma trận logic
Bước 4: Xác định độ hỗ trợ tối thiểu (minsup) cho mỗi cấp khác nhau (Người dùng tự đưa ra)
Bước 5: Tạo tập 1-tập mục phổ biến L1 ở cấp 1.
Bước 6: Tỉa ma trận logic
Bước 7: Thực hiện phép toán AND để tạo ra 2-tập mục và 3-tập mục và k-tập mục ở cấp H.
Bước 8: Tăng giá trị H lên một đơn vị. Từ tập mục Lk quay lại bước 4 để lặp lại toàn bộ quá trình xử lý cho cấp tiếp theo.
Cụ thể các bước trong thuật toán:
b. Chuyển đổi cơ sở dữ liệu thành ma trận logic
Giả sử D là cơ sở dữ liệu được khai thác, với D có m giao tác và n tập mục. Gọi T = {T1, T2, …, Tm} là tập các giao tác và I = {I1, I2,…,In} là tập các tập mục. Tạo ma trận Am*n, với m là số hàng và n là số cột. Duyệt cơ sở dữ liệu D, nếu tập mục Ij có trong giao tác Ti thì phần tử Aij có giá trị là 1 ngược lại Aij có giá trị là 0. [6]
c. Tạo tập 1-tập mục phổ biến L1 ở cấp 1
Ma trận logic Am*n được duyệt và tính độ hỗ trợ cho tất cả các mục. Nếu tập mục Ij có độ hỗ trợ nhỏ hơn minsup thì tập mục Ij không phải là tập mục phổ biến. [6]
Tỉa ma trận logic có nghĩa là xóa đi một vài cột trong ma trận logic. Cụ thể: Ma trận logic Am*n được duyệt và tính độ hỗ trợ cho tất cả các mục. Nếu tập mục Ij có độ hỗ trợ nhỏ hơn minsup thì cột j trong ma trận logic sẽ bị xóa khỏi ma trận Am*n. [6]
e. Tạo tập k-tập mục phổ biến Lk
Từ ma trận (k-1)-tập mục phổ biến ta thực hiện phép toán AND để tạo ra ma trận k-tập mục ứng cử (giả sử tập k-tập mục ứng cử có n tập mục). Sau đó, từ ma trận Am*n tính độ hỗ trợ của từng tập mục, tập mục nào có độ hỗ trợ nhỏ hơn minsup thì bị loại bỏ khỏi ma trận Am*n, tập mục nào có độ hỗ trợ lớn hơn hoặc bằng minsup thì đưa vào tập k-tập mục phổ biến Lk [6].
F:\DỮ LIỆU COP CỦA CHỊ YẾN\DAI HOC DA NANG\LUAN VAN 2015\KHOA HOC MAY TINH\PHAN THI HUYEN TRANG
