CF

Chia sẻ: Tan Gia | Ngày: | Loại File: DOC | Số trang:24

Thêm vào BST

Báo xấu

601
lượt xem 10
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Trong cuộc sống hàng ngày, mọi người thường tin vào những lời giới thiệu từ những người khác nhau thông qua lời nói, thư từ văn bản, các bản ghi mới có được ở các phương tiện thông tin đại chúng, ở các cuộc điều tra nói chung, các hướng dẫn và v.v.. Đó là lý do tại sao các hệ tư vấn ra đời, với mục đích hỗ trợ và làm tăng thêm tiến trình xã hội tự nhiên này, hệ tư vấn giúp mỗi người có thể chọn lọc một cách kỹ lưỡng thông qua những quyển sách, bài báo, trang web,...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: CF

CF Là một trong những phương pháp xây dựng hệ thống tư vấn thành công nhất, CF thông qua các thị hiếu đã được biết đến của một nhóm người dùng để đưa các t ư v ấn ho ặc d ự đoán v ề th ị hi ếu chưa biết cho một số người dùng khác. 1. Giới thiệu Trong cuộc sống hàng ngày, mọi người thường tin vào những lời gi ới thi ệu t ừ những ng ười khác nhau thông qua lời nói, thư từ văn bản, các bản ghi m ới có đ ược ở các ph ương ti ện thông tin đại chúng, ở các cuộc điều tra nói chung, các hướng dẫn và v.v.. Đó là lý do t ại sao các h ệ t ư v ấn ra đời, với mục đích hỗ trợ và làm tăng thêm tiến trình xã h ội t ự nhiên này, h ệ t ư v ấn giúp m ỗi ng ười có thể chọn lọc một cách kỹ lưỡng thông qua những quyển sách, bài báo, trang web, phim, nhà hàng, truyện cười, các sản phẩm…để tìm ra thông tin hữu ích và đáng chú ý nhất cho h ọ. Nhà phát tri ển của một số những hệ tư vấn đầu trong tiên là Trapestry [1]( [1]D.Goldberg,D.Nichols,B.M.Oki,andD.Terry,“Using collaborative filtering to weave an information tapestry,”CommunicationsofACM,vol.35,no.12,pp.61–70,1992.) (các hệ tư vấn khác gồm tư vấn dựa trên luật,, và tùy biến theo khách hàng) đưa ra thuật ngữ “Collaborative Filtering ( CF_ Lọc cộng tác)”. Giả thuyết cơ bản của CF là nếu có X và Y người dùng đánh giá cho n item t ương t ự nhau, hoặc có hành vi tương tự nhau (ví dụ, mua, xem, nghe,…) thì h ọ sẽ có đánh giá ho ặc hành đ ộng tương tự trong các item khác cũng nhau [3_ [3]K.Goldberg,T.Roeder,D.Gupta,andC.Perkins,“Eigentaste: a constant time collaborative filtering algorithm”, InformationRetrieval,vol.4,no.2,pp.133–151,2001.] Kỹ thuật CF sử dụng cơ sở dữ liệu về sở thích của người dùng đ ối v ới các item đ ể d ự đoán các chủ để hoặc sản phẩm thêm vào cho một người dùng mới có cùng sở thích. Trong ng ữ c ảnh c ụ thể của CF, có một danh sách của m người dùng {u1, u2, …,um} và một danh sách của n item {i1, i2, …,in}, và mỗi người dùng ui có một danh sách item Iui đã được đánh giá hoặc suy luận được thông qua các hành vi của họ. Các đánh giá này có thể là các thể hiện tường minh ví d ụ n ằm trong kho ảng 1 – 5 (ghét – rất thích), hoặc không tường minh, như vi ệc mua bán ho ặc click – through ( kích ho ạt vào một trang web nào đó - thể hiện c ủa m ột vài người click trong nh ững b ản qu ảng cáo trên internet). Cho ví dụ, chúng ta có thể chuyển đổi danh sách người dùng và các b ộ phim h ọ thích ho ặc không thích (Bảng 1(a)) với ma trận trọng số user – item (Bảng 1 (b)), trong đó Tony là m ột ng ười
dùng chính mà chúng ta muốn tư vấn. Ở đây một vài giá trị trong ma tr ận b ị thi ếu do nh ững ng ười dùng này không đưa ra đánh giá của mình cho những item đó. Có rất nhiều thách thức đối với các nhiệm vụ của công lọc cộng tác (Phần 2). Bởi vì thuật toán CF yêu cầu phải có khả năng giải quyết vấn đề thưa thớt dữ li ệu cao, t ỷ l ệ v ới s ố ng ười dùng và item tăng lên, đưa ra những tư vấn thích h ợp trong th ời gian ngắn, và gi ải quy ết đ ược các v ấn đ ề khác như tính đồng nghĩa (xu hướng giống nhau hoặc item tương tự nhua nhưng khác nhau về tên), các tấn công khác, dữ liệu bị nhiễu và các vấn đề về bảo mật. Các hệ lọc cộng tác ra đời sớm như GroupLens [5] P.Resnick, N.Iacovou, M.Suchak, .Bergstrom, and J.Riedl, “Grouplens: an open architecture for collaborative filtering of netnews,” in Proceedings of the ACM Conferenceon Computer Supported Cooperative Work, pp. 175–186, New York, NY, USA,1994.], sử dụng dữ liệu đánh giá của người dùng đ ể tính toán đ ộ t ương t ự ho ặc trọng số giữa các người dùng hoặc item và đưa ra dự đoán, tư vấn theo những giá trị tương tự đó. Ở đó sử dụng phương thức CF dựa trên bộ nhớ (Phần 3) và sau này đ ược tri ển khai thành các h ệ thống thương mại đánh chú ý như http://www.amazon.com (như hình 1) và Barnes và Noble vì chúng dễ cài đặt và đưa ra hiệu quả cao. Tính suy biến (Customization) trong h ệ CF cho m ỗi ng ười dùng giảm dần theo những nỗ lực tìm kiếm của người dùng. Nó cũng đảm b ảo đ ược s ố l ượng khách hàng trung thành tăng lên, tỷ lệ cao hơn, tổng thu nhập quảng cao nhi ều h ơn và nhi ều h ứa h ẹn ở phía trước đang mở ra.
Tuy nhiên có một vài giới hạn trong kỹ thuật CF dựa trên bộ nh ớ, như trên th ực t ế giá tr ị tương tự dựa trên các item nói chung vì vậy khi dữ liệu ít thì nó không còn đáng tin cậy nữa. Để đạt được hiệu suất dự đoán tốt hơn và khắc phục những thi ếu sót c ủa các thu ật toán CF dựa trên bộ nhớ, phương pháp CF dựa trên mô hình ra đời. K ỹ thuật này (Phần 4) s ử d ụng d ữ li ệu đánh giá thuần túy để ước lượng hoặc học mô hình nhằm đ ưa ra d ự đoán [[9] J. Breese, D. Heckerman, and C. Kadie, “Empirical analysis of predictive algorithms for collaborative filtering,” in Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence(UAI’98),1998.]). Mô hình có thể được xem là data mining hoặc thuật toán học máy và kỹ thuật được biết đến nhiều nhất gồm có mô hình mạng Bayes, mô hình Clustering và mô hình Latent semantic [7 _ [7] T. Hofmann, “Latent semantic models for collaborative filtering,” ACM Transactions on Information Systems, vol. 22, no.1,pp.89–115,2004.) Bên cạnh lọc cộng tác, lọc dựa trên nội dung cũng là một mảng quan trọng khác của hệ tư vấn. Hệ tư vấn dựa trên nội dung đưa ra các tự vấn thông qua vi ệc phân tích ngữ nghĩa c ủa thông tin và tìm ra quy luật trong nội dung đó. Điểm khác nhau c ơ bản gi ữa CF và các h ệ t ư v ấn d ựa trên n ội dung là CF chỉ sử dụng dữ liệu đánh giá giữa user – item để đưa ra dự đoán, trong khi hệ tư vấn dựa trên nội dung lại dựa trên các đặc trưng c ủa người dùng và item để d ự đoán [15_ L. Si and R. Jin, “Flexible mixture model for collaborative filtering,” in Proceedings of the 20th International Conferenceon Machine Learning (ICML ’03), vol. 2, pp. 704–711, Washington,DC,USA,August2003.]. Tất nhiên, cả CF và hệ tư vấn dựa trên nội dung đều có gi ới hạn. Trong khi các hệ CF không kết hợp chặt chẽ các thông tin đặc tr ưng m ột cách t ường minh thì
hệ tư vấn dựa trên nội dung lại không kết hợp các thông tin c ần thi ết về sở thích t ương t ự nhau giữa mỗi các nhân [8_ L. Si and R. Jin, “Flexible mixture model for collaborative filtering,” in Proceedings of the 20th International Conference on Machine Learning (ICML ’03), vol. 2, pp. 704– 711, Washington,DC,USA,August2003.]. Kỹ thuật Hybrid CF kết hợp giữa kỹ thuật CF và kỹ thuật dựa trên nội dung hy v ọng tránh được những hạn chế của cả hai phương pháp trên vì vậy sẽ c ải thi ện được hi ệu su ất c ủa vấn đ ề tư vấn (Phần 5) Bảng tóm tắt của kỹ thuật CF được mô tả khá chi tiết trong bảng 2: Để đánh giá thuật toán CF (Phần 6), chúng ta cần dử dụng độ đó theo ki ểu ứng d ụng c ủa CF. Thay vì Classification Error lỗi phân loại, ngày nay để đánh giá hi ệu su ất d ự đoán c ủa CF th ường sử dụng Mean Absolute Error MAE và dữ liệu để làm thí nghi ệm thường dùng là c ơ s ở d ữ li ệu c ủa MovieLens [18], Jester [19] và Netflix prize [20]. Trong phần 7 chúng tôi s ẽ đ ưa ra tóm t ắt và nh ững mô tả trong công việc này. 2. Các đặc trưng và thách thức của lọc cộng tác: Các thuật toán tư vấn trong thương mại điện tử thường hoạt đ ộng trong m ột môi tr ường mang tính thách thức, đặc biệt là trong các công ty mua s ắm tr ực tuy ến l ớn nh ư eBay và Amazon. Thường thì một hệ thống tư vấn với các giải pháp nhanh chóng và chính xác sẽ thu hút s ự thích thú của khách hàng và mang lại lợi nhuận cho các công ty. Đ ối v ới các h ệ th ống CF, vi ệc đ ưa ra nh ững
sự dự báo hay các gợi ý chất lượng cao phụ thuộc vào khả năng xác đ ịnh xác đ ịnh t ối đa các thách thức của chúng, đây cũng chính là các đặc trưng của các nhiệm cụ của CF. Thưa thớt dữ liệu: 2.1. Trong thực tế, rất nhiều hệ thống tư vấn thương mại được sử dụng đ ể đánh giá hàng lo ạt các sản phẩm rất lớn. Vì vậy, ma trận user – item được sử dụng trong l ọc c ộng tác s ẽ c ực kỳ th ưa thớt và hiệu suất thành công cho các dự đoán hay gợi ý của các h ệ th ống CF đ ưa ra tr ở thành m ột thách thức lớn. Các thách thức về thưa thớt dữ liệu thường xuất hiện trong nhiều tình huống, đ ặc bi ệt v ấn đề khởi động lạnh “cold start” diễn ra khi một người dùng m ới hay item m ới v ừa m ới đ ược thêm vào hệ thống và việc tìm những sự tương đồng thật khó khăn vì không đủ thông tin (trong vài trường hợp, vấn đề cold star còn được gọi là vấn đề người dùng m ới và vấn đ ề item m ới). Các item mới không thể được đưa vào hệ thống nếu không có người dùng nào đánh giá chúng, và ng ười dùng mới không thể có một sự gợi ý tốt n ếu thi ếu trọng số ho ặc b ản li ệt kê v ề nh ững đánh giá hay mua sắm trước đây của họ. Coverage (Độ bao phủ) được định nghĩa như là phần trăm c ủa các item thuật toán cung cấp để đưa ra tư vấn. Vấn đề giảm độ bao ph ủ (Reduced coverage) x ảy ra khi s ố lượng các đánh giá của người dùng có hteer nhỏ hơn so với số l ượng l ớn các item trong h ệ th ống và hệ tư vấn không có khả năng sinh ra tư vấn cho họ. Neighbor transitivity (Tính t ịnh ti ến hàng xóm) đề cập tớ vấn đề về cơ sở dữ liệu thưa thớt, ở đó những người dùng v ới th ị hi ếu t ương t ự nhau không được xác định nếu họ không cùng đánh giá về các item gi ống nhau. V ấn đ ề này đã làm gi ảm hiệu năng của hệ tư vấn dựa vào sự so sánh từng cặp gi ữa các người dùng t ừ đó sinh ra các d ự đoán. Để giảm bớt vấn đề thưa thớt dữ liệu có rất nhiều phương pháp đ ược đ ưa ra. K ỹ thu ật giảm chiều SVD (Singular Value Decomposition) là một trong số đó[23 _ D. Billsus and M. Pazzani, “Learning collaborative information filters,” in Proceedings of the 15th International Conference on Machine Learning(ICML’98),1998.]. Nhiệm vụ chính của kỹ thuật này là gi ảm những người dùng hoặc item không tiêu biểu và không quan trọng để giảm chi ều của ma tr ận user – item m ột cách trực tiếp. LSI (Latent Semantic Indexing) được sử dụng trong vấn đ ề truy v ấn thông tin đã r ất thành công khi tính toán dựa trên SVD để tìm ra độ tương tự gi ữa các người dùng thông qua vi ệc bi ểu diễn họ trong không gian đã giảm chiều. Bên cạnh đó, Goldberg et al. [3] đã phát tri ển eigentaste áp dụng Principle Component Analysis (PCA), một kỹ thuật phân tích h ệ số có liên h ệ gần gũi nhau được mô tả đầu tiên bởi Pearson vào năm 1901 [26] nhằm làm gi ảm số chi ều không gian. Tuy nhiên, một khi người dùng hoặc item nào đó bị loại bỏ, thì những thông tin h ữu ích cho vi ệc t ư v ấn liên quan đến họ cũng có thể bị mất và chất lượng tư vấn có thể bị giảm xuống [6, 27].
Thuật toán CF lai hay còn gọi là thuật toán content – boosted CF r ất h ữu ích trong vi ệc gi ải quyết vấn đề thưa thớt bởi ở đó thông tin nội dung m ở r ộng đ ược dùng đ ể tìm ra nh ững d ự đoán cho người dùng hoặc item mới. Trong Ziegler et al [28], m ột ph ương pháp l ọc c ộng tác lai đã đ ược đưa ra nhằm khai thác thông tin phân loại chính cho các sản phẩm c ần phân lo ại chính xác và nó thường được dùng trong các vấn đề thưa thớt dữ li ệu của các h ệ t ư v ấn CF, d ựa trên các h ồ s ơ cá nhân được tạo ra nhờ sự suy luận của điểm được ghi trong các ch ủ đ ề con và trong s ự đa d ạng c ủa các chủ đề [28]. Schein et al. cũng đã đưa ra ph ương th ức bi ến ti ềm ẩn c ủa mô hình khía c ạnh (aspect model latent variable) cho tư vấn khởi động lạnh (cold start), đây chính là s ự kết h ợp gi ữa thông tin cộng tác và nội dung trong mô hình lọc. Kim và Li đ ưa ra mô hình xác su ất đ ể gi ải quy ết vấn đề khởi động lạnh, các items được sắp xếp thành các nhóm và những d ữ đoán ng ười dùng t ạo ra được xem là sự phân loại Gaussian với trọng số đánh giá tương ứng [30] Thuật toán CF dựa trên mô hình như TAN – ELR (tree augment naïve Bayes đ ược t ối ưu hóa thông qua sự hồi quy logic mở rộng), tập trung vào vấn đ ề th ưa th ớt thông qua vi ệc cung c ấp nhi ều hơn những dự đoán chính xác cho dữ li ệu thưa thớt. M ột vài k ỹ thu ật CF d ựa trên mô hình m ới được đưa ra bao gồm kỹ thuật truy vấn liên kết (association retrieval technique), áp d ụng v ới thu ật toán hoạt hóa mở rộng nhằm khai thác sự liên kết bổ sung gi ữa những người dùng nh ờ tr ọng s ố đánh giá và các bản tiểu sử của họ [32]; MMMF (Maximum margin matrix factorizations_ các th ừa số ma trận dư cực đại) hay còn gọi là ma trận lồi [33, 34]; multiple imputation – based CF approaches [36]; và thuật toán imputation – boosted CF [37]. Scalability (khả năng mở rộng) 2.2. Khi số lượng người dùng và items ngày càng tăng, thu ật toán CF truy ền th ống s ẽ g ặp ph ải vấn đề nghiêm trọng về khả năng mở rộng, với một lượng tính toán vượt quá m ức th ực hành và cho phép. Chẳng hạn, với 10 triệu khách hàng (M) và hàng tri ệu item khác nhau (N), thu ật toán CF với độ phức tạp tính toán là O (n) sẽ là quá lớn. Tương t ự nh ư vậy, v ới nheiefu h ệ th ống yêu c ầu ngay lập tức đưa ra kết quả (ví dỵ yêu cầu trực tuyến) và tư vấn cho t ất c ả khách hàng mà không hề quan tâm để việc trao đổi cũng như trọng số đánh giá trước đây c ủa h ọ, đi ều đó đòi h ỏi kh ả năng mở rộng lớn của một hệ thống CF [6]. Kỹ thuật giảm chiều như SV có thể giải quyết vấn đề này và cung cấp những tư v ấn có chất lượng tốt, nhưng chúng phải trải qua những bước tính toán th ừa s ố ma tr ận r ất ph ức t ạp. M ột thuật toán CF cải tiến SVD [38] tính toán lại chiều SVD sử dụng nh ững người dùng đã có s ẵn. Khi có một tập trọng số đánh giá mới được thêm vào cơ sở dữ liệu, thuật toán sử dụng k ỹ thu ật l ấp đầy (folding - in) [25, 39] để xây dựng hệ thống c ải ti ến mà không c ần tính toán l ại mô hình có chiều thấp hơn từ vạch xuất phát. Vì vậy, nó tạo ra hệ thống tư vấn cớ khả năng mở rộng cao.
Thuật toán CF dựa trên mô hình, như thuật toán độ tương quan Pearson dựa trên item có th ể đạt được khả năng mở rộng thích hợp. Thay vì việc tính toán độ tương tự giữa tất c ả các cặp items, CF Pearson dựa trên item tính toán độ tương tự chỉ gi ữa nhưng c ặp item có liên quan đ ến nhau c ủa cùng một người dùng [6,40]. Một thuật toán CF Bayesian đơn giản cũng gi ải quyết vấn đề m ở r ộng thông qua việc đưa ra nhưng dự đoán dựa trên trọng số có sẵn [41]. Thu ật toán CF d ựa trên mô hình ví dụ như clustering CF, tập trung vào vấn đề mở rộng tại vị trị mà các c ụm có đ ộ t ương t ự cao và có ít tư vấn cho người dùng hơn thay vì trên toàn b ộ c ơ sở d ữ li ệu [13, 42 – 44], nh ưng cũng c ần phải cân bằng giữa hiệu suất mở rộng và dự đoán. 2.3. Synonymy (Tính đồng nghĩa) Tính đồng nghĩa đề cập đến số những item giống hoặc rất tương tự nhau ch ỉ khác nhau v ề tên hoặc mục từ. Hầu hết các hệ thống tư vấn không có khả năng khám phá ra m ối liên quan v ề mặt ngữ nghĩa này vì vậy việc nghiên cứu về những sản phẩm này là r ất khác nhau. Ch ẳng h ạn, nếu nhìn vào hai item này “children movie” và “children film” th ực t ế đây là hai item gi ống nhau, nhưng các hệ thống CF dựa trên bộ nhớ lại đưa kết quả không khớp gi ữa chúng khi tính toán đ ộ tương tự. Thật ra, độ biến thiên trong cách dùng các thuật ngữ mô t ả nói chung là r ất l ớn. Vì v ậy, tính phổ biến của từ đồng nghĩa làm giảm hiệu suất của các hệ tư vấn CF. Các cố gắng trước đây nhằm giải quyết vấn đề về tính đồng nghĩa ph ụ thu ộc nhi ều vào s ự triển khai thuật ngữ một cách tự động hoặc có tri thức hoặc thông qua việc xây dựng từ đi ển li ệt kê các từ đồng nghĩa với nhau. Trở ngại cho các ph ương th ức t ự đ ộng chính là m ột s ố item đ ược b ổ sung có thể có ý nghĩa khác với dự định, dẫn đến giảm sút nhanh chóng hiệu suất tư vấn [45]. Kỹ thuật SVD, cụ thể là phương thức Latent Semantic Indexing (LSI), có khả năng gi ải quy ết vấn đề từ đồng nghĩa. SVD đưa ra một ma trân lớn các tài li ệu thu ật ngữ liên quan đ ến d ữ li ệu và xây dựng một không gian ngữ nghĩa mà ở đó các thuật ngữ và tài li ệu liên quan m ật thi ết v ới nhau. SVD cho phép sắp xếp không gian nhằm mang lại những m ẫu liên k ết chính trong d ữ li ệu, và b ỏ qua những mẫu nhỏ hơn và ít quan trọng hơn. Hiệu suất của LSI trong việc gi ải quyết v ấn đ ề tính đồng nghĩa là tạo ra mức độ recall (gọi lại) cao h ơn t ại nh ững n ơi mà m ức đ ộ chính xác ban đ ầu khá thấp, làm cho những cải thiện tương ứng lớn. Tuy nhiên, hi ệu suất của phương th ức LSI t ại mức thấp nhất của recall khá là ít [25]. Phương thức LSI chỉ giải quyết được một phần vấn đề đa nghĩa mà trong thực tế hầu hết các từ đều nhiều hơn một nghĩa [25]. 2.4. Gray Sheep (Tính mập mờ) Vấn đề này đề cập đến những người dùng có ý ki ến không kiên đ ịnh đ ồng ý ho ặc không đồng ý vói một nhóm người và vì vậy không có l ợi cho h ệ l ọc c ộng tác [46]. Black sheep là nhóm
ngược nhau, đây là nhóm mà thị hiếu đặc trưng c ủa h ọ đ ưa ra những t ư v ấn g ần nh ư là không có khả năng xảy ra. Mặc dù đây là lỗi của hệ thống tư vấn, nhưng những h ệ tư v ấn không đi ện t ử cũng gặp những vấn đề lớn này, vì vậy black sheep là lỗi không thể chấp nhận được [47]. Claypool et al. đã đưa ra phương pháp lai kết hợp gi ữa hệ tư v ấn CF và h ệ t ư v ấn d ựa trên nội dung như là cơ sở dự đoán trọng số đánh giá trung bình c ủa d ự đoán d ựa trên n ội dung và CF. Với phương pháp này, trọng số đánh giá được xác dịnh dựa trên việc nghiên cứu kỹ lương, cho phép hệ thống xác định sự tối ưu hóa khi trộn lẫn tư vấn dựa trên n ội dung và CF cho m ỗi ng ười dùng, giúp giải quyết vấn dề gray sheep [46]. 2.5. Shilling Attacks (Sự tấn công) Trong trường hợp này những người đưa ra lời đánh giá thì đưa ra nhi ều nh ững đánh giá t ốt cho sản phẩm của họ và xấu cho những sản phẩm c ạnh tranh v ới h ọ. Và các h ệ th ống CF không thể phòng ngừa những hiện tượng này [2]. Hiên nay, các mô hình shilling attacks cho hệ lọc c ộng tác được xác đ ịnh và hi ệu qu ả c ủa nó vẫn là một vấn đề cần nghiên cứu. Lam và Riedl đã thấy rằng thuật toán CF d ựa trên item ch ịu tác động của những sự tấn công này ít hơn so với thuật toán d ựa trên người dùng, và h ọ đã đ ưa ra m ột phương pháp mới được dùng để đánh giá và loại bỏ kiểu tấn công này trong các hệ tư vấn [48]. Mô hình tấn công của shilling cho các hệ CF dựa trên item đã đ ược nghiên c ứu b ởi Mobasher et al. và các hệ CF khác như hệ CF lai và hệ CF dựa trên mô hình cũng đ ược tin t ưởng r ằng có kh ả năng giải quyết một phần lỗi này [49]. O’Mahony et al. đã góp phần vào vi ệc gi ải quyết vấn đ ề shilling attacks bằng việc phân tích thế mạnh, khả năng phục hồi hệ tư vấn từ những tình tr ạng chông phá có ác ý trong ma trận trọng số khách hàng/ sản phẩm [50]. Bell và Koren [51] sử dụng phương pháp lĩnh hôi để gi ải quyết v ấn đề shilling attacks b ằng việc gỡ bỏ các ảnh hưởng toàn cục trong trạng thái dữ li ệu đã bị bình th ường hóa c ủa CF d ựa trên hàng xóm, và làm việc với những ảnh hưởng toàn cục còn lại để lựa ch ọn ra các hàng xóm. Và h ọ đã cải thiện được hiệu suất của CF trong dữ liệu Netflix [20]. 2.6. Các thách thức khác. Nhiều người không muốn những thói quen và cách nhìn của mình đ ược bi ết đ ến r ộng rãi, trong khi các hệ tư vấn CF cũng cần tập trung vào những thông tin riêng tư c ủa m ỗi người. Miller et al. [4] và Canny [52] đã tìm ra các phương thức để bảo vệ thông tin cá nhân c ủa ng ười dùng trong các công việc về tư vấn cho CF. Sự gia tăng của nhiễu ( Sự phá hoại _ sabotage) cũng là m ột thách th ức khác, nh ư ng ười dùng cũng có nhiều thể loại khác nhau. Kỹ thuật lựa chọn thể hi ện và tính th ừa s ố mà tr ận d ư c ực đ ại được xem nhưng là phương pháp hữu ích để giải quyết vấn đề này cho CF. Thuyết Dempster –
Shafer (DS) và kỹ thuật gán là một thành công trong việc cung cấp dữ li ệu không hoàn ch ỉnh và pha trộn cho các công việc phân loại và biểu diễn tri thức, chúng cũng có sức mạnh l ớn trong vi ệc gi ải quyết vấn đề pha trộn của CF. Khả năng suy luận cũng là một khía cạnh quan trọng trong các h ệ t ư vấn. Lý do ban đ ầu nh ư “ban sẽ thích quyển sách này vì bạn đã thích những quyển sách kia” sẽ được xuất hiện và có ích cho người đọc, thay vì sự đánh giá chính xác của những lời giảng giải [57]. Thách thức Netflix Prize (Đòn bẩy) 2.7. Được giới thiệu vào tháng 10 năm 2006, thách thức đòn bẩy Netflix [20] đã thu hút hàng nghìn nghiên cứu đang cạnh tranh với hàng triệu đô la nhằm cải thi ện t ốt nh ất hi ệu su ất t ư v ấn v ề phim. Thách thức này đặc trưng với tập dữ liệu công nghiệp với số lượng lớn (480,000 người dùng và 17,770 bộ phim) và độ đo hiệu suất suất không mềm dẻo của RMSE (xem chi tiết phần 6). Cho đến tháng 7, năm 2009. Leaderboard trong cuộc tranh đua về Netflix Prize đã đ ưa ra k ết quả như bảng 3 (RSME đã cải thiện được 10.5% trên các hệ th ống t ư vấn phim Netflix: Cinematch) thông qua các yếu tố ngữ nghĩa và mô hình hàng xóm [58]. M ột vài trang nghiên c ứu đáng chú ý về thách thức này có thể được tìm thấy trong 2008 KDD Netflix Workshop(http://netflixddworkshop2008.info. ) 3. Lọc dựa trên bộ nhớ
Thuật toán CF dựa trên bộ nhớ sử dụng toàn bộ ho ặc m ột mẫu dữ li ệu user – item đ ể sinh ra dự đoán. Mỗi người dùng là một phần của nhóm những người có sở thích gi ống nhau. B ằng vi ệc xác định những hàng xóm cho người dùng mới (ho ặc người dùng chính), m ột d ự đoán v ề s ở thích với các item mới được tạo ra. Thuật toán CF dựa trên hàng xóm là thuật toán CF d ựa trên b ộ nh ớ đ ược s ử d ụng r ộng rãi thường tiến hàng theo các bước sau: tính toán độ tương tự hoặc trọng số w i, j nhằm đưa lại khoảng cách, độ tương quan, hoặc trọng số đánh giá giữa hai người dùng ho ặc hai item, i và j; t ừ đó sinh ra những dự đoán cho người dùng chính bằng việc lấy trọng số trung bình c ủa tất c ả các đánh giá c ủa người dùng hoặc item của một item hoặc người dùng nào đó, ho ặc đ ơn gi ản là l ấy trung bình các trọng số đánh giá [40]. Khi công việc sinh ra một tư vấn top – N, chúng ta c ần tìm k ng ười dùng hoặc item giống nhau nhất ( các hàng gần nh ất) sau đó tính toán đ ộ tr ương t ự và cu ối cùng là t ập hợp các hàng xóm lấy các item thường xảy ra nhất trong top – N đem tư vấn. 3.1 Tính toán độ tương tự Tính toán độ tương tự giữa người dùng hoặc item là một bước cơ bản trong thuật toán l ọc cộng tác dựa trên bộ nhớ. Với các thuật toán CF dựa trên item, ý tưởng cơ bản của việc tính toán độ tương tự giữa item i và item j bước đầu tiên là làm việc với những người dùng có cùng đánh giá v ề các item này và sau đó áp dụng việc tính toán đẻ xác định độ tương tự w i, j giữa hai item cùng trọng số đánh giá của những người dùng này [40]. Đối với thuật toán CF d ựa trên ng ười dùng, b ước đ ầu tiên chúng ta phải tính toán độ tương tự w u, v giữa hai người dùng u và v, những người mà cùng đánh giá về các item giống nhau. Có rất nhiều phương pháp khác nhau để tính toán độ tương tự ho ặc trọng số gi ữa những người dùng hoặc item. 3.1.1. Độ tương tự dựa trên sự tương quan Trong trường hợp này, độ tương tự wu, v giữa hai người dùng u và y, hoặc wi, j giữa hai item I và u được đánh giá bằng việc tính toán độ tương quan Pearson hoặc các độ tương t ự d ựa trên đ ộ tương quan khác. Độ tương quan Pearson đo phạm vi giữa hai biến tuyến tính có quan hệ với nhau [5]. Ch ẳng hạn đối với thuật toán dựa trên người dùng, độ tương quan Pearson giữa người dùng u và v là:
là xét trên toàn bộ các item của cả người dùng u và v đã đánh giá và Trong đó là đánh giá trung bình của items được đánh giá bởi người dùng thứ u. Chẳng h ạn trong b ảng 4, chúng ta có w1, 5 = 0.756 Đối với thuât toán dựa trên item, cho tập người dùng u thu ộc U là nh ững ng ười cùng đánh giá về hai item i và j, ta có độ tương quan Pearson được tính toán như sau: Trong đó ru, I là đánh giá của người dùng u cho item i, là đánh giá trung bình của item thứ I bởi những người dùng khác, được biểu diễn như hình 2 [40] Một vài biến đổi trong độ tương quan Pearson dựa trên người dùng và item có th ể đ ược tìm thấy trong [59]. Thuật toán CF dựa trên độ tương quan Pearson là m ột thu ật toán CF đi ển hình và thường được việc nghiên cứu CF.
Độ tương tự dựa trên tính tương quan khác bao gồm: độ tương quan Pearson ràng bu ộc, và một sự đa dạng của độ tương quan Pearson sử dụng điểm trung tâm thay vì tr ọng số đánh giá trung bình; độ tươn quan hạng Spearman, giống như độ tương quan Pearson, nó mong đ ợi các đánh giá giống như là các thứ hạng; và độ tương quan Kendall’s, giống như độ tương quan hạng Superman, nhưng thay vì sử dụng các thứ hạng cảu chúng, ở đây chỉ những thứ hạng có liên quan m ới đ ược dùng để tính toán độ tương quan [3, 60]. Thông thường số những người dùng trong việc tính toán dộ tương tự là rất đáng quan tâm so với kích thước những hàng xóm của người dùng chính, và CF d ựa trên đ ộ t ương t ự đ ược xem nh ư là CF dựa trên hàng xóm. 3.1.2 Độ tương tự dựa trên vector cosine Độ tương tự giữa hai tài liệu có để được đo thông qua việc xem xét m ỗi tài li ệu nh ư m ột vector về tần suất xuất hiện từ và tính toán cosine về góc giữa các vector tần su ất đó [61]. D ạng thức này có thể được chấp nhận trong lọc cộng tác, người dùng và item thay cho các tài li ệu và các trọng số đánh giá thay cho tần suất xuất hiện từ. Cụ thể, nếu R là ma trận user – item m x n, độ tương tự gi ữa hai item, i và j đ ược xác đ ịnh là cosine của các vector n chiều tương ứng với cột thứ i và j trong ma trận R Độ tương tự vector giữa item i và j được tính như sau: . biểu thị tích giữa hai vector. Từ đó đưa ra tính toán độ tương tự cho n item, và ma Trong đó trận độ tương tự n x n được thực hiện [27]. Chẳng hạn, nếu cho vector và vector , ta có độ tương tự cosine vector giữa và là Trong trường hợp cụ thể, những người dùng khác nhau có thể đưa ra những khoảng đánh giá khác nhau, vì vậy độ tương tự cosine vector không thể tính đến. Để giải quyết mặt hạn chế này, độ
tương tự cosine điều chỉnh đã đưa ra thông qua việc trừ đi mức trung bình của người dùng tương ứng từ mỗi cặp có cùng đánh giá. Độ tương tự cosine điều chỉnh có thể xem như là độ tương quan Pearson. Trên thực tế, độ tương quan Pearson thực hiện độ tương tự cosine nhờ sự sắp xếp các đánh giá của những người dùng theo đánh giá của chính họ. Vì vậy, chúng ta phải đưa ra những giá trị không tích cực với độ tương quan Pearson nhưng lại tích cực với độ tương tự cosine, với giả thuyết rằng chúng ta khoảng đánh giá là n điểm. 3.1.3 Độ tương tự khác: Có nhiều phép đo độ tương tự khác như độ tương tự dựa trên xác suất có điều kiện [62, 63]. Nhưng nó không được sử dung rộng rãi và phổ biến vì vậy tôi không mô tả chi tiết ở đây. 3.2. Tính toán dự đoán và tư vấn Để thu được những dự đoán hoặc lời gợi ý là một bước quan trọng trong hệ tư vấn lọc cộng tác. Trong thuật toán CF dựa trên hàng xóm, tập con những hàng xóm gần nhất của người dùng thực sự được lựa chọn dựa trên độ tương tự chủa chúng với anh hoặc chị ta, và tập hợp trọng số của những đánh giá đó được dùng để sinh ra dự đoán cho người dùng chính [64]. 3.2.1. Tổng trọng số của những đánh giá khác nhau: Để đưa ra được một dự đoán cho người dùng chính a đối với một item i nào đó, ta có thể lấy một trọng số trung bình của tất cả các đánh giá trên item theo công thức sau: [5] là những đánh giá trung bình của người dùng a và người dùng u trên tất Trong đó: và cả các item đã được đánh giá, và wa, u là trọng số giữa người dùng a và u. Tổng là tất cả các người đã đánh giá cho item i. Cho một ví dụ đơn giản ở bảng 4, sử dung thuật toán CF dựa dùng trên người dùng , để dự đoán đánh giá cho U1 về I2, ta có:
Chú ý dự đoán trên dựa trên hàng xóm của người dùng thực sự. 3.2.2. Trung bình trọng số đơn giản Đối với dự đoán dựa trên item, chúng ta có thể sử dụng trung bình trọng số đơn giản để dự đoán đánh giá Pu, i cho người dùng u và item i [40] Trong đó phép tổnglà trên tất cả các item đã được đánh giá cho người dùng u, wi, n là trọng số giữa item i và n, ru, n là đánh giá của người dùng u cho item n. 3.3. Tư vấn Top –N Tư vấn Top – N dùng một tập N các item có thứ hạng cao nhất thể hiện mối quan tâm của một người dùng nào đó. Chẳng hạn, nếu bạn là một khách hàng cũ, khi bạn muốn đăng nhập vào tài khoản của mình vào trang http://amazon.com, bạn sẽ được tư vấn một danh sách các sách (hoặc sản phẩm khác) mà có thể bạn sẽ quan tâm (như hình 1). Kỹ thuật tư vấn Top – N phân tích mà trận user – item để khám phá ra các mối liên hệ giữa những người dùng hoặc item khác nhau và dùng chung để tính toán ra các gợi ý. Một vài mô hình như các mô hình dựa trên ngữ nghĩa luật liên kết, có thể được sử dụng để tạo ra các tư vấn Top – N, mà tôi sẽ giới thiệu ở phần 4. 3.3.3 Các thuật toán tư vấn Top – N dựa trên người dùng Các thuật toán tư vấn Top – N dựa trên người dùng đầu tiên phải xác định được k người dùng tương tự nhau nhất (hàng xóm gần nhất) đối với người dùng chính nhờ sử dụng độ tương quan Pearson hoặc mô hình không gian vector [9, 27], trong đó mỗi người dùng được xem như một vector tromg không gian item m chiều và độ tương tự giữa người dùng thực sự và những người dùng khác được tính toán giữa các vector. Sau khi có được k người dùng tương tự nhau, các cột tương ứng
trong ma trận user – item được tập hợp lại thàm một nhóm item C. Với tập C này, kỹ thuật CF dựa trên người dùng sau đó có thể gợi ý những item top – N có tần số xuất hiện lớn nhất trong C mà người dùng thực sự chưa được biết đến. Thuật toán tư vấn Top – N dựa trên người dùng bị giới hạn bởi mối quan hệ với hiệu suất về khả năng mở rộng và thời gian thực [62]. 3.3.2. Thuật toán tư vấn Top – N dựa trên item Thuật toán tư vấn Top – N dựa trên item được phát triển nhằm giải quyết vấn đề về khả năng mở rộng của thuật toán top – N dựa trên người dùng. Đầu tiên thuật toán tính toán k item gần nhau nhất cho mỗi item theo độ tương tự; sau đó định nghĩa ra tập C như là một ứng cử của việc tư vấn thông qua việc lấy phàn k item gần nhất và loại bỏ những item trong tập U mà người dùng đánh giá rồi; sau đó tính toán độ tương tự giữa item trong tập C và tập U. Kết quả tập item trong C sẽ được đưa ra làm gợi ý thông qua danh sách Top – N dựa trên item đã được sắp xếp theo thứ tự giảm dần về độ tương tự [62]. Tuy nhiên có một vấn đề trong phương thức này đó là ki sự phân bố của tập các item khác với sự phân bố của item các cụ thể trong tập, thì lược đồ ở trên có thể sinh ra những tư vấn dưới mức tối ưu. Để giải quyết vấn đề này, Deshpanda và Karypis [63] đã phát triển một thuật toán tư vấn top – N dựa trên item có thứ tự ở mức cao hơn nhờ vào việc sử dụng kết hợp tất cả các item theo một kích thước cụ thể khi xác định tập item đem tư vấn cho người dùng. 3.4 Mở rộng thuật toán dựa trên bộ nhớ 3.4.1. Mặc định lựa chọn Trong nhiều hệ lọc cộng tác, độ tương tự giữa một cặp người dùng chỉ được tính toán từ tập những item giao nhau thông qua việc cùng được cả hai người dùng đó đánh giá[5, 27]. Tuy nhiên, nó sẽ không còn đáng tin cậy nữa khi có quá ít đánh giá để sinh ra các giá trị tương tự. Đồng thời, việc chỉ tập trung vào tập item giao nhau sẽ làm chúng ta không thể chú ý tới những hành vi có đánh giá chung mà đã được phản ánh thông qua toàn bộ những thông tin trước đây của người dùng. Dựa vào kinh nghiệm, giả thuyết rằng một vài giá trị lựa chọn đã được mặt định cho những đánh giá còn thiếu có thể cải thiện hiệu suất dự đoán của CF, Herlocker et al. [64] chỉ xem xét các tập item giao nhau có kích thước nhỏ bằng cách giảm trọng số của những người dùng có ít hơn 50 item để chia sẻ. Chee et al. [13] sử dụng mức trung bình của một nhóm (hoặc nhóm nhỏ) như là một lựa chọn mặc định để mở rộng thông tin đánh giá trước đây của mỗi người dùng. Breese et al. [9] thì gán giá trị trung lập hoặc một vài thi hiếu mang tính tiêu cực khi không có đánh giá và sau đó tính toán độ tương tự giữa những người dùng trên tập dữ liệu kết quả đánh giá. 3.4.2. Tần suất người dùng nghịch đảo Ý tưởng của tần suất người dùng nghịch đảo [61] được áp dụng trong lọc cộng tác, ở đó những item tương đối phổ biến được xem là không hữu ích bằng các item ít được biết đến trong
vấn đề nắm bắt độ tương tự. Tần suất nghịch đảo có thể được xác định là trong đó nj là số người dùng đã đánh giá cho item j và n là tổng số người dùng. Nếu mọi người đều đánh giá item j thì fj là 0. Để áp dụng tần suất người dùng nghịch đảo trong đó sử dụng thuật toán CF dựa trên độ tương tự vector, chúng ta cần sử dụng một đánh giá biến đổi, đơn giản là đánh giá khởi tạo được sinh ra nhờ hệ số fj [9]. 3.4.3. Sự khuyêch đại trường hợp Sự khuyếch đại trường hợp đề cập đến một biến đổi được áp dụng cho những trọng số dùng trong dự đoán lọc cộng tác cơ bản. Sự biến đổi này nhấn mạnh đến những trọng số cao và hạ thấp những trọng số thấp [9]: là lũy thừa sự khuyếch đại trường hợp, và lựa chọn tiêu biểu của Trong đó là 2.5 [65]. Sự khuyếch đại trường hợp giảm độ pha trộn trong dữ liệu. Nó có khuynh hướng giúp những trọng số cao cũng như những giá trị thấp từ lớn trở thành không đáng kể. Chẳng hạn nếu trọng số cao, wi.j = 0.9 thì nó chỉ còn ; nếu nó thấp wi, j = 0.1, thì chúng trở thành không đáng kể . 3.4.4. Thuật toán CF Imputation – Boost Khi dữ liệu đánh giá cho các nhiệm vụ CF cực kỳ là thưa thớt, nó sẽ tạo ra một vấn đề khó giải quyết khi đưa ra những dự đoán chính xác thông qua việc sử dụng CF dựa trên độ tương quan Pearson. Su et al [37, 66] đã đề xuất ra một khung làm việc imputation – boosted collaborative filtering (IBCF); đầu tiên sử dụng một kỹ thuật imputation để lấp đầy những dữ liệu còn thiếu trước khi sử dụng thuật toán CF truyền thống dựa trên độ tương quan Pearson từ đó đưa ra dự đoán cụ thể cho người dùng về một item đã được chỉ định. Sau khi triển khai hoàn toàn kỹ thuật imputation chuẩn (bao gồm mean imputation, linear regression imputation và predictive mean matching imputation, và Bayesian multiple imputation ) và sự phân loại máy học [67] (bao gồm naïve Bayes, SVM, mạng nhân tạo, câu quyết định, luật Baysian lazy) giống với IBCF, nói chung chúng thực hiện rất hiệu quả và đem lại hiệu suất cao. 4. Kỹ thuạt lọc cộng tác dựa trên mô hình Việc thiết ké và phát triển theo mô hình (như các thuật toán máy h ọc, ng ữ nghĩa) có th ể cho phép hệ thống học những mẫy phức tạp dựa trên dữ liệu đào tạo, và sau đó đ ưa ra nh ững d ự đoán
thông mình trong các nhiệm vụ của lọc cộng tác đổi với dữ liệu test ho ặc th ế gi ới th ực s ự trên mô hình đã được học. Các thuật toán CF dựa trên mô hình như mô hình Bayes, mô hình clustering, và các mạng phụ thuộc phải được xem xét để giải quyết những hạn chế trong các thu ật toán CF d ựa trên bộ nhớ [9,71]. Thông thường thuật toán phân loại được dùng nh ư là các mô hình CF n ếu các đánh giá của người dùng là rõ ràng và các mô hình hồi quy và ph ương th ức SVD dùng cho các đánh giá dưới dạng số học. Các thuật toán CF Bayesian belief net (BN) _ mạng bayes tin cậy 4.1. BN là một đồ thị có hướng không tạo thành chu trình (DAG) v ới b ộ ba , trong đó mỗi node biểu diễn các biến ngẫu nhiên, mỗi hướng giữa các node là một liên kết xác suất giữa các biến, và là một bảng xác suất có điều kiện có thể xác định được có bao nhiêu node phụ thuộc vào cha của nó [72]. BN thường được dùng cho những nhiệm vụ liên quan đến việc phân loại. 4.1.1. Thuật toán CF Bayes đơn giản Thuật toán CF Bayes đơn giản thường sử dụng là Naïve Bayes (NB) để đ ưa ra các d ự đoán cho nhiệm vụ CF. Giả thuyết rằng các đặc tính là độc lập v ới l ớp đ ược đ ưa ra, xác su ất c ủa m ột lớp nào đó được đưa ra cho tất cả các đặc tính có thể tính toán được, và sau đó l ớp có xác su ất cao nhất sẽ được sắp xếp thành lớp được dự đoán [41]. Đối với dữ li ệu chưa hoàn ch ỉnh, vi ệc tính toán các xác suất và việc tạo ra các phân loại được tính toán dựa trên những d ữ li ệu có th ể nhìn th ấy được (giả sử trong biểu thức dưới đây o biểu thị những giá trị có thể nhìn thấy được): Đánh giá Laplace thường được dùng để giải quyết việc tính toán xác suất và tranh xác su ất có điều kiện bằng 0: là kích thước của tâp class {X i}. Chẳng hạn có lớp nhị phân Trong đó sẽ thành (0+1)/(2+2) = ¼, sẽ thành khi sử dụng độ đánh giá Laplace.
Việc sử dụng ví dụ tương tự như trong bảng 4, tập class {1, 2, 3, 4, 5} đ ược dùng đ ể t ạo ra đánh giá cho U1 trong I2 khi sử dụng thuật toán CF Bayes đơn giản và độ đánh giá Laplace, chúng ta có: Trong đó Miyahara và Pazzani, dữ liệu đa class đầu tien được chuyển đổi thành dữ li ệu class nh ị phân, và sau đó chuyền thành ma trận đánh giá Boolean feature vector. S ự chuy ển đ ổi này làm cho vi ệc s ử dụng thuật toán NB cho mục đinh CF dễ dàng hơn, nhưng nó l ại đem đén nh ững v ấn đ ề liên quan đến khả năng mở rộng và mất thông tin multiclass cho dữ li ệu multiclass. Trong Miyahara và Pazzani [41], chúng ta chỉ có thể áp dung mô hình CF Bayes đơn giản trong dữ liệu nhị phân Vì dữ liệu CF trong thế giới thực hầu hết là multiclass, nên Su và Khoshgoftaar [41] áp d ụng thuật toán Bayes CF với dữ liệu multiclass cho các nhi ệm v ụ c ủa CF, tuy nhiên đ ộ chính xác d ự đoán của chúng lại rất tồi, mặc dù nó xử lý kh ả năng m ở r ộng t ốt h ơn so v ới CF d ựa trên đ ộ t ương quan Pearson vì nó tạo ra những dự đoán dựa trên các đánh giá có s ẵn và ti ến trình d ự đoán đánh giá tiết kiệm được thời gian. Thuật toán CF Bayes đơn giản đáng được xem như kỹ thuật CF dựa trên mô hình vì nó tính toán dựa trên bộ nhớ để đưa ra dự đoán CF. Chúng ta đ ặt nó t ỏng ph ần này vì h ầy h ết các thu ật toán CF Bayes khác là CF dựa trên mô hình. 4.1.2. Các thuật toán CF Bayes khác. BN với cây quyết định tại mỗi node. Mô hình này đươc xem là cây quyết định tại mỗi node c ủa BN, trong đó m ỗi node t ương ứng với một item trong miền xác định và trạng thái của mỗi node tương ứng với khả năng được đánh giá của mỗi item[9]. Kết quả này đã thể hiện rằng mô hình này tương tự như hiệu su ất d ự đoán đ ộ
tương tự của các phương thức CF dựa trên độ tương quan Pearson và có hi ệu su ất Bayes – clustering và các thuật toán CF dựa trên bộ nhớ vector cosine. Baseline Bayesian model sử dụn BN không có cung trong l ọc c ộng tác (baseline model) và t ư vấn các item trên tất cả item [75]. Tuy nhiên, hiệu suất lại trở thành một hạn chế. 4.2. Clustering CF Algorithms. Một cluster là một tập dữ liệu các đối tượng tương tự nhau trong cùng m ột c ụm và không phân biệt với các đối tượng trong các cụm khác. Phép đo độ tương tự gi ữa các đối tượng đ ược xác định thông qua việc sử dụng khoảng cách Minkowsski và độ tương quan Pearson. Cho hai đối tượng dữ liệu, , khoảng và Y = cahcs Minkowsk được tính như sau: Trong đó, n là số chiều của đối tượng và x i , yi là giá trị của chiều thứ i của đối tượng X và Y, q là một số nguyên dương. Khi q = 1, d là khoảng cách Mahanttan; khi q = 2, d là kho ảng cách Euclidian [76]. Các phương thức Clustering có thể được phân loại thành 3 lo ại: phương th ức phân chia, phương thức dựa trên mối tương quan và phương thức phân cấp [76, 77]. Phương thức phân chia thường được sử dụng là k – means, được đưa ra bở Mc Queen [78] v ới hai l ợi ích chính: hi ệu qu ả về mối quan hệ và thực thi dễ dàng. Phương thức c ụm dựa trên mối t ương quan, đây là m ột ki ểu tìm kiếm điển hình các cụm đối tượng được phân tách bởi các miền thưa thớt có sự bi ểu di ễn pha trộn. DBSCAN [79] và OPTIC được biết đến như là những phương thức cụm d ựa trên t ương quan nổi tiếng. Các phương thức phân tầng như BIRICH [81] tạo ra m ột s ự phân tích t ập đ ối t ượng d ữ liệu phân cấp thông qua một vài chuẩn. Trong hầy hết các trường hợp, cụm được xem là m ột b ước trung gian và các k ết qu ả c ụm được dùng cho việc phân tích và xây dựng quá trình phân lo ại ho ặc cho các nhi ệm v ụ khác. Các mô hình CF cụm có thể được áp dụng theo nhiều cách thức khác nhau. Sarwar et al. [43] và O’Connor và Herlocker [42] sử dụng kỹ thuật phân cụm để chia dữ liệu thành những cụm và sử dụng thuật toán CF dựa trên bộ nhớ như thuật toán độ tương quan Pearson để đưa ra các dự đoán cho các nhi ệm v ụ CF trong mỗi cụm đó. Việc sử dụng phương thức k – means với k = 2, phương th ức RecTree, đ ược đ ưa ra b ởi Chee et al [13ư đã chia đệ quy dữ liệu đánh giá rất lớn ban đầu ra thành hai c ụm con, nó xây d ựng
RecTree từ gốc tới lá của nó. Kết quả RecTree được xem như là m ột cây nh ị phân không đ ối x ứng, trong đó các node lá là ma trận tương tự nhau và các node bên trong giữ tâm đánh giá cảu các cây bên trong của chúng. Dự đoán của người dùng thực sự được tạo ra ngay trong các node lá. RecTree có độ phức tạp cho các tư vấn không trực tuyến và cho các tư vấn trực tuyến. trong đó n là kích thước tập dữ liệu và b là kích thước của sự phân chia và b là m ột h ằng s ố, nó có thể cải thiện được tính chính xác dựa vào độ tương quan Pearson khi lựa chọn tương ứng v ới kích thước của những lời cố vấn (cụm người dùng). Mô hình hỗn hợp linh hoạt (FMM) mở rộng thuật toán phân cụm tr ước đây c ủa CF thông qua việc phân cụm cả người dùng và item tại cùng một thời điểm, theo đó m ỗi người dùng và item được xem là cụm đa cấp và là các cụm người dùng hoặc item đ ược mô hình hóa. K ết qu ả c ủa th ực nghiệm này dã chứng minh rằng thuật toán FMM đem lại m ức độ chính xác cao h ơn thu ật toán CF dựa trên độ tương quan Pearson và mô hình khía cạnh [83]. Các mô hình phân cụm có khả năng mở rộng hơn các ph ương pháp l ọc c ộng tác tr ước đây vì chúng đưa ra các dự đoán trong các cụm nhỏ hơn rất nhi ều sơ v ới toàn b ộ t ập ng ười dùng [13, 27, 44, 84]. Độ phức tạp tính toán xảy ra khi thuật toán này chạy trong môi tr ường tr ực tuy ến. Tuy nhiên, chất lượng tư vấn nói chung là thấp. Tuy nhiên chất l ượng đó có th ể đ ược c ải thi ện nh ờ việc sử dụng những cụm có chất lượng tốt nhưng nói chung h ầu hết s ự phân lo ại các c ụm ng ười dùng trở lên khó khăn trong việc tìm kiếm các người dùng tương tự nhau khi s ử d ụng l ọc c ộng tác dựa trên bộ nhớ [6]. Việc có được các cụm tối ưu trên tập d ữ li ệu l ớn trên th ực t ế là không có, h ầu hết các ứng dung sử dụng rất nhiều kỹ thuật sinh ra phân cụm. Đối với cá tập d ữ liệu l ớn, đ ặc bi ệt là có số chiều cao việc giảm chiều hoặc giảm mẫu là một điều cần thiết. Các kỹ thuật CF dựa trên mô hình khác 4.3. Các thuật toán CF dựa trên luật liên kết thường sử dụng nhi ệm v ụ tư vấn top – N đ ể d ự đoán. Sarwar et al [27] mô tả phương thức của họ nhờ vi ệc sử d ụng thu ật toán ng ữ nghĩa d ựa vào luật liên kết truyền thống để tìm ra các quy tắc phát triển top – N, nhờ đó học có th ể tìm ra các item có độ tin cậy và trọng số đánh cao theo thứ tự từ trên xuống, và tất nhiên chúng sẽ đ ược đem ra t ư vấn [27]. Leng et al đã đưa ra một khung làm vi ệc m ới cho l ọc c ộng tác nh ờ s ử d ụng các lu ật liên kết mờ và độ tương tự đa cấp [102]. Một kỹ thuật CF dựa trên mô hình khác đó là phương pháp entropy c ực đài, ở đó tr ước tiên dữ liệu được phân cụm và sau đó trong các cụm được đưa ra h ọ sử d ụng các entropy c ực đ ại nh ư một hàm đối tượng để tạo ra mô hình entropy cực đại có điều ki ện nhằm sinh ra các d ự đoán. Mạng phụ thuộc là một mô hình đồ thị liên quan đến xác suất, đồ thị ở đây là m ột quy trình. Các