Luận văn thạc sĩ Khoa học máy tính: Lọc tin theo một chủ đề và truy nguồn trên mạng xã hội

Nếu khai thác được lượng dit liệu khổng lồ này, lọc được nhữngthông tin hữu ích cho từng lĩnh vực, nó sẽ góp phần to lớn trong việc xác định thịhiếu người dùng, xác định hướng phát triển

ĐẠI HỌC QUÓC GIA TP HCMTRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN

3

NGUYEN CHi TOAN

LỌC TIN THEO MOT CHỦ DE VÀ TRUY NGUON

TREN MANG XA HOI

Nganh: Khoa Hoc May Tinh

Mã số: 60 48 01 01

LUAN VAN THAC Si

NGƯỜI HƯỚNG DAN KHOA HOC: PGS TS BO PHÚC

LỜI CẢM ƠN

Luận văn Thạc Sỹ này được thực hiện tại Trường Đại Học Công Nghệ

Thông Tin TP Hồ Chí Minh Đề hoàn thành khóa luận này, tôi xin tỏ lòng biết ơnsâu sắc và gửi lời cảm ơn chân thành đến Thầy PGS.TS Đỗ Phúc, đã tận tình hướngdẫn, giúp đỡ cho tôi trong suốt quá trình thực hiện tốt luận văn thạc sĩ

Tôi xin chân thành cảm ơn quý thây, cô trong khoa khoa học máy tính vàphòng sau đại học của Trường Đại Học Công Nghệ Thông Tin TP Hồ Chí Minh đã

tận tình truyền đạt kiến thức, tạo điều kiện thuận lợi về mặt thủ tục cho hoạt động

học tập và thực hiện luận văn của tôi.

Tôi cũng xin gửi lời cảm ơn tới các anh chị và các bạn lớp cao học khóa 8 đã

giúp tôi rất nhiều trong quá trình học tập cũng như hoàn thành luận văn

Cuối cùng, tôi xin được bày tỏ lòng biết ơn sâu sắc tới gia đình, bạn bè đã

luôn động viên, khích lệ tỉnh thần để tôi có đủ nghị lực hoàn thành luận văn thạc sỹ

TP Hồ Chí Minh, tháng 03, năm 2016

Nguyễn Chí Toàn

LỜI CAM ĐOAN

Tôi cam đoan các kết quả tìm hiểu đưa ra trong khóa luận này dựa trên các kết quả

thu được trong quá trình tìm hiểu của riêng tôi

Nội dung của khóa luận có tham khảo và sử dụng một số thông tin, tài liệu từcác nguồn sách, tạp chí, website được liệt kê trong danh mục các tài liệu tham khảo

TP Hồ Chí Minh, tháng 03, năm 2016

Nguyễn Chí Toàn

TÓM TAT

Ngành công nghệ thông tin phát triển như vũ bảo kéo theo số lượng người sử

dụng internet tăng cao làm cho dữ liệu xung quanh chúng ta được tạo ra lớn hơn

bao giờ hết Dữ liệu tăng lên rất nhanh, vượt qua giới hạn xử lý của các hệ quản trị

cơ sở dữ liệu truyền thống Việc lưu trữ và khai thác lượng dữ liệu khổng lồ nay délọc ra được những dữ liệu hữu dụng quả là một thử thách lớn nhất mà người ta gặpphải trong xã hội hiện đại Việc khai thác được khối lượng dữ liệu không lồ nàyđang đặt ra những thuận lợi và thử thách vô cùng to lớn cho giới nghiên cứu vềkhoa học máy tính Nếu khai thác được lượng dit liệu khổng lồ này, lọc được nhữngthông tin hữu ích cho từng lĩnh vực, nó sẽ góp phần to lớn trong việc xác định thịhiếu người dùng, xác định hướng phát triển của công ty, hoặc là trong việc kiểm

soát và ngăn chặn phát tán thông tin trên mạng xã hội.

Kết quả của luận văn là một hệ thống xác định chủ đề thông tin, xác địnhthông tin là tích cực hay tiêu cực, xác định đường đi của thông tin, thời điểm phát

tán thông tin và cuối cùng vẽ biểu đồ lan truyền của thông tin:

Trong luận văn này sẽ từng bước thực hiện các bước theo trình tự sau:

- _ Nghiên cứu cơ sở lý thuyết về mô hình Latent Dirichlet Allowcation (LDA),

giải thuật lay mẫu Gibbs cho mô hình LDA

- Nghiên cứu giải thuật Support Vector Machine (SVM).

- Nghiên cứu giải thuật Naive Bayes.

- Nghién cứu Waikato Environment for Knowledge Analysis (Weka).

- Phân tích và thiết kế hệ thống

- Xây dựng hệ thống thực nghiệm

Luận văn xây dựng hệ thống thực nghiệm để thực hiện các vấn đề đã nghiên

cứu, thực nghiệm này được xây dựng bằng ngôn ngữ lập trình JAVA, nhằm khai

thác được những tính năng mạnh mẽ của ngôn ngữ lập trình này.

Chương 1: TONG QUA

1.1 Tính khoa học và tính mới của dé tai

1⁄2 Lý do chọn dé tài

1.3 Mục tiêu nghiên cứu

1.4 _ Đối tượng nghiên cứu

1.5 Phạm vi nghiên cứu.

1.6 _ Tình hình nghiên cứu

1.6.1 Tình hình nghiên cứu thé giới -~-~ ==~~~-====~============== 14

1.6.2 Tình hình nghiên cứu trong nước -~-~~~~~=~~===============~~~~ 15

17 _ Phương pháp thực hién:

18 Dự kiến kết quả đạt được:

19 Dự kiến cấu trúc luận văn sẽ thực hié

Chương 2: CƠ SỞ LÝ THUYET -~ =-=~~====+=================>=== 18

2.1 Các khái niệm

2.1.1 Khái niệm mạng xã

hội-2.1.2 Cấu trúc mạng xã hội -~ ~ ~-=-=~-====-=======z============== 19

2.1.3 Ảnh hưởng của mạng xã hội -~-7~-=~-==-==~==~==~==~======= 19

