Đăng ký Đăng nhập
Trang chủ Nghiên cứu, phát triển phương pháp lọc cộng tác dựa vào bộ nhớ...

Tài liệu Nghiên cứu, phát triển phương pháp lọc cộng tác dựa vào bộ nhớ

.PDF
24
236
138

Mô tả:

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG --------------------------------------- ĐỖ THỊ LIÊN NGHIÊN CỨU, PHÁT TRIỂN PHƯƠNG PHÁP LỌC CỘNG TÁC DỰA VÀO BỘ NHỚ Chuyên ngành: Hệ thống thông tin Mã số: 60.48.01.04 TÓM TẮT LUẬN VĂN THẠC SĨ HÀ NỘI - 2013 Luận văn được hoàn thành tại: HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG Người hướng dẫn khoa học: TS. Nguyễn Duy Phương Phản biện 1: …………………………………………………………………………… Phản biện 2: ………………………………………………………………………….. Luận văn sẽ được bảo vệ trước Hội đồng chấm luận văn thạc sĩ tại Học viện Công nghệ Bưu chính Viễn thông Vào lúc: ....... giờ ....... ngày ....... tháng ....... .. năm ............... Có thể tìm hiểu luận văn tại: - Thư viện của Học viện Công nghệ Bưu chính Viễn thông 1 MỞ ĐẦU 1. Đặt vấn đề Lọc thông tin (Information Filtering là lĩnh v c nghi n c u các uá trình lọc b nh ng thông tin không thích hợ và cung cấ thông tin thích hợ đ n với m i người d ng. Lọc thông tin được xem là hương há hiệu uả hạn ch tình trạng uá tải thông tin được quan tâm nhiều nhất hiện nay. Các hương há lọc thông tin đóng vai trò uan trọng đối với các thống thương mại điện tử, đặc biệt là hệ tư vấn (Recommender System . Hệ tư vấn (Recommender System là hệ thống có khả năng t động hân tích, hân loại, l a chọn và cung cấ cho người d ng nh ng thông tin, hàng hóa hay dịch vụ mà họ uan tâm. Hệ tư vấn được xem như một bi n thể điển hình có vai trò uan trọng trong lọc thông tin. Nhiều hệ tư vấn đã được thương mại hóa và triển khai thành công, ti u biểu là hệ tư vấn của các hãng Amazon.com, Netflix.com, Procter & Gamble. Hệ tư vấn được xây d ng d a tr n hai kỹ thuật lọc thông tin chính: Lọc theo nội dung (Content-Based Filtering và lọc cộng tác (Collaborative Filtering . Lọc theo nội dung khai thác nh ng khía cạnh li n uan đ n các đặc trưng nội dung thông tin sản hẩm người d ng đã từng sử dụng hay truy nhậ trong uá kh để tạo n n tư vấn. Lọc theo nội dung cho lại k t uả khá tốt tr n các dạng thông tin được biểu diễn bằng các đặc trưng nội dung, nhưng gặ hải khó khăn tr n các dạng thông tin đa hương tiện (hình ảnh, âm thanh, dịch vụ . Trái lại, lọc cộng tác khai thác nh ng khía cạnh li n uan đ n thói uen sử dụng sản hẩm của cộng đồng người d ng có c ng sở thích để tạo n n tư vấn. So với lọc theo nội dung, lọc cộng tác có một số ưu điểm như đơn giản trong cài đặt và có thể lọc được mọi loại thông tin hay hàng hoá mà không cần hải biểu diễn dưới dạng văn bản. Lọc cộng tác cho hệ tư vấn được ti cận theo hai hương há chính: Lọc cộng tác d a vào bộ nhớ (Memory-Based Collaborative Filtering) và lọc cộng tác d a vào mô hình (Model-Based Collaborative Filtering . Điểm khác biệt uan trọng trong hai hương há ti cận là hương há xây d ng mô hình huấn luyện và mô hình d đoán. Lọc d a vào bộ nhớ ti n hành xây d ng đồng thời mô hình huấn luyện và mô hình d đoán. Ngược lại, lọc d a vào mô hình xây d ng mô hình huấn luyện và mô hình d đoán độc lậ nhau. So với lọc cộng tác d a vào mô hình, lọc cộng tác d a vào bộ nhớ được á dụng rộng rãi hơn do tính hiệu uả, đơn giản và có độ chính xác khá cao. 2 Lọc cộng tác d a vào bộ nhớ được th c hiện theo hai hương há chính: Lọc d a vào người d ng (User-Based Collaborative Filtering và lọc d a vào sản hẩm (ItemBased Collaborative Filtering . Hiệu uả của các hương há lọc d a vào bộ nhớ hụ thuộc vào độ đo tương t gi a các cặ người d ng hoặc sản hẩm. Trong uá trình nghi n c u và ng dụng, nhiều nghi n c u đã được đề xuất để cải thiện các độ đo tương t , đặc biệt trong trường hợ d liệu thưa. Mặc d đã có nhiều nghi n c u nhắm tới nội dung này, nhưng đây vẫn là nh ng vấn đề nghi n c u mở, có tính thời s và thu hút s ua tâm của cộng đồng nghi n c u. Đề tài “Nghiên cứu, phát triển phương pháp lọc cộng tác dựa vào bộ nhớ” được th c hiện trong khuôn khổ luận văn thạc sĩ chuy n ngành “Truyền d liệu và mạng máy tính” nhằm gó hần giải uy t một số vấn đề còn tồn tại của lọc cộng tác d a vào bộ nhớ. 2. Mục tiêu của luận văn Mục ti u của luận văn là nghi n c u á dụng, cải ti n hương há lọc cộng tác d a tr n bộ nhớ nhằm cải thiện độ chính xác k t uả d đoán cho các hệ tư vấn. Đặc biệt, nghi n c u tậ trung vào việc nâng cao k t uả d đoán nhu cầu người d ng trong trường hợ d liệu thưa. 3. Các đóng góp của luận văn Đóng gó của luận văn là đề xuất một hương há tính toán m c độ tương t gi a các cặ người d ng hoặc sản hẩm d a vào đồ thị để nâng cao chất lượng d đoán cho các hệ tư vấn. Nh ng đóng gó cụ thể của luận văn bao gồm bao gồm: - Mở rộng biểu diễn đồ thị của Huang [23] cho các hệ thống lọc cộng tác. Phương há biểu diễn h hợ với tất cả các bộ d liệu cho lọc cộng tác hiện tại. - Đề xuất hương há tính toán m c độ tương t gi a các cặ người d ng d a vào hương há ước lượng trọng số các đường đi từ đỉnh người d ng đ n đỉnh người d ng. Đề xuất được á dụng cho hương há UserBased đạt k t uả tốt tr n các bộ d liệu thử nghiệm khác nhau. - Đề xuất hương há tính toán m c độ tương t gi a các cặ sản hẩm d a vào hương há ước lượng trọng số các đường đi từ đỉnh sản hẩm đ n đỉnh sản hẩm. Đề xuất được á dụng cho hương há ItemBased đạt k t uả tốt tr n các bộ d liệu thử nghiệm khác nhau. 3 - Xây d ng được bộ d liệu thử nghiệm cho lọc cộng tác với 7682 người d ng và 3000 sản hẩm di động khác nhau. - Xây d ng hệ tư vấn sản hẩm điện thoại di động. Hệ thống cho hé xem, đánh giá, gợi ý nh ng sản hẩm hợ với sở thích của m i người d ng. 4. Bố cục của luận văn Luận văn được tổ ch c thành ba chương, trong đó : Chương 1 : Giới thiệu tổng uan về lọc cộng tác d a vào bộ nhớ. Nội dung chính của chương trình bày nh ng nghi n c u cơ bản về lọc cộng tác, các hương há lọc cộng tác, đi sâu trình bày về các hương há lọc cộng tác d a tr n bộ nhớ. Tr n cơ sở nh ng nghi n c u cơ bản, xác định rõ hướng nghi n c u của đề tài. Chương 2 : Trình bày hương há lọc cộng tác d a tr n mô hình đồ thị, bao gồm : Phương há lọc d a tr n người d ng, hương há lọc d a tr n sản hẩm. Nội dung trình bày trong chương này được tổng hợ từ k t uả nghi n c u đã được trình bày tại hội nghị Quốc Gia lần th 6 về “Nghi n c u cơ bản và ng dụng công nghệ thông tin” tổ tr c tại Hu ngày 20-21/6/2013 [1]. Chương 3 : Trình bày thi t k và xây d ng hệ tư vấn sản hẩm điện thoại di động sử dụng hương há lọc cộng tác d a tr n mô hình đồ thị được đề xuất trong chương 2. 4 CHƯƠNG 1: LỌC CỘNG TÁC DỰA VÀO BỘ NHỚ Mục ti u chính của chương này trình bày nh ng vấn đề tổng uan về lọc cộng tác, các hương há lọc cộng tác, hân tích rõ nh ng hạn ch tồn tại của m i hương há để từ đó xác định rõ hướng nghi n c u cụ thể của đề tài. Nh ng k t uả nghi n c u của đề tài sẽ được trình bày trong các chương ti 1.1. theo của luận văn. Phát biểu bài toán lọc cộng tác Cho tậ hợ h u hạn U = {u1, u2,…, uN} là tậ gồm N người d ng, P = {p1, p2,.., pM} là tậ gồm M sản hẩm. M i sản hẩm pxP có thể là hàng hóa, him, ảnh, tạ chí, tài liệu, sách, báo, dịch vụ hoặc bất kỳ dạng thông tin nào mà người d ng cần đ n. Để thuận tiện trong trình bày, ta vi t pxP ngắn gọn thành xP, uiU là iU. Mối uan hệ gi a tậ người d ng U và tậ sản hẩm P được biểu diễn thông ua ma trận đánh giá R ={ rix , i = 1..N, x = 1..M}. M i giá trị rix thể hiện đánh giá của người dùng uiU đối với sản hẩm pxP. Giá trị rix có thể được thu thậ tr c ti h i ý ki n người d ng hoặc thu thậ gián ti thông ua cơ ch bằng cách hản hồi của người d ng. Giá trị rix =  được hiểu người d ng ui chưa đánh giá hoặc chưa bao giờ bi t đ n sản hẩm px. Nhiệm vụ của lọc cộng tác là d đoán uan điểm của người d ng uaU đối với nh ng mặt hàng mới px P, tr n cơ sở đó tư vấn cho người d ng ua nh ng sản hẩm được đánh giá cao [7]. Bảng 1 là một ví dụ về ma trận đánh giá cho hệ lọc cộng tác gồm 3 người d ng U ={ u1, u2, u3} và 4 sản hẩm P = {p1, p2, p3, p4}. Các giá trị đánh giá được biểu diễn có giá trị rix {, 1, 2, 3, 4, 5}. Nh ng giá trị rix= được hiểu là người d ng iU chưa bi t đ n sản hẩm xP. Ô điền ký t “?” là giá trị cần điền vào của các hương há lọc cộng tác. Bảng 1-1. Ma trận đánh giá của lọc cộng tác. p1 p2 p3 p4 u1 5  4  u2  3 4  u3 ? 3 ? 2 5 Ma trận đánh giá R = (rix) là thông tin đầu vào duy nhất của các hương há lọc cộng tác. D a tr n ma trận đầu vào, các hương há lọc cộng tác th c hiện như được mô tả trong Hình 1.1. Hình 1-1. Các thành phần của hệ thống lọc cộng tác D a tr n ma trận đánh giá, các hương há lọc cộng tác th c hiện hai tác vụ: D đoán uan điểm của người d ng hiện thời (Active User về các sản hẩm mà họ chưa đánh giá, đồng thời đưa ra một danh sách các sản hẩm có đánh giá cao nhất hân bổ cho người d ng hiện thời. Có nhiều hương há đề xuất khác nhau để giải uy t bài toán lọc cộng tác. Tuy vậy ta có thể hân loại các hương há thành hai cách ti cận chính: Lọc cộng tác d a vào bộ nhớ và lọc cộng tác d a vào mô hình. Trong hai hương há này, hương há lọc cộng tác d a vào bộ nhớ được sử dụng rộng dãi hơn cho các hệ thống lọc thông tin th c t do cài đặt đơn giản, độ chính xác cao, chi hí tính toán thấ . Chính vì vậy, hướng ti cận của luận văn tậ trung nghi n c u hát triển hương há lọc cộng tác d a vào bộ nhớ. Lọc cộng tác d a tr n bộ nhớ được ti cận theo hai hương há chính: Phương pháp lọc d a vào người d ng (UserBased và lọc d a vào sản hẩm (ItemBased . Nội dung cụ thể của hai hương há này được trình bày trong nh ng mục ti theo. 6 1.2. Phương pháp lọc cộng tác dựa trên sản phẩm 1.2.1. Thuật toán lọc cộng tác dựa trên sản phẩm Thuật toán lọc cộng tác d a vào sản hẩm xây d ng cho sản hẩm một tậ láng giềng có các đánh giá tương t nhất trong ma trận người d ng – sản hẩm. Các đánh giá của nh ng sản hẩm láng giềng này sau đó được sử dụng để đưa ra d đoán. Thuật toán lọc cộng tác d a tr n sản hẩm (Item-Based) được th c hiện thông ua 3 bước: Bước 1: Tính toán độ tương t sản hẩm Bước 2: Xác định tậ láng giềng cho sản hẩm cần tư vấn Bước 3: Tính toán đưa ra lời d đoán 1.2.2. Ví dụ lọc cộng tác dựa trên sản phẩm 1.2.3. Hạn chế của phương pháp lọc cộng tác dựa trên sản phẩm  Vấn đề d liệu thưa (S arsity Data Problem  Vấn đề người d ng mới (New User Problem  Vấn đề sản hẩm mới (New Item Problem 1.3. Phương pháp lọc cộng tác dựa trên người dùng 1.3.1. Thuật toán lọc cộng tác dựa trên người dùng Thuật toán lọc cộng tác d a vào người d ng xây d ng cho m i người d ng một tậ các láng giềng có các đánh giá tương t trong ma trận người d ng – sản hẩm. Các đánh giá từ nh ng người d ng này sau đó được sử dụng để đưa ra d đoán. Kĩ thuật lọc cộng tác d a trên người d ng (User-Based) được th c hiện thông ua 3 bước: Bước 1. Tính toán m c độ tương t gi a các cặ người d ng Bước 2: Xác định tậ láng giềng cho người d ng cần tư vấn Bước 3: Tính toán đưa ra d đoán 1.3.2. Ví dụ lọc cộng tác dựa trên người dùng 1.3.3. Hạn chế của phương pháp lọc cộng tác dựa trên người dùng  Vấn đề d liệu thưa (S arsity Data Problem  Vấn đề người d ng mới (New User Problem  Vấn đề sản hẩm mới (New Item Problem 7 1.4. Mục tiêu nghiên cứu của luận văn Như đã trình bày ở trên lọc cộng tác được hân chia thành hai hướng ti cận: lọc cộng tác d a vào bộ nhớ và lọc cộng tác d a vào mô hình. Trong hai hương há này, hương há lọc cộng tác d a vào bộ nhớ được sử dụng rộng dãi hơn cho các hệ thống lọc thông tin th c t do cài đặt đơn giản, độ chính xác cao, chi hí tính toán thấ . Tuy nhi n với việc sử dụng các dộ đo tương uan, độ đo tương t hiện tại thì các hệ thống lọc thông tin chỉ khai thác được mối uan hệ tr c ti nhiều mối uan hệ gián ti gi a các đối tượng, như vậy b ua rất gi a các đối tượng trong hệ thống. Chính vì vậy, hướng ti cận của luận văn tậ trung nghi n c u hát triển hương pháp lọc cộng tác d a vào bộ nhớ với mục ti u cụ thể như sau:  Nghi n c u và đề xuất hương há hạn ch ảnh hưởng tình trạng d liệu thưa của lọc cộng tác d a tr n mô hình đồ thị. Phương há đề xuất được trình bày trong Chương 2.  Xây d ng một ng dụng d a tr n hương há đề xuất. K t uả hân tích thi t k và xây d ng ng dụng được trình bày trong Chương 3. 1.5. Kết luận chương 1 Nội dung chương 1 đã trình bày tổng uan về lọc cộng tác, các hương há lọc cộng tác d a vào bộ nhớ. Qua đó hân tích rõ nh ng hạn ch tồn tại của m i hương há để xác định rõ hướng cụ thể của đề tài về nghi n c u và hát triển hương há lọc cộng tác d a vào bộ nhớ. 8 CHƯƠNG 2: PHƯƠNG PHÁP USER-BASED VÀ ITEM-BASED DỰA TRÊN MÔ HÌNH ĐỒ THỊ Mục ti u chính của chương này trình bày k t uả nghi n c u của luận văn về hát triển hương há lọc cộng tác d a vào bộ nhớ tr n mô hình đồ thị. Sử dụng biểu diễn đồ thị cho hé tận dụng được mối uan hệ gián ti gi a các đối tượng người d ng và sản hẩm vào uá trình d đoán và tư vấn. Khác với cách ti cận trong [23, 29], hương há d đoán của luận văn được th hiện d a tr n việc xây d ng một độ đo tương t gi a các cặ người d ng hoặc sản hẩm. D a tr n độ đo tương t này, ta xác định được tậ láng giềng tốt hơn so với các hương há lọc d a vào bộ nhớ sử dụng các độ đo tương uan. Để thuận tiện cho việc trình bày: Mục (2.1 trình bày hương há biểu diễn đồ thị hai hía cho lọc cộng tác. Mục (2.2 trình bày hương há lọc d a tr n người d ng tr n mô hình đồ thị. Mục (2.3 trình bày hương há lọc d a tr n sản hẩm tr n mô hình đồ thị. Mục (2.4 trình bày điều kiện cần và đủ để các hệ thống lọc cộng tác á dụng tất cả các hương há tr n mô hình đồ thị. Mục (2.5 trình bày về k t uả thử nghiệm, so sánh và đánh giá với các hương há lọc khác. Mục cuối c ng (2.6) là k t luận và hướng nghi n c u ti theo. Nội dung trình bày trong chương này được tổng hợ từ k t uả nghi n c u trong [1]. 2.1. Biểu diễn đồ thị hai phía cho lọc cộng tác Giả sử ta có hệ lọc cộng tác gồm N người d ng U và M sản hẩm P với ma trận đánh giá là R=(rij: i=1, 2, ..N; j =1, 2, ..,M . Không hạn ch tính tổng uát của bài toán, ta giả sử rix= +v n u người d ng iU đánh giá sản hẩm xP ở m c độ v, trong đó v[0, 1]. v rix    Nếu người dùng i thích sản phẩm x ở mức độ v. Nếu người dùng i chưa biết đến sản phẩm x. (2.1) Biểu diễn ma trận đánh giá theo (2.1 sẽ không ảnh hưởng đ n các hệ thống lọc cộng tác sử dụng đánh giá nhị hân (0,1 hoặc có nhiều m c đánh giá trong khoảng [0,1]. Đối với các bộ d liệu có giá trị đánh giá rix{1, 2, .., V}, ta chỉ cần th c hiện hé bi n đổi đơn giản chuyển rix  rix . Phé bi n đổi này vẫn bảo toàn được m c độ đánh giá theo V th t khác nhau của các hệ lọc cộng tác. Đây là một biểu diễn mở rộng của Huang đã 9 th c hiện trong [22]. Ví dụ với hệ lọc cộng tác được cho trong Bảng 1, sẽ được chuyển đổi biểu diễn theo (2.1 thành Bảng 2.1. Muc đích của việc chuyển đổi rix[0,1] để sử dụng trong hương há tính toán m c độ tương t gi a các cặ người d ng và sản hẩm. Nội dung này sẽ được trình bày chi ti t trong các mục ti theo. Bảng 2-1. Ma trận đánh giá được chuyển đổi p1 p2 p3 p4 u1 1.0  0.8  u2  0.6 0.8  u3 ? 0.6 ? 0.4 Hệ lọc cộng tác với ma trận đánh giá xác định theo (2.1 hình thành n n một đồ thị hai hía, một hía là tậ người d ng, hía còn lại là tậ sản hẩm, ký hiệu là đồ thị G =. Tậ đỉnh V của đồ thị được chia thành hai tậ : tậ người d ng và tậ sản hẩm (V=UP . Tậ cạnh E của đồ thị được xác định theo công th c (2.2 . M i cạnh eE đều có dạng e = (i, x , trong đó iU và xP. Không tồn tại các cạnh của nối gi a hai đỉnh người d ng hoặc cạnh nối gi a hai đỉnh sản hẩm. Trọng số của m i cạnh được xác định theo (2.3). E  e  (i, x) : i U  x  P | rix   (2.2) rix if (i, x)  E wix   0 otherwise (2.3) Gọi C=(cij là ma trận trọng số biểu diễn đồ thị G (i =1, 2,.., N+M; j = 1, 2, .., N+M . Khi đó, ma trận vuông C sẽ được chia thành bốn hần theo công th c (2.4). Trong đó, ma trận vuông U(NN biểu diễn mối uan hệ gi a người d ng và người d ng, P(MM biểu diễn mối uan hệ gi a sản hẩm với sản hẩm, W(NM được xác định theo (2.3 biểu diễn mối uan hệ gi a người d ng và sản hẩm, WT(MN là chuyển vị của W(NM biểu diễn mối uan hệ gi a sản hẩm và người d ng. Các hần tử của ma trận U(NN), P(MM ban đầu đều có giá trị 0. U N  N  C   T W M  N  W N  M   PM  M   (2.4) 10 Ví dụ, với hệ lọc cộng tác được cho trong Bảng 2.1, khi đó đồ thị hai hía biểu diễn cho lọc cộng tác được thể hiện trong Hình 2.1, thành hần của ma trận trọng số được thể hiện trong Hình 2.2. p1 p2 1.0 0.8 p3 0.6 u1 0.8 p4 0.6 u2 0.4 u3 Hình 2-1. Đồ thị hai phía biểu diễn cho lọc cộng tác. U(NN) C= W(NM) 0.0 0.0 0.0 1.0 0.0 0.8 0.0 0.0 0.0 0.0 0.0 0.6 0.8 0.0 0.0 0.0 0.0 0.0 0.6 0.0 0.4 1.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.6 0.6 0.0 0.0 0.0 0.0 0.8 0.8 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.4 0.0 0.0 0.0 0.0 WT(MN) P(MM) Hình 2-2. Ma trận trọng số biểu diễn đồ thị hai phía. Cho đồ thị G = biểu diễn dưới dạng ma trận trọng số C xác định theo (2.4). Khi đó, lọc cộng tác có thể được xem xét như bài toán tìm ki m tr n đồ thị. Trong đó, mức độ tương tự giữa các cặp người dùng được tính toán dựa vào trọng số các đường đi từ đỉnh người dùng đến đỉnh người dùng, mức độ tương tự giữa các cặp sản phẩm được tính toán dựa vào trọng số các đường đi từ đỉnh sản phẩm đến đến đỉnh sản phẩm, mức độ phù hợp của người dùng đối với sản phẩm được tính toán dựa vào trọng số các đường đi từ đỉnh người dùng đến đỉnh sản phẩm. M c độ tương t gi a các cặ người d ng sẽ được điền giá trị vào ma trận U(NN , m c độ tương t gi a các cặ sản hẩm sẽ được điền giá trị vào ma trận P(MM , m c độ h hợ của người d ng đối với sản hẩm được điền giá trị vào ma trận W(NM) và WT(MN . Trong đó,U(NN), P(MM), W(NM), WT(MN được xác định theo (2.4). Nội dung cụ thể m i hương há ti sẽ được trình bày trong các mục ti theo. cận 11 2.2. Phương pháp user-based dựa trên mô hình đồ thị hai phía Thuật toán UserBased-Graph: Đầu vào:  Ma trận trọng số C là biểu diễn đồ thị G = cho lọc cộng tác .  iU là người dùng cần được tư vấn.  K là số lượng người dùng của tập láng giềng. Đầu ra:  Dự đoán x: rix | xP\Pi.( quan điểm của người dùng i đối với các sản phẩm mới xP). Các bước tiến hành: Bước 1. Tính toán mức độ tương tự giữa các cặp người dùng: L 2;//Thi t lậ độ dài đường đi ban đầu Repeat W N  M *W T M  N  U L N  N    W N  M *W T M  N *U L  2 N  N  if L2 if L  4,6,8,.. (2.5) L  L + 2; //Tăng độ dài đường đi. Until ( u ijL  0 với mọi j(U \ i) ); Bước 2. Xác định tậ láng giềng cho người d ng iU.  Sắ x u ijL  0 theo th t giảm dần (ij).  Chọn K người d ng jU đầu ti n làm tậ láng giềng của người d ng i (Ký hiệu tậ láng giềng của người d ng iU là Ki). Bước 3. D đoán uan điểm của người d ng i đối với các sản hẩm xP\Pi. rix  1 Ki r jx ; jK i Bước4. Chọn K sản hẩm có m c độ tương t cao nhất tư vấn cho người d ng i. Hình 2-3. Thuật toán UserBased-Graph. M c độ tương t gi a các cặ người d ng được xác định theo (2.5) hụ thuộc vào độ dài đường đi L từ đỉnh người d ng đ n đỉnh người d ng tr n đồ thị. Do vậy, một vấn đề đặt ra là với m i người d ng iU giá trị của L được lấy bằng bao nhi u cho tốt. Ngược lại đồ thị G= hải có tính chất gì để ta có thể xác định được L sao cho m c độ tương t gi a các cặ người d ng uij0. Định lý 1 dưới đây sẽ cho ta một cách xác định L trong trường hợ đồ thị biểu diễn của lọc cộng tác G = liên thông. 12 Định lý 1. N u đồ thị biểu diễn cho các hệ lọc cộng tác G= liên thông thì luôn luôn tồn tại số t nhi n chẵn L để u ijL  0 với mọi i, jU . Trong đó, u ijL được xác định theo công th c ở bước 1. Phương pháp item-based dựa trên mô hình đồ thị hai phía 2.3. Thuật toán ItemBased-Graph: Đầu vào:  Ma trận trọng số C là biểu diễn đồ thị G = cho lọc cộng tác .  xP là sản phẩm cần dự đoán  K là số lượng sản phẩm của tập láng giềng. Đầu ra:  Dự đoán x: rix | iU\Ux.( quan điểm của người dùng i đối với phẩm mới xP). Các bước tiến hành: Bước 1. Tính toán mức độ tương tự giữa các cặp sản phẩm L 2;//Thi t lậ độ dài đường đi ban đầu Repeat W T M  N *W N  M  P L M  M    W T M  N *W N  M * P L  2 M  M  if L2 if L  4,6,8,.. (2.6) L  L + 2; //Tăng độ dài đường đi. Until ( p xyL  0 với mọi y(P \ x) ); Bước 2. Xác định tậ láng giềng cho sản hẩm xP.  Sắ x L p xy theo th t giảm dần (xy).  Chọn K sản hẩm yP đầu ti n làm tậ láng giềng của sản hẩm x (Ký hiệu tậ láng giềng của sản hẩm xP là Kx). Bước 3. D đoán uan điểm của người d ng i đối với các sản hẩm xP\Pi. rix  1 Kx r ix ; xKx Bước4. Chọn K sản hẩm có m c độ tương t cao nhất tư vấn cho người d ng i. Hình 2-4. Thuật toán ItemBased-Graph. M c độ tương t gi a các cặ sản hẩm xác định theo (2.6) hụ thuộc vào độ dài đường đi L từ đỉnh sản hẩm đ n đỉnh sản hẩm tr n đồ thị. Do vậy, với m i sản hẩm xP ta cũng cần xác định giá trị của L để th c hiện tính toán. Định lý 2 dưới đây sẽ cho ta một cách xác định L trong trường hợ đồ thị biểu diễn của lọc cộng tác G = liên thông. 13 Định lý 2. N u đồ thị biểu diễn cho các hệ lọc cộng tác G= liên thông thì luôn luôn tồn tại số t nhi n chẵn L để p xyL  0 với mọi x, yP . Trong đó, PxyL được xác định theo công th c trong bước 1. 2.4. Điều kiện cần và đủ để các hệ thống lọc cộng tác áp dụng tất cả các phương pháp trên mô hình đồ thị Định lý 3. Điều kiện cần và đủ để U L N  N  được xác định theo (2.5), P L M  M  xác định theo (2.6) được điền đầy đủ giá trị khác 0 khi và chỉ khi đồ thị biểu diễn cho các hệ lọc cộng tác G= li n thông. 2.5. Kiểm nghiệm và đánh giá 2.5.1. Dữ liệu thử nghiệm Ti n hành kiểm thử tr n 2 tậ d liệu : MovieLens, vật giá. (1) Bộ d liệu MovieLens [24] gồm 1682 người d ng, 943 him với tr n 100000 đánh giá, các m c đánh giá được thi t lậ từ 1 đ n 5, m c độ thưa thớt d liệu đánh giá là 98,7%. Các m c đánh giá 1, 2, 3, 4, 5 được chuyển đổi thành 0.2, 0.4, 0.6, 0.8, 1.0. Chọn ngẫu nhi n : (80% 754 người d ng làm tậ huấn luyện (Training , (20% 189 người d ng còn lại làm tậ kiểm tra (Test như hình 2.6. Hình 2-5. Mô phỏng tập dữ liệu Movilens (2) Bộ d liệu vật giá [28] gồm 402 người d ng tr n 10 đánh giá, 3441 sản hẩm với 8885 đánh giá, các m c đánh giá được thi t lậ từ 1 đ n 5. Các m c đánh giá 1, 2, 3, 4, 5 được chuyển đổi thành 0.2, 0.4, 0.6, 0.8, 1.0. 14 Chọn ngẫu nhi n (80% 322 người d ng trong tậ huấn luyện, (20%) 80 người d ng trong tậ kiểm tra. (3) Bộ d liệu vật giá [28] gồm 1114 người dùng tr n 5 đánh giá, 4418 sản hẩm với 13476 đánh giá, các m c đánh giá được thi t lậ từ 1 đ n 5. Các m c đánh giá 1, 2, 3, 4, 5 được chuyển đổi thành 0.2, 0.4, 0.6, 0.8, 1.0. Chọn ngẫu nhi n (80% 892 người d ng trong tậ huấn luyện, (20%) 222 người dùng trong tậ kiểm tra. 2.5.2. Phương pháp thử nghiệm Trước ti n, toàn bộ tậ người d ng được chia thành hai hần, một hần Utr được sử dụng làm d liệu huấn luyện, hần còn lại Ute được sử dụng để kiểm tra. Tậ d liệu huấn luyện d ng để xây d ng mô hình theo các thuật toán lọc được sử dụng. Với m i người dùng u Ute, các đánh giá ru,p≠  được chia thành hai hần Ou và Pu. Ou được coi là đã bi t, trong khi đó Pu là đánh giá cần d đoán từ d liệu huấn luyện và Ou (hình 2.6). Giả sử hương há lọc đưa ra d đoán cho người d ng trong tậ Pu là P’u . Khi đó, sai số d đoán được th c hiện bằng cách so sánh các đánh giá trong hai tậ Pu là P’u . Có nhiều hương há đánh giá sai số hân loại khác nhau đã được đề xuất. Một trong số hương há hổ bi n nhất được sử dụng trong lọc cộng tác là đánh giá sai số hân loại thông ua độ đo trung bình giá trị tuyệt đối l i MAE. Sai số d đoán với m i khách hàng u thuộc tậ d liệu kiểm tra được tính bằng trung bình cộng của sai số tuyệt đối gi a hai giá trị được d đoán và giá trị th c của tất cả các sản hẩm thuộc tậ . | | ∑ | ̂ | (2.7) Sai số d đoán tr n toàn tậ d liệu kiểm tra được tính bằng trung bình cộng sai số d đoán cho m i khách hàng thuộc . ∑ | Giá trị MAE càng nh ch ng t hơn. 2.5.3. Kết quả thử nghiệm 2.5.3.1. Với bộ dữ liệu Movielens | (2.8) hương há đề xuất cho k t uả càng chính xác 15 Bảng 2-2. Độ đo MAE với các đánh giá biết trước của tập dữ liệu Movielens Số đánh giá bi t trước trong tậ kiểm tra Phương há 1 2 5 10 15 20 Top-N-ItemBased 0.4347 0.38 0.4536 0.4576 0.4128 0.3869 KNN-UserBased 0.7171 0.5519 0.4894 0.5554 0.6 0.6334 ItemBased-Graph 0.3819 0.3021 0.3269 0.2253 0.2024 0.1755 UserBased-Graph 0.3657 0.3584 0.3486 0.3475 0.3465 0.3336 2.5.3.2. Với bộ dữ liệu vật giá 402 người dùng Bảng 2-3. Độ đo MAE với các đánh giá biết trước của tập dữ liệu vật giá 402 người dùng Phương há 2.5.3.3. Số đánh giá bi t trước trong tậ kiểm tra 1 2 5 Top-N-ItemBased 0.7877 0.77215 0.7412 KNN-UserBased 0.8046 0.7978 0.7804 ItemBased-Graph 0.7503 0.7576 0.5788 UserBased-Graph 0.6549 0.6428 0.6596 Với bộ dữ liệu vật giá 1114 người dùng Bảng 2-4. Độ đo MAE với các đánh giá biết trước của tập dữ liệu vật giá 1114 người dùng Phương há Số đánh giá bi t trước trong tậ kiểm tra 1 2 5 Top-N-ItemBased 0.7804 0.7638 0.7327 KNN-UserBased 0.8042 0.798 0.7722 ItemBased-Graph 0.7444 0.7032 0.3248 UserBased-Graph 0.6593 0.6574 0.4891 K t uả kiểm nghiệm cho thấy, các hương há đề xuất d a tr n đồ thị cho lại sai số trung bình tuyệt đối l i MAE nh hơn với hương hương há lọc ItemBased và UserBased d a tr n độ tương uan Pearson. Điều đó có thể khẳng định, hương há d đoán d a tr n mô hình đồ thị có thể tích hợ được nhiều thông tin gián ti gi a người 16 d ng và sản hẩm vào uá trình huấn luyện. Lý do khi n hai hương há đề xuất cho lại k t uả tốt hơn là hương há đã d đoán d a vào tậ láng giềng của cộng đồng người d ng có chung sở thích. Nói cách khác hương há đề xuất xác định được tậ láng giềng chính xác hơn so với các hương há hiện tại. 2.6. Kết luận chương 2 Nội dung chương 2 đã trình bày k t uả nghi n c u của luận văn về hát triển hương há lọc cộng tác d a vào bộ nhớ tr n mô hình đồ thị. Phương há biểu diễn đồ thị cho hé tận dụng được mối uan hệ gián ti gi a các đối tượng người d ng và sản hẩm vào uá trình d đoán và tư vấn. Phương há d đoán được đưa về bài toán tìm ki m tr n đồ thị cho hé ta sử dụng biểu diễn đồ thị bằng ma trận thưa để giảm thiểu không gian biểu diễn d liệu, đồng thời có thể sử dụng các thuật toán hiệu uả tr n đồ thị. Phương há d đoán tr n tất cả các đánh giá, cho hé ta giảm thiểu các l i có thể xảy ra trong uá trình d đoán và hân bổ thông tin (Một sản hẩm người d ng “không thích” có thể có mặt trong danh sách các sản hẩm cần tư vấn. Một sản hẩm người d ng “thích” có thể có mặt trong danh sách các sản hẩm cần loại b . M c độ tương t gi a các cặ người d ng được tính toán d a vào trọng số các đường đi từ đỉnh người d ng đ n đỉnh người d ng, m c độ tương t gi a các cặ sản hẩm được tính toán d a vào trọng số các đường đi từ đỉnh sản hẩm đ n đ n đỉnh sản hẩm. Đây chính là điểm khác biệt uan trọng của mô hình đề xuất so với các mô hình trước đây. K t uả kiểm nghiệm tr n bộ d liệu MovieLens, vật giá cho thấy, mô hình đề xuất cho lại k t uả tốt hơn các hương há lọc cộng tác d a tr n độ tương uan thuần túy. 17 CHƯƠNG 3: XÂY DỰNG HỆ TƯ VẤN SẢN PHẨM ĐIỆN THOẠI DI ĐỘNG Mục ti u chính của chương này trình bày thi t k và xây d ng hệ tư vấn sản hẩm điện thoại di động sử dụng hương há lọc cộng tác d a tr n mô hình đồ thị được đề xuất trong chương 2. Hệ thống cho hé người d ng xem sản hẩm, đánh giá sản hẩm, tìm ki m sản hẩm, tư vấn sản hẩm đ n người d ng. Song song đó là xây d ng thành công một ng dụng tr n điện thoại thông minh chạy hệ điều hành Windows Phone sử dụng dịch vụ cung cấ bởi hệ tư vấn đã xây d ng. 3.1. Yêu cầu hoạt động của hệ thống Người d ng ng dụng tr n điện thoại thông minh chạy hệ điều hành Windows Phone đăng nhậ vào hệ thống bằng tài khoản của mình, ti n hành đánh giá nh ng sản hẩm. Hệ thống sẽ ghi nhận nh ng đánh giá đó để làm cơ sở khuy n nghị. Hệ thống sẽ d a vào nh ng đánh giá đó của người d ng để gợi ý cho người d ng nh ng sản hẩm h hợ , trả về điện thoại của người d ng. 3.2. Mô hình tổng quát của hệ thống Ki n trúc của hệ thống mô tả trong Hình 3.1 được thi t k gồm 2 hần chính như sau: 1. Phần 1: ng dụng máy khách được vi t tr n nền tảng hệ điều hành Windows Phone h trợ người sử dụng các ch c năng như: xem / tìm ki m thông tin các sản hẩm điện thoại di động, xem gợi ý về các sản hẩm di động h hợ với người d ng, đánh giá m c độ thích của người d ng với sản hẩm được xem. 2. Phần 2: ng dụng máy chủ bao gồm: - Dịch vụ web hụ trách việc truyền nhận thông tin gi a máy khách và máy chủ. - Hệ thống khuy n nghị người d ng. Hệ thống này có 2 ch c năng : ch c năng huấn luyện và ch c năng tư vấn.  Ch c năng huấn luyện (th c hiện học offline hía Back-end : có nhiệm vụ xây d ng mô hình d a tr n d liệu đánh giá sản hẩm của người d ng được xây d ng theo mô hình đồ thị đã trình bày trong chương 2.  Ch c năng tư vấn (th c hiện online được cung cấ thông ua dịch vụ webservice : Khi có y u cầu tư vấn từ một người d ng được gửi từ ng dụng máy khách thông ua webservice tới hệ thống tư vấn, ch c năng sẽ sử dụng 18 d liệu được xây d ng từ ha học offline để lấy về To -N sản hẩm có đánh giá d đoán cao nhất để tư vấn cho khách hàng. 3.3. Phân tích thiết kế hệ thống 3.3.1. Phân tích hệ thống 3.3.1.1. Xây dựng biểu đồ use case và scenario của các use case 3.3.1.2. Xây dựng biểu đồ lớp phân tích 3.3.2. Thiết kế hệ thống 3.3.2.1. Xây dựng biểu đồ tuần tự 3.3.2.2. Xây dựng biểu đồ lớp thiết kế 3.4. Mô hình dữ liệu hệ thống 3.4.1. Mô tả dữ liệu Nguồn thông tin về các sản hẩm điện thoại tr n thị trường được trích xuất từ trang web vật giá [28], gồm : 7682 người d ng, 3000 sản hẩm với 16110 đánh giá, các m c đánh giá được thi t lậ từ 1 đ n 5. 3.4.2. Mô hình dữ liệu hệ thống Hình 3-1. Mô hình dữ liệu hệ thống tư vấn sản phẩm điện thoại 3.5. Kết luận chương 3 Nội dung chương 3 đã trình bày thi t k và xây d ng hệ tư vấn sản hẩm điện thoại di động sử dụng hương há lọc cộng tác d a tr n mô hình đồ thị được đề xuất trong chương 2. Song song đó là xây d ng thành công một ng dụng tr n điện thoại thông minh chạy hệ điều hành Windows Phone sử dụng dịch vụ cung cấ bởi hệ tư vấn đã xây d ng.
- Xem thêm -

Tài liệu liên quan