Luận văn: Nghiên cứu các Tập Rút Gọn trong Bảng Quyết Định
Nghiên cứu tập rút gọn trong bảng quyết định giúp tối ưu hóa quy trình, giảm thiểu dư thừa và nâng cao hiệu quả ra quyết định. Tìm hiểu ngay!
Trường đại học
Trường Đại Học Công Nghệ - Đại Học Quốc Gia Hà NộiChuyên ngành
Công Nghệ Thông TinNgười đăng
Ẩn danhThể loại
Luận Văn Thạc SĩPhí lưu trữ
30 PointMục lục chi tiết
Tóm tắt
I. Tổng Quan Nghiên Cứu Rút Gọn Bảng Quyết Định 55 Ký Tự
Khai phá dữ liệu đang là một trong những lĩnh vực nghiên cứu sôi động, với ứng dụng rộng rãi. Trong số nhiều phương pháp khai phá dữ liệu, lý thuyết tập thô nổi lên như một công cụ quan trọng. Lý thuyết tập thô đã chứng minh hiệu quả trong việc rút gọn dữ liệu, trích lọc tri thức tiềm ẩn dưới dạng mẫu và luật quyết định, cũng như làm việc với bảng quyết định. Trong thực tế, dữ liệu trong bảng quyết định thường đa dạng, không đầy đủ, thiếu chính xác và dư thừa, đặt ra yêu cầu rút gọn thuộc tính. Mục tiêu là tạo ra các thuộc tính cốt yếu và cần thiết trong cơ sở dữ liệu. Rút gọn là bài toán quan trọng nhất trong lý thuyết tập thô. Mục tiêu là loại bỏ tối đa các thuộc tính dư thừa, giữ lại những thuộc tính cốt lõi chứa đầy đủ thông tin, từ đó sinh luật và phân lớp hiệu quả. Trong những năm gần đây, các hướng nghiên cứu về rút gọn thuộc tính trong lý thuyết tập thô đã phát triển mạnh mẽ. Nhiều nhóm nhà khoa học trên thế giới đã nghiên cứu các phương pháp rút gọn thuộc tính khác nhau, bao gồm phương pháp dựa trên miền dương, lý thuyết thông tin, ma trận phân biệt, tính toán hạt, và metric. Mỗi phương pháp phù hợp với một lớp bài toán thực tế. Với một bảng quyết định, có thể tồn tại nhiều tập rút gọn khác nhau. Tuy nhiên, thực tế thường chỉ yêu cầu tìm một tập rút gọn tốt nhất theo một tiêu chuẩn đánh giá cụ thể. Các phương pháp rút gọn thuộc tính đều đưa ra một thuật toán heuristic để tìm tập rút gọn. Các thuật toán này giảm thiểu đáng kể khối lượng tính toán, cho phép áp dụng vào các bài toán có khối lượng dữ liệu lớn. Vì vậy, luận văn tập trung vào “Nghiên cứu các tập Rút gọn trong bảng quyết định”. Luận văn này tập trung vào: (1) Tìm hiểu lý thuyết về hệ thống thông tin, bảng quyết định, tập rút gọn. (2) Nghiên cứu về cơ sở dữ liệu. (3) Tìm hiểu thuật toán tìm một tập rút gọn và tất cả các tập rút gọn. (4) Cài đặt và thử nghiệm thuật toán tìm tập rút gọn. Luận văn bao gồm các chương: Mở đầu, Chương 1 (Các khái niệm cơ bản), Chương 2 (Thuật toán tìm tập rút gọn), Chương 3 (Triển khai và thử nghiệm), Tài liệu tham khảo.
1.1. Hệ thống thông tin và bảng quyết định trong rút gọn
Lý thuyết tập thô, do Zdzislaw Pawlak đề xuất, được xem là công cụ hữu hiệu để giải quyết các bài toán phân lớp, phát hiện luật chứa dữ liệu mơ hồ không chắc chắn. Công cụ này cho phép biểu diễn một mô hình toán học về tri thức, nhờ đó tri thức được định nghĩa một cách rõ ràng dưới dạng toán học và có thể được phân tích và xử lý bằng các công cụ mạnh mẽ và hiệu quả của toán học. Từ khi xuất hiện, lý thuyết tập thô đã được sử dụng hiệu quả trong các bước của quá trình khai phá dữ liệu và khám phá tri thức, bao gồm tiền xử lý số liệu, trích lọc các tri thức tiềm ẩn trong dữ liệu và đánh giá kết quả thu được. Trong lý thuyết tập thô, dữ liệu được biểu diễn thông qua một hệ thống thông tin IS U , A với U là tập các đối tượng và A là tập các thuộc tính. Phương pháp tiếp cận chính của lý thuyết tập thô là dựa trên quan hệ không phân biệt được để đưa ra các tập xấp xỉ biểu diễn tập đối tượng cần quan sát. Khi đó, mọi tập đối tượng đều được xấp xỉ bởi hai tập rõ là xấp xỉ dưới và xấp xỉ trên của nó. Xấp xỉ dưới bao gồm các đối tượng chắc chắn thuộc tập đó, còn xấp xỉ trên chứa tất cả các đối tượng có khả năng thuộc về tập đó. Nếu tập xấp xỉ dưới bằng tập xấp xỉ trên thì tập đối tượng cần quan sát là tập rõ, ngược lại là tập thô. Các tập xấp xỉ là cơ sở để đưa ra các kết luận từ dữ liệu. Bảng quyết định là một hệ thông tin IS với tập thuộc tính A được chia thành hai tập con khác rỗng rời nhau C và D , lần lượt được gọi là tập thuộc tính điều kiện và tập thuộc tính quyết định. Nói cách khác, DS U , C D với C D . Bảng quyết định là mô hình thường gặp trong thực tế, khi mà giá trị dữ liệu tại các thuộc tính điều kiện có thể cung cấp cho ta thông tin về giá trị của thuộc tính quyết định. Bảng quyết định là nhất quán khi phụ thuộc hàm C D là đúng, trái lại là không nhất quán.
1.2. Tầm quan trọng của rút gọn thuộc tính trong bảng quyết định
Trong bảng quyết định, các thuộc tính điều kiện được phân thành thuộc tính lõi và thuộc tính không cần thiết. Thuộc tính lõi là thuộc tính cốt yếu, không thể thiếu trong việc phân lớp chính xác tập dữ liệu. Thuộc tính không cần thiết là thuộc tính dư thừa mà việc loại bỏ thuộc tính này không ảnh hưởng đến việc phân lớp dữ liệu. Các thuộc tính không cần thiết được phân thành hai nhóm: Thuộc tính dư thừa thực sự và thuộc tính rút gọn. Thuộc tính dư thừa thực sự là những thuộc tính dư thừa mà việc loại bỏ tất cả các thuộc tính như vậy không ảnh hưởng đến việc phân lớp dữ liệu. Thuộc tính rút gọn, với một tổ hợp thuộc tính nào đó, nó là thuộc tính dư thừa và với một tổ hợp các thuộc tính khác nó có thể là cốt yếu. Cho bảng quyết định DS U , C D,V , f . Thuộc tính c C được gọi là không cần thiết (dư thừa) trong DS dựa trên miền dương nếu POSC D POS(C c) D ; Ngược lại, c được gọi là cần thiết. Tập tất cả các thuộc tính cần thiết trong DS được gọi là tập lõi dựa trên miền dương và được ký hiệu là PCORE C . Lúc đó, thuộc tính cần thiết còn được gọi là thuộc tính lõi. Cho bảng quyết định DS U ,C D ,V , f và tập thuộc tính R C . Nếu 1) POSR ( D) POSC ( D) 2) r R, POSRr ( D) POSC ( D) thì R là một tập rút gọn của C dựa trên miền dương. Tập rút gọn định nghĩa như trên còn gọi là tập rút gọn Pawlak. Ký hiệu PRED C là họ tất cả các tập rút gọn Pawlak của C. Cho bảng quyết định DS U , C D,V , f và a C . Ta nói rằng a là thuộc tính rút gọn của DS nếu tồn tại một tập rút gọn R PRED C sao cho aR . Cho bảng quyết định DS U , C D,V , f và a C . Ta nói rằng a là thuộc tính dư thừa thực sự của DS nếu a C R.
II. Phương Pháp Tìm Tập Rút Gọn Tối Ưu Nhất 58 Ký Tự
Rút gọn thuộc tính là ứng dụng quan trọng nhất trong lý thuyết tập thô. Mục tiêu của rút gọn thuộc tính là loại bỏ các thuộc tính dư thừa để tìm ra các thuộc tính cốt yếu và cần thiết trong cơ sở dữ liệu. Với bảng quyết định, rút gọn thuộc tính là tìm tập con nhỏ nhất của tập thuộc tính điều kiện bảo toàn thông tin phân lớp của bảng quyết định. Đối với một bảng quyết định có thể có nhiều tập rút gọn khác nhau. Số lượng các tập rút gọn trong trường hợp xấu nhất có thể là 2k - 1, với k là các thuộc tính điều kiện. Tuy nhiên, trong thực tế thường không đòi hỏi tìm tất cả các tập rút gọn mà chỉ cần tìm được một tập rút gọn theo tiêu chí đánh giá nào đó là đủ. Trong phần này, chúng tôi xin giới thiệu một số phương pháp tìm tập rút gọn và đưa ra một số thuật toán tìm một tập rút gọn mới với độ phức tạp có thời gian đa thức đồng thời đưa ra một số thuật toán tìm tất cả các tập rút gọn.
2.1. Sử dụng Metric để tìm tập rút gọn trong bảng quyết định
Cho U là tập hữu hạn các đối tượng và X , Y U . Biểu thức X Y D X ,Y 1 X Y được gọi là khoảng cách Jaccard (Jaccard distance) giữa X và Y và biểu thức X Y J X ,Y X Y được gọi là hệ số Jaccard. Hệ số Jaccard đo độ tương tự giữa hai tập hợp X và Y. Cho U là tập hữu hạn các đối tượng và P U là tập các tập con của U. Khoảng cách Jaccard là một metric trên P U , nghĩa là mọi X ,Y , Z P U thỏa mãn các điều kiện sau: (P1) D X , Y 0 , điều kiện D X , Y 0 khi và chỉ khi X = Y. Chứng minh Hiển nhiên, D X , Y thỏa mãn điều kiện (P1) và (P2). Để chứng minh điều kiện (P3) (bất đẳng thức tam giác), ta cần chứng minh bất đẳng thức sau.
2.2. Độ quan trọng của thuộc tính dựa trên metric LSI Keyword
Cho bảng quyết định DS U , C D,V , f , B C và b C B . Độ quan trọng của thuộc tính b đối với B được định nghĩa bởi SIGB b d J K B , K B D d J K B b , K B b D với giả thiết ui U với mọi ui U , i 1. Do đó, SIGB b được tính bởi lượng thay đổi khoảng cách giữa B và B D khi thêm thuộc tính b vào B , SIGB b càng lớn thì lượng thay đổi khoảng cách càng lớn, hay thuộc tính b càng quan trọng và ngược lại. Độ quan trọng của thuộc tính b đặc trưng cho chất lượng phân lớp của thuộc tính b, và được sử dụng làm tiêu chuẩn lựa chọn thuộc tính trong thuật toán heuristic tìm tập rút gọn của bảng quyết định. Để xây dựng thuật toán heuristic tìm tập rút gọn, ta có thể sử dụng hai hướng tiếp cận: hướng tiếp cận từ dưới lên (bottom-up) và hướng tiếp cận từ trên xuống (top-down). Trong phần này, luận văn tìm hiểu thuật toán heuristic tìm tập rút gọn tính toán lõi theo hướng tiếp cận bottom-up. Ý tưởng của thuật toán là xuất phát từ tập lõi, lần lượt bổ sung vào tập lõi các thuộc tính có độ quan trọng lớn nhất cho đến khi tìm được tập rút gọn. Thuật toán đưa ra sử dụng chiến lược Thêm - Xóa [20].
2.3. Thuật toán tìm tập lõi sử dụng metric LSI Keyword
Đầu vào: Bảng quyết định DS U , C D,V , f . Đầu ra: Tập lõi MCORE C . MCORE C ; If d J ( K C c , K C c D ) d J ( K C , K C D ) then MCORE C : MCORE C c; Return MCORE C ; Phân tích độ phức tạp thời gian của Thuật toán 2.1 Sử dụng thuật toán trong [9] để tính U / C , độ phức tạp thời gian là O C U . Do đó, độ phức tạp thời gian để tính d J K C , K C D là O C U . Vì vậy, độ phức tạp thời gian của vòng lặp For từ dòng lệnh thứ 3 đến dòng lệnh 2 thứ 7 là O C U và độ phức tạp thời gian của Thuật toán 2.
III. Nghiên Cứu Tham Số Độ Chắc Chắn Luật Quyết Định 57 Ký Tự
Như đã trình bày ở phần trên, tập rút gọn tốt nhất thu được bởi Thuật toán 2.3 chính là tập rút gọn Entropy Shannon nên bảo toàn độ chắc chắn của tập luật quyết định và độ chắc chắn của tất cả các luật phân lớp vào các lớp quyết định. Tuy nhiên, nhiều bài toán trong thực tế không thể tìm được tập rút gọn mà bảo toàn độ chắc chắn của tập luật quyết định. Do đó, vấn đề đặt ra là tìm một tập rút gọn tốt nhất sao cho độ chắc chắn của tập luật quyết định chỉ cần lớn hơn một giá trị ngưỡng cho trước chứ không cần bằng độ chắc chắn của tập luật trên bảng quyết định ban đầu. Trong [1], tác giả Hoàng Thị Lan Giao cũng đề xuất các thuật toán tìm tập rút gọn dựa trên các tiêu chuẩn đánh giá sai số khác nhau, còn gọi là tập rút gọn xấp xỉ, sử dụng ma trận phân biệt và các phép toán trong đại số quan hệ. Tuy nhiên, các thuật toán trong [1] chỉ tìm tập rút gọn xấp xỉ của bảng quyết định nhất quán. Dựa vào tính chất của metric được xây dựng là đại lượng đối ngẫu với độ chắc chắn của tập luật quyết định, luận văn đi tìm hiểu Thuật toán 2.4 tìm một tập rút gọn tốt nhất theo tham số đưa vào là độ chắc chắn . Nghĩa là, độ chắc chắn của tập luật quyết định dựa trên tập rút gọn sẽ lớn hơn một ngưỡng độ chắc chắn cho trước.
3.1. Tìm kiếm tập rút gọn theo ngưỡng độ chắc chắn cho trước
Giả sử DS là độ chắc chắn của tập luật trên bảng quyết định ban đầu DS và DS ' là độ chắc chắn của tập luật trên bảng quyết định DS ' với tập rút gọn R C , là ngưỡng độ chắc chắn với DS . Tìm một tập rút gọn tốt nhất theo ngưỡng độ chắc chắn Đầu vào: Bảng quyết định DS U , C D,V , f , giá trị ngưỡng độ chắc chắn với DS . Đầu ra: Một tập rút gọn tốt nhất R sao cho DS ' .
3.2. Ảnh hưởng của tham số độ chắc chắn tới kết quả LSI Keyword
Khởi tạo DS ' 0 ; Tính d J K R , K R D ; // Thêm dần vào R các thuộc tính có độ quan trọng lớn nhất theo ngưỡng While DS ' do Chọn am C R sao cho SIGR am Max SIGR a ; End; //Loại bỏ các thuộc tính dư thừa trong R nếu có theo ngưỡng . If DS ' then R R a ; Return R ; Tương tự Thuật toán 2.3, độ phức tạp của Thuật toán 2.
IV. Thuật Toán Tìm Thuộc Tính Rút Gọn Bảng Nhất Quán 53 Ký Tự
Trong các bài toán thực tế, bảng quyết định thường chứa các đối tượng không nhất quán (là các đối tượng bằng nhau trên tập thuộc tính điều kiện nhưng khác nhau trên tập thuộc tính quyết định), gọi là bảng quyết định không nhất quán. Tuy nhiên, tùy thuộc vào lớp bài toán cần giải quyết mà ta có thể chuyển bảng quyết định không nhất quán về bảng quyết định nhất quán qua bước tiền xử lý số liệu bằng cách loại bỏ các đối tượng không nhất quán. Như đã trình bày trong chương 1, bảng quyết định DS U , C d ,V , f là nhất quán khi và chỉ khi phụ thuộc hàm C d đúng và B là một tập rút gọn của C nếu B là tập tối thiểu thỏa mãn phụ thuộc hàm B d [12]. Trong cơ sở dữ liệu quan hệ, với quan hệ r trên tập thuộc tính R thì B R là một tập tối thiểu của thuộc tính d R, d B nếu B là tập tối thiểu thỏa mãn phụ thuộc hàm B d [6]. Do đó, khái niệm tập rút gọn của bảng quyết định tương đương với khái niệm tập tối thiểu của thuộc tính d trên quan hệ. Với đối tượng nghiên cứu là các bảng quyết định nhất quán, chương này trình bày một số thuật toán liên quan đến tập rút gọn sử dụng một số thuật toán và một số kết quả liên quan đến tập tối thiểu của một thuộc tính trong cơ sở dữ liệu quan hệ.
4.1. Kết nối giữa tập rút gọn và tập tối thiểu Semantic Keyword
Bảng quyết định trong các bài toán thực tế thường chứa một số thuộc tính dư thừa thực sự, là những thuộc tính mà việc loại bỏ chúng không ảnh hưởng gì đến việc phân lớp tập đối tượng. Sự có mặt của các thuộc tính này làm cho độ phức tạp tính toán của bài toán khai phá dữ liệu tăng lên rất lớn. Việc loại bỏ các thuộc tính này trước khi thực hiện các nhiệm vụ khai phá dữ liệu có ý nghĩa thực tiễn cao trong bối cảnh dữ liệu ngày càng lớn, ngày càng đa dạng và phức tạp. Như đã trình bày trong Mục 1.4, trong bảng quyết định thuộc tính dư thừa thực sự là thuộc tính không xuất hiện trong bất kỳ tập rút gọn nào và thuộc tính rút gọn là thuộc tính xuất hiện trong một tập rút gọn nào đó. Khi đó, bài toán tìm tập tất cả thuộc tính dư thừa thực sự tương đương với bài toán tìm tập tất cả các thuộc tính rút gọn. Để giải quyết bài toán này, phương pháp tiếp cận thông thường là tìm họ tất cả các tập rút gọn của bảng quyết định, sau đó tìm phép hợp giữa các tập rút gọn. Tuy nhiên, cách tiếp cận này không khả thi với các bảng dữ liệu kích thước lớn vì độ phức tạp thời gian của thuật toán tìm họ tất cả các tập rút gọn của bảng quyết định là hàm mũ đối với số thuộc tính điều kiện. Trong phần này, luận văn tìm hiểu một thuật toán tìm tập tất cả các thuộc tính rút gọn của bảng quyết định nhất quán có độ phức tạp thời gian là đa thức.
4.2. Bổ đề Demetrovics J.D và ứng dụng trong rút gọn
Trong cơ sở dữ liệu quan hệ, Demetrovics J.D [5] đã chứng minh bổ đề quan trọng sau. Giả sử K là một hệ Sperner trên R, khi đó K R K . Trên quan hệ r, do K ar là hệ Sperner trên R nên ta có bổ đề sau: Cho r là một quan hệ trên R và a R , khi đó K R K Cho bảng quyết định nhất quán DS U , C d ,V , f với U u1 , u2 ,. Xét quan hệ r u1 , u2 ,., um trên tập thuộc tính R C d , từ khái niệm tập rút gọn của bảng quyết định nhất quán và tập tối thiểu của một thuộc tính trên quan hệ được trình bày, ta có PRED C K dr d , với PRED C là họ tất cả các tập rút gọn Pawlak của C trong DS và K dr là họ các tập tối thiểu của thuộc tính d trên r. Do đó, nếu ký hiệu REAT C là tập tất cả các thuộc tính rút gọn của C thì REAT C d R R R RPRED C d K r
4.3. Thuật toán tìm thuộc tính rút gọn LSI Keyword
Đầu vào: Bảng quyết định DS U , C d ,V , f với POSC d U , C c1 , c2 ,., um Đầu ra: REAT C là tập tất cả các thuộc tính rút gọn của C. Xét quan hệ r u1 , u2 ,., um trên tập thuộc tính R C d . Từ r ta tính hệ bằng nhau Er Eij :1 i j m với Eij a R : a ui a u j . Từ Er ta xây dựng tập M d A Er : d A B Er : d B, A B . Xây dựng tập V R K . Tập REAT C được xây dựng là tập tất cả các thuộc tính rút gọn của C.
V. Xây Dựng Phụ Thuộc Hàm Từ Bảng Quyết Định 54 Ký Tự
Cho bảng quyết định nhất quán DS U , C d ,V , f với U u1 , u2 ,. Trong phần này, luận văn trình bày thuật toán xây dựng sơ đồ quan hệ sd R, F với R C d và F là tập các phụ thuộc hàm có dạng Ki d với Ki C sao cho PRED C K ds d , K ds là họ các tập tối thiểu của thuộc tính d trên sd .
5.1. Thuật toán xây dựng phụ thuộc hàm LSI Keyword
Đầu vào: Bảng quyết định DS U , C d , V , f với POSC d U . Đầu ra: sd R, F mà K ds d PRED C Bước 1. Từ bảng quyết định DS, Sử dụng Thuật toán 2. Giả sử PRED C K1 , K2 ,. Với mỗi Ki PRED C ,1 i t xây dựng PTH Ki d . SĐQH sd R, F với R C d và F Ki d : Ki PRED C là SĐQH cần xây dựng. Chứng minh PRED C K ds d
5.2. Mối liên hệ giữa phụ thuộc hàm và tập rút gọn
Với K PRED C ta có K d , K d và không tồn tại K ' K sao cho K ' d . Do đó, theo định nghĩa K là một tập tối thiểu của thuộc tính d trên sd , nghĩa là K K ds d . Ngược lại, với K K ds d ta có K d , K d và không tồn tại K ' K sao cho K ' d . Dễ thấy với mọi Ki PRED C ,1 i t , K Ki .10) Vì nếu K Ki thì K i không phải là một tập rút gọn của DS. Hơn nữa, với mọi Ki PRED C ,1 i t , Ki K .11) Vì nếu Ki K thì K không phải là một tập tối thiểu của thuộc tính d trên sd . Từ công thức (2., Kt là hệ Sperner và với mọi A K ta có A d . Do đó, với quan hệ r trên tập thuộc tính R C d ta có K d là họ các tập tối thiểu của thuộc tính d trên quan hệ r.
VI. Thực Nghiệm Thuật Toán Rút Gọn trong Bảng 52 Ký Tự
Tìm hiểu một thuật toán heuristic tìm một tập rút gọn tốt nhất theo tiêu chuẩn đánh giá là độ quan trọng của thuộc tính (chất lượng phân lớp của thuộc tính). Thuật toán này giảm thiểu đáng kể khối lượng tính toán, nhờ đó có thể áp dụng đối với các bài toán có dữ liệu lớn. Các thuật toán heuristic này thường được xây dựng theo hai hướng tiếp cận khác nhau: hướng tiếp cận từ dưới lên (bottom-up) và hướng tiếp cận từ trên xuống (top-down). Dựa vào nhận xét tập lõi xuất hiện trong mọi tập rút gọn nên các thuật toán xây dựng theo hướng tiếp cận bottom-up được chia thành hai nhóm: các thuật toán tính toán lõi và các thuật toán không tính toán lõi. Ý tưởng chung của các thuật toán tính toán lõi là xuất phát từ tập lõi, bổ sung dần dần các thuộc tính có độ quan trọng lớn nhất vào tập lõi cho đến khi thu được tập rút gọn. Các thuật toán không tính toán lõi xuất phát từ tập rỗng và bổ sung dần các thuộc tính có độ quan trọng lớn nhất cho cho đến khi thu được tập rút gọn. Các thuật toán được xây dựng theo hướng tiếp cận buttom-up xuất phát từ tập thuộc tính điều kiện ban đầu, loại bỏ dần các thuộc tính có độ quan trọng nhỏ nhất cho đến khi thu được tập rút gọn. Cả hai hướng tiếp cận này đều đòi hỏi phải sắp xếp danh sách các thuộc tính theo thứ tự giảm dần hoặc tăng dần của độ quan trọng tại mỗi bước lặp.
6.1. So sánh hiệu quả thuật toán CEBARKCC và MBAR
Trong phần này, chúng tôi chọn thuật toán tìm một tập rút gọn tốt nhất sử dụng entropy Shannon có điều kiện có tính toán lõi [18] (gọi tắt là thuật toán CEBARKCC) để so sánh với thuật toán sử dụng khoảng cách do chúng tôi tìm hiểu (gọi tắt là thuật toán MBAR – Metric Based Attribute Reduction) về thời gian thực hiện và kết quả thực hiện. Để tiến hành thử nghiệm, chúng tôi thực hiện các công việc sau: - Cài đặt thuật toán CEBARKCC và thuật toán MBAR bằng ngôn ngữ C#. Cả hai thuật toán đều sử dụng thuật toán trong [11] để tính U / C . - Chạy thử nghiệm cả hai thuật toán trên cùng một cấu hình máy tính, so sánh kết quả thực hiện hai thuật toán và đánh giá tính hiệu quả của thuật toán MBAR về thời gian thực hiện. Trước hết, chúng tôi trình bày thuật toán CEBARKCC .
6.2. Đánh giá và kết quả thử nghiệm trên bộ dữ liệu UCI LSI Keyword
Sau khi cài đặt, chúng tôi tiến hành thử nghiệm thuật toán CEBARKCC và thuật toán MBAR trên 8 bộ số liệu vừa và nhỏ lấy từ kho dữ liệu UCI [21]. Môi trường chạy thử nghiệm là máy tính PC với cấu hình Pentium dual core 2.13 GHz CPU, 1GB bộ nhớ RAM, sử dụng hệ điều hành Windows XP Professional. Với mỗi bộ số liệu, giả sử U là số đối tượng, C là số thuộc tính điều kiện, R là số thuộc tính của tập rút gọn thu được; t là thời gian thực hiện thuật toán (đơn vị là giây s). Kết quả chạy thử nghiệm được tổng kết trong Bảng 3.2 sau đây:
24/09/2025