2.1.4 Các lợi ích của việc khai phá dữ liệu mạng xã hội 20

2.1.5 Các trang mạng xã hội hiện nay -~ =~~~ ===~~¬===~~=====~~~~ 20

2.1.6 Email tích cực, tiêu cực

22 MôhìnhLDA

2.3 Giải thuật lay mẫu Gibbs cho mô hình LDA

2.4 Giải thuật SVM

2.5 Giải thuật Naive Bayes

26 Weka

27 Lan truyền trên mạng xã hội

2.8 Lan truyền theo thời gian

Chương 3: PHAN TÍCH VA THIẾT KE HE THÓNG -= ~-== 38

3.1 Giới thiệu Database của hệ thống

3.2 Mô hình các đối tượng

3.3 Mô hình hệ thống

3.3.1 Chạy LDA trên tập dữ liệu Enron Email - 42

3.3.1.1 Làm sạch dữ liệu -~ -~~ -=================================== 42 3.3.1.2 Tạo tập tin đat -7~~~-~-~=~===========zzz===================rr 44

3.3.1.3 Chạy LDA -~-~ ==========~=~=~=~==========rzrzzrzrz=r==r=r======rr=re 44

3.3.2 Chạy LDA trên tập dữ liệu huấn luyén, - 51

3.3.2.1 Chay LDA -~-~-~ -=======~=~~~=~=~=~======rrrrr=r~=r==r======r=rrrre 51

3.3.2.2 Doc tập tin đặc trưng.

3.3.3 Gan nhãn chủ đề va tìm chủ dé ấn của từng email - 51

3.3.3.1 Gan nhãn chủ đề -~ =~=-==~==========================r=== 513.3.3.2 Tìm chủ để din -~-~ ~ =============z======================z 533.3.4 Xác định tin xấu -~ ~-=~-=-==~==~============================= 543.3.5 Xác định lan truyền -~ ~-=~~====~====~==~==~=========r===~r~ 543.3.6 Xác định lan truyền theo thời gian - 55

3.4 Thiết kế giao diện

Chương 4: XÂY DỰNG HỆ THÓNG THỰC NGHIỆM

4.1 Tập dữ liệu Enron Email

4.2 Xác định chủ đề a

4.3 Xác định tin tích cực

4.4 Xác định lan truyền "

4.5 Lan truyền theo thời gian

4.6 Lược đồ thống kê dữ liệu

DANH MỤC CÁC KÝ TỰ, CHỮ VIET TAT

Latent Dirichlet Allocation

Giải thuật lay mẫu Gibbs

Support Vector Machine Giai thuat Naive Bayes Waikato Environment for Knowledge Analysis

Markov Chain Monte Carlo

Tập ngữ liệu Enron Email

Gửi lại, gửi cho mọi người

Gửi, carbon copy, blind carbon copy

Gửi chuyển tiếpThích, liên kết, liên kết, bình luận

Dịch bệnh ebola Người dùng

Van hóa

Kinh tếĐời sống

Mô tả dữ liệu Message

Mô tả dữ liệu Referenceinfo.

Mô tả dữ liệu Recipientinfo.

Mô tả dit liệu Employeelist

Thông tin cấu hình đề nghị cài đặt hệ thống .Bảng hiển thị danh sách từ vựng tương ứng với từng chủ đề .Bảng từng email thuộc về từng chủ đề với xác suất tương ứng Bảng tập dữ liệu huấn luyện

Hình 2.7: Email lan truyền theo thời gian

Hình 3.1: cơ sở dữ liệu mang Enron email

Hình 3.2: mô hình dữ liệu mạng Enron email

Hình 3.3: mô hình dữ liệu hệ thống

Hình 3.4: Danh sách các từ dùng

Hình 3.5: Danh sách các dòng dữ liệu cân chạy LDA

Hình 3.6: Tập tin model-final.others

Hình 3.7: Tap tin model-final.phi

Hình 3.8: Tâp tin modemodel-final.tassign

Hình 3.9: Tâp tin Tập tin model-final.theta

Hình 3.10: Tap tin Tập tin model-final.twords

Hinh 3.11: Tap tin Tap tin model-final.twords

Hinh 3.12: Chu dé được đưa vào phân tích trên tap dữ liệu Hình 3.13: Danh sách chủ đề được đưa vào để huấn luyện

Hình 3.14: Xác định được chủ đề

Hình 3.15: API được cung cấp bởi Weka

Hình 3.16: Lược đồ lan truyền

Hình 3.17: Lược dé lan truyền theo thời gian

Hình 3.18: Giao diện chính của chương trình

Hình 3.19: Giao diện tab Training

Hình 3.20: Giao diện tab Spread

Hình 3.21: Giao diện tab Spread Time

Hình 3.22: Giao diện tab Chart

Hình 4.1: Tập tin đặc trưng cho chủ đề EconomicHình 4.2: Cập nhật đặc trưng cho chủ dé Economic

Hình 4.4: Các bước thực hiện xác định chủ đê

Hình 4.5: Kết quả trả v

Hình 4.6: Sơ đồ lan truyền t

Hình 4.7: Sơ đồ lan truyền tin theo thời gian

Hình 4.8: Biéu đồ thống kê chủ đề

Chương 1: TONG QUAN

Chúng ta đang sống trong một thời đại mới, thời đại phát triển rực rỡ của

CNTT.Tác động của CNTT đối với xã hội loài người vô cùng to lớn Sự phát triển

và ứng dụng của Internet đã làm thay đổi mô hình và cách thức hoạt động kinhdoanh của doanh nghiệp CNTT đã ở một bước phát triển cao, đó là số hóa tất cảcác dữ liệu thông tin, luân chuyển mạnh mẽ và kết nối tất cả chúng ta lại với nhau.Đồng thời cùng với sự phát triển của mạng xã hội, đã cho phép người dùng tự do

tạo các nội dung trên mạng xã hội, tốc độ tăng trưởng dữ liệu tràn lan đến chóng

mặt do sự phát triển của công nghệ Hàng ngày số lượng dữ liệu về hình ảnh, blog,

