Báo cáo thực tập tại công ty trách nhiệm hữu hạn cổ phần dịch vụ thương mại và truyền thông Thế giới trẻ

uá trình lâu dài và phức tạp nhằm nhận biết các mẫu hoặc mô hình ẩn chứa trong dữ liệu dựa trên các kỹ thuật thiết kế, tổng hợp, thăm dò, phân tích để phát hiện ra các mẫu dữ liệu thích hợp từ đó hợp thức hóa các kết quả tìm được bằng cách áp dụng các mẫu đã phát hiện cho tập con mới của dữ liệu. Ngày nay, trong hầu hết các lĩnh vực từ đời sống, kinh tế, xã hội, đến khoa học kỹ thuật, đều cần các công nghệ khai phá dữ liệu hiện đại, hiệu quả nhằm tìm ra các tri thức từ một khối lượng lớn thông tin, dữ liệu. Quá trình khai phá dữ liệu xuyên suốt qua nhiều giai đoạn từ xác định vấn đề, tiền xử lý (làm trong sáng dữ liệu, tổng hợp dữ liệu, chuyển đổi dữ liệu,), khai phá dữ liệu, đánh giá mẫu được khai phá đến trình bày tri thức được khai phá. Trong các giai đoạn này thì giai đoạn tiền xử lý dữ liệu là giai đoạn tốn thời gian nhất và giai đoạn khai phá dữ liệu là giai đoạn quan trọng nhất. Nhiệm vụ của khai phá dữ liệu là tìm ra các mẫu cần được quan tâm phù hợp với yêu cầu của đối tượng cần khai phá từ một khối lượng khổng lồ dữ liệu. Các mẫu sau khi khai phá là tri thức nằm tiềm ẩn trong dữ liệu và có thể được khai phá từ nhiều mô hình cơ sở dữ liệu khác nhau như: cơ sở dữ liệu quan hệ, cơ sở dữ liệu hướng đối tượng, cơ sở dữ liệu không gian, hoặc từ các dạng lưu trữ thông tin khác như cơ sở dữ liệu đa phương tiện, cơ sở dữ liệu thời gian thực,. Việc khai phá dữ liệu phù hợp và hiệu quả đối với các cơ sở dữ liệu lớn vẫn đang là nhu cầu và thách thức đối với các nhà khoa học 2.3. CÂY QUYẾT ĐỊNH 2.3.1. Khái niệm chung Phân lớp và dự đoán Trong một cơ sở dữ liệu lớn thường có nhiều thông tin hữu ích còn bị ẩn khuất, mà những thông tin này có thể được sự đụng để ra quyết định giao dịch hoặc là các tiên đoán thông minh đối với nhiều lĩnh vực. Đối với những dạng thông tin như thế thường thì các phương pháp phân tích, tổng hợp và thống kê truyền thống khó có thể phát hiện ra. Sự phân lớp và sự dự báo là hai dạng phân tích dữ liệu, chúng có thể được sử dụng để rút trích ra các mô hình mô tả các lớp dữ liệu quan trọng hoặc là để dự đoán các xu hướng dữ liệu tương lai. Trong khi sự phân lớp (classifcation) được dừng để dự đoán các nhãn rõ ràng, còn sự dự báo (prediction) được sử dụng để cho ra mô hình từ các hàm giá trị liên tục. Sự dự báo có thể được xem như sự xây dựng và sử dụng một mô hình để truy cập tới lớp mẫu không có nhãn, hoặc để truy cập các giá trị hoặc vùng giá trị của một thuộc tính, đây là các giá trị được mong đợi có mặt trong mẫu đã cho. Với cách nói này, thì sự phân lớp và sự hồi qui (classifcation and regression) là hai dạng cơ bản của các vấn đề dự đoán, trong khi sự phân lớp được sử dụng để dự đoán các giá trị được định danh hoặc các giá trị rời rạc, còn sự hồi qui thì được sử dụng để dự đoán các giá tri liên tục hoặc có thứ tự. Tuy nhiên, trong khai phá dữ liệu người ta thường chấp nhận: sự phân lớp dùng để dự đoán các nhãn lớp, còn sự dự đoán dùng để tiên đoán các giá trị liên tục (như việc sử dụng kỹ thuật hồi qui). Trong phần này và phần 3 sau đây, chúng ta sẽ nghiên cứu kỹ thuật phân lớp dữ liệu cơ bản đó là cơ sở dữ liệu quan hệ, các tính chất của cơ sở dữ liệu quan hệ, phụ thuộc hàm xấp xỉ và phân lớp bằng cây quyết định, một số phương pháp xây dựng cây quyết định và đây cũng chính là trọng tâm của báo cáo. Cây quyết định Cây quyết định là một kiểu mô hình dự báo (predictive model), nghĩa là một ánh xạ từ các quan sát về một sự vật/hiện tượng tới các kết luận về giá trị mục tiêu của sự vật/hiện tượng. Cây quyết định có cấu trúc hình cây và là một sự tượng trưng của một phương thức quyết định cho việc xác định lớp các sự kiện đã cho. Mỗi nút của cây chỉ ra một tên lớp hoặc một phép thử cụ thể, phép thử này chia không gian các dữ liệu tại nút đó thành các kết quả có thể đạt được của phép thử. Mỗi tập con được chia ra là không gian con của các dữ liệu được tương ứng với vấn đề con của sự phân lớp. Sự phân chia này thông qua một cây con tương ứng. Quá trình xây dựng cây quyết định có thể xem như là một chiến thuật chia để trị cho sự phân lớp đối tượng. Một cây quyết định có thể mô tả bằng các khái niệm nút và đường nối các nút trong cây. Mỗi nút của cây quyết định có thể là: Nút lá (leaft node) hay còn gọi là nút trả lời (answer node), nó biểu thị cho một lớp các trường hợp, nhãn của nó là tên của lớp. Nút không phải là lá (non-leaf node) hay còn gọi là nút trong (inner node), nút này xác định một phép thử thuộc tính (attribute test), nhãn của nút này có tên của thuộc tính và sẽ có một nhánh (hay đường đi) nối nút này đến cây con (sub-tree) ứng với mỗi kết quả có thể có của phép thử. Nhãn của nhánh này chính là giá trị của thuộc tính đó. Nút không phải lá nằm trên cùng là nút gốc (root node). Một cây quyết định sử dụng để phân lớp dữ liệu bằng cách bắt đầu đi từ nút gốc của cây và đi xuyên qua cây theo các nhánh cho tới khi gặp nút lá, khi đó ta sẽ được lớp của dữ kiện đang xét. Ví dụ: Giả sử ta có tập huấn luyện như sau: STT Tuổi Hệ số lương Ngạch công chức Học vị Có chức danh 1 >40 Cao Nghiên cứu viên chính Tiến sĩ khoa học Có 2 >40 Cao Nghiên cứu viên chính Tiến sĩ Có 3 >40 Trung bình Nghiên cứu viên Tiến sĩ Có 4 >40 Trung bình Nghiên cứu viên Thạc sĩ Không 5 30-40 Trung bình Nghiên cứu viên chính Tiến sĩ Có 6 30-40 Thấp Nghiên cứu viên Thạc sĩ Không 7 <30 Trung bình Nghiên cứu viên Tiến sĩ Có 8 <30 Thấp Nghiên cứu viên Thạc sĩ Không 9 30-40 Thấp Nghiên cứu viên Thạc sĩ Không Bảng 2.1.1.1. Tập mẫu dữ liệu huấn luyện về cán bộ, công chức Cây quyết định được xây dựng từ tập dữ liệu chuẩn đã cho ở bảng 2.1.1.1, bảng dữ liệu này được thu thập ở Viện Khoa học và Công nghệ Việt Nam về các cán bộ, công chức, viên chức đang làm việc tại Viện. Tập dữ liệu này gồm các thuộc tính tuổi, bảo về luận án ở nước ngoài, ngạch công chức, học vị. Các thuộc tính này được gọi là các thuộc tính ứng viên hay còn gọi là các thuộc tính kiểm tra và thuộc tính chức danh là thuộc tính lớp hay thuộc tính quyết định. Cây quyết định cho trường hợp này như sau: Bảng 2.1.1.1. Cây quyết định về việc có chức danh của cán bộ, viên chức Tóm lại, cây quyết định thường được dùng để mô tả tri thức dưới dạng đơn giản, dễ hiểu và gần gũi với con người từ tập dữ liệu lớn, phức tạp. Nó phân chia các đối tượng dữ liệu thành các lớp, tên của các lớp là các nhãn của các nút lá, nhãn của các nút trong là tên của các thuộc tính còn nhãn của các nhãnh chính là giá trị của các thuộc tính. Việc xây dựng cây quyết định thông thường thông qua các bước xây dựng, cắt tỉa và đánh giá. 2.3.2. Xây dựng cây quyết định Quá trình xây dựng cây quyết định được thực hiện bằng cách chia đệ quy tập dữ liệu mẫu cho tới khi mọi nút lá đều thuất nhất. Thuần nhất có nghĩa là sao cho tất cả các mẫu dữ liệu ở cùng một lớp. Nếu các nút là là không thuần nhất, cần thiết phải được kiểm tra để tìm ra phép tách tốt nhất. Thuộc tính được lựa chọn sau kiểm tra sẽ được gán nhãn cho nút tách đó và tập dữ liệu sẽ được chia ra thêm nữa theo các giá trị của thuộc tính. 2.3.3. Cắt tỉa cây quyết định Bước cắt tỉa cây quyết định được sử dụng để tối ưu hóa cây thu được sau khi xây dựng bao gồm: tối ưu về độ lớn của cây và tối ưu về độ chính xác của sự phân lớp bằng cách cắt tỉa các nhánh không phù hợp. Thông thường cây được sinh ra sẽ hoạt động tốt trên tập huấn luyện nhưng có thể hoạt động không chính xác đối với tập dữ liệu ẩn hoặc không nhìn thấy được. Các dữ liệu này là các dữ liệu bị nhiễu hoặc thiếu trong tập huấn luyện. Bước cắt tỉa nhằm mục tiêu cố gắng loại bỏ các nhánh bị lỗi khỏi cây và giữ lại độ chính xác của phân lớp. 2.3.4. Đánh giá cây quyết định Tại bước này, độ chính xác của cây kết quả được xác định thông qua sử dụng một tập dữ liệu không nhìn thấy độc lập. Cây được áp dụng cho từng dữ liệu vào và nhãn của lớp đã được dự đoán trước so sánh với nhãn lớp thực tế. Vì thế, tiêu chuẩn để đánh giá là số các mẫu được phân lớp chính xác. Có rất nhiều phương pháp xây dựng cây quyết định, để có cái nhìn tổng quan nhất chúng ta có thể xem xét các thuật toán này một cách kỹ càng hơn ở phần sau. 2.4. CƠ SỞ DỮ LIỆU QUAN HỆ 2.4.1. Quan hệ Định nghĩa 1.1. (Tệp dữ liệu). Một tệp dữ liệu là một tệp bao gồm nhiều bản ghi (record) có cùng một cấu trúc xác định loại bản ghi, đồng thời các bản ghi lại được phân chia thành các trường dữ liệu (field). Định nghĩa 1.2. (Khái niệm quan hệ) Cho R = {a1,...,an}là một tập hữu hạn và không rỗng các thuộc tính. Mỗi thuộc tính ai có một miền giá trị là Dai. Khi đó r là một tập các bộ {hi, ...,hm} được gọi là quan hệ trên R với hj (j=1,...,m) là một hàm: hi:RàDai aiÎR sao cho hj(ai)ÎDai Chúng ta cũng có thể biểu diễn quan hệ r thành một bảng. 2.4.2. Cơ sở dữ liệu quan hệ Một cơ sở dữ liệu thông thường bao gồm một tập các quan hệ được gọi là cơ sở dữ liệu quan hệ. Đối với người sử dụng, một cơ sở dữ liệu quan hệ là một cơ sở dữ liệu bao gồm các bảng thay đổi theo thời gian. Khi sử dụng một cơ sở dữ liệu quan hệ, các thao tác cơ bản và quan trọng nhất là: tạo quan hệ mới, cập nhật dữ liệu và cuối cùng là khai thác dữ liệu. Chức năng quan trọng nhất của cơ sở dữ liệu là khai thác dữ liệu từ dữ liệu được lưu trữ. Các vấn đề liên quan đến khai thác dữ liệu luôn đi đôi với việc lưu trữ dữ liệu một cách hiệu quả. 2.4.3. Đại số quan hệ Khi nói đến cơ sở dữ liệu quan hệ thì đại số quan hệ đóng vai trò hết sức quan trọng. Người đặt nền móng và đưa ra những đóng góp quan trọng trong việc phát triển đại số quan hệ có thể nói là E.F. Codd. Đại số quan hệ cung cấp các phép toán tác động trên các quan hệ và cho kết quả cũng là các quan hệ. Các phép toán đó là phép toán hợp, phép toán giao, phép hiệu, phép toán tích Descartes, phép chọn, phép chiếu, phép kết nối và phép chia. Ở đây, chúng ta giả sử các phép toán này đã quen thuộc. 2.4.4. Phụ thuộc hàm Định nghĩa a. Khái niệm phụ thuộc hàm Cho R = {a1,...,an}là tập các thuộc tính, r = {h1,...,hm}là một quan hệ trên R, A,BÍR. Khi đó chúng ta nói A xác định hàm cho B hay B phụ thuộc hàm vào A trong r. Ký hiệu: hay (A,B) hay A®B. nếu("hi,hjÎr)(((aÎA)(hi(a)=hj(a))(((bÎB)(hi(b)=hj(b))). Trong ví dụ được nêu ở trên thì ta có thể thấy rằng b. Họ đầy đủ các phụ thuộc hàm của một quan hệ Giả sử r là một quan hệ trên R. Họ đầy đủ các phụ thuộc hàm của r được ký hiệu Fr sao cho: Fr={(A,B):A,BÍR, }. c. Phụ thuộc hàm trên tập các thuộc tính Phụ thuộc hàm trên tập các thuộc tính R là một dãy ký tự dạng A®B đúng trong quan hệ r nếu . Chúng ta cũng nói rằng r thỏa mãn A®B. Tập tất cả các phụ thuộc hàm có thể dẫn xuất từ F được ký hiệu là F+ Hệ tiên đề Armstrong Giả sử R là tập các thuộc tính hữu hạn. Và giả sử P(R) là tập các tập con của R. Cho Y=P(R). Khi đó ta nói Y là một họ f trên R nếu với mọi tập thuộc tính A,B,C,DÍR: (A,A)ÎY. (A,B)ÎY,(B,C)ÎYÞ(A,C)ÎY. (A,B)ÎY, AÍC, DÍB Þ (C,D)ÎY. (A,B)ÎY, (C,D)ÎY Þ (AÈC,BÈD)ÎY Bao đóng của tập phụ thuộc hàm và tập thuộc tính Giả sử F là một tập các phụ thuộc hàm trên sơ đồ quan hệ s=. Một tập tất cả các phụ thuộc hàm có thể suy dẫn logic từ F bởi các luật của hệ tiên đề Amstrong. Ký hiệu là F+ khi đó F+ được gọi là bao đóng của F. Khóa tối tiểu của sơ đồ quan hệ và quan hệ a. Khóa Giả sử r là một quan hệ, s= là một sơ đồ quan hệ. Y là một họ f trên R, và AÍR. Khi đó A là một khoá của r (tương ứng là một khoá của s, một khoá của Y) nếu (A®RÎF+, (A, R)ÎY). b. Khoá tối tiểu Chúng ta gọi A là một khoá tối tiểu của r (tương ứng của s, của Y) nếu: A là một khoá của r (tương ứng của s, của Y). Bất kỳ một tập con thực sự của A không là khoá của r (tương ứng của s, của Y). Chúng ta ký hiệu Kr, (tương ứng Ks, KY) là tập tất cả các khoá tối tiểu của r, (tương ứng của s, của Y). Các dạng chuẩn Thông thường, việc cập nhật một cơ sở dữ liệu được thực hiện thông qua các thao tác thêm, sửa, xóa. Các thao tác này dễ gây nên những lỗi trong cơ sở dữ liệu mà nguyên nhân chính là do quá trình lặp đi lặp lại một số dữ liệu trong quan hệ. Để làm giảm thiểu các sai sót khi cập nhật dữ liệu người ta thường tách các quan hệ thành các quan hệ nhỏ hơn hay biến đổi chúng về các dạng chuẩn thích hợp. Quá trình đó gọi là quá trình chuẩn hóa. Trước tiên, chúng ta xét các khái niệm sau a. Phụ thuộc hàm đầy đủ, phụ thuộc hàm bộ phận Cho trước F là tập phụ thuộc hàm trên R và X ® Y là một phụ thuộc hàm trong F. Tập Y gọi là phụ thuộc hàm đẩy đủ vào tập X nếu không tồn tại một tập con thật sự Z nào của X mà Z®YÎF+ . Trong trường hợp ngược lại Y được gọi là phụ thuộc bộ phận vào X. b. Phụ thuộc hàm bắc cầu Cho F là tập phụ thuộc hàm trên R và X,YÍR. Tập Y được gọi là phụ thuộc bắc cầu vào X nếu tồn tại một tập con thực sự Z của X sao cho X®ZÎF+, Z®YÎF+, X®ZF+ và Y không là tập con thực sự của Z. Trong trường hợp ngược lại, Y được gọi là phụ thuộc hàm trực tiếp vào X. c. Dạng chuẩn Cho trước một sơ đồ quan hệ s = , với R là tập thuộc tính và F là tập phụ thuộc hàm khi đó s được gọi là: ở dạng chuẩn 1(1NF) nếu toàn bộ miền giá trị của các thuộc tính trong s là không thể phân chia được nữa. ở dạng chuẩn 2 (2NF) nếu s ở dạng chuẩn một và mọi thuộc tính không cơ bản của s đều phụ thuộc đầy đủ vào mọi khóa tối tiểu của s ở dạng chuẩn 3 (3NF) nếu s ở dạng chuẩn một và không có thuộc tính cơ bản của s nào phụ thuộc vào bất kỳ một khóa tối tiểu của s ở dạng chuẩn Boyce-Codd (BCNF) nếu s ở dạng chuẩn một và không có thuộc tính nào của s phụ thuộc bắc cầu vào bất kỳ một khóa tối tiểu của s. Đối với quan hệ r trên tập thuộc tính R, thì r được gọi là ở dạng chuẩn một (tương ứng là ở dạng chuẩn hai, dạng chuẩn ba và dạng chuẩn Boyce-Codd) 2.4.5. Phụ thuộc hàm xấp xỉ Khái niệm phụ thuộc hàm xấp xỉ (approximate functional dependency ) và phương pháp phát hiện các phụ thuộc hàm xấp xỉ đã được nhiều tác giả đề cập đến và được ứng dụng trong nhiều bài toán phân lớp của data mining. Theo các tác giả này thì một phụ thuộc hàm xấp xỉ là một phụ thuộc hàm hầu như đúng trên một quan hệ r (đa số các bộ của r thoả mãn điều kiện của phụ thuộc hàm). Để xác định các phụ thuộc hàm xấp xỉ người ta cần xác định được tỉ số giữa số lượng các bộ không thoả mãn luật với tổng số các bộ có trong quan hệ. Một trường hợp xấp xỉ khác là có những nhóm thuộc tính mặc dù giữa chúng không có sự phụ thuộc hàm theo kiểu bằng nhau tuyệt đối (theo cách định nghĩa phụ thuộc hàm thông thường) mà có sự phụ thuộc theo kiểu tương quan hàm số (tuyến tính hoặc phi tuyến). Trường hợp này xảy ra khá nhiều và liên quan đến nhiều bài toán thực tế. Ví dụ giữa mã hàng hoá và đơn giá, giữa doanh thu và chi phí Để phân biệt với khái niệm phụ thuộc hàm xấp xỉ của các tác giả đã đưa ra ( tạm gọi đó là phụ thuộc hàm xấp xỉ loại 1), phụ thuộc hàm xấp xỉ mà em nghiên cứu xây dựng được gọi là phụ thuộc hàm xấp xỉ loại 2. Khái niệm về phần tử ngoại lai (outliers) đã được một số tác giả như Knorr , Arning, Hawkins đề xuất và nghiên cứu theo các hướng tiếp cận theo thống kê và độ đo. Theo các hướng nghiên cứu này, các phần tử ngoại lai được xác định dựa trên sự khác biệt của một nhóm các phần tử này đối với đa số các phần tử khác trong một tập dữ liệu (khác biệt về khoảng cách, khác biệt về phân phối...). Hướng tiếp cận xác định phần tử ngoại lai theo luật (Rules Base) được đề xuất dựa trên việc các phần tử trong một quan hệ không tuân theo các ràng buộc, qui tắc cho trước. Các (qui tắc) ràng buộc được đề cập bao gồm những ràng buộc về cấu trúc của CSDL (phụ thuộc hàm, các dạng chuẩn,..) hoặc các ràng buộc về ngữ nghĩa mà các phần tử trong quan hệ phải tuân theo. Việc nghiên cứu về phần tử ngoại lai có nhiều ý nghĩa ứng dụng trong việc làm sạch dữ liệu; phát hiện sai sót trong quá trình xây dựng cây quyết định khi khai phá dữ liệu. Các khái niệm và tính chất của phụ thuộc hàm xấp xỉ, giá trị ngoại lai và khoảng cách giúp xác định phụ thuộc hàm xấp xỉ và tính chất của các Định nghĩa a. Định nghĩa 1. Cho e, 0 ≤ e ≤ 1, X à Y là phụ thuộc hàm xấp xỉ nếu: approx(XàY) ≤ e, với approx(XàY) = 1 – (max{|s|, s là tập con của r và XàY đúng trên s}/|r|). Ở đây, |s|, |r| là số phần tử của s và r. b. Định nghĩa 2 (phụ thuộc hàm xấp xỉ loại 2) Giả sử X, Y Í R và với một số d cho trước , 0 £ d dY nếu với mọi cặp bộ t1, t2 Î r, mà r(t1(X), t2(X))£ d thì ta cũng có r(t1(Y), t2(Y)) £ d. trong đó r(t1(X), t2(X)) là khoảng cách giữa hai bộ giá trị trên thuộc tính, r(t1(X), t2(X)) được tính: Với 2 bộ t1, t2 Î r, ta kí hiệu r(t1(X), t2(X)) là khoảng cách giữa t1 và t2 trên tập thuộc tính X Í R, được xác định như sau: r(t1(X), t2(X)) = max (½t1(Ai) - t2(Ai)½/ max(½t1(Ai½,½t2(Ai)½), Ai Î X ); hàm max(x,y) là hàm chọn ra số lớn nhất trong 2 số x,y; Trường hợp max(½t1(Ai)½,½t2(Ai)½) = 0, tức t1(Ai =t2(Ai)=0 thì ta qui ước: ½t1(Ai) - t2(Ai)½/ max(½t1(Ai)½,½t2(Ai)½) = 0 Tính chất Tồn tại thuật toán có độ phức tạp thời gian đa thức để xây dựng một cây quyết định từ một tập phụ thuộc hàm xấp xỉ cho trước. Xét tập X là tập con của r, và Error(X) là đánh giá lỗi tập nhỏ nhất cần phải loại bỏ khỏi tập r để X là khóa của r. Nếu Error(X) <e thì X được gọi là khóa xấp xỉ trên r. Một số tính chất của hàm khoảng cách r(t1(X), t2(X)): Định nghĩa khoảng cách r(t1(X), t2(X))nêu trên thoả mãn các tính chất của hàm khoảng cách: a1. r(t1(X), t2(X)) ³ 0 với t1 , t2 , X tùy ý; a2. r(t1(X), t2(X))= 0 Û t1(X)= t2(X). a3. r(t1(X), t2(X)) £ r(t1(X), t3 (X)) + r(t3(X), t2(X)) a4. Nếu XÍ Y thì r(t1(X), t2(X)) £ r(t1(Y), t2(Y)) a5. r(t1(XY), t2(XY)) = max (r(t1(X), t2(X)), r(t1(Y), t2(Y))) 2.5. ĐỘ ĐO TƯƠNG TỰ HỖN HỢP CHO DỮ LIỆU VỚI CÁC THUỘC TÍNH SỐ, KÝ HIỆU VÀ THỨ TỰ Như đã đề cập ở phần tổng quan về C4.5 ta nhận thấy, hầu hết các dữ liệu của các ứng dụng không chỉ liên quan đến thuộc tính có giá trị rời rạc, rõ ràng mà còn liên quan tới các giá trị thuộc tính liên tục, thay đổi theo thời gian Bài toán đặt ra ở đây là các dữ liệu với các thuộc tính số, ký hiệu và thứ tự này cũng cần phải có một giá trị, có một độ đo giống nhau để có thể so sánh, dựa vào đó để xây dựng và xác định giá trị RatioGain sao cho lớn nhất. Chính vì vậy trong phần này, em có tìm hiểu và đưa ra một số các phép xây dựng tính độ đo cho các dữ liệu này. 2.5.1. Khái niệm Gọi O là tập các đối tượng. Độ đo giống nhau giữa hai đối tượng x và y trong O được định nghĩa thỏa mãn với mọi x với mọi cặp x, y trong đó smin chỉ mức độ giống nhau ít nhất và smax chỉ mức độ giống nhau nhiều nhất. Cả hai giá trị này đều là các số thực và smin < smax. Tương tự, độ đo khoảng cách giữa hai đối tượng x và y trong O được định nghĩa thỏa mãn với mọi đối tượng x với mọi cặp x, y trong đó dmin chỉ khoảng cách bé nhất và dmax chỉ khoảng cách lớn nhất và dmin < dmax. Việc chuyển đổi từ độ đo giống nhau sang khoảng cách có thể được thực hiện bằng nhiều cách. Cách đơn giản nhất là đặt và . Ngược lại s cũng có thể đặt là (nếu khoảng giá trị không chứa giá trị 0) hoặc sử dụng hàm mũ . Độ đo biến nhị phân: Trong trường hợp thuộc tính rời rạc chỉ nhận hai giá trị, kí hiệu là 0 và 1, thì được gọi là thuộc tính nhị phân. Với thuộc tính nhị phân ta có thể chia ra làm hai loại: đối xứng và không đối xứng. Thuộc tính nhị phân đối xứng là biến mà hai giá trị 0 và 1 có vai trò như nhau. Ví dụ, thuộc tính giới tính là đối xứng vì nó chỉ nhận hai giá trị nam và nữ và ta có thể mã hoá nam là 0, nữ là 1 hoặc ngược lại. Thuộc tính nhị phân với ý nghĩa là đối tượng có/không có thuộc tính đó thì được gọi là không đối xứng. Trước hết ta xét trường hợp đối tượng chỉ bao gồm một loại thuộc tính. Trường hợp đối tượng bao gồm cả thuộc tính rời rạc và liên tục sẽ được xét riêng. Ngoài ra ta cũng giả sử các thuộc tính có ảnh hưởng như nhau tới độ giống nhau. Khi đó độ giống nhau s(x, y) giữa hai đối tượng x và y sẽ phụ thuộc vào số lượng các giá trị trùng nhau giữa chúng. Kí hiệu với . Dễ thấy , trong đó m là số các thuộc tính. Độ đo giống nhau cho thuộc tính nhị phân có công thức tổng quát trong đó a và b là các hệ số và có giá trị tuỳ thuộc vào từng độ đo giống nhau cụ thể. Bảng dưới đây sẽ nêu một số độ đo cho thuộc tính nhị phân đối xứng và không đối xứng. Độ đo biến rời rạc: Xét trường hợp đối tượng chỉ bao gồm các thuộc tính rời rạc. Trong trường hợp này ta cũng có thể sử dụng độ đo giống nhau của thuộc tính nhị phân bằng cách chuyển đổi các giá trị rời rạc thành số nhị phân. Tuy nhiên, ta cũng có thể sử dụng cách tiếp cận tương tự như đối với thuộc tính nhị phân. Kí hiệu a= là số cặp giá trị trùng nhau và là số cặp giá trị khác nhau, thì độ đo giống nhau có có dạng tổng quát trong đó là các trọng số nhận giá trị cụ thể tuỳ từng loại độ đo. Loại thuộc tính Tên độ đo Biểu thức Đối xứng Simple matching Jaccard Sokal & Sneath Rogers & Tanimoto Không đối xứng Simple matching Jaccard Dice Một số độ đo Độ đo cho biến liên tục: Xét trường hợp đối tượng chỉ bao gồm các thuộc tính liên tục. Trong trường hợp này thường sử dụng khoảng cách Euclidean là trường hợp riêng của khoảng cách 2.5.2. Độ đo hỗn hợp Một trong các độ đo hỗn hợp (độ đo MSM) được đưa ra bởi Goodall. Để tính độ đo giống nhau giữa các đối tượng, đầu tiên ta tính độ đo cho từng thuộc tính, sau đó kết hợp lại. Dưới đây ta sẽ lần lượt xét các độ đo cho từng loại thuộc tính liên tục và rời rạc. Ngoài ra, ta cũng xét độ đo cho loại thuộc tính thứ tự trên thuộc tính rời rạc. Thuộc tính rời rạc Loại thuộc tính đầu tiên mà ta xét là thuộc tính rời rạc. Các giá trị khác nhau thuộc tính không thể được so sánh. Ta coi cặp các giá trị khác nhau có độ giống nhau bằng 0; cặp các giá trị trùng nhau có độ giống nhau khác 0 và phụ thuộc vào xác suất xuất hiện của cặp giá trị đó. Cặp giá trị trùng nhau có xác suất xuất hiện nhỏ hơn sẽ có độ giống nhau lớn hơn. Kí hiệu Vi là các giá trị khác nhau của thuộc tính. Xác suất xuất hiện của các giá trị này là . Kí hiệu Sij là độ giống nhau của cặp giá trị Vi và Vj, ta có: ngoài ra, Gọi Pij là xác suất xuất hiện một cặp giá trị có độ giống nhau lớn hơn cặp (Vi, Vj). Dễ thấy trong đó Từ đó, suy ra với Q được xác định theo công thức ở trên. Trong thực tế, các giá trị xác suất pi là không biết trước nhưng ta có thể xấp xỉ các giá trị này bằng tần suất xuất hiện của chúng trong tập mẫu. Gọi m là số lượng các phần tử trong tập mẫu và fi là tần suất của giá trị Vi, độ đo giống nhau có thể được tính xấp xỉ bởi trong đó Thuộc tính có thứ tự Trong trường hợp này, ta cần phải tính tới tính có thứ tự trong độ đo giống nhau. Do có tính thứ tự nên thông thường một cặp giá trị sẽ có độ giống nhau nhỏ hơn so với các cặp giá trị nằm giữa chúng. Ví dụ, ta nói cặp (B, C) sẽ có độ giống nhau lớn hơn cặp (A, C) và (B, E). Tuy nhiên, ta không thể có sự so sánh như vậy với hai cặp (A, C) và (B, E). Trong trường hợp này, chúng ta lại sử dụng đến xác suất xuất hiện của các giá trị. Giả sử các giá trị của thuộc tính là . Theo cách hiểu thông thường và lập luận ở trên, ta có và Xác suất để xuất hiện một cặp có độ giống nhau hơn cặp là với và trong đó là số thoả mãn Trong trường hợp phải tính xấp xỉ, ta sử dụng công thức Thuộc tính liên tục Với thuộc tính liên tục, ta sẽ sử dụng khoảng cách – trị tuyệt đối của hiệu của hai giá trị – làm tiêu chuẩn chính trong việc đo độ giống nhau. Cặp của hai giá trị trùng nhau thì có độ giống nhau lớn hơn cặp của hai giá trị khác nhau; cặp có khoảng cách nhỏ hơn sẽ giống nhau hơn cặp có khoảng cách lớn hơn. Và khi các cặp có cùng khoảng cách ta sẽ sử dụng đến xác suất. Ta có: Tương tự, xác suất Pij là trong đó và Công thức để tính gần đúng độ giống nhau trong trường hợp này: Kết hợp độ đo của thuộc tính Trong các phần trên ta đã xét độ giống nhau cho từng thuộc tính riêng rẽ. Độ đo giống nhau cho cặp hai đối tượng sẽ được kết hợp từ các độ đo này. Để có thể kết hợp được, ta phải giả sử là các giá trị của các thuộc tính của một đối tượng là độc lập với nhau. Kí hiệu Og và Oh là hai đối tượng cần tính độ giống nhau và là xác suất xuất hiện cặp giá trị của thuộc tính k có độ giống nhau lớn hơn cặp . Ta định nghĩa quan hệ giữa hai đối tượng như sau: trong đó t là số lượng thuộc tính và là kí hiệu chỉ độ giống nhau giữa hai đối tượng. Nếu kí hiệu là xác suất xuất hiện một cặp đối tượng có độ giống nhau lớn hơn cặp (Og, Oh), thì tương tự như đối với thuộc tính riêng rẽ, ta có: trong đó là xác suất xuất hiện giá trị thứ i của thuộc tính thứ k và Q là tập tất cả các cặp đối tượng (Oi, Oj) thoả mãn Việc tính chính xác theo công thức trên yêu cầu số lượng tính toán rất lớn và trong thực tế người ta thường tính xấp xỉ nó bằng các phân bố của Fisher và Lancaster như sau trong đó và , với cho các thuộc tính liên tục (phân bố Fisher) và cho thuộc tính rời rạc (phân bố Lancaster). 2.5.3. Thuật toán nhanh cho thuộc tính liên tục Để tính độ đo giống nhau trong trường hợp thuộc tính rời rạc, ta cần phải duyệt qua các xác suất xuất hiện của giá trị của thuộc tính. Do đó, độ phức tạp tính toán trong trường hợp này là , với n là số lượng giá trị. Trong trường hợp thuộc tính liên tục (số), nếu tính trực tiếp theo công thức MSM như C. Li và G. Biswas đề nghị thì độ phức tạp tính toán trong trường hợp xấu nhất là . Ở đâ