Đặt vấn đề Do việc xác định luật kết hợp mẫu âm phải thông qua luật kết hợp dương, nếu chúng ta để độ hỗ trợ và độ tin cậy nhỏ thì sẽ rất khó để xác định các luật kết hợp dương mong muốn, bởi vậy chúng ta phải chấp nhận để độ hỗ trợ và độ tin cậy dương đủ lớn để dễ cho việc xác định luật kết hợp dương và khi đó các luật kết hợp âm tìm thấy sẽ có độ hỗ trợ và độ tin cậy thấp. Lúc này chúng ta phải chấp nhận một số kết quả tìm kiếm được sẽ không như mong muốn. Việc loại bỏ các luật không như mong muốn này 19 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com chúng ta chỉ có thể sử dụng những miền tri thức trong kho dữ liệu để dự đoán và loại bỏ chúng để cuối cùng có tập các luật kết hợp mẫu âm khả thi. Chúng ta xem xét sự phân loại sau: Giả sử T là tập các loại mặt hàng như hình trên, gồm các đỉnh và các cạnh.
Mỗi đỉnh biểu diễn một lớp (Hardware, Computers, Electronics,.), đỉnh mà không có đỉnh con(hay có độ sâu bằng 0) thì được coi là các mặt hàng. Hai đỉnh được kết nối với nhau thông qua một cạnh. Các đỉnh, cành này sẽ tạo ra một miền tri thức (domain Knowledge). Trong sự phân loại trên, có hai mối quan hệ quan trọng đó là quan hệ theo chiều dọc và quan hệ theo chiểu ngang.
Mối quan hệ theo chiều dọc là mối quan hệ cha – con, mối quan hệ theo chiều ngang là mối quan hệ anh – em. Chúng ta gọi mối quan hệ anh – em là mối quan hệ địa phương (Locality Of Similarity – LOS). Các mục cùng LOS sẽ có xu hướng tham gia vào cùng một luật kết hợp. Ví dụ trong một cơ sở dữ liệu bán lẻ, các mục cùng LOS sẽ có nhiều khả năng cùng được tham gia vào các giao dịch của khách hàng.
Do vậy trong quá trình bán hàng, người bán hàng không đưa ra những tham khảo hợp lý thì người mua hàng rất khó có thể 20 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com chọn một món hàng mà họ muốn.Thay vào đó chúng ta có thể đưa ra một tham khảo theo LOS, để khách hàng có thể chọn một số món hàng mà họ muốn. Trong hình ví dụ trên, chúng ta để „IBM Aptiva‟ và „Compaq Deskpro‟ cùng cấp và cùng thuộc dòng máy tính để bàn, khi đó khách hàng muốn mua máy tính để bàn có thể xem máy IBM Aptive hay Compaq Deskpro, thay vì khách hàng phải loay hoay với các loại như Notebook, Parks, Electronics… Như vậy LOS có thể được hiểu như là quan hệ anh – em, được biểu diễn như sau [„IBM Aptiva‟,„Compaq Deskpro‟]. Tuy nhiên LOS cũng có thể mở rộng trên cấp, chẳng hạn chúng ta có thể đặt „IBM Aptiva‟, „Compaq Deskpro‟, Notebook, Parks vào cùng một LOS khi chúng ta nhìn cơ sở dữ liệu ở tầm cao hơn (Computers). Bây giờ chúng ta xem xét các luật liên quan tới LOS.
Với giả thiết: a) Các tập X = { i1, i2,…, ih,…, im }, Y = { j1, j2,…, jl } và X, Y I, X Y= b) h I, ik X, thỏa mãn [ih , ik] và supp(ih) ≥ minsup, supp(ik) ≥ minsup. Thì khi đó cũng có một khả năng Conf(X‟Y) ≥ minconf, trong đó X‟={ i1, i2,…, ik,…, im }, cũng tương tự như X, ngoại trừ việc ih thay thế cho ik Chúng ta gọi luật X‟Y là r‟. Khi đó luật r và r‟ được gọi là luật anh em. 21 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.2 Quá trình phát hiện luật kết hợp mẫu âm LOS sẽ cung cấp một số khả năng để xác định luật âm, giả sử ih,ik I, đều là thành viên của một LOS, thỏa mãn [ih,ik].
Nếu luật r: XY đúng và ih X, khi đó sẽ sinh được luật anh em r‟: X‟Y, tuy nhiên nếu luật này không hỗ trợ, tức là Y không có mối quan hệ với X‟ thì sự kết hợp âm có thể tồn tại. Để phát hiện luật kết hợp mẫu âm, trước hết chúng ta xác định độ lệch giữa các đội tin cậy như sau: Trong đó conf(r’) là độ tin cậy của r‟ được tính toán theo công thức (4). E(conf(r’)) là dự báo độ tin cậy của r‟, được định nghĩa bằng độ tin cậy của r dựa trên các giả thiết tương tự. Nếu giá trị SM lớn thì khi đó luật X‟ Y là sai, và khi đó luật X‟ ¬Y đúng.
Từ cách lập luận trên cho thấy, với giá trị SM càng lớn thì càng cho thấy lượng thông tin lớn. Đồng thời các ứng viên luật kết hợp âm tạo ra cũng phải đáp ứng cả hai tiêu chí về độ hỗ trợ và độ tin cậy thì sẽ được giữ lại. Trên thực tế để đủ điều kiện là một luật kết hợp âm thì phải thỏa mãn hai điều kiện: - Có độ lệch lớn giữa độ tin cậy thực tế và độ tin cậy dự báo - Có độ hỗ trợ và độ tin cậy lớn hơn cực tiểu. 22 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Như vậy trong quá trình khai phá luật kết hợp mẫu âm, chúng ta có sử dụng quá trình dự đoán, nên khi khai phá luật kết hợp mẫu âm sẽ có có một số luật không mong muốn, và một trong những công việc quan trọng trong quá trình phát hiện luật kết hợp mẫu âm là loại bỏ một số luật không mong muốn.
Một ví dụ về sự loại bỏ luật dư thừa, giả sử chúng ta có hai luật “Female Buy Hat” và luật “¬Male Buy Hat”. Trong miền thuộc tính về giới tính, giả sử chỉ có hai giá trị Male và Female, như vậy ¬Male cũng là Female. Như vậy trong hai luật trên chỉ có một luật được giữ lại. Như vậy, quá trình khai phá luật kết hợp mẫu âm có thể chia làm 3 giai đoạn: 1.
Xác định một tập các luật kết hợp dương. Sinh các luật kết hợp âm dựa vào luật kết hợp dương đã có ở bước 1 và miền tri thức đã có. Loại các luật dư thừa.3 Thuật toán phát hiện luật kết hợp âm Từ việc phân tích các giai đoạn trong quá trình phát hiện luật kết hợp âm ở trên, chúng ta có thể xem xét giải thuật tìm kiếm luật kết hợp âm cụ thể như sau: //Tìm tất cả các luật dương: FreqSet1 = {frequent1 – itemsets}; k=2; while (FreqSetk-1 ) for all trấnctions g DataSet 23 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com CandidateSet1 = subset (CandidateSetk , g); for all candidates c CandidateSet1 c.count + 1; endfor endfor FreqSetk = {c CandidateSet1 | c.count ≥ minsup}; k = k + 1; endwhile // Sinh các luật dương với giải thuật Apriori postiveRule = genRule(FreqSetk); Rule = postiveRule; //Sinh các luật âm: Delete all items t from the taxonomy, t FreqSet1 For all rules r postiveRule tmpRuleSets = genNegCand(r); for all rules tr tmpRuleSets if SM(tr.conf) > confDeviate 24 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Rule = {Rule, Neg(tr) | Neg(tr).supp>minsup, Neg(tr).conf > minconf}; endif endfor endfor // Loại bỏ các luật dư thừa: If all members of LOS have common itemset that form {r1, r2,…, rn} Rule delete rk, where rk falls in the categories endif 1.4 Kết luận chương Như vậy qua chương đầu tiên, luận văn đã đưa ra được những vấn đề cơ bản của luật kết hợp, luật kết hợp mẫu âm. Ý nghĩa thực tế của việc khai phá luật kết hợp mẫu âm.
Và cũng đã phân tích được các bước cơ bản để phát hiện luật kết hợp, luật kết hợp mẫu âm. Một số thuật toán phổ biến trong khai phá luật kết hợp, luật kết hợp mẫu âm cũng đã được trình bày trong chương này. Với những vấn đề cơ bản của luật kết hợp, luật kết hợp mẫu âm như vậy, trong chương tiếp theo, luận văn sẽ đi vào xem xét bài toán cụ thể cần phải giải quyết đó là dựa vào luật kết hợp mẫu âm để xác định sự biến động giá cả dựa trên thông tin về giá cả hàng hóa trong 2 năm qua. 25 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chương 2 Xác định bài toán ứng dụng phát hiện luật kết hợp mẫu âm.1 Bài toán Những năm gần đây, trong công tác điều hành các hoạt động thương mại cho thấy trong rất nhiều trường hợp nhà nước cho phép nhập khẩu nhóm mặt hàng này, thì đồng thời phải cấm nhập khẩu nhóm mặt hàng khác; hoặc khi xây dựng các dòng thuế cho các nhóm ngành hàng, vẫn thường xẩy ra trường hợp việc cho phép tăng, giảm thuế một số mặt hàng trong nhóm phải được gắn liền với việc không cho phép tăng, giảm thuế của một số mặt hàng khác.
Trong y học thì những tình huống như vậy là khá phổ biến, ở đó khi người bệnh có một số triệu chứng biểu hiện của một căn bệnh nào đó thì chắc chắn người đó không thể có một số triệu chứng biểu hiện cho một số căn bệnh khác, … Đặc biệt sự biến động giá cả của các mặt hàng cho thấy trong rất nhiều trường hợp, nhóm mặt hàng này tăng thì sẽ có một số mặt hàng khác tăng, và cũng có thể sẽ kéo theo một số mặt hàng khác giảm. Tuy nhiên để xác định được mối quan hệ này thì trước hết phải thu thập được dữ liệu chính xác và đầy đủ về giá cả của các mặt hàng cần quan tâm và đây chính là vấn đề mà chương 2 của luận văn sẽ đề cập tới. Với nền kinh tế lạm phát cao, giá cả mặt hàng biến động liên tục. Bài toán đặt ra là trong sự biến động của các mặt hàng phải chăng có sự liên quan giữa các mặt hàng hay không? Và làm cách nào để xác định sự liên quan này? Đây là nội dung cơ bản mà luận văn sẽ phải làm rõ.
Theo kinh nghiệm của Viện Nghiên cứu giá cả thị trường Bộ Tài Chính và Trung tâm Thông tin Công nghiệp và Thương mại Bộ Công Thương, các cơ quan này thường 26 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com theo dõi biến động giá cả của những mặt hàng thuộc các nhóm: hàng hóa nhập khẩu, hàng hóa xuất khẩu, hàng hóa dân sinh, giá của một số mặt hàng trên thế giới và chỉ số giá tiêu dùng(CPI). Mặc dụ trên thị trường có hàng nghìn mặt hàng được lưu thông, tuy nhiên các mặt hàng được lựa chọn này đã chiếm tỉ trọng lớn, trên 90% tổng số lượng mặt hàng lưu thông. Do vậy kết quả của việc nghiên cứu biến động giá cả trên các mặt hàng này cũng đảm bảo tương đối chính xác cho tình hình biến động giá cả trên toàn thị trường. Giá cả của những mặt hàng này được thu thập theo tất cả các tuần trong 2 năm 2008, 2009 và quý 1 năm 2010.
Chi tiết được thể hiện trong phụ lục 1.