Tóm tắt Luận văn Thạc sĩ Hệ thống thông tin: Ứng dụng các mô hình chủ đề ẩn vào mô hình phân hạng lại dòng cập nhật trên mạng xã hội Twitter

pdf
Số trang Tóm tắt Luận văn Thạc sĩ Hệ thống thông tin: Ứng dụng các mô hình chủ đề ẩn vào mô hình phân hạng lại dòng cập nhật trên mạng xã hội Twitter 24 Cỡ tệp Tóm tắt Luận văn Thạc sĩ Hệ thống thông tin: Ứng dụng các mô hình chủ đề ẩn vào mô hình phân hạng lại dòng cập nhật trên mạng xã hội Twitter 975 KB Lượt tải Tóm tắt Luận văn Thạc sĩ Hệ thống thông tin: Ứng dụng các mô hình chủ đề ẩn vào mô hình phân hạng lại dòng cập nhật trên mạng xã hội Twitter 0 Lượt đọc Tóm tắt Luận văn Thạc sĩ Hệ thống thông tin: Ứng dụng các mô hình chủ đề ẩn vào mô hình phân hạng lại dòng cập nhật trên mạng xã hội Twitter 0
Đánh giá Tóm tắt Luận văn Thạc sĩ Hệ thống thông tin: Ứng dụng các mô hình chủ đề ẩn vào mô hình phân hạng lại dòng cập nhật trên mạng xã hội Twitter
4.2 ( 5 lượt)
Nhấn vào bên dưới để tải tài liệu
Đang xem trước 10 trên tổng 24 trang, để tải xuống xem đầy đủ hãy nhấn vào bên trên
Chủ đề liên quan