cập nhật mạng xã hội hàng ngày, tài liệu điện tử, tập tin nhạc và video được phát

triển với một tốc độ nhanh chóng Bên cạnh những trang web lớn có uy tín tồn tạikhông ít các trang web, tiểu blog mang không ít các thông tin mà độ chính xác hay

tin cậy không được xác nhận Đây là vấn đề bức xúc, nan giải trong việc kiểm soát

thông tin trên trang mạng gặp nhiều khó khăn Đặc biệt là những mạng xã hội như

Facebook, LinkedIn, Twitter đã thu hút hằng triệu lượt truy cập mỗi ngày, cho phép

chia sẻ các thông điệp, tài liệu hình anh

Mạng xã hội: Mạng xã hội được lan rộng thông qua các tương tác của các

thành viên Mọi thành viên trong mạng xã hội cùng kết nói và mỗi người là một mắt

xích để tạo nên một mạng lưới rộng lớn truyền tải thông tin trong đó Về cơ bản,

mạng xã hội giống như một trang web mở với nhiều ứng dụng khác nhau Mạng xãhội khác với trang web thông thường ở cách truyền tải thông tin và tích hợp ứngdụng Trang web thông thường cũng giống như truyền hình, cung cấp càng nhiềuthông tin, thông tin càng hap dẫn càng tốt còn mạng xã hội tao ra các ứng dụng mở,các công cụ tương tác để mọi người tự tương tác và tạo ra dòng tin rồi cùng lantruyền dòng tin đó

Đặc điển của mạng xã hội: Cho phép người dùng giao lưu và chia sẻ thông tinmột cách có hiệu quả, vượt ra ngoài những giới hạn về địa lý và thời gian Xâydựng lên một cộng đồng mạng trực tuyến nhằm phục vụ những yêu cầu công congchung và những giá trị của cộng đồng Nâng cao vai trò của mỗi công dân trong

việc tạo lập quan hệ và tự tổ chức xoay quanh những mối quan tâm chung trong

những cộng đồng thúc đầy sự liên kết các tổ chức xã hội Với các tính năng: chat,

e-mail, phim ảnh, voice chat, chia sẻ file, blog và bình luận cho phép mọi người kếtnối với nhau thông qua một trang web Trang web này chứa đựng nhiều ứng dụng

cho phép nhiều người cùng tương tác, chia sẻ, kết ban

Phân tích mạng xã hội: là đánh giá, ánh xạ môi quan hệ giữa các thành viên

trên mạng xã hội Thống kê, nghiên cứu về các thông điệp được trao đồi

Tiếp thị mạng xã hội: là phương pháp lan truyền những thông tin cần tiếp thịcho các cư dân mạng Thông tin về các dịch vụ, sản phẩm „sẽ được lan truyền từ

người này qua người khác một cách nhanh chóng.

Quản trị thông tin: kiểm soát, ngăn chặn một số tin đồng thời tìm ra nguồngốc phát tán đề có biện pháp ngăn chặn kịp thời

Với mong muốn nghiên cứu các phương pháp phân tích mạng xã hội theo

hướng nội dung, trong phạm vi luận văn này em xin sẽ giải quyết bài toán với đầuvào là các thông điệp, các bài viết Dữ liệu đầu ra sẽ là danh sách các chủ đề được

thảo luận trong các thông điệp, bài viết Xác định thông điệp, bài viết nào có đấu

hiệu tiêu cực từ đó tìm ra ai là người lan truyền, phát tán thông điệp, bài viết đó

1.1 Tính khoa học và tính mới của đề tài

Mang xã hội trở nên vô cùng phô biến, chính vì vậy nó cho phép mọi người đều cóthể cung cấp, đồng thời truy cập, khai thác, sử dụng tất cả các thông tin có trên

internet Bên cạnh đó, các thông tin đưa lên internet hiện nay có rất nhiều nguồn Có

nguồn từ các cơ quan báo chí, từ các trang thông tin điện tử của các cá nhân, cũng

như các tổ chức trong nước, lai cũng có nguồn từ các trang thông tin điện tử, cácwebsite, blog của các cá nhân và các tổ chức ngoài nước Vì vậy, việc quản lý thong

tin trên internet là một việc làm hoàn toàn không đơn giản Việc thông tin tràn lan

trên phương tiên thông tin dai chúng nếu như không chon lọc thì thông tin không cólợi mà chỉ có hại, ít thì có thể gây ra ảnh hưởng tâm lý không thoải mái, khó chịucho người cần tìm hiểu thông tin, nhiều khi gây ra hành động mat kiểm soát tạo sự

Việc xây dựng một hệ thống thực nghiệm cho phép:

- Xác định chủ dé ân

- _ Xác định thơng điệp cĩ dấu hiệu mang nội dung xấu

- — Xác định lan truyền.

- Xác định mức độ lan truyền theo thời gian

Là hết sức cần thiết và mang tính cấp thiết Trong đĩ, luận văn tập trung vào các mơ.hình LDA, SVM va Naive Bayes Từ việc nghiên cứu này, luận văn hi vọng sẽ hỗtrợ cho việc phân loại và kiểm sốt các luồng thơng tin trên mạng xã hội

1.2Lý do chọn đề tài

Do những nhu cầu của phân tích những luồng thơng tin trên mạng là hết sức cầnthiết nên đây là một để tài rất hợp với su thế, sự phát triển của CNTT Luận vănđĩng một vai trị quan trọng trong việc cung cấp một cái nhìn mới về mạng xã hội,các thơng tin được lan truyền hằng giây, hằng phút, hằng giờ trên internet Luận văn

mang hơi thở của thời đại, khi mà sức ảnh hưởng của mạng xã hội lớn hơn bao giờ

hết

1.3 Mục tiêu nghiên cứu

Trong đĩ luận văn tập trung vào nghiên cứu đặc điêm của các mơ hình LDA, SVM

và Nạve Bayes Từ việc nghiên cứu này, luận văn sẽ hỗ trợ cho việc phân loại vàkiểm sốt các luồng thơng tin trên mạng xã hội Nắm được cách thức tổ chức và cơchế hoạt động của mạng xã hội

