Đề tài Nghiên cứu một số phương pháp khai thác dữ liệu và ứng dụng

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC ĐÀ LẠT BÁO CÁO ĐỀ TÀI NGHIÊN CỨU KHOA HỌC CẤP BỘ 2007 - 2009 “NGHIÊN CỨU MỘT SỐ PHƯƠNG PHÁP KHAI THÁC DỮ LIỆU VÀ ỨNG DỤNG” Mã số : B2007 - 14 - 14 Chủ nhiệm đề tài : ThS. Trần Tuấn Minh Đà Lạt, 5/2009 DANH SÁCH NHỮNG NGƯỜI THAM GIA THỰC HIỆN STT Họ và Tên Đơn vị 1 PGS. TS Lê Hoài Bắc Khoa Công nghệ thông tin Trường đại học KHTN tp HCM 2 TS. Trương Chí Tín Khoa Toán Tin Trường Đại học Đà Lạt 3 ThS. Trần Ngọc Anh Khoa Toán Tin Trường Đại học Đà Lạt 4 Nguyễn Văn Phúc Khoa Công nghệ thông tin Trường Đại học Đà Lạt 5 Nguyễn Ngọc Hoàng Trâm MỤC LỤC Trang ƒ Danh sách những người tham gia 2 ƒ Mục lục 3 ƒ Tóm tắt kết quả nghiên cứu đề tài (tiếng Việt) 4 ƒ Tóm tắt kết quả nghiên cứu đề tài (tiếng Anh) 6 ƒ Giới thiệu đề tài (Mục tiêu, cách tiếp cận, phương pháp, phạm vi, nội dung nghiên cứu . . .) 8 ƒ Phần 1: “Về một thuật giải phân lớp dữ liệu dựa vào tập thô dung sai” . 13 ƒ Phần 2 : “Thuật toán khai thác luật kết hợp rút gọn từ dàn” . 23 ƒ Phần 3: Hệ thống một số thuật giải trong các phương pháp gom cụm dữ liệu, khai thác luật kết hợp và cài đặ chương trình ứng dụng. 38 o A. Hệ thống một số thuật giải gom cụm dữ liệu 38 o B. Hệ thống một số thuật giải khai thác luật kết hợp 57 o C. Cài đặt chương trình ứng dụng” 72 ƒ Phần 4: Kết luận và Kiến nghị 80 ƒ Tài liệu tham khảo 82 ƒ Phụ lục 85 TÓM TẮT KẾT QUẢ NGHIÊN CỨU ĐỀ TÀI KHOA HỌC VÀ CÔNG NGHỆ CẤP BỘ • Tên đề tài: • “Nghiên cứu một số phương pháp khai thác dữ liệu và ứng dụng” • Mã số : B2007 - 29 - 55 • Chủ nhiệm đề tài : ThS. Trần Tuấn Minh • Cơ quan chủ trì đề tài : Trường Đại học Đà Lạt • Cơ quan và cá nhân phối hợp thực hiện: o PGS. TS Lê Hoài Bắc, Khoa Công nghệ thông tin Trường đại học KHTN tp HCM o TS. Trương Chí Tín, Khoa Toán Tin - Trường Đại học Đà Lạt o ThS. Trần Ngọc Anh, Khoa Toán Tin - Trường Đại học Đà Lạt o KS. Nguyễn Văn Phúc, Khoa Công nghệ thông tin - Trường Đại học Đà Lạt o KS. Nguyễn Ngọc Hoàng Trâm. • Thời gian thực hiện: 3/2007 → 3/2009 I. Mục tiêu: • Hệ thống một số thuật giải gom cụm dữ liệu, khai thác luật kết hợp và cài đặt chương trình minh họa. • Nghiên cứu phân lớp dữ liệu bằng công cụ tập thô. • Nghiên cứu khai thác luật kết hợp rút gọn từ dàn. II. Nội dung chính: Trong các phương pháp khai thác dữ liệu phổ biến, đề tài tập trung tìm hiểu, nghiên cứu các phương pháp sau: • Gom cụm dữ liệu: Trong lĩnh vực gom cụm dữ liệu, các tác giả tìm hiểu, nghiên cứu và hệ thống các thuật giải gom cụm dữ liệu • Phân lớp dữ liệu: Trong phân lớp dữ liệu, các tác giả tìm hiểu, nghiên cứu công cụ tập thô, tập thô dung sai để phân lớp dữ liệu. • Khai thác luật kết hợp: Trong lĩnh vực khai thác luật kết hợp, các tác giả tìm hiểu, nghiên cứu và hệ thống các thuật giải tìm các tập luật, và nghiên cứu phương pháp rút gọn tập luật. Về ứng dụng, các tác giả cài đặt chương trình minh họa các thuật giải gom cụm và khai thác luật kết hợp và thực hiện trên bộ dữ liệu thử nghiệm, qua đó đưa ra ý kiến tư vấn sinh viên liên quan chọn chuyên ngành học. III. Kết quả chính đạt được 1. CÔNG TRÌNH KHOA HỌC Đà CÔNG BỐ: - Trần Tuấn Minh (2007), “Về một thuật giải phân lớp dữ liệu dựa vào tập thô dung sai”, Kỷ yếu Hội thảo quốc gia “Một số vấn đề về Công nghệ thông tin và truyền thông ” lần thứ IX, Trang 405 – 414, Nhà xuất bản Khoa học và Kỹ thuật, Hà Nội. - Trương Chí Tín, Trần Ngọc Anh, Trần Tuấn Minh (2007), “Thuật toán khai thác luật kết hợp rút gọn từ dàn” , “Thông báo Khoa học” của trường Đại học Đà Lạt năm 2007, trang 193 – 206. 2. BÁO CÁO KỸ THUẬT - Nguyễn văn Phúc, Nguyễn Ngọc Hoàng Trâm, Trần Tuấn Minh, “Hệ thống một số thuật giải gom cụm dữ liệu và luật kết hợp, cài đặt chương trình ứng dụng ”. 3. ĐÀO TẠO: - Sinh viên ngành Công nghệ thông tin : 3 S TT Họ và tên Sinh viên Đề tài Năm bảo vệ 1 Nguyễn Văn Phúc Nguyễn ngọc Hoàng Trâm Tìm hiểu phương pháp gom cụm dữ liệu và luật kết hợp và ứng dụng 2007 2 Phan Ngọc Bảo Tìm hiểu gom cụm văn bản và ứng dụng 2008 SUMMARY • Project title : RESEARCH SOME DATA MINING METHODS AND ITS APPLICATIONS • Code number: B2007 - 29 - 55 • Coodinator: Tran Tuan Minh, MSc. • Implementing Institution: University of Dalat • Cooperating Institutions: o Le Hoai Bac, Ph.D., Associated Professor, Faculty of Information Technology, University of Science Ho Chi Minh City. o Trương Chí Tín, Ph.D., Faculty of Mathematics and Computer Science, University of Dalat o Tran Ngoc Anh, MSc., Faculty of Mathematics and Computer Science, University of Dalat o Nguyen Van Phuc, BSc., Faculty of Information Technology, University of Dalat o Nguyễn Ngọc Hoàng Trâm, bsC. • Duration: From 2007 to 2009 (24 months) I. Objectives • Systematizing some clustering algorithm, mining association rules and implementing demonstration application. • Studying data classifying by rough sets. • Studying exploration mining rule from lattices. II. Main Contains: Among popular data mining methods, this project focuses on researching and studying those methods: • Data clustering: In the data clustering area, authors researched, studied and systemized the data clustering algorithms. • Data Classifying: In the data classifying area, authors researched and studied tolerance rough sets. • Exploring association rules: In the exploring association rule area, the authors studied, researched and systemized finding rules algorithm and researched reduction rule set methods. About application, the authors implemented demonstration application of clustering algorithms and exploring association rule algorithms. Build an application about prediction of selection of field of study base on one experiment database. III. Results obtained: • Improved one data classifying algorithm base on Tolerant Rough Set of Daijin Kim. • Provided some algorithms about finding reducted-rule set and result-rule set which is intefere from two simple normal rule "understandable in logic" from popular rule set build up from lattices. GIỚI THIỆU ĐỀ TÀI I. Mở đầu Với sự phát triển mạnh mẽ của công nghệ điện tử tạo ra bộ nhớ có dung lượng lớn, bộ xử lý tốc độ cao, các công ty xí nghiệp tạo ra các hệ thống thông tin nhằm tự động hóa các họat động kinh doanh của mình. Điều này đã tạo ra một dòng dữ liệu tăng lên không ngừng vì ngay các giao dịch đơn giản như một cuộc gọi điện thoại, một lần kiểm tra sức khỏe,. . . đều được ghi vào bộ nhớ máy tính. Nhiều hệ quản trị cơ sở dữ liệu mạnh với các công cụ phong phú đã giúp cho con người khai thác có hiệu quả các nguồn dữ liệu đó. Mô hình cơ sở dữ liệu quan hệ và ngôn ngữ SQL đã có vai trò hết sức quan trọng trong việc tổ chức khai thác cơ sở dữ liệu. Cùng với sự gia tăng không ngừng khối lượng dữ liệu, các hệ thống thông tin cũng được chuyên môn hóa, phân chia theo tùng lĩnh vực ứng dụng. Như vậy, sự thành công trong kinh doanh không chỉ phụ thuộc vào chức năng khai thác dữ liệu có tính chất nghiệp vụ, mà còn phụ thuộc vào tính linh họat và sẵn sàng đáp ứng yêu cầu trong thực tế. Nói cách khác, cơ sở dữ liệu cần đem lại tri thức hơn chính những dữ liệu đó. Từ khối dữ liệu khổng lồ sẵn có, phải tìm ra các thông tin tiềm ẩn có giá trị mà trước đó chưa được phát hiện, tìm ra những xu hướng phát triển và những yếu tố tác động lên chúng, các quyết định chính xác cần phải đưa ra càng nhanh càng tốt. Lúc này, các mô hình cơ sở dữ liệu truyền thống đã cho thấy không có khả năng thực hiện tốt công việc. Để lấy được các tri thức trong lượng thông tin khổng lồ đó, cần phải có những công nghệ, những kỹ thuật khác. Đó là Khám phá tri thức và khai thác dữ liệu (KDD: Knowledge Discovery in Database) - thực hiện quá trình khám phá tri thức trong cơ sở dữ liệu mà trong đó kỹ thuật cho phép ta lấy được tri thức chính là Khai thác dữ liệu. II. Mục đích của khai thác dữ liệu Theo Fayyad, khai thác dữ liệu là tiến trình tìm kiếm các mẫu mới, có ích, tiềm ẩn trong khối dữ liệu lớn. Các tri thức chiết xuất được sẽ được sử dụng cho lợi ích cạnh tranh trên thương trường hay trong nghiên cứu khoa học. Cho nên có thấy mục đích chính của khai thác dữ liệu là mô tả và dự báo. 1. Mô tả (Description ): Mô tả tập trung vào việc tìm kiếm các mẫu mô tả dữ liệu mà con người có thể hiểu được. Các mô hình KTDL càng dễ hiểu càng tốt. Những kết quả từ mô hình KTDL cần phải mô tả trong sáng các mẫu để biểu diễn và giải thích một cách trực quan. Sự mô tả đạt chất lượng cao thường có thể được hoàn thành bởi sự phân tích dữ liệu có tính khám phá, đó là một phương pháp đồ thị của việc khám phá dữ liệu trong việc tìm kiếm các mô hình và khuynh hướng. 2. Dự báo (Prediction ): Dự báo liên quan đến việc sử dụng các biến hoặc các trường trong CSDL để chiết xuất ra các mẫu là các dự đoán những giá trị chưa biết hoạc những giá trị trong tương lai của các biến đáng quan tâm. III. Những nhiệm vụ chính trong khai thác dữ liệu (KTDL) 1. Phân lớp (Classification): Phân lớp là việc học một hàm ánh xạ một mấu dữ liệu vào một trong số các lớp đã xác định. 2. Hồi quy (Regression): Hồi quy là việc học một hàm ánh xạ từ một mẫu dữ liệu thành một biến dự đoán có giá trị thực. 3. Gom cụm (Clustering): Là việc mô tả để tìm ra các nhóm dữ liệu, các nhóm này có thể rời nhau, phân cấp hay gối lên nhau. 4. Tóm tắt (Summarization): Liên quan đến các phương pháp tìm kiếm một mô tả tóm tắt cho một tập con dữ liệu. 5. Mô hình hóa phụ thuộc (Dependency Modeling): Tìm kiếm mô hình mô tả sự phụ thuộc giữa các biến. IV. Các phương pháp khai thác dữ liệu phổ biến: 1. Phương pháp quy nạp (induction): Cách thức suy ra các thông tin từ cơ sở dữ liệu; Có nghĩa là tìm kiếm, tạo mẫu và sinh ra tri thức chứ không phải bắt đầu với các tri thức đã biết trước. 2. Cây quyết định (decision tree) và luật (Rule): Cây quyết định là mô tả tri thức dạng đơn giản nhằm phân các đối tượng dữ liệu thành một số lớp nhất định. Các luật được tạo ra nhằm suy diễn một số mẫu có ý nghĩa về mặt thống kê. Các luật có dạng “Nếu P thì Q” với P là mệnh đề đúng với một phần trong cơ sở dữ liệu, Q là mềnh đề dự đoán. 3. Phát hiện các luật kết hợp (Association ): Phương pháp này phát hiện ra các luật kết hợp giữa các thành phần dữ liệu trong cơ sở dữ liệu. Mẫu đầu ra thuật giải phát hiện luật kết hợp là tập các luật kết hợp tìm được. Các luật kết hợp thường ở dạng “nếu nguyên nhân (antecedent) thì kết quả (consequent)”, cùng với độ hỗ trợ (support) và độ tin cậy (confidence) liên quan đến luật. 4. Phân lớp (Classification ): Xác định một đối tượng vào một trong các lớp đã biết. 5. Gom cụm (Clustering ): Gom cụm là nhóm các đối tượng tương tự (giống nhau) thành các cụm. Một cụm (cluster) là một tập các đối tượng tương tự nhau và không giống với các đối tượng trong các nhóm khác. Các thuật giải gom cụm tìm và phân đoạn toàn bộ tập dữ liệu thành các nhóm hay các nhóm con tương đối đồng nhất, ở đó sự giống nhau (tương tự) của các đối tượng trong nhóm được chú trọng và không quan tâm đến sự giống nhau tới các đối tượng bên ngoài. 6. Mạng nơron (Neuron Network) Mạng neuron là tiếp cận tính toán mối liên quan đến việc phát triển các cấu trúc toán học và khả năng học. Phương pháp này là kết quả của việc nghiên cứu mô hình học của hệ thống thần kinh con người. Mạng neuron có thể đưa ra ý nghĩa từ các dữ liệu phức tạp hoặc không chính xác và có thể sử dụng để chiết xuất các mẫu. 7. Thuật giải di truyền (Genetic Algorithm ): Mô phỏng lại hệ thống tiến hóa trong tự nhiên . Thuật giải chỉ ra các cá thể được hình thành, được ước lượng và biến đổi như thế nào.Thuật giải di truyền được sử dụng tìm lời giải cho các bài toán tối ưu. . . . V. Nội dung và Phạm vi nghiên cứu: Trong các phương pháp khai thác dữ liệu phổ biến, đề tài tập trung tìm hiểu, nghiên cứu các phương pháp sau: • Gom cụm dữ liệu: Trong lĩnh vực gom cụm dữ liệu, các tác giả tìm hiểu, nghiên cứu và hệ thống các thuật giải gom cụm dữ liệu • Phân lớp dữ liệu: Trong phân lớp dữ liệu, các tác giả tìm hiểu, nghiên cứu công cụ tập thô, tập thô dung sai để phân lớp dữ liệu. • Khai thác luật kết hợp: Trong lĩnh vực khai thác luật kết hợp, các tác giả tìm hiểu, nghiên cứu và hệ thống các thuật giải tìm các tập luật, và nghiên cứu phương pháp rút gọn tập luật. VI. Mục tiêu của đề tài: • Hệ thống một số thuật giải gom cụm dữ liệu, khai thác luật kết hợp và cài đặt chương trình minh họa. • Nghiên cứu phân lớp dữ liệu bằng công cụ tập thô. • Nghiên cứu khai thác luật kết hợp rút gọn từ dàn. VII. Cấu trúc trình bày nội dung kết quả nghiên cứu: Các kết quả chính được trình bày trong báo cáo tổng kết đề tài theo cấu trúc sau: Phần 1: Trình bày kết quả báo cáo khoa học “Về một thuật giải phân lớp dữ liệu dựa vào tập thô dung sai” của tác giả Trần Tuấn Minh, công bố năm 2007 trong Kỷ yếu Hội thảo quốc gia “Một số vấn đề về Công nghệ thông tin và truyền thông ” lần thứ IX . Phần 2: Trình bày kết quả báo cáo khoa học “Thuật toán khai thác luật kết hợp rút gọn từ dàn” của các tác giả Trương Chí Tín, Trần Ngọc Anh, Trần Tuấn Minh, công bố năm 2007 trong “Thông báo Khoa học” của trường Đại học Đà Lạt. Phần 3: Trình bày báo cáo kỹ thuật về kết quả tìm hiểu lĩnh vực gom cụm dữ liệu và khai thác luật kết hợp : “ Hệ thống một số thuật giải trong các phương pháp gom cụm dữ liệu, khai thác luật kết hợp và cài đặt chương trình ứng dụng”. Phần 4: Kết luận và kiến nghị. Phần 1: VỀ MỘT THUẬT GIẢI PHÂN LỚP DỮ LIỆU DỰA VÀO TẬP THÔ DUNG SAI Trần Tuấn Minh Khoa Công nghệ Thông tin – Đại học Đà Lạt Email: minhtuan53@gmail.com Tóm tắt: Có nhiều cách tiếp cận cũng như có nhiều thuật giải để giải bài toán phân lớp dữ liệu trong khai thác dữ liệu. Daijin Kim đã đưa ra trong [1] một thuật giải sử dụng công cụ tập thô dung sai. Thuật giải của Daijin Kim tiến hành 2 giai đoạn: giai đoạn đầu sử dụng công cụ tập xấp xỉ dưới để phân lớp dữ liệu. Giai đoạn hai tiến hành phân lớp các phần tử không phân lớp được trong giai đoạn đầu bằng cách sử dụng công cụ tập xấp xỉ trên và hàm thành viên thô. Trong giai đoạn hai của thuật giải phân lớp, Daijin Kim đã sử dụng tập biên BN(Y) = )(YAτ - Aτ (Y), với tập xấp xỉ trên )(YAτ có kích thước quá lớn, trong khi đó ta có thể chỉ ra một tập thực sự nhỏ hơn đáp ứng được yêu cầu thuật giải. Trong bài báo này tác giả chỉ ra một tập xấp xỉ trên )(YAτ thỏa mãn )()()( YYY A A A τττ ⊂⊆ . 1. TẬP THÔ DUNG SAI Lý thuyết tập thô (rough sets) do Pawlak đề xuất vào năm 1982 và có nhiều ứng dụng trong khai thác dữ liệu. Ý tưởng quan trọng của tập thô là xử lý dữ liệu không chắc chắn, khám phá các phụ thuộc, xấp xỉ dữ liệu, phân loại, đo ý nghĩa thuộc tính, thu giảm dữ liệu, thiết kế các luật quyết định, . . . Lý thuyết tập thô sử dụng trong các giai đoạn xử lý thông tin: ƒ Tổ chức bảng quyết định, trình bày hệ thống thông tin chứa dữ liệu không chắc chắn hoặc dữ liệu không đúng. ƒ Tính tập xấp xỉ dưới và xấp xỉ trên của tập dữ liệu. ƒ Nhận dạng và đánh giá sự phụ thuộc của các tập thuộc tính. ƒ . . . Trong phần này sẽ đề cập đến một số khái niệm cần thiết và quan trọng về tập thô có liên quan đến những vấn đề được đưa ra trong bài báo. 1.1 Hệ thống thông tin (information system) Hệ thông thông tin là bộ S = , trong đó: ƒ U là tập hữu hạn các đối tượng và khác ∅. ƒ Q là tập hữu hạn các thuộc tính và khác ∅. ƒ V = , với Va = Tập hữu hạn các giá trị của thuộc tính a. U Q∈a aV ƒ Hàm f : UxQ → V (x,a) → f(x,a) ∈ V; x ∈ U , a ∈ Q. gọi là hàm thông tin. 1.2 Bảng quyết định (decision table) Cho hệ thống thông tin S = . Bảng quyết định thiết kế từ hệ thống S, ký hiệu như sau: DT = trong đó: ∅ ≠ A, D ⊆ Q; A ∩ D = ∅ và A ∪ D = Q. ({A, D} là một phân hoạch khác rỗng của Q) Ta thường gọi A là tập các thuộc tính điều kiện, D là tập các thuộc tính quyết định. Trong thực tiễn, thường lấy D là tập chỉ gồm có 1 phần tử. Bảng quyết định trên còn ký hiệu vắn tắt . 1.3 Quan hệ bất khả phân (Indiscernibility relation) Cho hệ thống thông tin S = và A ⊆ Q , A ≠ ∅. Ta nói quan hệ bất khả phân trên U theo A, ký hiệu IND(A), được định nghĩa như sau: ∀u1,u2 ∈ U, u1 IND(A) u2 ⇔ ∀a∈A, f(u1,a) = f(u2,a). Khi đó, IND(A) là một quan hệ tương đương, tách tập U thành các lớp tương đương đôi một rời nhau. Một lớp tương đương trên U theo A với đại diện u ∈ U có dạng: [u]A = {x ∈ U: u IND(A) x} Tập A* = )(AIND U = {[u]A : u ∈ U } gọi là một phân lớp trên U. Một lớp tương đương [u]A còn được gọi là tập A-cơ bản trong hệ thống S. 1.4 Tập thô dung sai (Tolerant Rough Set) Tập thô được định nghĩa dựa vào quan hệ bất khả phân IND(A), với A là tập con khác rỗng của tập các thuộc tính Q, là một quan hệ tương đương, tức là các quan hệ hai ngôi trên U thỏa mãn 3 tính chất: ƒ Phản xạ. ƒ Đối xứng. ƒ Bắc cầu. Tuy nhiên trong thực tế ta hay gặp phải những quan hệ mà tính bắc cầu không được thỏa mãn, chẳng hạn quan hệ xác định các điểm gần biên. Quan hệ dung sai là quan hệ mở rộng quan hệ bất khả phân cho phù hợp với các bài toán phân lớp mà quan hệ giữa các đối tượng không có tính bắc cầu. 1.4.1 Quan hệ dung sai (the Tolerance Relation) Cho L là tập khác ∅. Một quan hệ hai ngôi trên L có các tính chất phản xạ và đối xứng được gọi là quan hệ dung sai. Vậy quan hệ bất khả phân là quan hệ dung sai. Ta cũng có thể chỉ ra dễ dàng có quan hệ dung sai nhưng không phải tương đương. 1.4.2. Tập thô dung sai Cho bảng quyết định DT = . Xét quan hệ dung sai τ trên U. Tập dung sai của đối tượng x ∈ U là tập ký hiệu và định nghĩa bởi: TS(x) = {y∈ U: xτ y} (TS(x) là tập gồm các phần tử trong U có quan hệ dung sai với x). Nhận xt: y∈TS(x) ⇔ x∈TS(y) 1.4.3. Tập xấp xỉ trên – tập xấp xỉ dưới Cho bảng quyết định DT = . Xét quan hệ dung sai τ trên U. Cho Y ⊆ U. ƒ Tập xấp xỉ dưới của Y là tập ký hiệu và định nghĩa bởi: τ (Y) = U Ux∈ {TS(x) : TS(x) ⊆ Y } ƒ Tập xấp xỉ trên của Y là tập ký hiệu và định nghĩa bởi: τ (Y) = U Ux∈ {TS(x) : TS(x) ∩ Y ≠ ∅ } 2. ĐỘ ĐO TƯƠNG TỰ (The similarity measure) 2.1 Độ đo tương tự theo thuộc tính Cho bảng quyết định DT = . Độ đo tương tự của 2 đối tượng x, y∈U theo thuộc tính a ∈ A là một giá trị ký hiệu và xác định như sau: Sa(x,y) = 1 – max ))(),(( d yaxad trong đó: d(a(x),a(y)): khoảng cách giữa hai giá trị thuộc tính a(x) và a(y). dmax : khoảng cách lớn nhất có thể giữa hai giá trị thuộc tính a(x) và a(y) (Lưu ý rằng dmax phụ thuộc vào thuộc tính a). Với mọi a ∈ A, quan hệ Ra trên Va định nghĩa như sau: ∀x, y ∈ U: a(x) Ra a(y) ⇔ Sa(x,y) ≥ t(a) với t(a) ∈ [0,1], gọi là giá trị ngưỡng tương tự của thuộc tính a. Ta gọi Ra là quan hệ tương tự trên Va. Nhận xét: 1. Dễ thấy Ra là quan hệ dung sai trên Va. 2. Ta có: d(a(x),a(y)) ≤ dmax ⇒ max )(),(( d yaxad ≤ 1 ⇒ Sa(x,y) ∈ [0,1]. 2.2 Độ đo tương tự theo tập các thuộc tính Độ đo tương tự của 2 đối tượng x,y∈U theo tập thuộc tính A được định nghĩa như sau: ∑ ∈ = Aa aA yxSA yxS ),(1),( Quan hệ Aτ trên U định nghĩa như sau: ∀x, y ∈ U: x Aτ y ⇔ SA(x,y) ≥ t(A) với t(A) ∈ [0,1], gọi là giá trị ngưỡng tương tự của tập A. Ta gọi Aτ là quan hệ tương tự theo tập A trên U. Nhận xét: 1. Dễ nhận thấy Aτ là quan hệ dung sai trên U. Ta gọi Aτ là quan hệ dung sai trên U theo tập thuộc tính điều kiện A. 2. Sa(x,y) ∈ [0,1] ⇒ AyxS Aa a ≤∑ ∈ ),( ⇒ ∑ ∈ = Aa aA yxSA yxS ),(1),( ≤ 1. Nên: SA(x,y) ∈ [0,1]. Trong phần sau, ta xét các tập thô dung sai của các đối tượng phụ thuộc vào quan hệ dung sai (tương tự) theo tất cả các thuộc tính Aτ . 3. PHÂN LỚP DỮ LIỆU DỰA TRÊN TẬP THÔ DUNG SAI 3.1 Phát biểu bài toán Cho bảng quyết định DT = trong đó: U = { x1 , x2 ,…., xN }; A ∩