Hệ Thống Gợi ý Sử Dụng Thuật Toán Tối ưu Bầy đàn

Trang chủ Tìm kiếm Trang chủ Tìm kiếm Hệ thống gợi ý sử dụng thuật toán tối ưu bầy đàn pdf 11 564 KB 1 77 4.1 ( 14 lượt) Xem tài liệu Nhấn vào bên dưới để tải tài liệu Tải về Đang chuẩn bị: 60 Bắt đầu tải xuống Đang xem trước 10 trên tổng 11 trang, để tải xuống xem đầy đủ hãy nhấn vào bên trên Chủ đề liên quan Thuật toán tối ưu bầy đàn Sử dụng thuật toán tối ưu bầy đàn Hệ thống gợi ý sử dụng thuật toán Phương pháp ICCF Phương pháp PSO Phân cụm Spectral

Nội dung

Kỷ yếu Hội nghị Quốc gia lần thứ VIII về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Hà Nội, ngày 9-10/7/2015 HỆ THỐNG GỢI Ý SỬ DỤNG THUẬT TOÁN TỐI ƯU BẦY ĐÀN Phạm Minh Chuẩn1, Lê Thanh Hương2, Trần Đình Khang2, Nguyễn Văn Hậu1 1 Khoa Công nghệ Thông tin, Đại học SPKT Hưng Yên 2 Viện CNTT & TT, Đại học Bách khoa Hà Nội chuanpm@gmail.com, huonglt@soict.hust.edu.vn, khangtd@soict.hust.edu.vn, nvhau66@gmail.com TÓM TẮT - Kỹ thuật lọc cộng tác (Collaborative Filtering - CF) là một kỹ thuật gợi ý phổ biến nhất được sử dụng nhiều trong các hệ thống gợi ý đã được tích hợp trong các website thương mại điện tử (chẳng hạn như amazon.com, barnesandnoble.com, Yahoo! news, TripAdvisor.com). Kỹ thuật CF dựa trên giả thiết rằng những người dùng (user) có cùng sở thích thì sẽ quan tâm một tập item tương tự. Phương pháp phân cụm lọc cộng tác (Iterative Clustered CF - ICCF) và lặp cộng tác tối ưu trọng số sử dụng thuật toán PSO (PSO-Feature Weighted) thể hiện tính hiệu quả cho hệ gợi ý mà giá trị đánh giá thuộc trong tập {1, 2,…, 5}. Tuy nhiên, các kỹ thuật đó không thể trực tiếp áp dụng cho các hệ thống gợi ý trong thực tế mà giá trị đánh giá trong tập {0, 1}. Do vậy, bài báo này đề xuất việc cải tiến hai phương pháp ICCF và PSO–Feature Weighted để có thể áp dụng được cho các hệ gợi ý mà giá trị đánh giá thuộc tập {0, 1}. Kết quả thực nghiệm của hai phương pháp mà chúng tôi đưa ra áp dụng trên bộ dữ liệu hệ gợi ý công việc cho thấy độ chính xác mô hình dự đoán có cải thiện rõ rệt so với phương pháp CF truyền thống đồng thời cũng giải quyết được vấn đề dữ liệu thưa mà phương pháp CF thường gặp phải. Từ khóa - Hệ thống gợi ý, kỹ thuật lọc cộng tác dựa trên Item, kỹ thuật lọc cộng tác dựa trên User, phân cụm lọc cộng tác, tối ưu trọng số lọc cộng tác, thuật toán tối ưu bầy đàn, phân cụm Spectral, thuật toán k-mean. I. GIỚI THIỆU Hệ thống gợi ý [1, 2] phân tích thông tin về sở thích của user về các item để cung cấp các khuyến nghị đối với các item mà phù hợp nhất với mong muốn và sở thích của người dùng. Trên thực tế, hệ thống gợi ý cố gắng thu thập những sở thích của user và mô hình hóa sự tương tác giữa user và item. Trong kỹ thuật lọc cộng tác (Collaborative Filtering – CF), việc đưa ra những khuyến nghị về các item đối với user được xác định dựa trên những quan điểm của những user có cùng sở thích với user đó. Hệ thống lọc cộng tác biểu diễn user dựa trên những đánh giá của họ đối với tập các item. Hệ thống sẽ lựa chọn những user cùng sở thích tùy thuộc vào độ đo tương tự hoặc tương quan. Sau đó, đưa ra những dự đoán đối với những item chưa từng được user đánh giá hoặc quan tâm. Cuối cùng hệ thống sẽ gợi ý những item nào với mức độ dự đoán cao nhất cho user mục tiêu. Kỹ thuật CF đã được khẳng định sự thành công bởi rất nhiều nghiên cứu và thực nghiệm trong nhiều ứng dụng thực tế [2, 3, 4]. Nhìn chung, chất lượng của hệ thống gợi ý cộng tác có thể được tăng cường bằng cách cải thiện độ đo tương tự và việc lựa chọn tập láng giềng. Một số hạn chế chính của CF như là vấn đề dữ liệu thưa, khả năng mở rộng và thiếu dữ liệu [5, 6] có ảnh hưởng lớn đến chất lượng gợi ý. Mặc dù có nhiều nhà nghiên cứu đã cố gắng giải quyết vấn đề này, kỹ thuật lọc cộng tác vẫn cần được cải tiến nhiều hơn để cải thiện độ chính xác mô hình gợi ý. Vì kỹ thuật lọc cộng tác dựa trên những quan điểm của tập láng giềng những user có cùng sở thích với user mục tiêu, nên điều quan trọng là phải chọn tập láng giềng chính xác. Độ đo mức độ tương tự càng được cải thiện, thì việc lựa chọn láng giềng càng chính xác và gợi ý càng đúng đắn hơn. Hiện tại, có nhiều phương pháp đã được đề xuất để cải thiện độ đo tương tự, những phương thức bao gồm độ đo PIP (Proximity-Impact-Popularity)[7], độ tương tự Union [8], Random walk counting [9], độ tương tự dựa trên phân lớp user (users–class similarity) [10], và thủ tục lặp message passing [11]; những phương pháp này đều có điểm mạnh riêng và hỗ trợ các tình huống khác nhau. Tuy nhiên, đa số các phương pháp đều tập trung trên một vấn đề cụ thể và bị ảnh hưởng bởi một vài hạn chế. Chẳng hạn, PIP đề xuất giải quyết vấn đề cold-start nhưng lại bị hạn chế bởi việc tính toán độ tương tự lọc cộng tác dựa trên user truyền thống. Độ tương tự dựa trên phân lớp user chỉ sử dụng được trong trường hợp lớp thông tin có sẵn và không nhận được kết quả ý nghĩa đối với tập dữ liệu lớn cũng như việc cập nhật độ đo tương tự được thực hiện nhiều lần. Union được sử dụng với dữ liệu thưa nhưng không có khả năng mở rộng. Trong [12] một hệ thống gợi ý phân cụm lặp cộng tác (Iterative Clustered CF - ICCF) được đề xuất. Trong đó, phương pháp phân cụm spectral được sử dụng lặp lại trong cả hai hướng tiếp cận lọc cộng tác dựa trên user (userbased) và dựa trên item (item-based) để dự đoán những đánh giá chưa biết. Vì thế, ICCF đã thành công trong việc giải quyết vấn đề dữ liệu thưa và cold–start. Tuy nhiên tất cả user và item đều có mức độ ảnh hưởng như nhau khi tính toán độ tương tự trong khi đó độ đo tương tự cần phản ánh mức độ quan trọng của các đặc trưng khác nhau. Một số nghiên cứu đưa ra sự cải thiện độ chính xác khi những đặc trưng được gắn trọng số trong trường hợp tính toán khoảng cách [13]. Trong CF, phương pháp trọng số đặc trưng gán một trọng số đến mỗi một đặc trưng (user hoặc item) để đo mức độ quan trọng của đặc trưng như thế nào trong toàn bộ độ tương tự. Breese và cộng sự [14] phỏng theo ý tưởng của tần số văn bản ngược (inverse document frequency) để gán trọng số đặc trưng trong CF. Ý tưởng chính của tiếp cận này, gọi là tần số user ngược (inverse user freqency), đó là những item phổ biến thì không HỆ THỐNG GỢI Ý SỬ DỤNG THUẬT TOÁN TỐI ƯU BẦY ĐÀN 287 cung cấp nhiều thông tin về sở thích thực sự của user. Vì thế trọng số của những item phổ biến được đánh giá cần phải giảm. Cùng với ý tưởng giảm trọng số đối với những item phổ biến được nhiều người biết đến được thực hiện bằng cách sử dụng phương sai trọng số [15]. Ở đây, những item có phương sai lớn hơn sẽ hỗ trợ tốt trong việc phân biệt sở thích của user, do đó, nó sẽ nhận trọng số lớn hơn. Tuy nhiên, các tác giả cũng cho rằng phương pháp này cũng giảm đáng kể trung bình lỗi tuyệt đối (Mean Squared Error-MAE) so với trường hợp không gán trọng số. Yu và cộng sự [16], giới thiệu tiếp cận lý thuyết thông tin đối với gán trọng số đặc trưng. Họ cho rằng những thông tin có tác động qua lại sẽ nhận được kết quả tốt hơn. Tác giả trong [17] cũng biểu diễn một lược đồ gán trọng số tự động khác đối với hệ thống gợi ý CF. Phương pháp này đã cố gắng tìm những trọng số gắn với các item khác nhau để làm cho mỗi user gần hơn với những người láng giềng của họ và xa hơn với những người không tương đồng. Phương pháp sử dụng ý tưởng tiếp cận dựa trên mô hình (model–based approaches) và làm giảm trung bình lỗi tuyệt đối. Ngoài ra, S. H. Min và I. Han [18] đã đề xuất mô hình GA-CF giống như lược đồ trọng số đặc trưng trong kỹ thuật lọc cộng tác dựa trên user truyền thống. Bên cạnh đó, tất cả các phương pháp gán trọng số đặc trưng, được đề xuất đến nay cố gắng nâng cao việc tính toán mức độ tương đồng mà không xem xét đến những hạn chế của CF, yếu tố ảnh hưởng nhiều đến hiệu năng của hệ thống gợi ý. Từ quan điểm toán học, trọng số đặc trưng có thể xem như một vấn đề tối ưu không lồi phi tuyến với tối thiểu đa cục bộ địa phương (multi local) [19]. Kỹ thuật tối ưu bầy đàn (Particle Swarm Optimization - PSO) có thể tìm ra giá trị tối ưu toàn cục với thiết lập điều kiện khởi tạo đơn giản. Vì nó chỉ sử dụng các phép toán nguyên thủy do đó tiết kiệm chi phí tính toán về bộ nhớ lưu trữ và tốc độ xử lý [20]. Phương pháp PSO-Feature Weighted do Abdelwahab và cộng sự [27] đề xuất sử dụng thuật toán PSO để tìm ra một bộ trọng số tối ưu ωU (đại diện cho mức độ quan trọng của user) và ω I (đại diện cho mức độ quan trọng của item) trong việc tính toán mức độ tương đồng giữa các user và giữa các item, điều này quyết định lớn đến mức độ chính xác của mô hình dự đoán. Phương pháp này làm tăng cường quá trình phân cụm theo user và item không chỉ dựa trên thông tin phản hồi tường minh của user được biểu diễn qua ma trận đánh giá Rmxn (m- số lượng user, n- số lượng item), mà còn sử dụng các trọng số thể hiện cho mức độ quan trọng của mỗi user và item. Vì vậy, nó cải thiện được tập láng giềng. Ngoài ra, mô hình dự đoán được lặp lại nhiều lần để ngoại suy các giá trị đánh giá chưa biết trong ma trận R, kết quả ngoại suy bước trước được sử dụng làm dữ liệu đầu vào cho bước tiếp theo cho đến khi nhận được ma trận R tối ưu dầy hơn và từ đó giúp nâng cao độ chính xác cho mô hình gợi ý. Hạn chế đáng kể của hai phương pháp ICCF và PSO-Feature Weighted là chúng không áp dụng được với hệ gợi ý mà ma trận đánh giá R chỉ nhận giá trị nhị phân, chẳng hạn như trong hệ thống gợi ý việc làm thì người xin việc sẽ lựa chọn những công việc để ứng tuyển, hoặc trong hệ thống gợi ý bài báo khoa học thì người dùng sẽ lựa chọn các bài báo quan tâm vào trong thư viện riêng của họ. Vì vậy, trong bài báo này chúng tôi sẽ đề xuất cải tiến cho hai phương pháp ICCF và PSO-Feature Weighted nhằm áp dụng đối với bài toán gợi ý mà ma trận đánh giá R nhận giá trị dạng nhị phân, đồng thời chúng tôi cũng điều chỉnh cách thức ước lượng giá trị rij chưa biết trong ma trận R để phù hợp với bài toán gợi ý công việc; ngoài ra, chúng tôi tiến hành xác định các trọng số khi lai ghép tuyến tính phương pháp lọc cộng tác dựa trên user và dựa trên item (ωIF và ωUF) cùng với quá trình tìm ra bộ trọng số tối ưu đại diện cho mức độ quan trọng của các user và item trong việc tính toán độ tương đồng (ωU và ωI) với mong muốn khai thác hiệu quả phương pháp lai ghép giữa kỹ thuật lọc cộng tác dựa trên user và dựa trên item nhằm nâng cao chất lượng của hệ thống gợi ý. II. GIỚI THIỆU CÁC KIẾN THỨC LIÊN QUAN 2.1. Phương pháp phân cụm Spectral Phương pháp ICCF ngoại suy ra các đánh giá chưa biết trong ma trận R thông qua quá trình lặp. Trong kỹ thuật này, mô hình dự đoán sử dụng phương pháp phân cụm spectral [22] trong cả hai hướng tiếp cận lọc cộng tác dựa trên user và dựa trên item [21] và phương pháp phân cụm spectral được thực hiện theo thủ tục sau đây: Bước 1: Tính độ tương đồng giữa các user và giữa các item. 1 2 Trong đó à là các véc tơ tương ứng với hàng thứ i và j trong ma trận R đại diện cho user i, j khi tính độ tương đồng giữa user i, j (và khi tính độ tương đồng giữa hai item i, j thì tương ứng với cột thứ i và j trong ma trận R) và σ là tham số điều chỉnh độ lớn của tập láng giềng. Nếu σ nhỏ sẽ thu được một cấu hình địa phương tốt hơn đối với tập láng giềng. Tuy nhiên nếu σ quá nhỏ thì các điểm sẽ bị phân tách (xa nhau). Do đó, giá trị thích hợp nhất của σ được tính theo công thức sau [23] 1 Trong đó d là khoảng giữa à , và n là số các user hoặc số các item 2 288 2 Phạm Minh Chuẩn, C Lê Thanhh Hương, Trần Đìnnh Khang, Nguy yễn Văn Hậu Bước B 2: Ma trrận D (diagonnal degree maatrix) là ma trận đường chééo chính, trongg đó các phầnn tử được tính h toán theo công c thức dướ ới đây: 3 Bước B 3: Dựa trên ma trận ttương tự S, thhuật toán phân n cụm Spectral xây dựng m một đồ thị tươnng đồng và tín nh toán ma trrận laplace L tương t ứng củaa nó như sau: 4 Bước B 4: Sau khi k tính toán m ma trận L, thuậật toán phân cụ ụm Spectral sẽẽ dựa trên k vééc tơ riêng (v1, v2,…, vk) ứn ng với k trị riêng r lớn nhất đầu tiên thỏa mãn biểu thức (5) 5 nxk Bước B 5: Xây dựng d một ma ttrận mới V∈R với các vécc tơ riêng (v1, v2,…, vk) tươnng ứng với cáác cột của ma trận t Bước B 6: Gọi yi∈Rk tương ứnng là các véc ttơ hàng của ma m trận V Bước B 7: Sử dụụng phương phháp phân cụm m k-means để phân p các điểm m (yi)i =1, 2,…n vàào k cụm (C1, C2,…, Ck) Bước B 8: Gán các c điểm dữ liiệu ban đầu (xxi)i=1,2,…n theo các c cụm Cj tươ ơng ứng với cụụm của các điiểm (yi)i=1,2,…n. 2.2. 2 Phương pháp p tối ưu bầy đàn (Partiicle Swarm Optimization O - PSO) Phươngg pháp tối ưu bầy đàn là mộột trong nhữn ng thuật toán xây x dựng dựa trên khái niệm m trí tuệ bầy đàn để tìm kiếm k lời giải cho c các bài tooán tối ưu hóaa trên một không gian tìm kiếm nào đó.. Phương phápp tối ưu bầy đàn đ là một dạng d của các thuật t toán tiếnn hóa quần thểể, với sự tương g tác giữa các cá thể trong m một quần thể để khám phá một không gian g tìm kiếm.. PSO là kết qquả của sự mô hình hóa việcc đàn chim baay đi tìm kiếm m thức ăn cho nnên nó thường g được xếp vào v các loại thhuật toán có sử ử dụng trí tuệ bầy đàn, đượ ợc giới thiệu vào v năm 1995 tại một hội nnghị của IEEE bởi James Kennedy K và Russell R C. Eberrhart [20]. Thuuật toán này đã đ được áp dụ ụng thành côngg trong nhiều lĩnh vực. Mộtt ứng dụng hiệu h quả về sinnh học áp dụnng PSO được ttrình bày trong g [25]. PSO [226] được khởi tạo bằng mộtt nhóm cá thể ngẫu nhiên và sau đó tìm nnghiệm tối ưuu bằng cách cậ ập nhật các th hế hệ. Trong mỗi thế hệ, m mỗi cá thể đượ ợc cập nhật th heo hai vị trí tốt t nhất. Giá ttrị thứ nhất là vị trí tốt nhấtt mà nó đã từ ừng đạt được cho tới thời đđiểm hiện tại, gọi là Pbest. Một M nghiệm tốii ưu khác mà cá thể này báám theo là ngh hiệm tối ưu toàn cục Gbest, đó là vị trí tốốt nhất trong ttất cả quá trình tìm kiếm cảả quần thể từ ttrước tới thời điểm hiện tạii. Nói cách khác, k mỗi cá thể t trong quầnn thể cập nhậtt vị trí của nó theo vị trí tốtt nhất của nó và của cả quầần thể tính tớii thời điểm hiện h tại (Hình 1) Hình 1. Sơ đồ một điểm m tìm kiếm bằng g phương pháp PSO đ Trong đó: k Xi : Vị trí t cá thể thứ i tại thế hệ thứ ứk Vik: Vậnn tốc cá thể thhứ i tại thế hệ tthứ k Xik+1: Vị V trí cá thể thứ ứ i tại thế hệ thhứ k+1 Vik+1: Vận V tốc cá thể thứ i tại thế hhệ thứ k+1 Pbest: Vị V trí tốt nhất của cá thể thứ i Gbest: Vị V trí tốt nhất trrong quần thểể Vận tốcc và vị trí của cá thể trong qquần thể được tính như sau: 6 7 HỆ THỐNG GỢI Ý SỬ DỤNG THUẬT TOÁN TỐI ƯU BẦY ĐÀN 289 Trong đó: ω: là hệ số quán tính c1, c2: Các hệ số gia tốc, nhận giá trị từ 1.5 đến 2.5 r1, r2: Các số ngẫu nhiên nhận giá trị trong khoảng [0, 1] Giá trị của trọng số quán tính ω sẽ giảm tuyến tính từ 1 đến 0 tùy thuộc vào số lần lặp xác định trước. Các nhà nghiên cứu đã tìm ra giá trị của ω lớn cho phép các cá thể thực hiện mở rộng phạm vi tìm kiếm, giá trị của ω nhỏ làm tăng sự thay đổi để nhận được giá trị tối ưu địa phương. Bởi vậy, người ta đã nhận thấy rằng hiệu năng tốt nhất có thể đạt được khi sử dụng giá trị ω lớn (chẳng hạn 0.9) ở thời điểm bắt đầu và sau đó giảm dần dần cho đến khi đưa ra được giá trị khác nhỏ của ω. Thuật toán PSO 1. Khởi tạo quần thể: (a) Thiết lập các hằng số: kmax, c1, c2. (b) Khởi tạo ngẫu nhiên vị trí cá thể x0i thuộc miền D trong tập IRn với i = 1, 2, ..., s. (c) Khởi tạo ngẫu nhiên vận tốc cá thể : 0 ≤ v0i ≤ v0max với i = 1, ..., s. (d) Đặt k = 1; 2. Tối ưu hóa: (a) Đánh giá hàm fki bằng tọa độ của xki tính toán được trong không gian tìm kiếm. (b) Nếu fki