1.4 Đối tượng nghiên cứu

Tap trung vào nghiên cứu đặc diém của các mơ hình :

- LDA

- SVM

- Naive Bayes

Đồng thời tiến hành nghiên cứu về mang xã hội về các mục tiêu:

- Cách thức tổ chức và cơ chế hoạt động của mạng xã hội

- _ Hiểu được phương pháp nghiên cứu mang xã hội

- Chon một phương pháp phân tích mạng xã hội

- _ Thử nghiệm với một mạng xã hội cụ thé

1.5 Phạm vi nghiên cứu

Nghiên cứu về các mô hình LDA, SVM, Naive Bayes Nghiên cứu về Weka và

cách thức tổ chức và cơ chế hoạt động của mạng xã hội Từ đó xây dựng một hệ

thống thực nghiệm giúp xác định chủ dé ẩn, xác định thông điệp có dấu hiệu mang

nội dung xấu Tìm ra người lan truyền tin xấu và xác định mức độ lan truyền theo

thời gian của thông tin.

1.6 Tình hình nghiên cứu

1.6.1 Tình hình nghiên cứu thế giới

Nghiên cứu sự lan truyền đữ liệu và lọc tin theo chủ đề trên mạng xã hội lần đầu

tiên được nghiên cứu từ những năm 2000 Trong những công trình này, họ đã xây

dựng chiến lược tiếp thị lan truyền (Viral Marketing) và phân tích quá trình lantruyền sử dụng cách tiếp cận theo khai phá dữ liệu Xây dựng mô hình bài toán tối

đa hóa tầm ảnh hưởng (Influence Maximization) trên mạng xã hội như là 1 bài toántối ưu (optimization problem)

Trong những nghiên cứu đầu tiên đã tập trung nghiên cứu vào mô hình lan

truyền thông tin độc lập (independence cascades), theo ngưỡng tuyến tinh (linear

threshold) và đưa ra mô hình chung tổng quát cho cả hai mô hình này, nghiên cứubài toán tối đa hóa tầm ảnh hưởng dưới bối cảnh phát hiện bùng phát Đặc biệt, họ

đã di sâu vào tìm ra tập các node trong mang dé phát hiện bùng phát cành sớm càng

-_ Công trình [9] mô hình hóa chủ đề an LDA dựa vào phân bó xác suất Ung

dụng vào bài toán chọn đặc trưng hay phân loại văn bản.

Công trình [6] nghiên cứu của Bing Liu về phân tích cảm xúc ở mức độ câu,văn bản và thực thể.

Công trình [8] nghiên cứu của David Kempe về mô hình lan truyền thông tin

Independent Cascade và Linear Thresholds.

Công trình nghiên cứu [7] của nhóm tác giả Byung-Won On, Ee Peng Lim,

Jing Jiang, and Loo Nin về hành vi của người trong mạng xã hội từ đó dựđoán thứ tự trả lời email và kết quả được chạy thử nghiệm trên tập ngữ liệu

Enron Email.

1.6.2 Tình hình nghiên cứu trong nước

Công trình [I] nghiên cứu, phát triển hệ thống lọc nội dung, hỗ trợ quản lý vàđảm bảo an toàn — an ninh thông tin trên mạng Internet - TS Nguyễn Viết

Thế Công trình nghiên cứu này dé xuất một giải pháp hỗ trợ công tác quản

lý một cách hiệu quả, an toàn các luồng dữ liệu ra vào Việt Nam và thế giới

qua mạng Internet.

Công trình nghiên cứu của Thạc Sỹ Nguyễn Xuân Nghề tim ra người có khả

năng lan truyền mạnh nhất, có ảnh hưởng lớn nhất trong mạng xã hội

Công trình nghiên cứu của Thạc Sỹ Nguyễn Văn Muôn phân tích chủ dé traođổi trên mạng xã hội

Công trình [17] của nhóm tác giả Muon Nguyen, Thanh Ho, Phuc Do nghiên

cứu mô hình lan truyền trên mạng xã hội LT-Linear Threshold và giải thuật

CELF Algorithm Từ đó tìm ra người có khả năng lan truyền mạnh nhất

trong mạng xã hội.

Công trình [18] nghiên cứu của nhóm tác giả Nguyen Le Hoang, Pham Vu

Dang Khoa, Phuc Do về việc dự đoán chủ đề được ưa thích của những người

dùng trong mạng xã hội.

Công trình[19] nghiên cứu của nhóm tác giả Phan Xuân Hiếu, Nguyễn Cảm

Tú về nhận dang chủ dé an đối với một tài liệu

1.7 Phương pháp thực hiện:

Nghiên cứu về các mô hình LDA, SVM, Naive Bayes

-_ Nghiên cứu về Weka.

- _ Nghiêm cứu cách thức tổ chức và cơ chế hoạt động của mạng xã hội

- Nghién cứu các phương pháp nghiên cứu mạng xã hội.

- Xây dựng hệ thống thực nghiệm thực hiện: xác định chủ dé an, xác dinh

thơng điệp cĩ dấu hiệu mang nội dung xấu, tim ra người lan truyền tin xấu,

xác định mức độ lan truyền theo thời gian, kiểm định thí nghiệm trang mang

xã hội.

- _ Đánh giá hệ thồng thực nghiệm, cho chạy thử và lấy ý kiến chuyên gia

1.8 Dự kiến kết qua đạt được:

Am hiểu về các mơ hình hình LDA, SVM, Naive Bayes và kết hợp với Weka Hiểutổng quan về cách thức tổ chức và cơ chế hoạt động của mang xã hội và các phương

pháp nghiên cứu mạng xã hội.

xác định chủ dé ân, xác định thơngXây dựng hệ thống thực nghiệm thực hiện:

điệp cĩ dấu hiệu mang nội dung xấu, tìm ra người lan truyền tin xấu, xác định mức

độ lan truyền theo thời gian

1.9 Dự kiến cấu trúc luận văn sẽ thực hiện:

