Luận văn Nghiên cứu xây dựng mô hình đặc trưng người dùng (user profile) và ứng dụng

sẽ trải qua bước cuối cùng là đánh giá bằng cách thực hiện những phần kiểm tra khác nhau trên tập đặc trưng gốc và tập đặc trưng con đã chọn. Đánh giá. Cùng mục tiêu là chọn đặc trưng, nhưng điều kiện của bài toán chọn đặc trưng không hoàn toàn khớp với bài toán luận văn quan tâm ở những chi tiết sau: -Bài toán chọn đặc trưng giúp tìm những đặc trưng tối ưu có xét đến mối tương quan giữa các đặc trưng và hướng đến việc làm rõ nghĩa dữ liệu, giảm kích thước dữ liệu. -Bài toán luận văn quan tâm là chọn đặc trưng để xây dựng profile, nghĩa là tìm những đặc trưng hữu ích, cần thiết. Tính hữu ích được xét độc lập trên từng đặc trưng, chưa quan tâm đến mối quan hệ giữa các đặc trưng. Bài toán cũng không đặt 20 trọng tâm vào việc giảm kích thước dữ liệu vì số lượng đặc trưng trong một profile thường không quá lớn (khoảng vài chục). 2.2.2. Phương pháp phân tích thành phần chính (Principal Component Analysis-PCA) Theo [5], quan điểm của các nhà thống kê cổ điển cho rằng phân tích thành phần chính là tìm các trục chính của Ellipsoid2 nhiều chiều bao hàm đám mây số liệu phân phối chuẩn nhiều chiều, các trục đó được ước lượng từ một mẫu n cá thể, trên mỗi cá thể người ta đo p chỉ tiêu. Người đầu tiên đưa ra kỹ thuật này là H. Hotelling (1933), sau đó là T.W. Anderson (1958) và A.M. Kshirsagar (1972). Theo quan điểm phổ biến hơn của các nhà phân tích số liệu thì phân tích thành phần chính là một kỹ thuật biểu diễn các số liệu một cách tối ưu theo một tiêu chuẩn đại số và hình học đặc biệt. Những tư tưởng của phương pháp này do K.Pearson (1901) đề xuất. Trong công trình của C.R.Rao (1964), nội dung lý thuyết của phương pháp thành phần chính được trình bày khá đơn giản và rõ ràng. Lĩnh vực ứng dụng của PCA rất rộng trong công nghiệp, nông nghiệp, kinh tế, khoa học cơ bản,… với bảng số liệu mà các cột là các biến và các dòng là các cá thể khảo sát, trên đó đo giá trị các biến. Với các bảng số liệu cồng kềnh phức tạp thì rất khó thấy những thông tin chứa trong đó. Mục đích chính của PCA là rút ra những thông tin chủ yếu chứa trong bảng số liệu bằng cách xây dựng một biểu diễn 2 Ellipsoid là một dạng mặt bậc hai có hình tương tự như elip trong không gian ba chiều. Phương trình của một ellipsoid chính tắc trong hệ tọa độ Descartes x, y, z là 21 đơn giản hơn, sao cho trong biểu diễn đó đám mây số liệu thể hiện rõ nhất, mà thông tin không bị sai lạc. Nội dung phân tích là tìm các vector biến (hay vector cá thể) “gần gũi” với nhau, ảnh hưởng “tích cực” hoặc “tiêu cực” lên nhau, hoặc hầu như không có quan hệ gì với nhau. Chẳng hạn trong trồng trọt, để tìm quy luật biểu diễn của sản lượng lúa ở các vùng sinh thái khác nhau, người ta có thể lập bảng phân tích thành phần chính mà các biến là: sản lượng, năng suất trung bình/ha, tỉ lệ diện tích trồng trọt, số lượng phân bón từng loại, dân số, lao động, các yếu tố thời tiết, địa hình, số lượng trâu bò cầy kéo, số lượng máy nông nghiệp các loại, vốn đầu tư,… Trong chăn nuôi có thể tìm ảnh hưởng các loại thức ăn đến tốc độ tăng trưởng của lợn, ta lập bảng mà các vector cột là: tuổi lợn, trọng lượng, mức tăng trọng/ngày, lượng cám, bột ngô, xác mắm, lượng rau từng loại,… Nhận xét: Bài toán luận văn quan tâm so với bài toán PCA có những điểm khác biệt như bảng 2.1. Do vậy, không thể sử dụng phương pháp PCA cho bài toán luận văn. Bảng 2.1. So sánh bài toán luận văn và PCA Bài toán của luận văn PCA số đặc trưng ít (hàng chục) số biến quá lớn (hàng ngàn, hàng chục ngàn) đặc trưng gồm đa dạng biến: dịnh danh, định lượng, thứ bậc chỉ xét trên biến định lượng hoặc có thể lượng hóa được mục tiêu là đánh giá tính hữu ích của từng đặc trưng mà không xem xét đến mối tương quan giữa các đặc trưng đặt biến quan tâm là thành phần chính, bài toán nhằm mục tiêu đánh giá mối tương quan giữa các biến khác đến biến chính, hỗ trợ hay đối nghịch với biến chính. 22 Qua hiện trạng nghiên cứu về cấu trúc profile, chúng tôi nhận thấy đã có nhiều cấu trúc profile tống quát cho các miền ứng dụng như hệ thống tư vấn thông tin, e- Learning,... Tuy nhiên, đối với một hệ thống mới thì không thể áp dụng một cách máy móc mà cần có sự chọn lọc đặc trưng hữu ích, cần thiết cho hệ thống đó. Từ đó, dẫn đến nhu cầu cần có phương pháp chọn đặc trưng hữu ích. Các phương pháp chọn đặc trưng và các phương pháp liên quan đến chọn đặc trưng như PCA đã được nghiên cứu, ứng dụng và mang lại kết quả khả quan cho nhiều ứng dụng. Tuy nhiên, các phương pháp này lại không hoàn toàn phù hợp với bài toán chọn đặc trưng hữu ích cho profile trong các hệ thống thích nghi. Do vậy, đề tài sẽ hướng đến việc đề xuất một phương pháp mới để đánh giá tính hữu ích của các đặc trưng của profile dựa trên kiến thức thống kê. 23 Chương 3. Phát biểu bài toán 3.1. Các định nghĩa 3.1.1. Cấu trúc profile Theo [14], nhiều mô hình biểu diễn cấu trúc profile đã được đề xuất như mô hình không gian vector, mô hình lịch sử khai thác, mô hình ma trận đánh giá,… Trong luận văn, chúng tôi định nghĩa cấu trúc profile như sau: Cấu trúc của profile trong một hệ thống cụ thể là một tập hợp các đặc trưng hữu hạn và có thứ tự. Ký hiệu NnfP niiu ∈>=< = ,1)( là profile của user u gồm n đặc trưng fi Ví dụ với profile gồm 3 đặc trưng tên, tuổi, giới tính, ta có thể biểu diễn profile của các user u1, u2 như sau: )( 1uP = )( 2uP = Hay với profile gồm 4 đặc trưng nguồn gốc cư trú, nơi sống, người sống cùng, điều kiện sống. Khi đó, ta có thể biểu diễn profile của các user u1, u2, u3 dưới dạng vector như sau: )( 1uP = )( 2uP = )( 3uP = Trong các ứng dụng khác nhau, cấu trúc profile sẽ khác nhau về số lượng đặc trưng và tên của các đặc trưng. Xét ở khía cạnh ứng dụng, các đặc trưng này có thể chia 24 thành hai loại: loại đặc trưng bắt buộc là những đặc trưng không thể thiếu trong hệ thống ứng dụng và loại đặc trưng tùy chọn là những đặc trưng có thể có trong hệ thống ứng dụng. Ví dụ trong hệ thống e-Commerce thì sở thích là đặc trưng bắt buộc, trình độ là đặc trưng tùy chọn và trong hệ thống e-Learning thì ngược lại. Do vậy, tiêu chí phân loại đặc trưng phụ thuộc vào ngữ cảnh của hệ thống ứng dụng. 3.1.2. Miền giá trị của đặc trưng Miền giá trị của đặc trưng là tập hợp tất cả các giá trị mà đặc trưng có thể nhận trong miền ứng dụng đang xét. Ký hiệu DOM(fi) là miền giá trị của đặc trưng fi iiji njvfDOM ≤≤= 1,}{)( (3.1) Trong đó: vij là các giá trị mà fi có thể nhận được ni là tổng số giá trị của đặc trưng fi Ta ký hiệu Nnnn ∈....,,, 321 lần lượt là kích thước của miền giá trị của các thuộc tính ....,,, 321 fff Ví dụ DOM(tên)={“Lan”, “Thanh”, “Hồng”,….} DOM(tuổi)={1, 2, 3,…, 100,…} Miền giá trị của đặc trưng thường là tập các số nguyên, miền số thực, tập các ký tự,…. 3.1.3. Ý nghĩa của miền giá trị Mỗi đặc trưng trong profile dùng để biểu diễn user ở một khía cạnh nào đó. Sự khác biệt giữa các user được tạo ra bởi giá trị của đặc trưng mà từng user nhận được. Chẳng hạn, xét về khía cạnh tuổi tác, điều tạo nên sự khác biệt giữa người trẻ và 25 người già là do số tuổi của họ, hay nói cách khác là do giá trị của đặc trưng tuổi tác tạo nên, người trẻ thì tuổi từ 1 đến 30, người trung niên từ 30 đển 50 và người già từ 60 trở lên. 3.2. Bài toán luận văn giải quyết Cho profile NnfP nii ∈>=< = ,1 là một tập gồm n đặc trưng fi. Trên thực tế, P thường bao gồm 2 tập con, một tập gồm các đặc trưng bắt buộc và một tập gồm các đặc trưng tùy chọn. Các đặc trưng bắt buộc luôn phải tồn tại trong cấu trúc profile vì sự cần thiết cho hệ thống. Ví dụ, trong hệ thống e-Learning thì trình độ kiến thức có thể xem như là đặc trưng bắt buộc, trong hệ thống e-Commerce thì sở thích có thể xem như là đặc trưng bắt buộc. Mục tiêu của luận văn hướng đến việc đánh giá tính hữu ích của các đặc trưng tùy chọn. Cho nên từ đây về sau trong luận văn, cấu trúc profile P được ngầm hiểu rằng chỉ chứa các đặc trưng tùy chọn và việc đánh giá chất lượng của profile P chỉ là đánh giá trên các đặc trưng tùy chọn này, nếu không gây ra sự nhầm lẫn nào khác. Trong một hệ thống thích nghi cá nhân, chìa khóa thành công của hệ thống chính là profile vì những đặc trưng rất riêng của từng cá nhân là cơ sở để hệ thống cung cấp các tài nguyên, dịch vụ phù hợp với từng người. Do vậy, một đặc trưng được xem là hữu ích khi nó tạo ra sự khác biệt giữa các user. Tính hữu ích của đặc trưng hoàn toàn phụ thuộc vào ngữ cảnh ứng dụng của hệ thống. Ví dụ đặc trưng giới tính được xem là hữu ích khi xét trong những trường học mà có cả nam lẫn nữ và được xem là không hữu ích khi xét trong trường chỉ có nữ sinh. Ngoài ra, đặc trưng hữu ích còn phải dựa trên một miền giá trị ‘hợp lý’. Chẳng hạn, với đặc trưng ca học gồm các giá trị sáng, trưa, chiều, tối. Nếu xét đặc trưng này trong hệ đào tạo chính quy chỉ học sáng hoặc trưa hoặc chiều thì giá trị 26 tối tỏ ra không hữu ích. Tuy nhiên, nếu xét đặc trưng này trong các hệ đào tạo tại chức, văn bằng 2,... thì giá trị tối lại hữu ích vì các lớp loại này đa số tổ chức vào ca tối bởi đối tượng chủ yếu là những người có việc làm vào ban ngày. Từ đó, nhu cầu phải tinh chỉnh lại miền giá trị cho phù hợp với hệ thống cụ thể cần được xem xét. Do vậy, bài toán xây dựng cấu trúc profile được chia thành hai bài toán con với thứ tự như sau: (a) Đánh giá các đặc trưng của profile, nghĩa là tìm tập P*⊆ P hữu ích. (b) Tinh chỉnh DOM(fi) , ∀fi∈P*. 27 Chương 4. Đánh giá tính hữu ích của đặc trưng và tinh chỉnh miền giá trị đặc trưng Trong chương này, luận văn giới thiệu các tiêu chí đánh giá tính hữu ích của đặc trưng và tiêu chí đánh giá tính hữu ích của giá trị đặc trưng. Trên cơ sở đó, luận văn sẽ đề xuất giải thuật khả thi cho hai bài toán con đặt ra ở chương 3. Cách tiếp cận của luận văn dựa trên thống kê và thực nghiệm. 4.1. Cách tiếp cận Có nhiều cách để đánh giá tính hữu ích của đặc trưng như dựa trên kinh nghiệm, hỏi ý kiến chuyên gia,… Tuy nhiên, cơ sở hợp lý nhất chính là sự đánh giá khách quan của người dùng trong hệ thống. Cách tiếp cận của luận văn là để cho người dùng đánh giá profile tổng quát và dựa trên kết quả thu được để phân tích chọn lọc ra những đặc trưng hữu ích và đồng thời tinh chỉnh miền giá trị của đặc trưng. Để thu được ý kiến phản hồi của người dùng, có thể sử dụng một trong các phương pháp như: hỏi trực tiếp, khảo sát bằng phiếu thăm dò ý kiến, ghi nhận ngầm (cách này chỉ dùng cho các hệ thống đã đi vào vận hành) hoặc cũng có thể kết hợp nhiều cách. Ở đây chúng tôi không đặt trọng tâm vào việc nên dùng cách nào để thu thập thông tin, mà luận văn chỉ khai thác số liệu có được để tiến hành phân tích và đặt trọng tâm vào xây dựng tiêu chí đánh giá đặc trưng, giá trị đặc trưng. 4.1.1. Ý tưởng của giải pháp Dựa trên ý kiến phản hồi của người dùng (mẫu khảo sát) về các đặc trưng và miền giá trị đặc trưng để đánh giá sự hữu ích của chúng trong việc hỗ trợ thích nghi 28 cá nhân. Hệ thống thích nghi có phục vụ tốt cho người dùng hay không phụ thuộc vào việc hệ thống có phân biệt được sự khác nhau giữa các user hay không. Nếu một đặc trưng không giúp ta nhận ra được sự khác biệt giữa các user thì có thể nói đó là một đặc trưng không hữu ích. Ví dụ, trong các trường học có cả nam lẫn nữ sinh, thì đặc trưng giới tính là hữu ích vì nó giúp nhận ra các em nam và các em nữ. Khi đó, hệ thống ứng dụng sẽ tư vấn hai phương pháp học khác nhau tùy theo đặc điểm tâm sinh lý của giới tính. Ngược lại, với trường chỉ có nữ sinh thì đặc trưng giới tính lại tỏ ra không hữu ích. 4.1.2. Ví dụ minh họa Xét bảng thông tin về các đặc trưng giới tính, ca học và tình trạng hôn nhân được khảo sát trên 100 sinh viên (bảng 4.1). Bảng 4.1. Bảng kết quả khảo sát các đặc trưng. Thống kê trên 100 mẫu của hệ thống, các giá trị của đặc trưng ‘tình trạng hôn nhân’ như ‘độc thân’, ‘kết hôn’, ‘ly dị’, ‘ở góa’ lần lượt nhận giá trị 98, 2, 0, 0. Trong cột thứ 4 của bảng 4.1 hầu như tất cả các mẫu đều nhận cùng một giá trị ‘độc thân’. Từ đó cho thấy đặc trưng ‘tình trạng hôn nhân’ tỏ ra không hữu ích vì nó không tạo ra sự khác biệt giữa các user. Trong cột thứ 2 và 3 của bảng 4.1, đặc User Giới tính (nam, nữ) Ca học (Sáng, trưa, chiều, tối) Tình trạng hôn nhân (độc thân, kết hôn, ly dị, ở góa) u1 Nam Sáng Độc thân u2 Nữ Sáng Độc thân u3 Nữ Tối Độc thân u4 Nam Trưa Độc thân u5 Nam Tối Độc thân u6 Nam Sáng Kết hôn u7 Nữ Tối Độc thân u8 Nữ Sáng Độc thân u9 Nữ Tối Độc thân u10 Nữ Chiều Độc thân … 29 trưng giới tính và ca học tỏ ra hữu ích vì nó tạo ra sự khác biệt giữa các user từ đó giúp hệ thống phân biệt được các user và phục vụ tốt hơn, phù hợp hơn. Đặc trưng không hữu ích rất dễ nhận ra vì trong miền giá trị của nó có chứa một giá trị chiếm ưu thế một cách vượt trội dẫn đến tần suất của giá trị này là rất lớn so với các giá trị còn lại. Trong luận văn, giá trị này được gọi là extra value. Giá trị này dễ nhận diện khi biểu diễn dưới dạng biểu đồ như hình 4.1 0 02 98 0 20 40 60 80 100 độc thân kết hôn ly dị ở góa Hình 4.1. Biểu đồ phân bố miền giá trị của đặc trưng ‘tình trạng hôn nhân’ Đến đây, ý tưởng giải quyết bài toán con (a) nêu trong chương 3 đã rõ ràng là chúng tôi sẽ tìm các đặc trưng không hữu ích-đặc trưng có chứa extra value- và xem xét loại ra khỏi profile thay vì tìm cách chọn lọc các đặc trưng hữu ích. Sau khi đã có được profile gồm các đặc trưng tốt thì công việc kế tiếp là tinh chỉnh miền giá trị của các đặc trưng này. Miền giá trị của đặc trưng được phân thành hai tập con: một tập gồm các giá trị bắt buộc và tập kia gồm các giá trị tùy chọn, có thể có hoặc không. Với những giá trị bắt buộc thì sự cần thiết của chúng trong profile là điều hiển nhiên. Do vậy, tiếp cận của luận văn chỉ đánh giá tính hữu ích của các giá trị tùy chọn và tinh chỉnh chúng. Phần còn lại của luận văn khi đề cập đến việc tinh chỉnh miền giá trị của đặc trưng thì ngầm hiểu đó là các giá trị tùy chọn. Trong ví dụ ở bảng 4.1, DOM(ca học) ={sáng, trưa, chiều, tối}. Kết quả thống kê trên 100 mẫu về các giá trị sáng, trưa, chiều, tối lần lượt nhận giá trị 47, 3, 30 28, 22. Xét trong ngữ cảnh của ứng dụng là hệ đào tạo từ xa có 3 buổi học online vào các sáng thứ 3, 5, 7, nghĩa là các học viên bắt buộc phải tham gia các buổi học này. Khi đó, giá trị ‘sáng’ là giá trị bắt buộc và việc đánh giá tính hữu ích chỉ xét trên các giá trị trưa, chiều, tối. Giá trị không hữu ích rất dễ nhìn thấy khi biểu diễn miền giá trị dưới dạng biểu đồ (hình 4.2). Trong ví dụ này, đó chính là giá trị ‘trưa’ vì tần suất của giá trị ‘trưa’ rất thấp so với các giá trị còn lại. Trong phạm vi luận văn, giá trị này được gọi là rare value 47 3 28 22 0 20 40 60 80 100 sáng trưa chiều tối Hình 4.2. Biểu đồ phân bố miền giá trị của đặc trưng ‘ca học’ Đến đây, ý tưởng giải quyết bài toán con (b) nêu trong chương 3 đã rõ ràng là chúng tôi sẽ tìm ra giá trị không hữu ích (rare value) và tinh chỉnh lại miền giá trị. Có hai cách xử lý: loại bỏ hẳn giá trị không hữu ích hoặc ghép giá trị đó vào một giá trị khác trong miền. 4.2. Cơ sở lý luận Trong phần này, chúng tôi sẽ đề xuất tiêu chí để tìm ra extra value và rare value. Trên cơ sở đó, đề xuất giải thuật để đánh giá đặc trưng và tinh chỉnh miền giá trị đặc trưng. 31 4.2.1. Extra value Extra value là giá trị có tần suất rất lớn, chiếm ưu thế so với các giá trị khác. Do vậy, trước hết ta định nghĩa khái niệm tần suất. Cho đặc trưng fi , ta định nghĩa tần suất của một giá trị vij∈DOM(fi) là tỷ lệ giữa số user nhận giá trị ijv trên tổng số mẫu khảo sát. n v vfreq ijij =)( (4.1) Trong đó: ijv là số user nhận giá trị vij khi xét đặc trưng fi. n là tổng số mẫu khảo sát Ví dụ 4.1. Thăm dò ý kiến của 60 người về đặc trưng ca học, có kết quả sau: 10 người có đặc trưng là học sáng, 5 người có đặc trưng là học trưa, 45 người có đặc trưng là học tối. Thực hiện tính tần suất của các giá trị thu được kết quả sau : 17.0 60 10)( ==sangfreq , 083.0 60 5)( ==truafreq , 75.0 60 45)( ==toifreq Tiếp theo, chúng tôi đề xuất một độ đo để xác định extra value. Xét DOM(fi) và cho trước một tham số θ. Ta gọi một giá trị vij là extra value khi freq(vij)>θ . Thông thường, một giá trị có tần suất trên 50% thì được xem là chiếm ưu thế trong một tập hợp. Cho nên, ở đây chúng tôi đề xuất ngưỡng cho tham số θ là 0 . 5≤θ≤ 1 . Giá trị của θ càng lớn thì độ tin cậy của kết quả càng cao. Việc xác định giá trị θ phụ thuộc vào ứng dụng và phụ thuộc vào số lượng giá trị trong DOM(fi). Do vậy, khi tìm extra value trong các đặc trưng khác nhau nên dùng các giá trị θ khác nhau. Như vậy, chúng tôi ký hiệu θi là tham số dùng cho đặc trưng fi . Nếu bỏ 32 qua ngữ cảnh ứng dụng, ta dễ thấy θi là hàm số theo DOM(fi), nghĩa là θi=g(ni), với ni là kích thước của DOM(fi) Ví dụ 4.2. Xét đặc trưng f1 = ‘giới tính’, với DOM(f1) = {‘nam’, ‘nữ’} Trong đó nam chiếm 57% nữ 43%. => freq(nam) = 0.57 và freq(nu) = 0.43 Nếu chọn 5.0=θ , dẫn đến kết luận nam là extra value (vì 0.57 > 0.5). Nếu chọn 8.0=θ , dẫn đến kết luận không có extra value trong DOM(f1). Một cách trực quan, hình 4.3 cho thấy không có extra value vì nam và nữ có mật độ không quá cách biệt. Suy ra, trong trường hợp ni nhỏ, ta nên chọn giá trị iθ lớn. 0.57 0.43 0 0.1 0.2 0.3 0.4 0.5 0.6 nam nữ Hình 4.3. Biểu đồ phân bố miền giá trị của đặc trưng ‘giới tính’ Ví dụ 4.3. Xét đặc trưng f2 = ‘nguồn gốc cư trú’, với DOM(f2) = {‘thành thị’, ‘nông thôn’, ‘miền núi’, ‘vùng sâu’, ‘vùng xa’} Trong đó freq(thành thị) = 0.57, freq(nông thôn) = 0.13, freq(miền núi) = 0.09, freq(vùng sâu) = 0.07, freq(vùng xa) = 0.14 Nếu chọn θ=0.5, dẫn đến kết luận thành thị là extra value (vì 0.57 > 0.5). Nếu chọn θ=0.55, dẫn đến kết luận tương tự (vì 0.57>0.55). Một cách trực quan, hình 4.4 cho thấy thành thị là extra value vì tần suất của nó 33 vượt trội so với các giá trị khác. Suy ra, trong trường hợp ni lớn, giá trị θi nhỏ vẫn cho kết quả hợp lý. 0.57 0.13 0.09 0.07 0.14 0 0.1 0.2 0.3 0.4 0.5 0.6 thành thị nông thôn miền núi vùng sâu vùng xa Hình 4.4. Biểu đồ phân bố miền giá trị của đặc trưng ‘nguồn gốc cư trú’ Cách xác định hàm số g Một trong số các phương pháp để tìm hàm số g là dùng phương pháp nội suy toán học. Trước hết, định ra một số cặp giá trị (ni,θi) đầu tiên dựa vào kinh nghiệm của chuyên gia (chẳng hạn bảng 4.2) Bảng 4.2. Bảng các cặp giá trị (ni,θi) ban đầu in 2 3 4 5 6 7 8 9 10 iθ 0.9 0.85 0.8 0.75 0.7 0.7 0.65 0.6 0.5 Sử dụng một công cụ nội suy toán học có sẵn để nội suy hàm g, chẳng hạn công cụ Curve Fitting có sẵn trong Maple ta được kết quả iii nng 045.0987.0)( −==θ (4.2) Từ kết quả trên, ta hoàn toàn có thể suy ra nhiều cặp giá trị (ni,θi) một cách tự động (như bảng 4.3) Bảng 4.3. Bảng các cặp giá trị (ni,θi) in 2 3 4 5 6 7 8 9 10 11 12 13 … iθ 0.897 0.852 0.807 0.762 0.717 0.672 0.627 0.582 0.537 0.492 0.447 0.402 … 34 Nhận xét rằng giá trị extra value nếu có là giá trị tối đại và duy nhất (xem phần 4.2.1.2 ). Do vậy, để tìm extra value ta chỉ cần xét giá trị tối đại trong miền có tần suất lớn hơn ngưỡng cho trước không, không cần tính tần suất của tất cả các giá trị. Điều này giúp thời gian xử lý nhanh hơn, hiệu quả hơn. 4.2.2. Mệnh đề Cho ngưỡng 0.5≤θ≤1. Giá trị extra value trong miền giá trị của một đặc trưng bất kỳ nếu có là giá trị tối đại và duy nhất. Chứng minh Tính duy nhất Xét đặc trưng fi bất kỳ. Ta sẽ chứng minh trong iiji njvfDOM ≤≤= 1},{)( không thể tồn tại hai giá trị extra value. Trước hết, ta có biểu thức sau. 1)( 1 =∑ = in j ijvfreq (4.3) Sử dụng công thức về tần suất được đề xuất trong 4.2.1.1. Giả sử tồn tại hai giá trị extra value ikv và ilv . Khi đó, ⎩⎨ ⎧ =≥>+⇒> > 15.0*22)()( )( )( θθ θ ilik il ik vfreqvfreq vfreq vfreq (4.4) Điều này mâu thuẫn với (4.3). Do vậy, giả sử sai. Điều đó chứng minh giá trị extra value (nếu có) là duy nhất. Tính tối đại Đặt giá trị tối đại là { } in jij vv 1max max == Giả sử tồn tại giá trị extra value ikv thỏa maxvvik < . 35 Khi đó )()( maxvfreqvfreq ik <<θ Dẫn đến maxv cũng là extra value. Điều này mâu thuẫn với tính duy nhất. Kết luận: giả sử sai. Điều này chứng minh giá trị bất thường lớn là giá trị tối đại. 4.2.3. Đặc trưng hữu ích Đến đây, chúng tôi đã xây dựng được tiêu chí tìm ra extra value trong miền giá trị của đặc trưng. Dựa trên cơ sở đó để kết luận về tính hữu ích của đặc trưng. Cho trước một profile NnfP nii ∈>=< = ,1 và một ngưỡng θi. Một đặc trưng fi được xem là hữu ích khi không tồn tại một extra value vij∈DOM(fi) nào (tức là không thỏa freq(vij)>θi ) 4.2.4. Đặc trưng không hữu ích Cho trước một profile NnfP nii ∈>=< = ,1 và một ngưỡng θi. Một đặc trưng fi được xem là không hữu ích khi tồn tại một extra value vij∈DOM(fi), nghĩa là freq(vij)>θi 4.3. Đánh giá tính hữu ích của đặc trưng 4.3.1. Ý tưởng giải thuật Cho trước một profile NnfP nii ∈>=< = ,1 và một dãy các ngưỡng θi. Việc chọn lọc và sử dụng các đặc trưng hữu ích trong profile cũng đồng nghĩa với việc tìm ra các đặc trưng không hữu ích và loại khỏi profile. Như vậy, để giải quyết bài toán này, chúng ta sẽ xét lần lượt từng đặc trưng fi ∈ P và đánh giá tính hữu ích của fi , nghĩa là tìm xem có giá trị extra value trong DOM(fi) hay không. Nếu tồn tại 36 extra value trong DOM(fi) thì kết luận fi không hữu ích. Như vậy, sau khi đánh giá từng đặc trưng ta đạt được kết quả là tách profile P thành hai nhóm *** PPP ∪= (4.5) Trong đó : *P là tập các đặc trưng hữu ích **P là tập các đặc trưng không hữu ích Luận văn chỉ dừng lại ở việc phát hiện ra các đặc trưng không hữu ích. Thông thường thì nên loại bỏ các đặc trưng này ra khỏi profile. Hoặc có thể tìm thêm mẫu khảo sát để đảm bảo tính chính xác của kết quả. 4.3.2. Thủ tục đánh giá tính hữu ích của đặc trưng fi với ngưỡng θi Input: ⎪⎩ ⎪⎨ ⎧ ≤≤ ≤≤ 15.0 )( 1, i i i fDOM nif θ Output: fi hữu ích hay không hữu ích. Bước 1: Tìm giá trị lớn nhất trong DOM(fi) là { } injijvv 1max max == Bước 2: Tính freq(vmax) Bước 3: If freq(vmax) > θi then fi là đặc trưng không hữu ích, else fi là đặc trưng hữu ích end if. Để đánh giá tính hữu ích của tất cả các đặc trưng trong profile NnfP nii ∈>=< = ,1 , ta lặp lại giải thuật trên cho từng đặc trưng fi như sau for i from 1 to n do đánh giá đặc trưng if end 37 4.3.3. Lưu đồ thủ tục đánh giá đặc trưng 15.0 ,1},{)( ,1 ≤≤ ∈≤≤= ∈>=< = i iiiji n ii NnnjvfDOM NnfP θ i ≤n { } injijvv 1max max == )( maxvfreqtinh ivfreq θ>)( max Yes }{**** ifPP ∪= OPP == *** No Yes No *** ,Re PPturn Begin End }{** ifPP ∪= 38 4.4. Tinh chỉnh miền giá trị của đặc trưng Đối với các đặc trưng đã được đánh giá là hữu ích theo giải thuật trên thì việc tiếp theo là cần phải tinh chỉnh lại miền giá trị của đặc trưng. Việc tinh chỉnh này nhằm đảm bảo các giá trị trong miền đều phải hữu ích, nghĩa là không có giá trị rare value như đã đề cập trong 4.2.1. Số lượng rare value trong miền giá trị thường rất ít. Trường hợp thường gặp là trong miền giá trị có tồn tại một rare value. Khi đó, có thể loại bỏ giá trị đó ra khỏi miền hoặc gộp nó vào một giá trị khác. Bây giờ, chúng tôi đề xuất tiêu chí để xác định rare value, trên cơ sở đó đưa ra giải pháp để tinh chỉnh miền giá trị. 4.4.1. Rare value Xét đặc trưng fi và cho trước ngưỡng β>0. Ký hiệu δ(vij) là độ lệch giữa giá trị vij và vik∈DOM(fi), i ≠ k . Nếu ∃!vij: δ(vij)>β thì vij được gọi là rare value. Ví dụ trong hình 4.2 giá trị ‘trưa’ là rare value. Nhận xét rằng rare value nếu có tồn tại sẽ là giá trị nhỏ nhất trong miền giá trị. Do vậy, trong các đề xuất sau đây về cách tính δ(vij), chúng tôi chú trọng vào giá trị nhỏ nhất để khảo sát. 4.4.2. Cách tiếp cận dựa trên độ lệch nhỏ nhất Nếu khoảng cách từ rare value đến tất cả các giá trị khác đều lớn hơn β thì khoảng cách nhỏ nhất trong số đó cũng lớn hơn β . Khoảng cách nhỏ nhất đó được xác định bằng khoảng cách từ rare value đến giá trị lớn kế tiếp nó trong miền giá trị. Do vậy, chúng tôi đề xuất cách tính )( ijvδ như sau Bước 1: Sắp xếp các giá trị theo thứ tự tăng dần. Không mất tính tổng quát, ta đặt lại chỉ số mới như sau kvvv ≤≤≤ ...21 39 Bước 2: Tính độ lệch của v1 1 12 1 )( vv vvv k − −=δ (4.6) Hình 4.5. Cách tiếp cận dựa trên độ lệch nhỏ nhất Bước 3 : So sánh và kết luận If βδ >)( 1v then kết luận v1 là rare value, else không có rare value trong DOM(fi) end if Ưu điểm và hạn chế của cách tiếp cận này. -Ưu điểm của phương pháp này là đơn giản, dễ tính toán. Việc định giá trị cụ thể cho tham số β rất linh động, tùy vào từng