Khóa luận Phát hiện luật bằng cách sử dụng siêu phẳng tối ưu theo hướng tiếp cân tập thô

thể tham gia cùng. 1.2.2.2. Lựa chọn thuộc tính dựa trên tập thô Các cơ sở dữ liệu trong thực tế thương có rất nhiều thuộc tính, những thuộc tính cần thiết cho lĩnh vực mà bài toán khai phá dữ liệu mà chúng ta đang xử lý không phải là tất cả. Việc lựa chọn những thuộc tính phù hợp để tiến hành các phương pháp khai phá dữ liệu là rất cần thiết. Các thuộc tính dư thừa không cần thiết trong quá trình khai phá tri thức không chỉ làm cho bài toán trở lên phức tạp mà còn dẫn đền một thực , )( )( )( XB XB XB =α tế là số tri thức được phát hiện sẽ không nhiều vì phải phụ thuộc vào cả những thuộc tính không được coi là đặc trưng của bài toán. Mục tiêu của việc lựa chọn thuộc tính là phải đưa ra được một tập tối ưu các thuộc tính trong cơ sở dữ liệu. Từ đó các luật sinh ra trong cơ sở dữ liệu sẽ đạt được hiệu quả cao nhất, dữ liệu mà chúng ta thực sự phải làm việc sẽ nhỏ đi rất nhiều. Có hai phương pháp lựa chọn thuộc tính thường được sử dụng là lọc và bọc. Trong đó thì phương pháp lọc thực chất là tìm những thuộc tính tối thiểu trong tập các thuộc tính, chọn ra các thuộc tính có độ phù hợp cao hơn theo tiêu chuẩn sau: − Lựa chọn những thuộc tính là cho số trường hợp thoả mãn tăng nhanh. − Chọn những thuộc tính có it giá trị khác nhau. Phương pháp này là khá đơn giản và tốc độ là tương đối nhanh. Phương pháp thứ hai sử dụng thuật toán quy nạp đánh giá. Tư tưởng của thuật toán này là sử dụng 3 cách tìm kiếm: tìm kiếm toàn bộ, tìm kiếm kinh nghiệm và tìm kiếm không xác định. Phương pháp này sử dụng các thuật toán quy nạp nên độ phức tạp lớn nhưng bù lại thì kết quả mang lại sẽ chính xác và toàn diện hơn. 1.2.2.3. Khám phá luật bới bảng phân bố tổng quát dựa trên tập thô Bảng phân bố tổng quát có những đặc điểm sau: − Bảng phân bố tổng quát mô tả quan hệ xác suất giữa các trường hợp có thể và các bộ sinh có thể. − Những trường hợp không thấy trong quá trình khai phá dữ liệu sự không chắc chắn của luật bao gồm cả khả năng dự đoán trước các trường hợp nó không được thể hiện rõ ràng trong độ mạnh của luật. − Có thể sử dụng tri thức nền làm cơ sở cho việc lập bảng phân bố tổng quát và quá trình khai phá. A. Skowronvà Ning Zong [2] đã đưa ra phương pháp khám phá luật sư dụng bảng phân bố tổng quát dựa trên tập thô với ý tưởng như sau: − Từ bảng quyết định xây dựng bảng phân bố tổng quát. − Dựa trên các bảng phân bố tổng quát này sinh các vector phân biệt được. − Tạo ra các tập rút gọn được từ các tập vector phân biệt được. − Sinh ra các luật bao phủ tất cả các trường hợp. 1.2.2.4. Khám phá mẫu trong hệ thông tin Việc tìm những mẫu quan hệ phức tạp được phát hiện trong những cơ sở dữ liệu lớn một cách tự động là một trong những hướng nghiên cứu đang được chú trọng trên thế giới. Trong trường hợp đơn giản thì mẫu chỉ là một vector có giá trị độ dài đủ lớn của một sô thuộc tính được hỗ trợ của một lượng đủ lớn các đối tượng. Các bài toán tìm mẫu thường có độ phức tạp lớn đòi hỏi những thuật toán tối ưu, thuật toán đánh giá kinh nghiệm đủ tốt để có thể rút ra các mẫu gần tối ưu từ những cơ sở dữ liệu lớn. Một lớp quan trọng của của phương pháp tìm kiếm mẫu là dựa trên những khuôn mẫu quan hệ. Những khuôn mẫu này được xác định từ một bảng dữ liệu cho trước sử dụng quan hệ thứ lỗi trong một số lớp quan hệ thứ lỗi giả định trước. Một quan hệ thứ lỗi là tối ưu nếu tập các tham số miêu tả quan hệ này cho phép xây dựng những khuôn mẫu dữ liệu thích hợp trên những bảng dữ liệu cho trước. Có rất nhiêu ứng dụng cho việc phát hiện những khuôn mẫu trong hệ thông tin. Một số có thể dùng để tách các bảng dữ liệu lớn, bảng dữ liệu lớn có thể được phân chia thành một cây nhị phân của các mẫu và khuôn mẫu. Mỗi nút của cây phụ thuộc vào một bước phân tách. Quá trình phân chia dừng lai khi thu được những bảng có kích thước đủ nhỏ để có thể áp dụng nhưng phương pháp khai phá tri thức khác. Người ta áp dụng những phương pháp tìm kiếm mẫu quyết định từ những bảng quyết đinh gắn với các lá đã có dựa trên cách tiếp cận tập thô. Quá trình phân lớp cho một đối tượng mới bắt đầu bằng việc tìm ra đường đi trên cây bằng cách so sánh các mẫu. Sau đó, đối tượng được phân lớp dựa trên luật quyết định được sinh ra từ bảng con gắn với các lá ở trên đường đó. Việc lựa chon một chiến lược tìm kiếm khuôn mẫu có trong các lớp quyết định đã được thảo luận rất nhiều. Quá trình này có thể coi là quá trình tìm luật quyết định xấp xỉ mạnh ngầm định. Các phương pháp này cũng có thể dùng để tìm luật quyết định xấp xỉ tổng hợp từ các bảng dữ liệu. Bản chất xấp xỉ của những luật này được mô tả bởi một số rằng buộc. 1.3 . Kết luận Trên đây chúng tôi đã trình bày một số khái niêm cơ bản về khai phá tri thức, và đăc biệc là khai phá tri thức theo cách tiếp cận tập thô. Khai phá tri thức có thể được hiểu đơn giản là quá trình tìm kiếm nhưng thông tin mới trong cơ sở dữ liêu. Nó bao gồm 5 quá trình, trong đó quá trình khai phá dữ liệu là quan trong nhất. Các kỹ thuật khai phá tri thức được chia thành 3 mảng chính: phân cụm và phân lớp dữ liệu,khai phá các luật kết hợp, khai phá chuỗi. Lý thuyết tập thô do P. Pawlak đưa ra trong những năm đầu của thập kỷ 80 đã tỏ ra là rất hiệu quả trong lĩnh vực khai phá tri thức. Nó tỏ ra thực sự hiểu quả trong các bài toán thực tế, những bài toán có dữ liệu thương ở dạng thô, chưa qua xử lý, trong dữ liệu có nhiều thông tin dư thừa. Chương 2 KHAI PHÁ LUẬT KẾT HỢP Khai phá luật kết hợp là một kỹ thuật quan trọng và phát triển mạnh mẽ trong những năm gần đây. Lần đầu tiên được Rakesh Agrawal, Tomasz Imielinski, Arun Swami đề xuất năm 1993 [6]. Sau đó được nhiều nhà khoa học phát triển và cải tiến. 2.1 . Khai phá luật kết hợp trong cơ sở dữ liệu 2.1.1. Bài toán xuất phát Cho trước một cơ sở dữ liệu lưu thông tin bán hàng của một siêu thị. Với lượng dữ liệu được lưu giữ là tương đối lớn, người sử dụng mong muốn có những tri thức từ cơ sở dữ liệu trên để có thể hoạch định kế hoạch kinh doanh phù hợp: Những câu hỏi được đặt ra như nên đầu tư cho những mặt hàng nào, số lượng là bao nhiêu? Sắp xếp các mặt hàng trong siêu thị như thế nào là hợp lý v . v ? Với những câu hỏi như trên thì người sử dụng mong muốn có những thông tin như là: ”75% những người mua bánh mì sẽ mua sữa”, hoặc “5% những người mua rượu sẽ mua lạc”. Những phát biểu trên được gọi là các luật kết hợp. Bản thân nó ngầm định một số quan hệ kết hợp một tập các đối tượng cùng tham gia mua hàng. Từ những luật dạng trên thì người sử dụng có thể dùng để hỗ trợ những quyết định của họ trong kinh doanh. Họ sẽ có chiến lược chẳng hạn như đầu tư lượng bánh mi và sữa gần bằng nhau sao cho hiệu quả. Trong phần này chúng tôi chỉ giải quyết ở mức độ là người khách hàng đó có mua mặt hàng đó hay không, khi đó thì mỗi thuộc tính chỉ có 2 giá tri khác nhau là 0 ứng với trường hợp người đó không mua mặt hàng này và bằng 1 nếu người đó có mua mặt hàng đó. 2.1.2. Mô hình hoá bài toán Trước tiên ta có một số định nghĩa như sau: I = {i1,i2,....,im} là tập toàn bộ các mục (chính là các mặt hàng trong bài toán trên). D : là cơ sở dữ liệu, nó bao gồm các tác vụ, trong đó mỗi tác vụ có thể coi như là một vector t=(t1, t2, . . .,tm) với ti = 0 nếu tác vụ t mua mặt hàng i, i=1, . . .,m. Với những định nghĩa trên thì cơ sở dữ liệu bán hàng của một siêu thị sẽ được biệt diễn là một tập D các tác vụ t. Trong đó I là tập các thuộc tính hay tập các mặt hàng. Ta có định nghĩa luật kết hợp như sau: Định nghĩa 11: Luật kết hợp là biểu thức có dạng X⇒Y trong đó X ⊂ I, Y ⊂ I và X∩Y=∅. Trong đinh nghĩa trên thì X được gọi là tiên đề. Y được gọi là kết quả của luật. Định nghĩa 12: Độ hỗ trợ của một tập mục X, ký hiệu là Supp(X), là tỉ số giữa số các tác vụ mà tập mục đó xuất hiện trên tổng số các tác vụ. Với định nghĩa trên thì ta dễ dàng có tính chất: Nếu A ⊆ B thì Supp(A)≥Supp(B). Định nghĩa 13: Độ hỗ trợ của luật X⇒Y , ký hiệu là Supp(X⇒Y) được xác định như sau: Supp(X⇒Y)= Supp(X∪Y). Định nghĩa 14: Độ tin cậy của luật dạng r=X⇒Y, ký hiệu là conf(X⇒Y) được định nghĩa: Conf(X⇒Y)=Supp(X∪Y)/Supp(X).ư Ta thấy độ tin cậy của một luật chính là xác suất có điều kiện của tác vụ chứa Y xét trong điều kiện chứa X Ví dụ: Để hiểu rõ hơn các định nghĩa trên chúng ta xét ví dụ sau: Cho một cơ sở dữ liệu như bảng sau: ID Tác vụ Các mục T1 A, C, D T2 B, E T3 A, B, C, E T4 B, E T5 B, D, F Bảng 3. Ví dụ về một cơ sở dữ liệu. Trong cơ sở dứ liệu trên gồm 5 tác vụ thao tác trên 6 tập mục là A, B, C, D, E, F. Khi đó thì độ hỗ trợ tương ứng của từng mục sẽ là: Ở đây tổng số tác vụ là 5, trong khi mục A xuất hiện trong 2 tác vụ là T1 và T3 nên có độ hỗ trợ là 2/5=40% { }( ) )( : )( Dcard TXTcard XSupp ∈= Mục Số tác vụ chứa mục Độ hỗ trợ A 2 40% B 3 80% C 2 40% D 2 40% E 3 60% F 1 20% Bảng 4. Độ hỗ trợ tương ứng của từng mục đơn. Tiếp tục tính độ hỗ trợ của các tập mục lớn hơn với mỗi tập gồm 2 mục ta có bảng : Mục Số tác vụ chứa mục Độ hỗ trợ A, C 2 40% A, B 1 20% B, D 1 20% C, D 1 20% A, B, C 1 20% A, B, E 1 20% A, C, D 1 20% B, D, F 1 20% A, B, C, E 1 20% Bảng 5. Độ hỗ trợ tương ứng của các tập mục khác Ta xét một số luật sinh từ các tập mục phổ biến trên trong bảng sau. Trong các luật của bảng ta xét luật A⇒B thì supp({A, B})=20%, supp(A)=40% vì vậy conf(A⇒B)=50%. Luật kết hợp Độ tin cậy conf(X⇒Y) A⇒C 100% A⇒B 50% B⇒D 25% A,B⇒C 100% A,C⇒B 50% B,E⇒A 33% Bảng 6. Độ tin cậy của các luật. 2.1.3. Thuật toán khai phá luật kết hợp. 2.1.3.1. Tập phổ biến. Định nghĩa 15: Tâp mục X⊆I được gọi phổ biến nếu thoả mãn supp(X) ≥ minsup. Trong đó minsup là một độ hỗ trợ tối thiểu cho trước. Khái niệm phổ biến này cho phép chúng ta chỉ xét những tập mục xuất hiện trong cơ sở dữ liệu là đủ lớn, lớn hơn một minsup nào đó. Khi đó luật của chúng ta sinh ra sẽ đáng tin cậy hơn. Ta có hệ quả sau: Cho A và B là hai tập mục, A⊆B. a. Nếu B là tập mục phổ biến thì A cũng là tập mục phổ biến. b. Nếu A là tập mục không phổ biến thì B cũng là tập mục không phổ biến. 2.1.3.2. Khai phá luật dựa trên tập mục phổ biến. Việc tìm kiếm luật kết hợp trong cơ sở dữ liệu được quy về 2 giai đoạn [7]: − Tìm tất cả các luật có độ hỗ trợ lớn hơn một minssup. Các tập mục này chính những tập mục phổ biến. Các thuật toán Apriori và AprioriTid nhằm giải quyết vấn đề này. − Từ các tập mục tìm được ở trên tiến hành sinh những luật có độ tin cậy lớn hơn một minconf nào đó. Hai tham số minsupp và minconf được người sử dụng đưa vào khi hệ thống khai phá tri thức. Các giá trị này thường được đưa ra bởi các chuyên gia kinh tế hoặc những người có kinh nghiệm. Ở trong giai đoạn nhất việc phát hiện những tập mục phổ biến tiến hành duyệt dữ liệu rất nhiều lần. Việc tìm các tập mục phổ biến thực hiện dựa trên hệ quả của định nghĩa 14 trình bày ở trên. Và thực hiện lần luợt các bước sau: − Đầu tiên người ta khởi tạo một tập thật giống các tập mục phổ biến và sinh các tập mục phổ biến dựa trên tập mục hạt giống này. − Từ các tập mục phổ biến người ta thực hiện ghép các tập mục phổ biến để được các tập mục lớn hơn, các tập mục này được gọi là tập ứng cử viên. − Để tính được độ hỗ trợ của các tập mục phổ biến người ta phải thực hiện duyệt toàn bộ dữ liệu. Khi đó sẽ tìm được những tập mục ứng cử viên là tập mục phổ biến. − Tập các tập mục ứng cử viên là phổ biến này được sử dụng là tập hạt giống cho bước tiếp theo. Cụ thể các thuật toán Apriori và AprioriTid sinh ra các tập ứng cử viên đó được tính trong một lần duyệt bằng việc sử dụng các tập mục được coi là phổ biến trong lần duyệt trước mà không cần quan tâm tới các tác vụ trong cơ sở dữ liệu. Việc chỉ xét các tập mục là phổ biến trong lần trước để sinh các tập mục ứng cử viên dựa hệ quả rút ra từ định nghĩa 14 đã trình bày ở trên: “Bất kỳ tập con của một tập mục phổ biến nào cũng là tập mục phổ biến”. Vì vậy tập ứng cử viên có k mục có thể sinh ra bởi tập các tập mục phổ biến có k-1 mục. Điều này có thể dẫn đến việc giảm đáng kể các tập mục ứng cử viên, là giảm độ phức tạp trong tính toán. Thuật toán Apriori: Đây là thuật toán dùng để phát sinh các tập mục phổ biến. − Lk là tập các tập mục phổ biến có kích thước k. − Ck là tập ứng cử viên, là các tập mục có tiềm năng trở thành tập mục phổ biến. − Thuật toán được tiến hành cho đến khi không tìm được một tập mục phổ biến nào trong một lần duyệt. Các bước của thuật toán được trình bày dưới đây: Lần duyệt 1 1. Phát sinh các ứng cử viên C1. Thực chất tất cả các tập mục đơn của cơ sở dữ liệu. 2. Kiểm tra và ghi lại những tập mục thuộc C1 là tập mục phổ biến và L1. Lần duyệt thứ k: 1. Phát sinh các tập ứng cử viên từ các tập mục phổ biến Lk-1. a. Kết hợp các Lk-1 để được tất cả các Ck. b. Với mỗi ứng cử viên Ck phát sinh tất cả k-1 tập con của Ck. c. Tỉa tất cả các ứng cử viên từ Ck trong đó có tập con (k-1) của nó không có trong tập mục phổ biến Lk-1. 2. Duyệt trong cơ sở dữ liệu để xác định độ hỗ trợ của các tập ứng cử viên Ck. 3. Ghi lại các tập mục phổ biến Lk. Trong bước thứ 2 của mỗi lần duyệt, để có thể tính độ hỗ trợ của các tập ứng cử viên thì thuật toán phải tiến hành duyệt lại toàn bộ cớ sở dữ liệu. Quá trình này là thực sự đáng kể với những cơ sở dữ liệu lớn. Khắc phục hạn chế trên thuật toán ApriporiTid đã lưu lai thông tin về các tác vụ gắn liền với mỗi tập mục phổ biến. Điều này có thể giúp chúng ta khắc phục được hạn chế về việc phải đọc dữ liệu nhiều lần tuy nhiên lại gây khó khăn hơn cho chúng ta khi tổ chức bộ nhớ chương trình. Ở giai đoạn 2, giai đoạn sinh luật với mỗi tập mục phổ biến l ta tiến hành xây dựng những luật dạng ( )ala −→ ở đây a là tập con của l sao cho ( ) ( ) confap lp min sup sup ≥ Ta có, với một tập aa ⊂* thì ( ) ( )apap sup*sup ≥ nên độ tin cây của luật dạng ( )** ala −→ không thể lớn hơn luật dạng ( )ala −→ . Do đó nếu luật ( )ala −→ không được chấp nhận thì luật dạng ( )** ala −→ cũng không thể chấp nhận được. Nhờ tính chất này mà ta có thể tiến hành xây dựng các luật chỉ có một tập mục ở phía phải sau đó kết hợp các luật thành dạng có 2 mục, 3 mục, ... ở phia phải 2.1.4. Kết luận. Việc tìm kiếm các luật kết hợp trong cơ sở dữ liệu được thực hiện theo thuật toán nguyên thuỷ Apriori và AprioriTid. Tuy nhiên một thực tế là số tập mục phổ biến có thể là rất nhiều, khắc phục hạn chế này chúng ta có thể dùng thuật toán CHARM được Mohammed .J Zaki và Ching-jui Hsiao đưa ra trong năm 2000 [13]. Thuật toán CHARM không tiến hành tìm những tập mục phổ biến mà tiến hành tìm những tập mục phổ biến đóng. Điều này dẫn đến số tập mục phổ biến tìm được là giảm đi rất nhiều và tại các bước của thuật toán việc cắt nhánh trong quá trình thực hiện là rất hiệu quả. Một hạn chế đáng kể của các thuật toán trình bày ở trên là chỉ làm việc với dữ liệu ở dạng nhị phân, tức là giá trị của các thuộc tính chỉ nhận 2 giá trị là 0 và 1. Điều đó dẫn đến việc thuật toán khó có thể áp dụng trực tiếp trên những cơ sở dữ liệu tự nhiên. Muốn thực hiện được thuật toán cần phải định lượng các thuộc tính thành dạng nhị phân. Quá trinh này làm giảm tính chính xác của kết quả thu được. Trong chương sau chúng tôi sẽ trình bày một thuật toán có thể làm việc được với dữ liệu là đa trị, dữ liêu là dạng số thực. 2.2 . Sinh cây quyết định từ hệ thông tin. 2.2.1. Thuật toán học cây quyết định. Phương pháp học cây quyết định là một trong những phương pháp được sử dụng rông rãi nhất cho việc học quy nạp từ một tập mẫu lớn [11]. Đây là phương pháp xấp xỉ các hàm mục tiêu có giá trị rời rạc. Mặt khác cây quyết định còn có thể chuyển sang dạng biểu diễn tương đương dưới dạng tri thức là các luật Nếu – Thì (if ... then). Xét một ví dụ về cây quyết định. Cho một bảng dữ liệu sau: Doc ai timetable system patallel relation database process graphic Class AI D1 1 1 0 0 0 0 0 0 1 D2 1 0 0 0 0 0 0 0 1 D3 0 1 0 0 1 1 1 1 1 D4 1 0 0 0 0 0 0 1 1 D5 1 1 1 1 1 0 0 1 1 D6 0 0 1 1 0 0 0 0 0 D7 0 0 1 0 0 0 0 1 0 D8 0 0 1 0 1 1 0 0 0 D9 1 0 1 1 0 1 0 0 0 D10 1 1 0 0 1 1 1 0 0 Bảng 6. Các ví dụ huấn luyện tron cây quyết định. Ta có cây quyết định: Hình trên là một ví dụ về cây quyết định phân lớp AI các mẫu đưa vào theo bảng 5. Mỗi nút của cây biểu diễn một thuộc tính trong các mẫu, mỗi một nhánh tới nút tương ứng với một trong những giá trị cụ thể cho thuộc tính này. Để đơn giản ta chỉ xét các thuộc tính nhị phân, tức là chỉ lấy giá trị là 0 và 1. Trong bảng 5, dữ liệu huấn luyện là 10 văn bản (trong các bài toán thực tế thì số lượng văn bản có thể lên tới hàng nghìn). Mỗi văn bản có 8 thuộc tính nhị phân tương ứng với việc văn bản đó có hay không có từ đó. Đó là các thuộc tính ai, system, paralell, relation, database, process, graphics.Thuộc tính cuối Class AI cùng là thuộc tính quyết định. Đó là hàm mục tiêu của chúng ta, nó nhận giá trị 1 tức là văn bản đó thuộc lớp AI, 0 tức là văn bản đó không thuộc lớp AI. Mặt khác, từ cây quyết định trên chúng ta có thể sinh ra được các luật như sau: 1) Nếu (System=1) và (Timetable =1 ) thì class AI =Yes. 2) Nếu (System=1) và (Timetable =0 ) thì class AI =No. 3) Nếu (System=0) và (Process =1 ) thì class AI =No. 4) Nếu (System=0) và ( Process=0 ) thì class AI =Yes. System Process Timetable 0 1 0 1 0 1 Yes No Yes No Hình 2.Một ví dụ về cây quyết đinh. Giải thích cụ thể hơn ta có: 1) Nếu văn bản có từ System và từ Timetable thì thuộc lớp AI. 2) Nếu văn bản có từ System và không có từ Timetable thì không thuộc lớp AI. 3) Nếu văn bản không có từ System và có từ Process thì không thuộc lớp AI. 4) Nếu văn bản không có từ System và không có từ Process thì thuộc lớp AI. Những bài toán nên sử dụng việc học cây quyết định: Trong [10], Mitchel đã chỉ việc sử dụng cây quyết định phù hợp với việc giải quyết các bài toán sau: − Các mẫu huấn luyện được biểu diễn thành những cặp giá trị - thuộc tính, các thuộc tính là một tập cố định. Các giá trị thuộc tính là rời rạc. Tuy nhiên trong các thuật toán sinh cây quyết định cải tiến sau này cho phép các thuộc tính nhận giá trị là giá trị thực. Đặc biệt là thuật toán sinh cây quyết định sử dụng siêu phẳng được đưa ra trong[9] sẽ được trình chi tiết sau. − Hàm mục tiêu phải có giá trị rời rạc, trong bài toán phân lớp văn bản trên thì hàm mục tiêu có thể mở rộng thành nhiều giá trị đầu ra. − Trong trường hợp cần biểu diễn kết quả thu được dưới dạng các mô tả: Chẳng hạn như là dưới dạng luật thì cấu trúc cây quyết định có thể chuyển sang một cách dễ dàng. − Tập dữ liệu huấn luyện có thể chứa lỗi: Phương pháp học cây quyết định có thể thực hiện tốt trên các tập dữ liệu chứa lỗi, cả trên các lỗi trong phân lớp ví dụ huấn luyện cũng như lỗi trên các giá trị thuộc tính trong các ví dụ này. − Tập dữ liệu có thể có những giá trị bị thiếu. Phương pháp cây quyết định có thể được sử dụng trong các trường hợp các ví dụ huấn luyện có những giá trị chưa biết. Thuật toán ID3 Đây là một thuật toán cơ bản nhất trong lĩnh vực học cây quyết đinh, hầu hết các thuật toán học cây quyết đinh cải tiến sau này đều dựa trên nó. ID3 và các thuật toán cải tiến của nó đều dựa vào cách tiếp cận từ trên xuống. Trong các thuật toán học cây quyết định thì thuật toán ID3 và thuật toán C4.5 là phổ biến nhất. Thuật toán ID3 lần đầu tiên được Quinlan giới thiệu năm 1975 trong tạp trí Machine Learning, Vol 1, No.1.Sau đây chúng tôi trình bày thuật toán ID3, thuật toán được mô tả như sau [9]: ID3(Examples, Target attribute, Attributes) Examples: Tập các ví dụ huấn luyện. Target attribute: là thuộc tính đầu ra cho cây quyết định. Attributes:Danh sách các thuộc tính. Kết quả trả về là một câu quyết định phân lớp đúng các mẫu ví dụ đưa ra. • Tạo một nút gốc Root cho cây quyết định. • Nếu toàn bộ Examples là ví dụ dương. Trả về cây Root một nút đơn, với nhãn +. • Nếu toàn bộ Examples là ví dụ âm. Trả về cây Root một nút đơn, với nhãn - . • Nếu tập thuộc tính là rỗng thì trả lại cây Root một nút đơn với nhãn bằng giá trị phổ biến nhất của Target_attribute trong Examples. • Ngược lại:Begin o A ←Thuộc tính từ tập Attributes mà phân lớp tốt nhất tập Examples. o Thuộc tính quyết định cho Root ←A. o For Mỗi giá trị cụ thể vi của A, ƒ Thêm một nhánh cây con ở dưới Root, phù hợp với biểu thức kiểm tra A=vi . ƒ Đặt Examplesvi là tập các ví dụ có giá trị của thuộc tính A là vi . ƒ Nếu Examplesvi rỗng • thì dưới nhánh mới thêm gán một nút lá với nhãn = giá trị phổ biến nhất của Target_attribute trong tập Examples. • ngược lại thì dưới nhánh mới này thêm một cây con: ID3(Examplesvi,Target_attribute,Attribute-{A}. • End. • Return Root. Chọn lựa thuộc tính tốt nhất Vấn đề quan trọng nhất của thuật toán ID3 là làm sao chọn lựa được thuộc tính tốt nhất để đưa vào các nút của cây. Để giải quyết vấn đề này, người ta sử dụng kết quả của lý thuyết thông tin là các độ đo là infomation gain và entropy. Entropy: Đây là đại lượng hết sức quan trọng trong lý thuyết thông tin. Entropy là đại lượng đo tính đồng nhất hay thuần tuý của các mẫu. Trước tiên ta xem xét trường hợp các thuộc tính của tập các mẫu huấn luyện S của cây quyết định chỉ có hai lớp phân biệt là mẫu ví dụ dương (possotive) và mẫu ví dụ âm (Negative). Khi đó Entropy của tập S được định nghĩa như sau: Entropy(S)≡-p⊕ log2p⊕--pΘ log2pΘ. Trong đó: p⊕ : là phân bố của các ví dụ dương trong S. pΘ : là phân bố của các ví dụ dương trong S. Chúng ta quy đinh 0log20 =0. Ví dụ: Xét trong ví dụ bảng 5, có10 mẫu huấn luyện, trong đó có 5 mẫu huấn luyện dương(Class AI=1) và 5 ví dụ âm (Class Ai=0). Khi đó đại lương Entropy S liên quan tới sự phân bố 2 lớp dương và âm của tập S là: Entropy(S) = -(5/10)log2(5/10)-(5/10)log2(5/10)= =1.0 Trong trường hợp tổng quát thì đại lượng Entropy được tính như sau: Trong đó: pi :là phân bố của lớp thứ i trong S. c : là số lớp trong S. Tương tự: Entropy(Sai=1) = -(4/6)log2(4/6)-(2/6)log2(2/6)=0,918. Entropy(Sai=0) = -(1/4)log2(1/4)-(3/4)log2(3/4)=0,812. ( ) ∑ = −= c i ii ppSEntropy 1 2log Information Gain Trong khi Entropy là đại lượng đo độ không đồng nhất của các mẫu, người ta đưa ra một độ đo sự ảnh hưởng của một thuộc tính trong mẫu đó trong việc phân lớp là information gain. Information gain của một thuộc tính A được tính như sau: Trong đó Sv là tập các phần tử mà thuộc tính A có giá trị là v. Ví dụ: Tiếp tục xét ví dụ trong bảng 5 ta có. Gain(S,ai) = Entropy(S)-(6/10)Entropy(Sai=1)-(4/10)Entropy(Sai=0) = 1.0-(6/10).0,918-(4/10).0,812 = 0,1244 Tương tự ta có thể xét các Gain của các thuôc tính khác có giá trị như bảng sau. Attribute ai timetable system parallel relation database process graphic Gain 0,1244 0,1244 0,2871 0,0349 0,0 0,1244 0,0 0,1244 Bảng 7. Giá trị informatin Gain của các thuộc tính. Khi đó theo thuật toán ID3 thì thuộc tính đầu tiên được chọn là thuộc tính system vì có giá trị information Gain là lớn nhất. ∑ ∈ −≡ )( )()(),( AValuesV V V SEntropy S S SEntropyASGain ( ) )()(, }1,0{ v v v SEntropy S S SEntropyaiSGain ∑ ∈ −= 2.2.2. Một số phương pháp giải quyết vấn đề rời rạc hoá 2.2.2.1. Maximal Discernibility (MD) Heuristic Theo như định nghĩa 8 được trình bày trong Chương 1 phần 1.2.1.4 trên một bảng quyết định bất kỳ ta luôn có thể định nghĩa một tập các nhát cắt. Từ tính chất này ta có thể xây dựng thuật toán sau: Từ một bảng quyết định A =(U, A∪{d}), chúng ta xây dựng một bẳng quyết định mới. A* =(U*, A*∪{d*}) như sau: • U* ={(u, v)∈ U2 : d(u)≠d(v)} ∪ {⊥}. • A* ={c: c là một nhát cắt trên A}. c(⊥)=0; c((ui, uj))=1 nếu c phân biệt được ui và uj. 0 nếu ngược lại. • d(⊥) và d*(ui, uj)=1. Ta thu được bảng quyết định dạng sau: A* c1 c2 . . . ck . . . d* (u1, u2) 1 0 . . . 0 . . . 1 (u1, u2) 1 1 . . . 1 . . . 1 . . (u1, u2) 0 1 1 . . . . ⊥ 0 0 . . . 0 . . . 0 Bảng 8. Một dạng của bảng quyết định dạng A* Như vậy việc tìm kiếm một sự rời rạc hoá tối ưu bảng quyết định A tương đương với việc tìm tập rút gọn nhỏ nhất trong bảng quyết định A*. Thuật toán MD[9] được xây dựng dựa trên việc tìm kiếm nhát cắt với số cặp đối tượng được phân biệt bởi nhát cắt là nhỏ nhất được mô tả như sau: Từ tập tất cả các nhát cắt A*, nhát cắt phân biệt số lớn nhất các cặp đối tượng thuộc những lớp quyết định khác nhau sẽ được chọn. Quá trình thực hiện đến khi hai đối tượng bất kỳ từ những lớp quyết định khác nhau đều bị phân biệt bởi một hoặc vài nhát cắt. Phương pháp này rất hiệu quả vì để tìm được nhát cắt với sự phân biệt là lớn nhất chúng ta chỉ cần O(nk) bước, trong đó n là số đối tượng và k là số thuộc tính.Vì thế tổng thời gian rời rạc hoá là O(nk.| P |), với P là tập nhát cắt cuối cùng tìm được. 2.2.2.2. Sự rời rạc hoá định nghĩa bằ