Luận án Hệ tư vấn dựa trên phân tích hàm ý thống kê

erage, Leverage 1 Mutual Information MI, 2-way Support Variation Specificity 1, Negative Reliability Zhang Zhang Directed Information ratio (DIR) MGK, Ion 44 Từ kết quả Bảng 2.2 cho thấy, lớp các độ đo hấp dẫn khách quan biến thiên tăng theo tham số n chiếm hơn 50% số lƣợng các độ đo đƣợc khảo sát. Kết quả này cho thấy giá trị hấp dẫn của các độ đo phụ thuộc vào kích thƣớc của tập dữ liệu dùng để khảo sát. Điều này có nghĩa là tỷ lệ biến thiên của các độ đo thuộc lớp này phụ thuộc vào tỷ lệ biến thiên của tham số n. Ngƣợc lại, lớp các độ đo có khuynh hƣớng biến thiên giảm theo tham số n chiếm số lƣợng khá nhỏ. Nó bao gồm các độ đo: Coverage, Descriptive-Confirm, Gain, Fukuda, Implication index, Prevalence, Putative Causal Dependency, K-measures. Lớp các độ đo không phụ thuộc vào tham số n là một lớp đặc biệt bởi hầu hết các độ đo thuộc lớp này là các độ đo thỏa tính chất mô tả (descriptive). Nó bao gồm các độ đo: Confidence, Descriptive, Confirmed-Confidence, Ganascia Index, Examples and counter-examples rate, IPEE, Kulczynski index, Laplace, Least contradiction, Recall, Completeness, Sebag and Schoenauer. Nếu một độ đo thỏa tính chất mô tả thì giá trị hấp dẫn của nó sẽ không phụ thuộc vào tham số n hay nói cách khác là giá trị hấp dẫn của độ đo này không phụ thuộc vào kích thƣớc của tập dữ liệu dùng để khảo sát. Điều này cho thấy kết quả phân lớp các độ đo dựa trên tham số hàm ý thống kê có sự tƣơng đồng về kết quả với phƣơng pháp phân lớp các độ đo dựa trên các thuộc tính. Cuối cùng, hai độ đo Directed Information ratio (DIR) và MGK là lớp các độ đo có giá trị hấp dẫn biến thiên phụ thuộc vào giá trị cụ thể của tham số n. Hình 2.2.5So sánh sự biến thiên của độ đo Implication index và độ đo Implication intensity theo tham số n ̅ 45 Hình 2.2 biểu diễn sự biến thiên giảm của độ đo Implication index và sự biến thiên tăng của độ đo Implication intensity. Đây là hai độ đo đại diện cho lớp các độ đo có sự biến thiên theo tham số n. 2.4.2. Kết quả phân lớp các độ đo dựa trên đạo hàm riêng theo Dựa trên dữ liệu khảo sát giá trị đạo hàm riêng theo tham , các độ đo đƣợc phân lớp theo các quy tắc đã trình bày trong phần 2.3.2. Kết quả phân lớp các độ đo theo tham số đƣợc trình bày trong Bảng 2.3. Bảng 2.3.4Kết quả phân lớp các độ đo dựa trên đạo hàm riêng theo Giảm Độc lập Tăng Khác Implication index Probabilistic measures of deviation from equilibrium (IPEE), Indice Probabiliste d’Ecart d’Equilibre Leverage, Leverage 1 Prevalence 1-way Support Added value, Pavillon, Centred Confidence, Dependency Bayes factor, Odd multiplier Causal-Confidence Causal-Confirmed confidence Loevinger, Certainty Factor, Satisfaction Confidence Causal Confirm Conviction Coverage Descriptive Confirmed-Confidence, Ganascia Index Descriptive-Confirm Entropic Implication Intensity 1 Entropic Implication Intensity 2 Examples and counter-examples rate Gain, Fukuda Gini index Goodman–Kruskal Implication Intensity MGK, Ion J-measures Klosgen K-measures Kulczynski index Laplace Least contradiction Mutual Information MI, 2-way Support Variation Putative Causal Dependency Recall, Completeness Sebag and Schoenauer Specificity 1, Negative Reliability Zhang Zhang Relative Risk , Class correlation ratio Collective strength Directed Information ratio (DIR) 46 Từ kết quả phân lớp trong Bảng 2.3 cho thấy lớp các độ đo hấp dẫn khách quan bất đối xứng biến thiên tăng theo tham số chiếm tỷ lệ rất cao trong tổng số các độ đo đƣợc khảo sát (31/39). Điều này có thể thấy rằng giá trị hấp dẫn của các độ đo dựa trên luật kết hợp phụ thuộc vào số phần tử thỏa vế trái của luật kết hợp ( ). Khi tham số tăng thì giá trị hấp dẫn của các độ đo thuộc lớp này tăng. Trong đó, nhóm các độ đo có nguồn gốc từ độ đo Confidence đều thuộc lớp các độ đo tăng theo tham số . Điều này phù hợp với nguyên tắc xác định độ tin cậy của một luật kết . Ngƣợc lại, lớp các độ đo biến thiên giảm theo tham số chiếm tỷ lệ rất nhỏ (3/39). Nó bao gồm ba độ đo thỏa tính chất thống kê: Implication index, IPEE, Leverage. Các độ đo Relative Risk, Collective strength, Directed Information ratio (DIR) thuộc lớp các độ đo có sự biến thiên phụ thuộc vào giá trị cụ thể của tham số . Khi giá trị của tham số tăng thì giá trị hấp dẫn của các độ đo này thể hiện ở ba trạng thái khác nhau: biến thiên tăng, ổn định và biến thiên giảm. Lớp cuối cùng chỉ chứa duy nhất một độ đo là Prevalence. Độ đo này hoàn toàn độc lập với tham số . Hình 2.3.6Biểu diễn sự biến thiên giảm của độ đo Implication index theo tham số ̅ 47 Độ đo Implication index là một độ đo biến thiên giảm theo tham số . Sự biến thiên giảm của độ đo này đƣợc biểu diễn trong Hình 2.3. Đây là độ đo đại diện cho lớp các độ đo có khuynh hƣớng biến thiên giảm theo tham số . 2.4.3. Kết quả phân lớp các độ đo dựa trên đạo hàm riêng theo Dựa trên dữ liệu khảo sát giá trị đạo hàm riêng theo tham , các độ đo đƣợc phân lớp theo các quy tắc đã trình bày trong phần 2.3.2. Kết quả phân lớp các độ đo theo tham số đƣợc trình bày trong Bảng 2.4. Bảng 2.4.5Kết quả phân lớp các độ đo dựa trên đạo hàm riêng theo Giảm Độc lập Tăng Khác 1-way Support Added value, Pavillon, Centred Confidence, Dependency Bayes factor, Odd multiplier Causal-Confidence Causal-Confirmed confidence Loevinger, Certainty Factor, Satisfaction Relative Risk , Class correlation ratio Collective strength Causal Confirm Conviction Entropic Implication Intensity 1 Entropic Implication Intensity 2 Gini index Goodman–Kruskal Implication Intensity J-measures Klosgen Kulczynski index Least contradiction Leverage, Leverage 1 Mutual Information MI, 2-way Support Variation Putative Causal Dependency Recall, Completeness Specificity 1, Negative Reliability Zhang Zhang Confidence Coverage Descriptive Confirmed- Confidence , Ganascia Index Descriptive-Confirm Examples and counter- examples rate Gain, Fukuda Probabilistic measures of deviation from equilibrium (IPEE), Indice Probabiliste d’Ecart d’Equilibre Laplace Sebag and Schoenauer Implication index K-measures Prevalence Directed Information ratio (DIR) MGK, Ion Từ kết quả phân lớp trong Bảng 2.4 cho thấy lớp các độ đo hấp dẫn khách quan biến thiên giảm theo tham số chiếm tỷ lệ khá lớn trong tổng số các độ đo đƣợc khảo sát (24/39). Kết quả này hoàn toàn phù hợp với các quy tắc dùng để xác 48 định giá trị hấp dẫn của luật kết hợp do các độ đo đƣợc khảo sát là các độ đo thỏa tính chất bất đối xứng. Khi giá trị của tham số tăng thì giá trị hấp dẫn của các độ đo này có khuynh hƣớng giảm. Tƣơng tƣ nhƣ trƣờng hợp phân lớp dựa trên đạo hàm riêng theo tham số n, các độ đo thỏa tính chất mô tả nhƣ Confidence, Coverage, Descriptive Confirmed-Confidence, Descriptive-Confirm, Examples and counter-examples rate, Gain, IPEE, Laplace, Sebag and Schoenauer đƣợc xếp vào lớp các độ đo độc lập với tham số . Lớp các độ đo biến thiên tăng theo tham số gồm hai độ đo: Implication index, K-measures và Prevalence. Ba độ đo này có khuynh hƣớng tăng khi số phần tử thỏa vế phải của luật kết hợp tăng ( ). Kết quả này phản ánh chính xác ý nghĩa thống kê của ba độ đo này. Cuối cùng, lớp các độ đo có sự biến thiên phụ thuộc vào giá trị cụ thể của tham số gồm hai độ đo Directed Information ratio (DIR) và MGK. Kết quả này hoàn toàn giống với kết quả phân lớp với tham số n đã thực hiện ở phần trên. Hình 2.4.7Biểu diễn sự độc lập của độ đo Laplace theo tham số ̅ Độ đo Laplace là một độ đo độc lập với tham số . Sự độc lập với giá trị tham số của độ đo này đƣợc biểu diễn trong Hình 2.4. Đây là một độ đo đại diện cho lớp các độ đo độc lập theo tham số . 2.4.4. Kết quả phân lớp các độ đo dựa trên đạo hàm riêng theo Dựa trên dữ liệu khảo sát giá trị đạo hàm riêng theo tham ̅, các độ đo đƣợc phân lớp theo các quy tắc đã trình bày trong phần 2.3.2. Kết quả phân lớp các độ đo theo tham số ̅ đƣợc trình bày trong Bảng 2.5. 49 Bảng 2.5.6Kết quả phân lớp các độ đo dựa trên đạo hàm riêng theo Giảm Độc lập Tăng Khác 1-way Support Added value, Pavillon, Centred Confidence, Dependency Bayes factor, Odd multiplier Causal-Confidence Causal-Confirmed confidence Loevinger, Certainty Factor, Satisfaction Relative Risk , Class correlation ratio Collective strength Confidence Causal Confirm Conviction Descriptive Confirmed-Confidence , Ganascia Index Descriptive-Confirm Entropic Implication Intensity 1 Entropic Implication Intensity 2 Examples and counter-examples rate Gain, Fukuda Implication Intensity MGK, Ion Klosgen K-measures Kulczynski index Laplace Least contradiction Leverage, Leverage 1 Putative Causal Dependency Recall, Completeness Sebag and Schoenauer Specificity 1, Negative Reliability Zhang Zhang Coverage Probabilistic measures of deviation from equilibrium (IPEE), Indice Probabiliste d’Ecart d’Equilibre Prevalence Implication index Directed Information ratio (DIR) Gini index Goodman–Kruskal J-measures Mutual Information MI, 2-way Support Variation Bảng 2.5 cho thấy lớp các độ đo hấp dẫn khách quan biến thiên giảm theo tham số ̅ chiếm tỷ lệ 71%. Điều này phản ánh đúng vai trò của tham số ̅ trong việc xác định giá trị hấp dẫn của luật kết hợp khi số lƣợng phản ví dụ càng tăng thì giá trị hấp dẫn của luật kết hợp càng giảm. Trong lớp này, có nhiều độ đo có nguồn gốc từ độ đo Confidence. Một độ đo rất phổ biến đƣợc dùng để xác định độ tin cập của luật kết hợp theo công thức: ̅ . Từ công thức 50 này ta thấy rằng tham số ̅ luôn tỷ lệ nghịch với độ tin cậy của luật kết hợp. Lớp các độ đo độc lập với tham số ̅ chiếm tỷ lệ khá nhỏ trong tổng số các độ đo đƣợc khảo sát. Nó bao gồm ba độ đo: Coverage, IPEE và Prevalence. Lớp các độ đo biến thiên tăng theo tham số ̅ chỉ có duy nhất một độ đo (implication index). Kết quả phân lớp này cho thấy tính đặc trƣng của độ đo Implication index so với các độ đo hấp dẫn khách quan khác trong việc xác định độ hấp dẫn của luật kết hợp. Thay vì quan tâm đến số lƣợng các ví dụ hỗ trợ việc hình thành của luật kết hợp, thì độ đo này quan tâm đến số lƣợng các phản ví dụ có khuynh hƣớng không hỗ trợ việc hình thành của luật kết hợp. Khi đó, một luật kết hợp sẽ bị bác bỏ nếu số lƣợng phản ví dụ vƣợt ngƣỡng cho phép. Lớp cuối cùng bao gồm 5 độ đo: Directed Information ratio (DIR), Gini index, Goodman–Kruskal, J-measures, Mutual Information MI. Trong đó, giá trị biến thiên của độ đo DIR phụ thuộc vào điều kiện ràng buộc của hai biểu thức ̅ và , các độ đo còn lại có giá trị biến thiên phụ thuộc vào giá trị cụ thể của tham số ̅. Hình 2.5.8Biểu diễn sự phụ thuộc giá trị của độ đo J-measures theo tham số ̅ ̅ Giá trị biến thiên của độ đo J-measures phụ thuộc giá trị chi tiết của tham số ̅. Giá trị biến thiên của độ đo này đƣợc biểu diễn trong Hình 2.5. Độ đo này đại 51 diện cho lớp các độ đo có giá trị biến thiên phụ thuộc vào giá trị cụ thể của tham số ̅. 2.5. So sánh và đánh giá kết quả phân lớp theo tham số hàm ý thống kê Từ kết quả phân lớp các độ đo hấp dẫn khách quan theo tham số hàm ý thống kê cho thấy có một số điểm tƣơng đồng so với kết quả phân lớp các độ đo dựa trên các thuộc tính [35]: - Lớp các độ đo độc lập với tham số n theo phƣơng pháp phân lớp theo tham số hàm ý thống kê đƣợc xếp vào lớp các độ đo thỏa tính chất mô tả (descriptive) theo phƣơng pháp phân lớp dựa trên thuộc tính của độ đo. Điều này chứng minh rằng kết quả phân lớp các độ đo theo tham số hàm ý thống kê có kết quả đáng tin cậy. - Phần lớn các độ đo thỏa tính chất bất đối xứng đều tăng theo tham số và giảm theo tham số khi tính giá trị dựa trên luật kết hợp. Điều này có thể thấy rằng giá trị hấp dẫn của các độ đo dựa trên luật kết hợp tăng theo số phần tử thỏa vế trái của luật kết hợp ( ) và giảm theo số phần tử thỏa vế phải của luật kết hợp ( ). - Lớp các độ đo thỏa tính chất thống kê (statistical) luôn biến thiên tăng hoặc giảm với các tham số hàm ý thống kê. Ví dụ, trong phân lớp dựa trên tham số hàm ý thống kê, độ đo chỉ số hàm ý thống kê và cƣờng độ hàm ý thống kê biến thiên theo tham số ̅, trong phân lớp dựa trên thuộc tính thì hai độ đo này thuộc lớp các độ đo thỏa tính chất thống kê. Dựa trên kết quả phân lớp, luận án đề xuất một số hƣớng sử dụng kết quả phân lớp độ đo cho các mô hình tƣ vấn nhƣ sau: - Các độ đo độc lập với tham số n có thể ứng dụng tốt trong các hệ thống có tổng số ngƣời dùng không ổn định. Khi đó, việc xác định giá trị hấp dẫn của luật kết hợp trong hệ thống chỉ quan tâm đến ba tham số ̅ - Các độ đo bất đối xứng biến thiên tăng theo tham số và biến thiên giảm theo tham số có thể ứng dụng tốt trong các mô hình tƣ vấn dựa trên luật kết hợp do phần lớn các độ đo thuộc nhóm này là các độ đo dành cho luật kết hợp. 52 - Trong kết quả phân lớp với tham số ̅ , độ đo chỉ số hàm ý thống kê (implication index) và độ đo cƣờng độ hàm ý thống kê (implication intensity) có khuynh hƣớng biến thiên trái ngƣợc nhau khi số lƣợng phản ví dụ tăng lên (tham số ̅ ). Kết quả trên cho thấy một điểm đặc biệt của hai độ đo đƣợc đề xuất từ phƣơng pháp phân tích hàm ý thống kê trong việc xác định giá trị hấp dẫn của luật kết hợp trong các mô hình tƣ vấn. 2.6. Kết luận chƣơng 2 Trong chƣơng này, thông qua việc khảo sát giá trị đạo hàm riêng của hàm tính giá trị hấp dẫn của độ đo theo các tham số hàm ý thống kê, luận án đề xuất phƣơng pháp phân lớp các độ đo hấp dẫn khách quan dựa trên tiếp cận bất đối xứng sử dụng các tham số hàm ý thống kê và triển khai phân lớp 39 độ đo hấp dẫn khách quan bất đối xứng. Kết quả phân lớp của 39 độ đo hấp dẫn khách quan bất đối xứng theo phƣơng pháp phân lớp độ đo do luận án đề xuất có nhiều điểm tƣơng đồng so với phƣơng pháp phân lớp các độ đo dựa trên thuộc tính. Từ kết quả này luận án đã đƣa ra định hƣớng sử dụng các độ đo trong các mô hình tƣ vấn cho phép lựa chọn độ đo hấp dẫn khách quan phù hợp khi biết đƣợc tính biến thiên tăng, giảm của từng độ đo theo các tham số hàm ý ‎thống kê. 53 CHƢƠNG 3. MÔ HÌNH TƢ VẤN DỰA TRÊN CHỈ SỐ HÀM Ý THỐNG KÊ Kết quả phân lớp các độ đo hấp dẫn khách quan bất đối xứng trong chƣơng 2 cho thấy độ đo chỉ số hàm ý thống kê là độ đo duy nhất có khuynh hƣớng biến thiên tăng theo tham số ̅ (số lƣợng phản ví dụ). Điều này phản ánh chỉ số hàm ý thống kê có ý nghĩa rất đặc biệt trong việc đánh giá chất lƣợng tri thức dƣới dạng luật kết hợp. Xuất phát từ nhận định trên, trong chƣơng này, luận án đề xuất mô hình tƣ vấn dựa trên tiếp cận bất đối xứng sử dụng luật kết hợp, độ đo chỉ số hàm ý thống kê và đạo hàm riêng theo các tham số hàm ý thống kê. Để khắc phục các nhƣợc điểm của mô hình tƣ vấn truyền thống, mô hình này đặc biệt quan tâm đến tỷ lệ hay mối quan hệ bất đối xứng giữa các thuộc tính điều kiện và các thuộc tính quyết định trên cùng một đối tƣợng ngƣời dùng. Từ giá trị hấp dẫn của độ đo chỉ số hàm ý thống kê và giá trị đạo hàm riêng theo các tham số hàm ý thống kê trên tập luật kết hợp đã chọn, mô hình đƣa ra kết quả tƣ vấn giúp ngƣời dùng lựa chọn giá trị cho các thuộc tính quyết định. Kết quả nghiên cứu của chƣơng này đƣợc công bố tại Hội nghị Quốc gia lần thứ VIII về Nghiên cứu cơ bản và ứng dụng Công nghệ Thông tin (FAIR’8) năm 2015 (1) và Hội thảo quốc gia lần thứ XVIII: Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông, chủ đề: xử lý dữ liệu lớn năm 2015 (2). 3.1. Luật kết hợp dựa trên thuộc tính quyết định 3.1.1. Định nghĩa luật kết hợp dựa trên thuộc tính quyết định Gọi { } là tập n ngƣời dùng, trong đó mỗi ngƣời dùng đƣợc lƣu trữ nhƣ một giao dịch, đƣợc xem là cơ sở dữ liệu giao dịch; { } là tập m thuộc tính của mỗi ngƣời dùng, trong đó { } là tập các thuộc tính điều kiện, { } là tập các thuộc tính quyết định. Một luật kết hợp dựa trên tập thuộc tính quyết định đƣợc sinh từ cơ sở dữ liệu giao dịch là một biểu thức hàm ý có dạng: 54 { | | | | | } 3.1.2. Thuật toán sinh luật kết hợp dựa trên thuộc tính quyết định Thuật toán sinh luật kết hợp dựa trên thuộc tính quyết định hoàn toàn dựa trên thuật toán sinh luật kết hợp Apriori [70], nhƣng chỉ quan tâm đến các luật kết hợp có vế phải chứa các thuộc tính quyết định. Thuật toán gồm 2 giai đoạn: Giai đoạn 1: Dựa trên ngƣỡng độ đo Support (min_sup) để tìm các tập thuộc tính phổ biến: Đầu tiên tìm tập 1 thuộc tính (ký hiệu ). đƣợc dùng để tìm tập 2 thuộc tính (ký hiệu ). đƣợc dùng để tìm tập 3 thuộc tính (k‎ý hiệu ) và tiếp tục cho đến khi không còn tìm thấy tập k thuộc tính (ký hiệu ). Giai đoạn 2: Dựa trên ngƣỡng độ đo Confidence (min_conf) để sinh ra các luật kết hợp mạnh có vế phải là thuộc tính quyết định cho mô hình tƣ vấn từ các tập thuộc tính phổ biến. Thuật toán sinh luật k t h p dựa trên thuộc tính quy t ịnh Input: Tập dữ li u giao dị n ời dùng . Output: Tập luật k t h p o mô ìn t vấn. Begin c 1: Duy t toàn bộ tập ể x ịnh support của mỗi ứng viên trong tập 1 thuộc tính, so sánh v m n_sup ể ó c tập 1 thuộc tính ( ). c 2: Sử dụng n i (join) ể sinh ra phần tử ứng viên của tập thuộc tính. Loại bỏ các tập không ph i là tập ph bi n t t u c tập thuộc tính. c 3: Duy t toàn bộ tập ể x ịnh Support của mỗi ứng viên trong tập thuộc tính, so sánh v m n_sup ể t u c tập k thuộc tính ph bi n ( ). c 4: Lặp lại từ o n khi tập ứng viên sinh ra là rỗng. c 5: V i mỗi tập ph bi n , sinh các tập con không rỗng của . c 6: V i mỗi tập con không rỗng của , sinh ra các luật: { | { } on n m n_ on } End. Ví dụ 3.1. Giả sử ta có tập dữ liệu dùng để phân nhóm thí sinh gồm 3 thuộc tính: { }; tập thuộc tính điều kiện { }; tập thuộc tính quyết 55 định { } ; trong đó, { }; { }; { } đƣợc trình bày trong Bảng 3.1. Bảng 3.1.7Tập dữ liệu phân nhóm thí sinh 2 1.0 A 1 1.5 A 1 1.5 A 1 1.5 A 3 0.5 B 2 1.0 A 3 0.5 B 3 0.5 B 2 1.0 A 2 1.0 A Áp dụng thuật toán sinh luật kết hợp dựa thuộc tính quyết định với MinSupp = 0.01 và MinConf = 0.5 gồm các bƣớc sau: Tìm tập phổ biến 1 phần tử: Duyệt tập dữ liệu để tính Support cho tập 1 phần tử và so sánh với MinSupp để xác định tập phổ biến 1 phần tử. Kết quả đƣợc trình bày trong Bảng 3.2. Bảng 3.2.8Kết quả sinh tập phổ biến 1 phần tử 1-items Support 1-items Support {i1=1} 0.3 {i1=1} 0.3 {i1=2} 0.4 {i1=2} 0.4 {i1=3} 0.3 Support 0.01 {i1=3} 0.3 {i2=1.0} 0.4 {i2=1.0} 0.4 {i2=1.5} 0.3 {i2=1.5} 0.3 {i2=0.5} 0.3 {i2=0.5} 0.3 {i3=A} 0.7 {i3=A} 0.7 {i3=B} 0.3 {i3=B} 0.3 Tìm tập phổ biến 2 phần tử: Từ tập phổ biến 1 phần tử sinh tập 2 phần tử, duyệt tập dữ liệu để tính Support cho tập 2 phần tử, so sánh với MinSupp để xác định tập phổ biến 2 phần tử. Kết quả đƣợc trình bày trong Bảng 3.3. Bảng 3.3.9Kết quả sinh tập phổ biến 2 phần tử 2-items Support 2-items Support {i1=1, i1=2} 0.0 {i1=3, i2=1.5} 0.0 {i1=1, i1=3} 0.0 {i1=3, i2=0.5} 0.3 2-items Support {i1=1, i2=1.0} 0.0 {i1=3, i3=A} 0.0 {i1=1, i2=1.5} 0.3 {i1=1, i2=1.5} 0.3 {i1=3, i3=B} 0.3 {i1=1, i3=A} 0.3 {i1=1, i2=0.5} 0.0 {i2=1.0, i2=1.5} 0.0 {i1=2, i2=1.0} 0.4 {i1=1, i3=A} 0.3 {i2=1.0, i2=0.5} 0.0 Support 0.01 {i1=2, i3=A} 0.4 {i1=1, i3=B} 0.0 {i2=1.0, i3=A} 0.4 {i1=3, i2=0.5} 0.3 {i1=2, i1=3} 0.0 {i2=1.0, i3=B} 0.0 {i1=3, i3=B} 0.3 {i1=2, i2=1.0} 0.4 {i2=1.5, i2=0.5} 0.0 {i2=1.0, i3=A} 0.4 {i1=2, i2=1.5} 0.0 {i2=1.5, i3=A} 0.3 {i2=1.5, i3=A} 0.3 {i1=2, i2=0.5} 0.0 {i2=1.5, i3=B} 0.0 {i2=0.5, i3=B} 0.3 {i1=2, i3=A} 0.4 {i2=0.5, i3=A} 0.0 {i1=2, i3=B} 0.0 {i2=0.5, i3=B} 0.3 {i1=3, i2=1.0} 0.0 {i3=A, i3=B } 0.0 56 Tìm tập phổ biến 3 phần tử: Từ tập phổ biến 2 phần tử sinh tập 3 phần tử, duyệt tập dữ liệu để tính Support cho tập 3 phần tử, so sánh với MinSupp để xác định tập phổ biến 3 phần tử. Kết quả đƣợc trình bày trong Bảng 3.4. Bảng 3.4.10Kết quả sinh tập phổ biến 3 phần tử 3-items Support 3-items Support {i1=1, i2=1.5, i3=A} 0.3 {i1=2, i2=1.5, i3=B} 0.0 {i1=1, i2=1.5, i3=B} 0.0 {i1=2, i2=0.5, i3=A} 0.0 {i1=1, i2=1.0, i3=A} 0.0 {i1=2, i2=0.5, i3=B} 0.0 3-items Support {i1=1, i2=1.0, i3=B} 0.0 {i1=3, i2=0.5, i3=A} 0.0 Support 0.01 {i1=1, i2=1.5, i3=A} 0.3 {i1=1, i2=0.5, i3=A} 0.0 {i1=3, i2=0.5, i3=B} 0.3 {i1=2, i2=1.0, i3=A} 0.3 {i1=1, i2=0.5, i3=B} 0.0 {i1=3, i2=1.5, i3=A} 0.0 {i1=3, i2=0.5, i3=B} 0.3 {i1=2, i2=1.0, i3=A} 0.3 {i1=3, i2=1.5, i3=B} 0.0 {i1=2, i2=1.0, i3=B} 0.0 {i1=3, i2=1.0, i3=A} 0.0 {i1=2, i2=1.5, i3=A} 0.0 {i1=3, i2=1.0, i3=B} 0.0 Sinh Luật kết hợp dựa trên thuộc tính quyết định Từ các tập phổ biến ta sinh tập luật kết hợp dựa trên thuộc tính quyết định gồm 9 luật đƣợc trình bày trong Bảng 3.5. Bảng 3.5.11Kết quả sinh luật kết hợp dựa trên thuộc tính quyết định TT Luật kết hợp dựa trên thuộc tính quyết định Support Confidence 1 {i1=1} => {i3=A} 0.3 1.0 2 {i2=1.5} => {i3=A} 0.3 1.0 3 {i1=3} => {i3=B} 0.3 1.0 4 {i2=0.5} => {i3=B} 0.3 1.0 5 {i2=1} => {i3=A} 0.4 1.0 6 {i1=2} => {i3=A} 0.4 1.0 7 {i1=1,i2=1.5} => {i3=A} 0.3 1.0 8 {i1=3,i2=0.5} => {i3=B} 0.3 1.0 9 {i1=2,i2=1} => {i3=A} 0.4 1.0 3.2. Tham số hàm ý thống kê của luật kết hợp 3.2.1. Tham số hàm ý thống kê Giá trị hấp dẫn của một luật kết hợp dựa trên thuộc tính quyết định theo một độ đo hấp dẫn khách quan sẽ đƣợc tính dựa trên bộ các thành phần ̅ của luật kết hợp [35]: ̅ Các tham số ̅ đƣợc gọi là các tham số hàm ý thống kê. Trong đó, là tổng số giao dịch trong hệ thống; là số giao dịch có chứa ; là số giao dịch có chứa ; và ̅ là số giao dịch có chứa nhƣng không chứa . 57 3.2.2. Tham số hàm ý thống kê dựa trên ma trận nhị phân Để xác định giá trị các tham số ̅ của từng luật kết hợp, luận án đề xuất phƣơng pháp chuyển đổi tập dữ liệu giao dịch và tập luật kết hợp sang dạng ma trận thƣa nhị phân (binary sparse matrix) [10]. Việc chuyển đổi này có hai mục tiêu chính. Thứ nhất là phần lớn thuật toán sinh luật kết hợp đều dựa trên dữ liệu nhị phân. Điều này sẽ thuận lợi khi triển khai thực nghiệm. Thứ hai là với cấu trúc ma trận thƣa nhị phận có thể giải quyết đƣợc vấn đề không gian lƣu trữ cho các tập dữ liệu lớn và tăng tốc độ xử lý của các thuật toán của mô hình. Do, các thuật toán chỉ xử lý dữ liệu trong bộ nhớ trong thay vì phải truy xuất bộ nhớ ngoài. 3.2.2.1. Chuyển tập dữ liệu giao dịch sang ma trận thưa nhị phân Cấu ma trận dữ liệu nhị phân gồm n dòng m cột với n là tổng số giao dịch của tập dữ liệu, m là tổng số giá trị của tất cả các thuộc tính có trong tập dữ liệu giao dịch. Trong đó, mỗi giao dịch đƣợc chuyển thành một dòng ma trận, mỗi giá trị của các thuộc tính trên tập dữ liệu giao dịch sẽ thành một cột của ma trận. Các giá trị của ma trận đƣợc xác định theo nguyên tắc sau: nếu giao dịch ở dòng i có chứa giá trị thuộc tính tƣơng ứng ở cột j thì giá trị của ô(i,j) đƣợc gán bằng 1, ngƣợc lại thì giá trị của ô(i,j) đƣợc gán bằng 0. Ví dụ 3.2. Từ tập dữ liệu giao dịch đã trình bày trong Ví dụ 3.1 ta tiến hành chuyển đổi dữ liệu sang dạng ma trận nhị phân nhƣ sau: ma trận có cấu trúc 10 dòng (do tập dữ liệu có 10 giao dịch) 8 cột (do tổng số giá trị của các thuộc tính là 8: i1 có 3 giá trị, i2 có 3 giá trị, i3 có 2 giá trị); do dữ liệu giao dịch ở dòng 1 chỉ chứa các giá trị i1=2, i2=1.0, i3=A nên các ô(1,2)=1, ô(1,5)=1, ô(1,7)=1 và các ô còn lại của dòng 1 bằng 0; tƣơng tƣ nhƣ dòng 1 ta xác định giá trị cho các dòng còn lại của ma trận. Kết quả chuyển đổi đƣợc trình bày trong Bảng 3.6. Bảng 3.6.12Kết quả chuyển từ dữ liệu giao dịch sang dạng ma trận nhị phân Dữ liệu giao dịch Ma trận dữ liệu nhị phân i1=1 i1=2 i1=3 i2=1.5 i2=1.0 i2=0.5 i3=A i3=B 2 1.0 A 0 1 0 0 1 0 1 0 1 1.5 A 1 0 0 1 0 0 1 0 3 0.5 B 0 0 1 0 0 1 0 1 3 0.5 B 0 0 1 0 0 1 0 1 2 1.0 A 0 1 0 0 1 0 1 0 1 1.5 A 1 0 0 1 0 0 1 0 1 1.5 A 1 0 0 1 0 0 1 0 2 1.0 A 0 1 0 0 1 0 1 0 3 0.5 B 0 0 1 0 0 1 0 1 2 1.0 A 0 1 0 0 1 0 1 0 58 3.2.2.2. Chuyển tập luật kết hợp sang ma trận thưa nhị phân Đối với tập luật kết hợp, dữ liệu chuyển đổi sang dạng ma trận nhị phân của tập luật đƣợc chia làm 3 phần: ma trận luật nhị phân đầy đủ, ma trận luật nhị phân vế trái và ma trận luật nhị phân vế phải. Trong từng ma trận nhị phân, việc chuyển đổi đƣợc thực hiện theo nguyên tắc sau: mỗi luật kết hợp đƣợc chuyển thành một dòng của ma trận, mỗi thuộc tính xuất hiện trong vế trái hoặc vế phải của luật kết hợp đƣợc chuyển thành một cột trong ma trận. Các giá trị của ma trận đƣợc xác định theo nguyên tắc sau: nếu vế trái hoặc vế phải của luật kết hợp ở dòng i có chứa thuộc tính tƣơng ứng ở cột j thì giá trị của ô(i,j) đƣợc gán bằng 1, ngƣợc lại thì giá trị của ô(i,j) đƣợc gán bằng 0. Ví dụ 3.3. Từ tập luật kết hợp đã trình bày trong Ví dụ 3.1 ta tiến hành ch