Nội dung

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THỊ TƯƠI ỨNG DỤNG CÁC MÔ HÌNH CHỦ ĐỀ ẨN VÀO MÔ HÌNH PHÂN HẠNG LẠI DÒNG CẬP NHẬT TRÊN MẠNG XÃ HỘI TWITTER Ngành: Hệ thống thông tin Chuyên ngành: Hệ thống thông tin Mã số: 60480104 TÓM TẮT LUẬN VĂN THẠC SĨ HỆ THỐNG THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. HÀ QUANG THỤY Hà Nội - 2016 MỞ ĐẦU Ngày nay, mạng xã hội phát triển mạnh mẽ mang những nhận xét, đánh giá, những thông tin phản ánh xã hội thực tới mỗi người, và ngày càng đi sâu vào cuộc sống của mỗi chúng ta. Chúng cung cấp nhiều thông tin cập nhật có tính thời gian thực có được từ kết nối trực tuyến của mọi người. Dòng các tin mới đến trang cá nhân của mỗi người dùng được gọi là dòng cập nhật của người dùng đó. Mặc dù dòng cập nhật đưa đến những thông tin mới, nhưng tồn tại một hạn chế là không ít người dùng đã phải dành khá nhiều thời gian với dòng cập nhật, vì có không ít tin mới trong dòng cập nhật mang lại thông tin không cần thiết cho họ. Nhiều người dùng rơi vào tình cảnh bị ngập trong dòng cập nhật mà không thể xử lý chúng một cách đầy đủ. Với mục đích giải quyết vấn đề này, giải pháp được quan tâm là sắp xếp các tin trong dòng cập nhật sao cho hợp lý nhất với mỗi người dùng. Liangjie Hong và cộng sự (2012) nêu bật vấn đề xếp hạng dòng cập nhật (gọi tắt là Xếp hạng dòng). Bài toán xếp hạng dòng trong mạng xã hội được đặt ra để giải quyết vấn đề cập nhật tin cho mỗi người dùng, đưa ra danh sách các tin trong dòng cập nhật theo một thứ tự (theo "hạng") quan tâm của người dùng, như là một hình thức tư vấn cho người dùng đó. Với bài toán này, việc xếp hạng các tin trong dòng cập nhật cần căn cứ vào lịch sử hành vi của người dùng để tìm ra mối quan hệ giữa cá nhân người dùng đó với đối tượng xếp hạng, thậm chí cả quan hệ với người dùng khác. Tương tự như các mạng xã hội khác, người dùng trên Twitter cũng đối mặt với lượng lớn các dòng cập nhật liên tục từ những người bạn của mình. Trong phạm vi luận văn, chúng tôi tập trung vào bài toán xếp hạng dòng trên mạng xã hội Twitter, và tiếp tục đề cập tới mô hình hệ thống xếp hạng dòng của mình [1]. Phương pháp phương pháp học tính hạng CRR [2] (Combined Regression and Ranking) được sử dụng. Mô hình xếp hạng dòng sử dụng thuật toán học tính hạng – thuật toán dựa trên nền tảng học máy, nên việc xây dựng các tập dữ liệu huấn luyện là cần thiết. Chúng tôi đi tìm các yếu tố đặc trưng của tweet. Như đã phát biểu trong [1], yếu tố nội dung của tweet - một yếu tố cơ sở tất yếu cho quá trình học, được tìm ra dựa vào phương pháp phân cụm không giám sát, đó là mô hình chủ đề ẩn [3, 4]. Yếu tố nội dung được biểu diễn dưới 1 hình thức một tập các phân phối tweet theo chủ đề. Trong mô hình xếp hạng dòng, mô hình chủ đề ẩn LDA được sử dụng. Ngoài yếu tố nội dung, độ ảnh hưởng người dùng được nhận diện là một yếu tố quan trọng. Các cập nhật của người dùng có độ ảnh hưởng lớn thường được nhiều người theo dõi hơn [5, 6]. Dựa trên quan điểm này, chúng tôi nhận thấy các dòng cập nhật từ những người bạn có ảnh hưởng tới người dùng đang xét nên được tư vấn cho người dùng đó. Hay nói cách khác, độ ảnh hưởng người dùng (user influence) nên được tham gia vào quá trình học tính hạng. Do vậy, chúng tôi quyết định cải thiện mô hình tính hạng [1] với sự tham gia của đặc trưng độ ảnh hưởng người dùng. Trong [7], Fredik và cộng sự đã thực hiện tìm các người dùng có độ ảnh hưởng lớn trên mạng xã hội dựa vào khai phá luật kết hợp. Học theo phương pháp này, chúng tôi công thức hóa độ ảnh hưởng của người dùng qua số lượng luật kết hợp tìm được trên tập các tweet. Thuật toán khai phá luật kết hợp được sử dụng là thuật toán Apriori [8]. Khái quát lại, luận văn đề xuất phương pháp cải thiện mô hình tính hạng mà chúng tôi đã đề xuất trong [1] thành mô hình với cốt lõi là phương pháp học tính hạng, xây dựng đặc trưng nội dung dựa trên mô hình LDA, và xây dựng đặc trưng người dùng dựa trên luật kết hợp. Nội dung của luận văn chia thành các chương như sau: Chương 1: Luận văn trình bày về các dòng cập nhật của mỗi người dùng trên mạng xã hội Twitter và phát biểu bài toán xếp hạng các dòng cập nhật đó. Đồng thời nêu lên hướng giải quyết và ý nghĩa của bài toán này. Chương 2: Luận văn trình bày về các phương pháp mà mô hình đề xuất sẽ sử dụng: phương pháp học tính hạng, mô hình chủ đề ẩn và luật kết hợp. Chương 3: Luận văn trình bày mô hình xếp hạng dòng và cách hoạt động của mô hình đó. Chương 4: Luận văn trình bày thực nghiệm cho việc áp dụng mô hình xếp hạng trong chương 3 vào việc tính hạng tập các tweet của người dùng trên Twitter. 2 DÒNG CẬP NHẬT TRÊN MẠNG XÃ HỘI TWITTER VÀ BÀI TOÁN XẾP HẠNG DÒNG Chương 1. Mạng xã hội Twitter và dòng cập nhật trên Twitter Twitter là dịch vụ mạng xã hội ra đời năm 2006, một trang microblog được phát triển bởi Twitter Inc, cung cấp một dịch vụ mạng miễn phí cho phép người dùng sử dụng gửi và nhận các tin nhắn (tweet), và đã trở thành một hiện tượng phổ biến toàn cầu. Tính đến tháng 12 năm 2012, số lượng thành viên của Twitter lên tới gần 500 triệu người dùng [9]. Dòng cập nhật trên mạng xã hội Twitter được hiểu là dòng cập nhật của mỗi người dùng. Người dùng A following B, thì A được gọi là follower của B, và B được gọi là followee của A. Khi các followee đăng các thông điệp, các thông điệp này sẽ được hiển thị trên timelines của follower [10]. Khi số lượng followee là lớn thì lượng dòng cập nhật đến trang của follower có thể lên tới hàng trăm tweet. Cheng Li và cộng sự [10] cũng chỉ ra rằng một khi số lượng dòng cập nhật là lớn, các cập nhật mới sẽ hiển thị trên đầu, thay thế các cập nhật cũ. Như vậy bất kì người dùng nào cũng có thể rơi vào tình cảnh bị tràn ngập thông tin và dễ bỏ qua những tin cần thiết với bản thân họ. Giải pháp xếp hạng dòng cập nhật của mỗi người dùng được đưa ra để giải quyết vấn đề này. 1.1. Hình 1.1. Minh họa dòng cập nhật trên Twitter 3 Bài toán xếp hạng dòng cập nhật Bài toán xếp hạng dòng cập nhật là bài toán sắp xếp các cập nhật đến trang của mỗi người dùng. Trước khi phát biểu về bài toán này trên mạng xã hội Twitter, chúng tôi đưa ra một số định nghĩa để tường minh hơn về bài toán. 1.2. 1.2.1. Một số định nghĩa • Dòng trên mạng xã hội Twitter được hiểu là dòng cập nhật của người dùng. Mỗi người dùng có các thông điệp mới (các cập nhật) đăng bởi các bạn bè trên trang của họ, đó là dòng cập nhật của họ. • Xếp hạng dòng trên mạng xã hội Twitter cơ bản là xếp hạng các thông điệp mới của mỗi người dùng trên mạng xã hội này. 1.2.2. Bài toán xếp hạng dòng cập nhật Bài toán xếp hạng dòng trên mạng xã hội Twitter là bài toán sắp xếp các tweet xuất hiện trong mỗi trang người dùng theo mức độ quan tâm của người dùng đó. Ta có:    Tập các người dùng trên mạng xã hội Twitter là 𝑈 = {𝑢𝑖 }, 𝑖 = 1, 𝑁 Tập các người dùng mà ui following là 𝑈𝑖 = {𝑢𝑖′ }, 𝑖 ′ = 1, 𝑛 (𝑖 ≠ 𝑖 ′ ) Tập các tweet hiển thị trên trang nhà (home) của ui là 𝑇𝑢𝑖 = {𝑡𝑢𝑖𝑗 }. Đây là tập hợp các tweet do các người dùng trong tập 𝑈𝑖 đăng lên Twitter. Nhiệm vụ của bài toán là sắp thứ tự các tweet 𝑡𝑘 theo mức độ quan tâm của người dùng ui. Bài toán được phát biểu như sau: Input: Các tweet mới đưa lên trên trang của người dùng 𝑢𝑖 . Output: Danh sách các tweet đó theo thứ tự giảm dần mức độ quan tâm của người dùng 𝑢𝑖 . Hướng tiếp cận giải quyết bài toán Để giải quyết một bài toán xếp hạng các dòng cập nhật hay các tweet mới đến của mỗi người dùng, hoàn toàn có thể áp dụng phương pháp xếp hạng đã được nghiên cứu trước đó dù bài toán này không có câu truy vấn. 1.3. 4 Một trong các hướng giải quyết gần đây là kĩ thuật học máy để học hàm xếp hạng tự động như học xếp hạng [11]. Trong [12], Liangjie và cộng sự cũng đề cập tới một mô hình giải bài toán xếp hạng cập nhật trên mạng xã hội LinkedIn, có liên quan tới phương pháp học tính hạng. Trong [1], chúng tôi nghiên cứu và áp dụng phương pháp của Liangjie và cộng sự cùng mô hình chủ đề ẩn được sử dụng để làm giàu đặc trưng dữ liệu vào bài toán trên. Trong luận văn, chúng tôi nâng cao hệ thống xếp hạng của mình bằng cách áp dụng độ ảnh hưởng của user (user influence) vào làm giàu đặc trưng vì độ ảnh hưởng của người dùng được đánh giá là rất hữu ích trong hệ tư vấn… [5, 6]. Do vậy, đây sẽ là một đặc trưng quan trọng góp phần vào nâng cao hệ thống xếp hạng. Đặc trưng này được tìm ra dựa vào luật kết hợp [7]. Ý nghĩa của bài toán xếp hạng dòng Kết quả của bài toán xếp hạng dòng là sự tư vấn cho người dùng, giúp họ nhanh chóng hơn trong việc nắm bắt các thông tin mình quan tâm và tiết kiệm thời gian cho bản thân. Mặt khác, sự tư vấn cho người dùng có kết quả tốt sẽ mang lại sự yêu thích của người dùng với mạng xã hội và số lượng người tham gia mạng sẽ tăng lên đáng kể. 1.4. Tóm tắt chương 1 Luận văn đã trình bày tổng quan về mạng xã hội Twitter và nội dung liên quan tới dòng cập nhật. Luận văn cũng đã nêu lên được vấn đề bất lợi cho người dùng khi bị tràn ngập thông tin và phát biểu được bài toán xếp hạng các dòng cập nhật cùng hướng tiếp cận để giải quyết bài toán. Ngoài ra, luận văn cũng đã nêu lên ý nghĩa của bài toán này. 1.5. Chương 2. CÁC PHƯƠNG PHÁP HỌC XẾP HẠNG, MÔ HÌNH CHỦ ĐỀ ẨN VÀ LUẬT KẾT HỢP 2.1. 2.1.1. Một số nội dung cơ bản về Xếp hạng dòng Giới thiệu Xếp hạng dòng chính là một loại Xếp hạng đối tượng (Tweet). Công việc thiết yếu là sắp xếp các đối tượng tweet của mỗi người dùng theo sự 5 giảm dần mức độ quan tâm của mỗi người dùng đó. Để xếp hạng các đối tượng, ta cần xác định hàm tính giá trị thứ hạng, gọi là hàm tính hạng. Mỗi đối tượng gồm có các đặc trưng là những chi tiết của bản thân đối tượng đó. Hàm tính hạng là sự kết hợp của các đặc trưng này. 2.1.2. Học xếp hạng Học xếp hạng là một loại học máy giám sát hoặc bán giám sát, trong đó mục tiêu là để tự động xây dựng một mô hình xếp hạng từ dữ liệu huấn luyện là tập dữ liệu đã có xếp hạng đúng. Như đã đề cập trong [1], các thuật toán học xếp hạng đều có hai nhiệm vụ chính: (1) xây dựng hàm tính hạng, (2) tính toán thứ hạng của đối tượng mới. Các nhiệm vụ có đầu vào và đầu ra khác nhau, cụ thể như sau:   Xây dựng hàm tính hạng o Đầu vào: Tập các đối tượng có sẵn thứ tự đúng và các đặc trưng o Đầu ra: Hàm tính hạng Tính toán thứ hạng đối tượng mới o Đầu vào: Tập đối tượng mới và hàm tính hạng o Đầu ra:Thứ hạng của mỗi đối tượng 2.1.3. Các phương pháp học xếp hạng điển hình 2.1.3.1. Phương pháp SVM-rank Xếp hạng SVM (SVM-rank) [13] là một ứng dụng của máy véc-tơ hỗ trợ (Support vector machine) được sử dụng để giải quyết bài toán xếp hạng bằng việc sử dụng thuật toán học giám sát SVM. SVM-rank được Joachims công bố năm 2002 với mục đích cải thiện hiệu suất của các công cụ tìm kiếm trên Internet. SVM-rank là thuật toán học xếp hạng theo hướng tiếp cận pairwise. Nhiều phương pháp dựa vào tối ưu SVM như [14]…Trong [2], Sculley đưa ra thuật toán CRR là sự kết hợp xếp hạng dựa trên SVM-rank với hồi quy. 2.1.3.2. Phương pháp CRR D.Sculley [2] đưa ra đưa ra phương pháp kết hợp cho hiệu quả tốt ở cả hồi quy và xếp hạng. Tư tưởng chính của phương pháp này là xây dựng mô hình tính hạng dựa trên mô hình hồi quy tuyến tính và mô hình tính 6 hạng pairwise (sử dụng SVM-rank). Thuật toán D.Sculley đưa ra gọi là thuật toán CRR, được trình bày như Error! Reference source not found.Error! Reference source not found.. Cho trước: α, , dữ liệu huấn luyện D và số lần lặp t. 𝑤𝑜 ← ∅ 𝑓𝑜𝑟 𝑖 = 1 𝑡𝑜 𝑡 𝑙ấ𝑦 𝑛𝑔ẫ𝑢 𝑛ℎ𝑖ê𝑛 𝑠ố 𝑧 𝑡ừ 0,1 𝑖𝑓 𝑧 < 𝛼 𝑡ℎ𝑒𝑛 (𝑥, 𝑦, 𝑞) ← 𝑅𝑎𝑛𝑑𝑜𝑚𝐸𝑥𝑎𝑚𝑝𝑙𝑒(𝐷) 𝑒𝑙𝑠𝑒 ((𝑎, 𝑦𝑎 , 𝑞), (𝑏, 𝑦𝑏 , 𝑞)) ← 𝑅𝑎𝑛𝑑𝑜𝑚𝐶𝑎𝑛𝑑𝑖𝑑𝑎𝑡𝑒𝑃𝑎𝑖𝑟(𝑃) 𝑥 ← (𝑎 − 𝑏) 𝑦 ← 𝑡(𝑦𝑎 − 𝑦𝑏 ) 𝑒𝑛𝑑 𝑖𝑓 1 𝑖 ← 𝑖 𝑤𝑖 ← 𝑆𝑡𝑜𝑐ℎ𝑎𝑠𝑡𝑖𝑐𝐺𝑟𝑎𝑑𝑖𝑒𝑛𝑡𝑆𝑡𝑒𝑝(𝑤𝑖−1 , 𝑥, 𝑦, , 𝑖 ) 𝑒𝑛𝑑 𝑓𝑜𝑟 𝑟𝑒𝑡𝑢𝑟𝑛 𝑤𝑡 Hình 2.1. Thuật toán CRR [2] Thuật toán thuần cho việc tối ưu sự kết hợp sẽ liệt kê đầy đủ tập các cặp ứng viên P. Số thành phần thuộc P là bình phương số thành phần thuộc D hay |P|=|D|2 nên khó thực hiện ở tập dữ liệu lớn. Joachims [14] đã đưa ra phương thức cho độ phức tạp O(|D|log|D|). Thuật toán đưa ra phương thức tối ưu sự kết hợp hồi quy và xếp hạng sử dụng phương pháp Stochastic gradient descent [2]. Phương pháp này giúp tối thiểu hàm mục tiêu, vấn đề xuất hiện trong học mô hình. Phương thức StochasticGradientStep trả ra kết quả khác nhau với các hàm sai số khác nhau. Chẳng hạn, với square loss, y  R, phương thức này trả ra (1 − 𝑖 )𝑤𝑖−1 + 𝑖 𝑥(𝑦 − (𝑤𝑖−1 , 𝑥)) Với logistic loss, giả sử y{0,1}, phương thức trả ra 1 ) (1 − 𝑖 )𝑤𝑖−1 + 𝑖 𝑥 (𝑦 − −(𝑤 1 + 𝑒 𝑖−1 ,𝑥) Như vậy, mô hình w được trả ra là mô hình học tính hạng. 7 2.1.4. Phương pháp đánh giá xếp hạng dòng Liangije và cộng sự [12] đã phân tích và lựa chọn các thước đo phổ biến dựa trên xếp hạng trong thu hồi thông tin (Information Retrieval). Đó là độ chính xác mức k (Precision@K – P@K) và độ chính xác trung bình (Mean Average Precision – MAP).  Độ chính xác mức K: P@K Độ chính xác xếp hạng ở mức K - Precision@K (P @K): độ chính xác của K đối tượng đầu bảng xếp hạng. Xác định số đối tượng đúng ở K vị trí đầu tiên của xếp hạng và gọi là Match@K, và độ chính xác mức K: Match@K P@K = K  Độ chính xác trung bình: MAP Độ chính xác trung bình là giá trị trung bình của các P@K tại các mức K có đối tượng đúng. Gọi I(K) là hàm xác định đối tượng ở vị trí hạng K nếu đúng I(K) =1 và ngược lại I(K) = 0. Độ chính xác trung bình: ∑𝑛𝐾=1 𝑃@𝐾 × 𝐼(𝐾) 𝐴𝑃 = ∑𝑛𝑗=1 𝐼(𝑗) Với n là số đối tượng được xét. MAP là độ chính xác trung bình trên N xếp hạng. (N truy vấn, mỗi truy vấn có một thứ tự xếp hạng kết quả tương ứng). MAP được tính như sau: ∑𝑁 𝑖=1 𝐴𝑃𝑖 𝑀𝐴𝑃 = 𝑁 2.2. 2.2.1. Mô hình chủ đề ẩn Giới thiệu Mô hình chủ đề ẩn [3] là mô hình xác suất phân phối các chủ đề ẩn trên mỗi tài liệu. Chúng được xây dựng dựa trên ý tưởng rằng mỗi tài liệu có một xác suất phân phối vào các chủ đề, và mỗi chủ đề là sự phân phối kết hợp giữa các từ khóa. Hay nói cách khác, ý tưởng cơ bản là dựa trên việc coi tài liệu là sự pha trộn của các chủ đề. Biểu diễn các từ và tài liệu dưới dạng phân phối xác suất có lợi ích rất lớn so với không gian vector thông thường. 8 2.2.2. Phương pháp mô hình chủ đề ẩn LDA là một mô hình Bayes phân cấp 3 mức (mức kho ngữ liệu, mức tài liệu và mức từ ngữ). Mỗi tài liệu trong tập hợp được coi là một hỗn hợp xác định trên tập cơ bản các chủ đề. Mỗi chủ đề là một hỗn hợp không xác định trên tập cơ bản các xác suất chủ đề. Về khía cạnh mô hình hóa văn Hình 2.2. Mô hình biểu diễn của LDA [17] bản, các xác suất chủ đề là một biểu diễn cụ thể, rõ ràng cho một tài liệu. Dưới đây, luận văn sẽ trình bày những nét cơ bản về mô hình sinh trong LDA. Cho trước tập M tài liệu D = {d1, d2…dM}, trong đó tài liệu thứ m gồm Nm từ, từ wi được rút ra từ tập các thuật ngữ {t1, t2…tV), V là số các thuật ngữ. Quá trình sinh trong mô hình LDA diễn ra như Hình 2.2 Ước lượng tham số cho mô hình LDA bằng tối ưu hóa một cách trực tiếp và chính xác xác suất của toàn bộ tập dữ liệu là khó có thể thực hiện. Một giải pháp đã được đề ra là sử dụng phương pháp ước lượng xấp xỉ như phương pháp biến phân [3] và lấy mẫu Gibbs [15]. Lấy mẫu Gibbs được xem là một thuật toán nhanh, đơn giản và hiệu quả để huấn luyện LDA. Trong luận văn, chúng tôi sử dụng phân phối topic của mỗi tài liệu được tìm ra từ LDA để làm đặc trưng nội dung cho việc xây dựng tập huấn luyện cho quá trình học của phương pháp học xếp hạng. 9
This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.