Chương 1 : Tơng quan: Trong chương nay sẽ trình bay các van dé cần nghiên cứu

dựa vào các mục tiêu đã đặt ra, nêu lên ý nghĩa khoa học của cơng trình nghiên cứu,

tình hình nghiên cứu trong nước và ngồi nước, phương pháp thực hiện Cuối cùng

là kết quả đạt được

Chương 2: Cơ sở lý thuyết: Là các cơ sở lý thuyết làm nền tản cho việc nghiên cứu

của luận văn này Các khái niêm liên quan đến mạng xã hội, mơ hình LDA, giải

thuật SVM, Nạve bayes và Weka.

Chương 3: Phân tích và thiết kế hệ thống thực nghiệm: Trong chương này sẽtrình bày các bước dé hiện thực chương trình Mơ tả hệ thống, xử lý chỉ tiết cho

từng module.

Chương 4: Xây dựng hệ thống thực nghiệm: Trong chương này sẽ trình bày quátrình thử nghiệm phần mềm ở chương 3 Thử nghiệm chương trình trên một bộ dữ

liệu thử nghiệm.

Chương 5: Kết luận và hướng phát triển : Trong chương này sẽ đưa ra những kếtquả đạt được, những hạn chế cũng như khó khăn trong quá trình làm luận văn vàđưa ra hướng phát triển của luận văn

Kết chương:

Trong chương | này đã trình bày một số khái niệm mang xã hội, phân tích mang xã

hội Tính khoa học, tính mới, mục tiêu nghiên cứu, phạm vi nghiên cứu của luận

văn Bên cạnh đó trong chương này cũng trình bày về tình hình nghiên cứu trongnước và ngoài nước Hướng tiếp cận và kết quả đạt được của luận văn

Chương 2: CƠ SỞ LÝ THUYET

Trong chương này tôi sẽ trình bày về các cơ sở lý thuyết về mạng xã hội, cấu trúc

mạng xã hội Tôi sẽ lần lượt đi sâu vào các thuật toán được áp dụng trong luận văn

này.

2.1 Các khái niệm

2.1.1Khái niệm mạng xã hội

Mạng xã hội [3] là dịch vụ nối kết các thành viên cùng sở thích trên Internet lại vớinhau với nhiều mục đích khác nhau không phân biệt không gian và thời gian

Những người tham gia vào mạng xã hội còn được gọi là cư dan mạng.

Mạng xã hội có những tính năng như chat, email, phim ảnh, voice chat, chia sẻ file,

blog và xã luận Các dịch vụ này có nhiều phương cách dé các thành viên tìm kiếm

bạn bè, đối tác: dựa theo group (ví dụ như tên trường hoặc tên thành phó), dựa trên

thông tin cá nhân (như địa chi e-mail hoặc screen name), hoặc dựa trên sở thích cá

nhân (như thê thao, phim ảnh, sách báo hoặc ca nhạc), lĩnh vực quan tâm: kinh

doanh, mua bán

Fanpage

Fanpage [2] là nơi giao lưu, tương tác giữa doanh nghiệp và khách hàng (gọi là

thành viên) hoặc các sự kiện được các doanh nghiệp đưa lên để thành viên tham gia

Mọi thông tin đưa lên sẽ được đăng lên tường của các trang cá nhân của các thành

viên Từ những trang cá nhân, bạn bẻ của họ có thé nhìn thấy các thông tin qua đónội dung thông tin cần được quảng cáo sẽ được lan truyền

Newfeed

News Feed [14] là nội dung nam trong cột chính giữa trang chủ Facebook của bạn

một danh sách cập nhật liên tục những câu chuyện từ mọi người và các trang ban

theo đối trên Facebook News feed bao gồm các status, hình ảnh, video, liên kết,hoạt động ứng dụng và like Đôi khi bạn sẽ thấy xuất hiện cả quảng cáo của các

trang fanpage trên News Feed của mình.

2.1.2 Cấu trúc mạng xã hội

Mạng xã hội là một đồ thị vô hướng trong đó mỗi thành viên trong mạng xã hội là

một nút Mối liên hệ giữa các nút được gọi là các liên kết

‘US Counternsurgency Policy

2.1.3 Ảnh hướng của mạng xã hội

Với sự phát triển của CNTT, các trang mạng xã hội gây ảnh hưởng to lớn đến kinh

tế, chính trị, văn hóa đặc biệt là lối sống của các cư dan mạng Bên cạnh những anhhưởng tích cực thì những ảnh hưởng tiêu cực ngày càng thẻ hiện rõ

- Anh hưởng tích cực

- _ Chia sẻ thông tin nhanh chóng, cung cấp tri thức cho con người

- Dễ dàng tìm ra những người có cùng quan điểm, sở thích

- Lan truyền thông tin nhanh chóng, tận dụng sức mạnh cộng đồng

- Hộ trợ đắc lực cho việc quảng cáo, tiếp thị sản phẩm.

- Anh hưởng tiêu cực

- Con người đắm chim trong thé giới ảo, giảm tương tác ngoài đời sống

thực tế

- Không tập trung vào các mục tiêu trong cuộc sống

- Dễ bị kẻ xấu lợi dụng dé phát tán những thông tin không đúng sự thật

-_ Nguy co mắc bệnh tram cảm

2.1.4 Các lợi ích của việc khai phá dữ liệu mạng xã hội

Từ những mặt tích cực và tiêu cực ta thấy cần có những công cụ hữu hiệu để khaiphá, phân tích mạnh xã hội Tìm ra được nội dung đang được cộng đồng quan tâm,thị hiếu của cộng đồng từ đó có những chiến lược phù hợp với những mục đích

khác nhau Khi phát hiện một thông tin có nội dung không đúng, sai sự thật ta có

thể tìm ra được ai là người đứng sau phát tán nội dung để có biện pháp ngăn chặn

kịp thời.

2.1.5 Các trang mạng xã hội hiện nay

Hiện nay có rất nhiều mạng xã hội, bảng 2.1 là danh sách các mạng xã hội được sửdụng nhiều nhất

hình ảnh

