ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ
TRƢƠNG VĨNH LONG MÔ HÌNH HÓA NGƢỜI DÙNG VÀ ỨNG DỤNG BỘ LỌC
CỘNG TÁC TRONG HỆ THỐNG GỢI Ý TIN TỨC LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN
Hà Nội - 2013
Hà Nội - 2013
1
Mục lục
Danh mục hình vẽ 3
Danh mục bảng 4
TÓM TẮT NỘI DUNG 5
Chƣơng 1: Đặt vấn đề 7
1.1. Bài toán xây dựng bộ lọc cho hệ thống gợi ý tin tức 7
1.1.1. Mục tiêu 7
1.1.2. Nội dung, phương pháp nghiên cứu 7
1.1.3. Kết quả đã đạt được 7
1.2. Giới thiệu một số hệ thống tổng hợp, gợi ý tin tức 8
1.2.1. News Dude 8
1.2.2. Trang web baomoi.com 9
Chƣơng 2: Các vấn đề nghiên cứu liên quan 11
2.1. Mô hình hóa người dùng 11
2.1.1. Các khái niệm 11
2.1.2. Vai trò của mô hình người dùng trong hệ thống thích nghi 12
2.1.3. Một số kỹ thuật mô hình hóa người dùng 13
2.1.4. So sánh các kỹ thuật mô hình hóa người dùng 15
Danh mục hình vẽ
Hình 1.1: Giao diện hệ thống News Dude[2] 8
Hình 1.2: Giao diện trang web baomoi.com 10
Hình 2.1: Vai trò của mô hình ngƣời dùng trong quá trình thích nghi[3] 12
Hình 2.2: Kiến trúc hệ thống xử lý đa tiêu chuẩn[21] 25
Hình 2.3 – Phƣơng pháp bất đồng – đồng nhất[21] 26
Hình 3.1: Giao diện minh họa hệ thống xenoNews[23] 30
Hình 3.2: Kiến trúc 3 tầng của hệ thống xenoNews[23] 31
Hình 3.3: Bộ lọc cộng tác trong tổng thể hệ thống xenoNews 34
Hình 3.4: Các bộ phận trong bộ lọc cộng tác 35
4
Danh mục bảng
Bảng 2.1: So sánh ƣu điểm và nhƣợc điểm của các kỹ thuật mô hình hóa 15
Bảng 2.2: So sánh các kỹ thuật mô hình hóa qua các đặc tính 17
Bảng 3.1: Bảng mô tả các thể loại tin tức trong hệ thống xenoNews 36
Bảng 4.1: Số lƣợng tin truy cập trong quá trình thử nghiệm 40
Bảng 4.2: Các độ đo theo thể loại 41 5
TÓM TẮT NỘI DUNG
Ngày nay với sự phát triển của Internet và các hệ thống cung cấp tin tức điện tử, độc
giả không chỉ có cơ hội tiếp cận nhiều luồng thông tin hơn mà còn tiến tới cập nhật thông
tin trong thời gian sớm nhất. Tuy nhiên sự gia tăng nhanh chóng về số lượng kèm theo
trạng thái tự nhiên không có cấu trúc của nội dung tin tức đã vượt quá giới hạn xử lý của
con người. Người dùng có thể rơi vào hoàn cảnh vừa thiếu các thông tin thực sự hấp dẫn,
Phần kết luận: tóm lược nội dung đã trình bày trong luận văn và hướng nghiên cứu
tiếp theo để cải tiến bộ lọc cộng tác.
7
Chƣơng 1: Đặt vấn đề
1.1. Bài toán xây dựng bộ lọc cho hệ thống gợi ý tin tức
Bộ lọc trong hệ thống gợi ý đóng vai trò trung tâm, giúp hệ thống xử lý dữ liệu và
đưa ra gợi ý thích hợp cho người dùng. Các loại bộ lọc cơ bản bao gồm: bộ lọc theo nội
dung, bộ lọc cộng tác và bộ lọc kết hợp hai loại trên. Luận văn chủ yếu đề cập tới bộ lọc
cộng tác trong hệ thống gợi ý tin tức.
Theo định nghĩa của A.Das, M.Datar và A.Garg [1], bộ lọc cộng tác là kỹ thuật có
nhiệm vụ học tập, tìm hiểu những sở thích của người dùng và tạo gợi ý dựa trên dữ liệu
người dùng và dữ liệu chung của tập người dùng.
Có thể hiểu bộ lọc cộng tác làm nhiệm vụ thu thập thói quen người dùng, tìm ra
những người dùng khác mang tính tương đồng về sở thích, chọn những nội dung họ quan
tâm đưa tới cho người dùng theo hướng gợi ý “nhiều người giống bạn quan tâm tới vấn đề
này, liệu bạn có quan tâm hay không”.
1.1.1. Mục tiêu
Luận văn tiến hành tìm hiểu lý thuyết mô hình hóa người dùng và công thức, ứng
dụng của bộ lọc cộng tác người dùng cho các hệ thống gợi ý tin tức dựa trên những
nghiên cứu đã có. Mục tiêu hướng tới là tổng hợp kiến thức về các hệ thống gợi ý tin tức
đã sử dụng mô hình cộng tác, dựa vào đó cài đặt và đánh giá một bộ lọc cộng tác người
dùng cho hệ thống chọn lọc gợi ý tin tức.
1.1.2. Nội dung, phƣơng pháp nghiên cứu
Để hoàn thành yêu cầu đề ra, trước hết tiến hành tìm hiểu, so sánh mô hình, phương
thức hoạt động trong các hệ thống gợi ý nói chung và hệ thống gợi ý tin tức nói riêng, tập
trung vào các bộ lọc cộng tác sử dụng phân tích lịch sử truy cập của tập người dùng.
Bước thứ hai là xây dựng một công thức cho bộ lọc cộng tác dựa trên cơ sở phân
tích lịch sử đọc tin của người dùng.
Bước ba tập trung cài đặt bộ lọc cộng tác đã xây dựng vào trong một hệ thống gợi ý
cần có nhiều lựa chọn phản hồi để gán các mức điểm số khác nhau. Mô hình của News
Dude kết hợp giữa mô hình ngắn hạn biểu diễn sở thích trong thời gian gần và mô hình
dài hạn biểu diễn sở thích chung của người dùng. Các tin tức được mô tả dưới dạng vector
ngữ nghĩa tf-idf kết hợp tính độ tương đồng theo độ đo Cosine.
1.2.2. Trang web baomoi.com
Baomoi.com là một trang web tổng hợp tin tức có nội dung tiếng Việt. Nội dung và
nguồn gốc các bản tin trên hệ thống Baomoi.com rất phong phú. Ngoài chức năng duyệt
tin như thông thường, Baomoi cũng cho phép người dùng đăng ký tài khoản để khai báo
các tiêu chí lọc tin cho riêng mình. Bộ lọc bao gồm phần chọn chuyên mục, từ khóa quan
tâm, chọn nguồn tin.
Các bài báo được tổng hợp về sẽ được gán với một số từ khóa chính (tag) dựa vào
nội dung. Khi người dùng yêu cầu tạo bộ lọc tin, hệ thống so sánh các tiêu chí của người
dùng với các thông số chuyên mục, nguồn gốc, đặc biệt là từ khoá của các bản tin để
quyết định đưa ra gợi ý. Vì vậy muốn tìm được tin tức theo ý muốn người dùng phải hoàn
thiện bộ lọc với các cụm từ khóa mang tính chính xác, khái quát.
Có một hạn chế về giao diện là khi người dùng chọn đọc một tin trong danh sách thì
tự động chuyển sang đường dẫn gốc, người dùng mất thêm thao tác với trình duyệt để trở
về danh sách trước đó.
10 Hình 1.2: Giao diện trang web baomoi.com
11
Chƣơng 2: Các vấn đề nghiên cứu liên quan
Trong chương 2 luận văn trình bày các vấn đề liên quan đã tìm hiểu, gồm có lý
thuyết chung về mô hình hóa người dùng, hệ thống gợi ý, phân loại hệ thống gợi ý. Sau
đó với hướng tập trung vào mô hình gợi ý dựa vào bộ lọc cộng tác, luận văn mô tả một số
2.1.2. Vai trò của mô hình ngƣời dùng trong hệ thống thích nghi
Mục đích cơ bản của mô hình người dùng gồm có
- Hỗ trợ người dùng trong quá trình học tập về một chủ đề
- Đưa thông tin đã điều chỉnh tới người dùng
- Thay đổi giao diện
- Giúp người dùng tìm kiếm thông tin
- Đưa phản hồi về kiến thức của người dùng
- Hỗ trợ công việc có tính cộng tác
- Hỗ trợ quá trình sử dụng hệ thống
Tất cả các mục đích đều xoay quanh người dùng nhưng chưa làm rõ bằng cách nào
mô hình người dùng tác động tới hệ thống. Có 3 cách chính để mô hình người dùng hỗ trợ
quá trình thích nghi hệ thống, giúp thực hiện các mục tiêu đã nêu.
Hình 2.1: Vai trò của mô hình người dùng trong quá trình thích nghi[3]
Những hành động thể hiện người dùng (interpret user actions) bao gồm toàn bộ
những hành động có thể thực hiện tại giao diện như dùng chuột điều khiển, gõ bàn phím,
đưa dữ liệu đầu vào. Mô hình người dùng hỗ trợ hệ thống lưu trữ và giải thích các hành
động đó. Ví dụ nếu dữ liệu đầu vào có tính nhập nhằng thì mô hình người dùng phải làm
cho rõ ràng hơn, hoặc phải loại bỏ những hành động không chính xác.
13
Những hành động của máy (machine actions) là những hành động được khởi tạo bởi
hệ thống. Mô hình người dùng có thể được tận dụng để điều khiển và sửa đổi những hành
động này theo sở thích của người dùng. Cách thức này bao gồm việc biến đổi hành vi của
hệ thống và theo dõi người dùng hoặc sự thích ứng hóa nội dung song song với trình diễn
chúng. Ví dụ hệ thống gợi ý tin tức có thể đưa ra những tin bài liên quan tới công nghệ
cho những người dùng thuộc lĩnh vực công nghệ thông tin , hoặc gợi ý tin về các khóa
học, học bổng cho người dùng là sinh viên.
Ứng dụng thứ ba của mô hình người dùng trong quá trình thích nghi nằm trong lòng
hệ thống. Mô hình người dùng hỗ trợ hệ thống trong các hành động nội tại (internal
thức hoạt hóa làm nhiệm vụ tính toán giá trị hoặc năng lượng của chúng. Dữ liệu
đầu vào sẽ kích hoạt mạng, tới lượt mình mạng sẽ kích hoạt các nút. Quá trình
tính toán thông báo kết quả trong toàn mạng, trả về tri thức theo yêu cầu. Các nút
tự động cập nhật mỗi khi có dữ liệu mới, vì thế mạng chứa ánh xạ tức thời của tri
thức trong hệ thống. Mạng neural có nhiều biến thể: dạng tĩnh hoặc dạng động,
mạng đơn chiều và mạng hai chiều, mạng đơn nguyên và mạng đa nguyên –
nhiều mạng tập hợp lại để cùng thực hiện mục đích chung. Trong mạng lưới
động, các nút không cố định mà có thể được xóa hoặc tạo mới, hỗ trợ những hình
thái tri thức linh hoạt, thông minh hơn.
- Khai phá văn bản (Text mining): Khai phá văn bản là một nhánh của quá trình
khai phá dữ liệu nhưng các thông tin đều dưới dạng văn bản hoặc mô tả không có
cấu trúc. Mục đích chính sau quá trình khai phá văn bản là trích xuất thông tin có
ý nghĩa từ văn bản, thường ở dạng từ khóa. Giải thuật phức tạp hơn cố gắng trích
xuất những câu hoàn chỉnh có tính quan trọng, chia nhỏ, tái cấu trúc văn bản.
Một trong những thách thức lớn nhất của khai phá văn bản là giao tiếp với những
sắc thái và tính bất quy tắc của tập từ vựng, ví dụ như từ đồng âm khác nghĩa.
Khai phá văn bản cũng được dùng khi thông tin trong lĩnh vực hiện tại không có
cấu trúc, cấu trúc quá dài. Các lĩnh vực mà khai phá văn bản cho nhiều kết quả
đó là phân tích kết quả nghiên cứu, dịch vụ tin tức, phân tích nội dung web.
- Mạng Bayes (Bayesian network): Kỹ thuật này có hiệu năng tốt và tính độc lập
cao. Mạng Bayes chứa những nút biểu diễn khả năng một sự kiện hoặc đặc tính
người dùng có giá trị true. Giống như trong mạng neural, các nút đều có khả
năng tự cập nhật, thay đổi ở nút cấp cao chuyển tới các nút con mở ra thông tin
mới. Xa hơn nữa, chúng có thể chứa thông tin và hàm tiện ích thay đổi theo thời
gian.
- Khai phá dữ liệu (Data mining)
+Phân lớp (Classification): Loại kỹ thuật này thực hiện phân chia đối tượng mới
về các lớp con dựa vào các đối tượng đã phân lớp trước đó. Nó phân tích các
thuộc tính, tìm ra những thuộc tính góp phần tạo ra tri thức đi kèm trong quá
trình phân lớp. Thường thì ngôn ngữ thể hiện cho bộ phân lớp là cây quyết định
- Dễ dàng sử dụng và tìm
hiểu
- Hiệu quả cao
- Áp dụng trong nhiều lĩnh
vực
- Không đáp ứng đủ yêu
cầu biểu diễn tri thức
16
- Dễ dàng sửa đổi
Cây quyết định
- Rất dễ đọc hiểu
- Hiệu suất tốt trong các
trường hợp cây nhị phân
- Cần kiến thức của các
chuyên gia
- Khó duy trì và sửa đổi
Mạng neural
- Hiệu suất tốt
- Có thể tự phát triển qua thời
gian
- Có thể tốn nhiều thời gian
để đưa về kết quả tối ưu
Phân lớp
- Có thể trả về cây quyết định
trực quan
- Có thể tham gia quá trình ra
quyết định
- Cần lượng lớn dữ liệu
luyện tập để đạt hiệu quả
Mạng Bayes
- Hiệu suất cao
- Biểu diễn cả lập luận khởi
tạo và dữ liệu sinh ra sau
- Có thể phát triển độc lập
- Cần kiến thức chuyên gia
cho việc khởi tạo giả định
Tiếp theo cần so sánh các kỹ thuật mô hình hóa dựa trên một vài đặc điểm hữu ích
và quan trọng nhất: nhanh chóng đạt ngưỡng tối ưu, dễ dàng xây dựng, hiệu suất độc lập
với hệ thống sử dụng, kiểm soát kết quả.
- Nhanh chóng đạt ngưỡng tối ưu (Rapid Optimum Threshold): Điều kiện kiểm tra nếu độ
chính xác của một kỹ thuật so với thực tế và biểu diễn tương ứng theo lĩnh vực đạt mức
tối ưu với tốc độ nhanh chóng hay không. Ví dụ những kỹ thuật yêu cầu tri thức khởi tạo
thì ngay lập tức đạt được mức tối ưu vì những tri thức khởi tạo đó được coi như đã có giá
trị.
- Dễ dàng xây dựng (Easy-building): Bao gồm đánh giá không chỉ về khó khăn trong quá
trình phát triển mà còn ở giai đoạn hoàn thiện hoặc sự buồn tẻ của công việc thực hiện.
- Hiệu suất độc lập với hệ thống sử dụng (Performance independent of system use): Đánh
giá xem hiệu suất tổng thể của kỹ thuật có sự sai khác tùy theo kích thước cơ sở dữ liệu,
hệ thống sử dụng hay không. Đặc tính này liên quan tới các thay đổi phức tạp đi kèm với
thay đổi của hệ thống. Ví dụ mô hình tuyến tính thường làm việc với giá trị trung bình,
tổng số và các phép toán khác, được tối ưu bên trong hệ quản trị cơ sở dữ liệu do đó
không phụ thuộc quá nhiều vào kích thước cơ sở dữ liệu. Trong khi đó tốc độ hoạt động
của kỹ thuật phân cụm chịu ảnh hưởng lớn từ số lượng đối tượng và số lượng thuộc tính.
- Kiểm soát kết quả (Control over results): Khả năng kỹ thuật được điều khiển và tùy
chỉnh bởi người sử dụng.
Bảng 2.2: So sánh các kỹ thuật mô hình hóa qua các đặc tính
Kỹ thuật
Nhanh chóng
Không
Không
Phân cụm
Không
Có
Không
Không
Luật kết hợp
Không
Có
Không
Không
Khai phá văn
bản
Không
Có
Không
Không
Mạng Bayes
Có
Không
Có
Có
2.2. Phân loại các hệ thống gợi ý tin tức
Các hệ thống gợi ý tin tức thường được chia thành 3 loại chính: hệ thống gợi ý dựa
vào nội dung (content-based), hệ thống gợi ý dựa vào cộng tác (collaborative), hệ thống
kết hợp (hybrid).
2.2.1. Hệ thống gợi ý dựa vào nội dung
Hệ thống gợi ý dựa vào nội dung hướng tới việc trả về cho người dùng những kết
trong một văn bản thì chỉ số TF của nó sẽ đạt giá trị cao. Tuy nhiên nếu cùng từ khóa đó
lại xuất hiện ở nhiều văn bản khác thì trên thực tế nó sẽ không mang nhiều ý nghĩa và độ
quan trọng trong văn bản giảm đi. Ví dụ nếu một văn bản xuất hiện nhiều lần từ “điện
thoại” thì có thể hiểu văn bản đó liên quan tới lĩnh vực viễn thông. Nhưng nếu đổi lại một
văn bản có nhiều từ “các bạn” thì không thể cho đây là một từ mang nhiều ý nghĩa đối với
văn bản đó.
Các từ khóa trong văn bản có mật độ xuất hiện không đồng đều. Có từ khoá xuất
hiện rất thường xuyên trong khi nhiều từ khoá chỉ xuất hiện một vài lần. Để khắc phục
điều này, nghịch đảo tần suất văn bản (IDF – Inverse Document Frequency) và tần số
logarit (tương tự tần số từ khóa) được đề xuất theo công thức
( ) log( )
i
i
N
IDF t
df
(2.2)
Trong công thức 2.2, N là tổng số tài liệu, df
i
là số lượng tài liệu có xuất hiện từ
khóa t
i
. Nếu t
i
xuất hiện trong càng ít văn bản thì có nghĩa khi nó xuất hiện trong văn bản
d trọng số của nó đối với d càng lớn, hay nói cách khác t
i
góp phần quan trọng trong việc
phân biệt d với các văn bản khác. Nghịch đảo tần số IDF được áp dụng nhiều hơn tần số
11
w
os( ( ), )
w*
n
ii
i
nn
ii
ii
x
c profile u d
x
(2.4)
Ngoài giải thuật dựa vào phương pháp thu thập thông tin truyền thống, còn có những
kỹ thuật khác đem lại hiệu quả cao như M. Pazzani sử dụng phân lớp Bayes để ước tính
xác suất người dùng quan tâm tới một đối tượng [7], hoặc sử dụng phân cụm, cây quyết
định, mạng noron nhân tạo.
Nhìn chung, các hệ thống gợi ý dựa trên nội dung còn có một số điểm hạn chế.
- Gợi ý cho người dùng mới: đây có thể coi là vấn đề chung của các hệ thống gợi ý.
Khi một người dùng tạo tài khoản mới và chưa tương tác nhiều với hệ thống thì
lượng dữ liệu làm đầu vào gợi ý chưa có đủ dẫn tới kết quả gợi ý không đạt độ
chính xác cao.
- Hạn chế trong việc phân tích đối tượng: Một số loại đối tượng có định dạng đa
phương tiện khiến cho hệ thống khó xác định nội dung chính xác một cách tự
cho bởi công thức
,
( , )*w(u , )
i
u s j i j
ji
r I u s u
(2.5)
Phương thức gợi ý dựa vào bộ nhớ phát triển nhanh chóng nhờ vào tính đơn giản và
quá trình huấn luyện tương đối dễ hiểu. Tuy vậy một trong số những trở ngại chính cho
phương thức này là khó có khả năng mở rộng [10].
Đối lập với thuật toán dự báo dựa vào bộ nhớ, thuật toán dự báo dựa vào mô hình cố
gắng tạo một mô hình người dùng dựa trên đánh giá của người dùng trong quá khứ và
dùng nó để dự đoán đánh giá của người dùng đối với các đối tượng chưa truy cập. Trong
báo cáo của J.Breese và đồng sự [11] có đề cập tới một ví dụ sử dụng hai mô hình xác
suất: mô hình phân cụm và mô hình Bayesian. Tuy nhiên thuật toán này lại chỉ chia người
dùng vào một nhóm duy nhất trong khi sở thích của họ lại có thể theo nhiều thể loại khác
nhau. Nhiều thuật toán dựa theo mô hình mới được nghiên cứu đã nắm bắt mối quan tâm
đa dạng của người dùng bằng cách phân họ vào nhiều cụm hoặc lớp khác nhau. Các
phương pháp dựa trên mô hình gồm có: chỉ số ngữ nghĩa ẩn (latent semantic indexing –
LSI) [12], phân cụm Bayesian [11], chỉ số ngữ nghĩa ẩn theo xác suất (probabilistic latent
semantic indexing – PLSI) [13], mô hình hệ số bội (multiple multiplicative Factor Model)
[14], tiến trình Markov (Markov Decision process) [15], phân phối Dirichlet (Latent
Dirichlet Allocation) [16].
Nhược điểm của các hệ thống gợi ý dựa vào cộng tác:
- Vấn đề người dùng mới: hệ thống dựa vào cộng tác cũng gặp phải vấn đề giống
như đối với hệ thống gợi ý dựa vào nội dung trong trường hợp người dùng mới
Các đặc trưng này góp phần trong công thức tính độ tương đồng giữa người
dùng, do đó tăng hiệu quả hệ thống gợi ý. Bổ sung này giúp cho hệ thống không
chỉ gợi ý tới người dùng những đối tượng được người dùng khác quan tâm mà
còn gợi ý cả những đối tượng phù hợp với đặc trưng của chính người dùng đó.
- Xây dựng mô hình thống nhất: hướng phát triển này cũng thu hút nhiều nghiên cứu
khác nhau. Một ví dụ là hệ thống gợi ý thống nhất của A.Gunawardara và
C.Meek sử dụng máy Boltzmann (Boltzmann machines) [19].
23
2.3. Một số hệ thống gợi ý tin tức theo hƣớng cộng tác
2.3.1. Mô hình cộng tác dựa trên chuỗi sự kiện
F.Garcin và các cộng sự [20] đề xuất một bộ lọc cộng tác dựa trên việc theo dõi
thạng thái duyệt tin của người dùng. Mô hình đưa ra gồm 2 tham số: tham số quá khứ p
và tham số tương lai f. Tham số quá khứ p chỉ ra lượng thông tin trong lịch sử dùng trong
việc tạo gợi ý và tham số tương lại f là số bước dự đoán trong tương lai. Ví dụ nếu p=3 và
f=2, mô hình hệ thống là mô hình 3 chiều và tìm kiếm khả năng dự đoán hành động người
dùng trong 1 hoặc 2 bước tiếp theo.
Ký hiệu N là tập hợp bản tin, và S là tập hợp các trạng thái. Một trạng thái s
S là
một chuỗi gồm p bản tin, biểu diễn s = (n
1
, n
2
, …, n
p
) với ý nghĩa n
1
→n
2
4
→n
5
).
Bộ lọc cộng tác trên cơ sở bản tin định nghĩa như sau. Ký hiệu TP(s
i
,s
j
) là khả năng
xảy ra chuyển đổi từ trạng thái s
i
sang trạng thái s
j
, biểu diễn bằng tỉ lệ số lượng trường
hợp chuyển đổi s
i
sang s
j
xảy ra trên tổng số lần chuyển đổi từ s
i
sang một trạng thái trên
hệ thống.
( , )
( , )
( , )
ij
ij
i
sS
count s s
(2.8)
Do đó, khả năng duyệt tới bản tin n từ trạng thái s sau nhiều nhất f bước chuyển
trạng thái là
Copyright: Tài liệu đại học ©