Twitter Twitter là một trang mạng xã hội và

blog Được thành lập 3/2006 Người dùng có

Hơn 400 triệu

thể gửi và đọc các tin nhắn văn bản

LinkedIn LinkedIn là trang mạng xã hội dành cho | Hơn 300 triệu

những người chuyên nghiệp Được ra mắt

vào 5/2003

Google Google plus+ là một lớp mạng xã hội bao | Hơn 600 triệu

Plus+ gồm nhiều tài sản trực tuyến của google

Pinterest Printerest là một website chia sẻ ảnh theo | Hơn 300 triệu

dạng mạng xã hội Người dùng được post và

phân loại dưới dạng các tắm bảng dán ảnh

2.1.6 Email tích cực, tiêu cực

Tích cực (positive): là đoạn văn (Email) chứa những từ ngữ mang ý nghĩa tốt,

lạc quan, yêu đời nó thường chứa các từ như: wonderful, good, cheerful, sweet

Tiêu cực (negative): là đoạn văn (Email) mang ý nghĩa bi quan, chán nản, giận dir nó thường chứa các từ như bad, poor, terrible, furious, angry

Topic proportions and

Topics Documents assignments

= # Seeking Life’s Bare (Genetic) Necessities

Hình 2.2: Mô hình LDA [10]

Dưới đây là các bước dé tạo ra một văn ban từ danh sách chủ đề Mỗi chủ đề gdm

một tập hợp từ.

1) _ Xác định số lượng các từ N trong văn bản

2) Chọn số lượng chủ dé cho tài liệu (k chủ đề) dựa theo phân bố đa thức

3) Sinh ra các từ cho tài liệu này theo các bước:

- _ Chọn một chủ đề dựa theo phân bé đa thức đã được xác định ở trên

- Sử dụng chủ đề đã được chọn đề tạo ra các từ theo xác suất của từng chủ

đề đã xác định ở trên

Ví dụ: Tạo ra tài liệu D với các từ được lấy từ các chủ đề cho trước (chủ đề

computer và economic)

- Đầu tiên chọn “Asus” thuộc về chủ đề computer đưa vào D

- Đầu tiên chọn “laptop” thuộc về chủ dé computer đưa vào D

- Chọn “brand” thuộc chủ đề economic đưa vào D

- Chọn “market” thuộc chủ để economic đưa vào D

Sau các bước trên ta sẽ tạo ra một tài liệu D bao gồm “Asus is a good laptop

brand in the market”.

Trong bài toán tìm chủ đề ẩn của các tài liệu: chúng ta làm ngược lại các bước

phía trên để suy ra chủ dé từ các tài liệu

2.3 Giải thuật lấy mẫu Gibbs cho mô hình LDA

Để có thể tìm ra các chủ đề từ các văn bản, chúng ta dùng suy diễn hậu nghiệm.Nghia là ta cần đảo lại quá trình sinh ra văn bản và học các phân bố hậu nghiệm củacác biến tiềm ẩn trên dữ liệu được quan sát Các đại lượng này được xác định quabiểu thức 2.1:

PO, 0,z, wa, B) p(wla, B)

Tuy nhiên trong thực tế, ta không thé tinh toán chính xác p(w| œ,B) do đó ta sẽ xử

p(0, Ø,z|w, a, ÿ) = (2.1)

dung thuat toan lay mau Gibbs [13]

Giải thuật lầy mẫu Gibbs là một trong những họ của giải thuật Markov Chain MonteCarlo Giải thuật này tạo ra xích Markov có phân bố hậu nghiệm ôn định Điều này

có nghĩa là lặp lại nhiều lần trên xích Markov, mẫu từ phân bố nên hội tụ giống với

mẫu từ xác suất hậu nghiệm mong muốn

Lấy mẫu Gibbs sẽ dựa vào việc lấy mẫu từ các phân bố điều kiện của các biến của

xác suất hậu nghiệm

Giải thuật được thực hiện như sau:

Qui ước các tham số cho giải thuật:

- Dlà tập ngữ liệu

- da một văn bản trong tập ngữ liệu

- klà số chủ dé

- _ Ww là một từ

-_ nạx số các từ được gán vào chủ đềk trong tập tài liệu d

- _ nụ là số lần từ w được gan vào chủ đề k

- nụ tổng số lần bat kỳ từ nào được gan vào chủ đề k

Giải thuật

Giải thuật được khởi tạo với các biến đếm ngẫu nhiên và chạy vòng lặp với số bước

lặp mong muốn (số bước lặp này thường từ 1000 đến 2000) Trong mỗi bước lặp,lần lượt các chủ đề sẽ được lấy mẫu cho mỗi từ trong tập ngữ liệu Kết thúc quá

trình lặp, các phân bố tiềm ẩn sẽ được tính dựa vào các biến đếm

Đầu vào: Tập các từ w của tập văn bản d

Đầu ra: Các phép gan chủ dé và các biến đêm nư„v;na,x; Me Bắt đầu

Khởi tạo ngẫu nhiên tập z và tăng các biến đếm For mỗi bước lặp do

na,chủ đ†=1/ Pnrừ,chủ adt=1; Nena đè†=1

End

End

Kết thúc

2.4 Giải thuật SVM.

Support Vector Machines (SVM) là một phương pháp phân loại xuất phát từ lý

thuyết thống kê và khoa học máy tính cho một tập các phương pháp học có giám sát

có liên quan đến nhau về phân loại và phân tích hồi quy

Y tưởng cho giải thuật SVM là dựa vào một tập huấn luyện cho trước đượcbiểu diễn trong không gian vector, mỗi tài liệu là một điểm Phương pháp này giúptìm ra một siêu phẳng f có thể chia các điểm trong không gian này thành hai lớpriêng biệt gọi là lớp “+” và lớp “-“ Chất lượng của siêu phẳng f được quyết định

bởi khoảng cách (gọi là biên) của điểm dữ liệu gần nhất của mỗi lớp đến siêu phẳng

f Do đó, chất lương của việc phân loại đạt độ chính xác cao nhất khi khoảng cáchbiên là lớn nhất

Ý tưởng của phương pháp này là ánh xạ tập dữ liệu cần phân loại vào khônggian vector đặc trưng mà ở đó một siêu phẳng f tối ưu được tìm ra dé phân loại dữ

liệu thuộc hai lớp khác nhau.

Hình 2.3 Mô hình SVM

Trong hình 2.3 đường tô đậm màu đỏ được gọi là siêu phẳng tốt nhất Các

điểm được bao quanh bởi hình chữ nhật là những điểm gần siêu phẳng nhất được

gọi là các vector hỗ trợ Các đường nét đứt được gọi là lề Mục tiêu của giải thuật

nay là tìm ra không gian F và siêu phẳng quyết định f trên F sao cho sai số trongviệc phân loại là thấp nhất

Ví dụ:

Cho tập mẫu D={(x1,y1), (X2;Y2), (xi,yi)} với xi ER"

Với yi € {-1,1} là nhãn lớp tương ứng của xi, (-1 là lớp “-“, 1 là lớp “+”).

Ta cĩ phương trình siêu phăng chứa vector X trong khơng gian:

+1x,.W+b>0

H.W+d=0 BAAR) =SienG.+b=0) =[ TU FP eo

fŒ?) được biểu diễn sự phân lớp của X; vào lớp + hoặc

-Ta noi: Yi=+1 nêu %; thuộc lớp + và yi=-1 nếu X; thuộc lớp -

2.5 Giải thuật Nạve Bayes.

Giải thuật Nạve Bayes [4] dựa trên định lý Bayes được phát biểu:

P(XY) _ P(XIY)P(Y)

PY|XSE Bay = pan (2.2)

- Y là giả thuyết Y được suy luận khi cĩ chứng cứ mới X

- P(X): xác suất xay ra X

- PCY): xác suất xảy ra Y

- P(XỊY): xác suất xảy ra X khi Y xảy ra

-_ P(Y|X): xác suất hậu nghiệm của Y nếu X được xác định

Trong bài tốn phân loại:

-_D: tập vector hĩa dữ liệu huấn luyện dưới dạng # = (Xi,X¿, ,Xa)

khai thác dữ liệu Các thuật toán hoặc có thé được áp dụng trực tiếp vào đữ liệu

hoặc cung cấp API có thể gọi từ Java

Weka cung cấp các tính năng chính:

- Công cụ đa dạng dé thay đổi tập dữ liệu, xử lý dữ liệu, giải thuật và đánh

giá.

- Giao diện đỗ họa người dùng

- Môi trường dé so sánh các giải thuật

Môi trường:

- Simple SLI: giao điện đơn giản đề chạy các câu lệnh Commant Line

- Explorer: giao diện đồ hoa đề thực hiện khai phá dữ liệu

- _ Experimenter: môi trường dé thí nghiệm và thống kê giữa các mô hình máy

“The University of Waikato

Hamilton, New Zealand

Hình 2.4 Giao diện chính của chương trình Weka

2.7 Lan truyền trên mạng xã hội

Lan truyền dữ liệu chính là việc truyền tải thông tin từ người dùng này qua ngườidùng khác Thông tin ở đây có thé là các dong trang thái, các tin tức hay các thôngđiệp quảng cáo từ nhà sản xuất muốn phát tán đến tay khách hàng của mình

Việc lan truyền được thực hiện qua một số cách

- Khi người dùng đăng lên một thông tin và dùng chức năng share cho các

)

thành viên trong danh sách bạn bè (like, public, tag.

Đăng tải lên tường của người khác.

Ví dụ:

- User 1 có danh sách bạn bẻ là user 2, user 3, user 4

User 2 có danh sách bạn bè là user 5, user 6.

- User 3 có danh sách bạn bè là user 7, user 8.

Trong hình 2.5 ta có:

- User 1 post một thông điệp và share cho danh sách bạn bè User 1 đã lan

truyền thông điệp đến user 2, user 3 và user 4

- User 2 share thông điệp đó cho user 5 và user 6 User 2 đã lan truyền thông

điệp đến user 5, user 6

- User 3 tag thông cho user 7 va user 8 User 3 đã lan truyền thông điệp đến

user 7 va user 8.

- User 4 like thông điệp trên Như vậy user 4 đã lan truyền ngược lại thông

điệp cho user 1.

Những cách trên thường dùng dé chia sẽ các thông tin trong một phạm vi nhỏ Dé

mở rộng phạm vi lan truyền Làm thé nào dé lan truyền đến nhiều người cùng một

lúc.

Để giải quyết vấn đề trên, người ta thường sử dụng Fanpage (trang hâm mộ).Các Fanpage thường đăng tải các nội dung thu hút sự chú ý của nhiều người dé détăng số lượng thành viên cũng như lượt theo dỏi Sau đó các trang mạng xã hội sẽ

xử dụng các thuật toán riêng đê đánh giá.

Đối với mạng xã hội facebook

Hiện tại mạng xã hội facebook đang xử dụng thuật toán Edgerank [11] để lan truyền

cao Ví dụ nếu bạn có một số lượng lớn bạn bè mà like cùng | page

thì những hành động “like” của những bạn này sẽ hiển thị trên

newfeed của bạn.

- We: Day là yếu tố bạn có thé dé dàng khai thác trong thuật toán

EdgeRank Có 2 loại Weight sau: một là các dong post (Photo, video,

link, text, text + link + photo ) trong đó photo có trọng số cao nhất.

Hai là các tương tác (share, comment, like) trong đó like có trọng sốthấp nhất

- de: đây là yếu tố quyết định kha năng được xuất hiện trên newfeed.Thông thường thì bài viết mới thường xuất hiện bên trên các bài viết

củ hơn.

Đối với mạng ngữ liệu Enron Email

Mang Enron Email có cấu trúc đặc thù dùng để trao đổi email giữa các user trong hệthống Việc lan truyền email được xác định qua các hành động: reply, reply all,send,

cc, bcc, forward trên một email Những hành động này được lưu trữ trong mạng Enron Email.

Sau đây là các bước dé xác định lan truyền

Bước 1:

Khởi tạo listEmail

Khởi tạo cây £

sendNode € Tách người gửi

listTo € Tách người nhận (to)

1istCC © Tách người nhận (cc) 1istBcc € Tách người nhận (bec)

From: Hyatt, Kevin Sent: Tuesday, August 14,

2001 7:52 AMTo: Brennan, LornaSubject: RE: Draft

Copy of ~CEC s Final Report on California Infrastructurecan i have the Reader s_ Digest

From: Brennan, Lorna Sent: Monday, August 13,

2001 10:54 AMTo: Chavez, Gabriel; Dowd, Stephen; Gadd, Eric; Hyatt, Kevin; Millar, John; Ratner, Michael; Taylor, Gina; Hass, Glen; Loeffler,

Michael; Stanton, Lon; Wilson, Rob; Harris, Steven;

Donoho, Lindy; Goradia, Pallavi; Lindberg,

Lorraine; Lohman, TK; Lokay, Michelle; Moore, Jan;

Watson, Kimberly; Huber, Lee; Pryor, TonySubject:

Draft Copy of CEC s Final Report on California Infrastructure << File: cec.infrastructure.pdf >>

Trong thông điệp trên email đầu tiền được gửi từ Brennan, Lorna đến Chavez, Gabriel; Dowd, Stephen;

Gadd, Eric; Hyatt, Kevin; Millar, John; Ratner,

Michael; Taylor, Gina; Hass, Glen; Loeffler,

Michael; Stanton, Lon; Wilson, Rob; Harris, Steven;

Donoho, Lindy; Goradia, Pallavi; Lindberg,

Lorraine; Lohman, TK; Lokay, Michelle; Moore, Jan;

Watson, Kimberly; Huber, Lee; Pryor, Tony.

Sau đó Hyatt, Kevin gửi nó đến cho Brennan, Lorna

Ta nói thông điệp trên được lan truyền từ Brennan,

Lorna đến Chavez, Gabriel; Dowd, Stephen; Gadd,

Eric; Hyatt, Kevin; Millar, John; Ratner, Michael;

Taylor, Gina; Hass, Glen; Loeffler, Michael;

Stanton, Lon; Wilson, Rob; Harris, Steven; Donoho,

Lindy; Goradia, Pallavi; Lindberg, Lorraine;

Lohman, TK; Lokay, Michelle; Moore, Jan; Watson,

Kimberly; Huber, Lee; Pryor, Tony Sau đó Hyatt,

Kevin tiếp tục lan truyền đến cho Brennan, Lorna.

2.8 Lan truyền theo thời gian

Khi có một tin đồn trên được phát tán trên mạng Người ta thường nói “Tin đó tràn

lan trên mạng” Bài toán đặt ra là làm thế nào để xác định mức độ “tràn lan” và độ

“hot” của tin Một thông tin thường xuất hiện trên mạng, được phát tán và cuối cùng

nó sẽ bị lãng quên.

Ví dụ:

Dịch bệnh Ebola ban đầu được phát tán ra, được lan truyền rộng rãi trên các trang

báo, mạng xã hội Nhưng đến thời điểm hiện tại, nó không còn được phán tán, lan

truyền

Đối với mạng xã hội facebook

Một thông tin được post, nó sẽ xuất hiện trên timeline Nó sẽ được like, share, tag,

comment Nhưng sau một thời gian Nó sẽ bị an đi và bị thay thế bằng những

post mới hơn Lan truyền theo thời gian là xác định những thời điểm post được like,

comment, tag, share và hành động đó sẽ lan truyền đến bao người dùng khác

Đối với mạng ngữ liệu Enron Email

Khi một email được gửi đi, sau đó sẽ có hàng loạt các hành động đối với email đó:

forwad, cc, bee, reply, reply all Trong trường hợp này, lan truyền theo thời gian

được xác định thông qua những thời điêm các user thực hiện các tác động trên email đó.

Sau đây là các bước dé xác định lan truyền theo thời gian của một email

Bước 1:

Khởi tạo listEmail

Khởi tạo listNode

Bước 2:

listEmail € Tach dt liệu đầu vào thành các email

riêng biệt Bước 3:

For i = listEmail.length-1 > 0 do

Khởi tạo biến đếm count, biên thời gian t

Khởi tạo danh sách node: JlistTo, listCC,

listBcc

listTo € Tách người nhận (to) listcc € Tách người nhận (cc) listBcc € Tách người nhận (bec)

t € Tach thời gian gửi listChildren.add(listTo)

From: Hyatt, Kevin Sent: Tuesday, August 14, 2001

7:52 AMTo: Brennan, Lorna Subject:RE: Draft Copy of

CEC s Final Report on California Infrastructurecan i

have the Reader s Digest condensed version

From: Brennan, Lorna Sent: Monday, August 13, 2001

10:54 AMTo: Chavez, Gabriel; Dowd, Stephen; Gadd,

Eric; Hyatt, Kevin; Millar, John; Ratner, Michael;

Subject: Draft Copy of CEC s Final Report on California Infrastructure << File: cec.infrastructure.pdf >>

Email trên được biểu diễn bằng hình 2.7

Ratner, Michael Millar, John

Hình 2.7: Email lan truyền theo thời gian

Trong hình 2.7 ta có:

Vào thời điểm 13/8/2001 10 :54 AM

- Brennan, Lorna gửi email đến Chavez, Gabriel; Dowd, Stephen; Gadd, Eric;

Hyatt, Kevin; Millar, John; Ratner, Michael;

Vào thời điểm 13/8/2001 10 :54 AM

Hyatt, Kevin gửi email đến Brennan, Lorna

Kết chương:

Trong chương 2 đã trình bày chỉ tiết các khái niệm về mạng xã hội, fanpage và các

mơ hình, giải thuật được áp dụng vào luận văn: LDA, SVM, Nạve Bayes, Weka.

Ngồi ra trong chương này cịn trình bày về hướng tiếp cận xác định lan truyềnnhằm tìm ra người phát tán tin tiêu cực và phát tán trong những khoản thời gian

nào.