Bài giảng Khai phá dữ liệu web - Chương 5: Biểu diễn web - Hà Quang Thụy

BÀI GIẢNG KHAI PHÁ DỮ LIỆU WEBCHƯƠNG 5. BIỂU DIỄN WEBPGS. TS. HÀ QUANG THỤYHÀ NỘI 02-2011TRƯỜNG ĐẠI HỌC CÔNG NGHỆĐẠI HỌC QUỐC GIA HÀ NỘI1Nội dungGiới thiệuPhân tích văn bảnBiểu diễn TextLựa chọn đặc trưngThu gọn đặc trưngBiểu diễn Web2Giới thiệuBiểu diễn văn bảnLà bước cần thiết đầu tiên trong xử lý văn bảnPhù hợp đầu vào của thuật toán khai phá dữ liệuTác động tới chất lượng kết quả của thuật toán KHDLThuật ngữ tiếng Anh: (document/text) (representation/indexing)Phạm vi tác động của một phương pháp biểu diễn văn bảnKhông tồn tại phương pháp biểu diễn lý tưởngTồn tại một số phương pháp biểu diễn phổ biếnChọn phương pháp biểu diễn phù hợp miền ứng dụngMột sơ đồ sơ lược: Tomek Strzalkowski: Document Representation in Natural Language Text Retrieval, HLT 1994: 364-3693Nghiên cứu về biểu diễn văn bảnNghiên cứu biểu diễn văn bản (Text + Web) Luôn là nội dung nghiên cứu thời sựBiểu diễn Web bổ sung một số yếu tố cho biểu diễn TextSố công trình liên quan"Document representation”mọi nơi: 8000 bài; tiêu đề: 200 (60 bài từ 2006-nay)“Document indexing”mọi nơi: 5200 bài; tiêu đề: 220 (60 bài từ 2006-nay)“Text representation”mọi nơi: 9200 bài; tiêu đề: 240 (60 bài từ 2006-nay)“Text indexing”mọi nơi: 6800 bài; tiêu đề: 210 (60 bài từ 2006-nay)Ghi chú: các bài “ở mọi nơi” phần đông thuộc vào các bài toán xử lý văn bản bao gồm bước trình bày văn bản4Nghiên cứu về biểu diễn văn bản (2)5Dunja Mladenic' (1998). Machine Learning on Non-homogeneous, Distributed Text Data. PhD. Thesis, University of Ljubljana, Slovenia.Phân tích văn bảnMục đích biểu diễn văn bản (Keen, 1977 [Lew91])Từ được chọn liên quan tới chủ đề người dùng quan tâmGắn kết các từ, các chủ đề liên quan để phân biệt được từ ở các lĩnh vực khác nhauDự đoán được độ liên quan của từ với yêu cầu người dùng, với lĩnh vực và chuyên ngành cụ thểMôi trường biểu diễn văn bản (đánh chỉ số)Thủ công / từ động hóa. Thủ công vẫn có hỗ trợ của công cụ máy tinh và phần mềmĐiều khiển: chọn lọc từ làm đặc trưng (feature) biểu diễn) / không điều khiển: mọi từ đều được chọn.Từ điển dùng để đánh chỉ số. Từ đơn và tổ hợp từ.6Luật ZiptMột số dạng khácPhân phối YuleMô hình thống kê c=log(C), b= log(B)Biến thể loga-chuẩnPhân phối Weibull với 0<<1	7Luật ZiptCho dãy dữ liệu được xếp hạng x1x2 xnthì hạng tuân theo công thức 	C là hằng số,  gần 1; kỳ vọng dạng logaDạng hàm mật độ: Luật Zipt trong phân tích văn bảnTrọng số của từ trong biểu diễn văn bản (Luhn, 1958)Dấu hiệu nhấn mạnh: một biểu hiện của độ quan trọng thường viết lặp lại các từ nhất định khi phát triển ý tưởnghoặc trình bày các lập luận,phân tích các khía cạnh của chủ đề. Các từ có tần suất xuất hiện cao nhất lại ít ngữ nghĩa. Từ xuất hiện trung bình lại có độ liên quan cao.Luật ZiptLà một quan sát hiện tượng mà không phải là luật thực sự: xem hình vẽ “Alice ở xứ sở mặt trời”rt * ft = K (hằng số): rt : độ quan trọng của từ t; ft: tần số xuất hiện từ t. Có thể logarith8Luật Zipt trong tiếng Anh9Một lượng nhỏ các từ xuất hiện rất thường xuyênCác từ có tần suất xuất hiện cao nhất lại ít ngữ nghĩa, thường là các từ chức năng trong câu (chắng hạn, giới từ)Hầu hết các từ có tần suất thấp.Luật Zipt: ước lượng trang web được chỉ sốƯớc lượng tối thiểu lượng trang web chỉ số hóaật Zipt: từ kho ngữ liệu DMOZ có hơn 1 triệu trang webDùng luật Zipt để ước tính lượng trang web chỉ số hóa.Mỗi ngày: 50 từ (đều ở đoạn logarith luật Zipt) gửi tới 4 máy tìm kiếm Google, Bing, Yahoo Search và Ask.Trừ bớt phần giao ước tính giữa các công cụ tìm kiếm: làm giàThứ tự trừ bớt phần giao → tổng (được làm non)10Các mẫu luật Zipt khácDân số thành phốDân số thành phố trong một quốc gia: có  = 1. Đã xác nhận ở 20 quốc gia.Có thể mở rộng sang: dân cư khu đô thị, vùng lãnh thổLượt thăm trang web và mẫu giao vận Internet khácSố lượt truy nhập trang web/thángCác hành vi giao vận Internet khácQuy mô công ty và một số số liêu kinh tế khácXếp hạng công ty theo: số nhân viên, lợi nhuận, thị trường Các hành vi giao vận Internet khác[Li02] Wentian Li (2002). Zipf's Law Everywhere, Glottometrics 5 (2002): 14-2111Phương pháp lựa chọn từ Luhn58Bài toánInput: Cho một tập văn bản: có thể coi tất cả các văn bản trong miền ứng dụng; ngưỡng trên, ngưỡng dưới dương.Output: Tập từ được dùng để biểu diễn văn bản trong tậpGiải phápTính tần số xuất hiện mỗi từ đơn nhất trong từng văn bảnTính tần số xuất hiện của các từ trong tập toàn bộ văn bảnSắp xếp các từ theo tần số giảm dầnLoại bỏ các từ có tần số xuất hiện vượt quá ngưỡng trên hoặc nhỏ thua ngưỡng dưới.Các từ còn lại được dùng để biểu diễn văn bản“Từ” được mở rộng thành “đặc trưng”: n-gram, chủ đề.. Lưu ýChọn ngưỡng: ngưỡng cố định, ngưỡng được điều khiểnLiên hệ vấn đề chọn lựa đặc trưng (mục sau).12Phương pháp đánh trọng số của từBài toánInput: Cho một tập văn bản miền ứng dụng D và tập từ được chọn biểu diễn văn bản V (sau bước trước đây).Output: Đánh trọng số từ trong mỗi văn bản  Xây dựng ma trận {wi,j} là trọng số của từ wi V trong văn bản dj D.Giải phápMột số phương pháp điển hìnhBooleandựa theo tần số xuất hiện từ khóaDựa theo nghịch đảo tần số xuất hiện trong các văn bản Phương pháp Boolean Đơn giản: trọng số là xuất hiện/ không xuất hiệnwi,j = 1 nếu wi xuất hiện trong văn bản dj, ngược lại wi,j = 0.13Các phương pháp đánh trọng số của từ theo tần sốDạng đơn giản: TFwi,j = fi,j: trong đó fi,j là số lần từ khóa wi xuất hiện trong văn bản djMột số phiên bản khác của dạng đơn giảnCân đối số lần xuất hiện các từ khóa: giảm chênh lệch số lần xuất hiện Giảm theo hàm căn wi,j = Tránh giá trị “0” và giảm theo hàm loga: wi,j = 1+log(fi,j)Nghịch đảo tần số xuất hiện trong tập văn bản: IDFTừ xuất hiện trong nhiều văn bản thì trọng số trong 1 văn bản sẽ thấpwi = Trong đó m = |D|, dfi là |d  D: wi xuất hiện trong d}14Phương pháp TFIDFTích hợp TF và IDFDạng đơn giản: wi,j = fi,j* dfi /mDạng căn chỉnh theo hàm loga	wi,j Ngoài ra, có một số dạng tích hợp trung gian khác15Mô hình biểu diễn văn bảnBài toánInput: Cho tập văn bản miền ứng dụng D = {dj }, tập đặc trưng được chọn biểu diễn văn bản V = {wi }, ma trân trọng số W = (wi,j) .Output: Tìm biểu diễn của các văn bản dj D.Một số mô hìnhMô hình BooleanMô hình không gian vectorMô hình túi các từ (Mô hình xác suất)Các mô hình khácMô hình BooleanTập các từ thuộc V mà xuất hiện trong văn bản16Mô hình không gian vectorNội dung chínhÁnh xạ tập tài liệu vào không gian vector n =|V| chiều.Mỗi tài liệu được ánh xạ thành 1 vector	di  (wi1, wi2, , win) Độ đo tương tự nội dung văn bảnChuẩn hóa vector: đưa về độ dài 1Độ “tương tự nội dung” giữa hai văn bản  độ tương tự giữa hai vectorMột số phương án sơ khai “các thành phần giống nhau”, “nghịch đảo khoảng cách”, ..Phổ biến là tính độ đo cosin của góc giữa hai vector: không yêu cầu chuẩn hóa17Mô hình không gian vector18Khaled Shaban (2006). A semantic graph model for text representation and matching in document mining, PhD Thesis, University of Waterloo, CanadaMô hình xác suấtGiả thiết chínhMô hình xác suất: cặp (Y, P) với Y là tập quan sát được và P là mô hình xác suất trên Y (có thể coi Y là quan sát được các từ/đặc trưng trên văn bản).Các từ xuất hiện trong văn bản thể hiện nội dung văn bảnSự xuất hiện của các từ là độc lập lẫn nhau và độc lập ngữ cảnhDạng đơn giản: chỉ liệt kê từ, dạng chi tiết: liệt kê từ và số lần xuất hiệnLưu ý: Các giả thiết về tính độc lập không hòan toàn đúng (độc lập lẫn nhau, độc lập ngữ cảnh) song mô hình thi hành hiệu quả trong nhiều trường hợp.Độ đo tương tự nội dung văn bảnSo sánh hai túi từ19Mô hình túi từ (bag-of-word)20Dunja Mladenic' (1998). Machine Learning on Non-homogeneous, Distributed Text Data. PhD. Thesis, University of Ljubljana, Slovenia.Mô hình biểu diễn LSI và theo phân cụmGiới thiệuTồn tại nhiều phương pháp biểu diễn khácTồn tại nhiều phiên bản cho một phương phápGần đây có một số phương pháp mớiHai phương pháp phổ biến: LSI và theo phân cụmLưu ý: Giá phải trả khi tiền xử lý dữ liệuMô hình phân cụmPhân cụm các từ trong miền ứng dụng: ma trận trọng sốThay thếtừ bằng cụm chứa nóMô hình biểu diễn LSILSI: Latent Semantic Indexing biểu diễn ngữ nghĩa ẩnNâng mức ngữ nghĩa (trừu tượng) của đặc trưngRút gọn tập đặc trưng, giảm số chiều không gian biểu diễnKhông gian từ khóa  không gian khái niệm (chủ đề).Phương pháp chuyển đổiMa trận trọng số  ma trận hạng nhỏ hơn Phép biến đổi đó Từ khóa  khái niệm. Thay thế biểu diễn.21Lựa chọn từ trong biểu diễn văn bảnLoại bỏ từ dừngNhững từ được coi là không mạng nghĩaCó sẵn trong ngôn ngữĐưa về từ gốcCác ngôn ngữ có biến dạng từ: Anh, NgaThay từ biến dạng về dạng gốcChon đặc trưng n-gramCác âm tiết liền nhau n-gramUni-gram: chỉ chứa một âm tiếtBigram: chứa không quá 2 âm tiếtTrigram: chứa không quá 2 âm tiếtN-gram: Thường không quá 4 gramMột số đặc trưngChính xác hơn về ngữ nghĩaTăng số lượng đặc trưngTăng độ phức tạp tính toán22Một số đô đo cho lựa chọn đặc trưngGiới thiệu chungLựa chọn đặc trưng: lợi thế chính xác, lợi thể tốc độ hoặc cả haiCác độ đo giúp khẳng định lợi thếPhân nhóm độ đoHai nhóm: theo tần số và theo lý thuyết thông tinMột số độ đo điển hìnhXem hai trang sau23Một số đô đo cho lựa chọn đặc trưng24Một số đô đo cho toàn bộ các lớp25Thu gọn đặc trưngGiới thiệu chung“Tối ưu hóa” chọn tập đặc trưngSố lượng đặc trưng nhỏ hơnHy vọng tăng tốc độ thi hànhTăng cường chất lượng khai phá văn bản. ? Giảm đặc trưng đi là tăng chất lượng: có các đặc trưng “nhiễu”Hoặc cả hai mục tiêu trên Hai tiếp cận điển hình Tiếp cận lọcTiếp cận bao góiVới dữ liệu văn bảnTập đặc trưng: thường theo mô hình vectorTính giá trị của từng đặc trưng giữ lại các đặc trưng được coi là “tốt”.26Tiếp cận tổng quát: lọcTiếp cận lọcĐầu vào: Không gian tập các tập đặc trưngĐầu ra: Tập con đặc trưng tốt nhấtPhương phápDò tìm “cải tiến” bộ đặc trưng: Thuật toán tối ưu hóaĐánh giá chất lượng mô hình: độc lập với thuật toán học máy27Tiếp cận bao gói tổng quátTiếp cận bao góiĐầu vào: Không gian tập các tập đặc trưngĐầu ra: Tập con đặc trưng tốt nhấtPhương phápDò tìm “cải tiến” bộ đặc trưng: Thuật toán tối ưu hóaĐánh giá chất lượng mô hình: Dùng chính thuật toán học để đánh giá28Thu gọn đặc trưng văn bản textThu gọn đặc trưngĐầu vào: Vector đặc trưngĐầu ra: k đặc trưng tốt nhấtPhương pháp (lùi)Sắp xếp các đặc trưng theo độ “tốt” (để loại bỏ bớt)Tính lại độ “tốt” của các đặc trưngChọn ra k-đặc trưng tốt nhấtCác kiểu phương phápTiến / Tiến bậc thang (có xem xét thay thế khi tiến)Lùi / Lùi bậc thang (có xem xét thay thế khi lùi)29Thu gọn đặc trưngphân lớp text nhị phânMột thuật toán lựa chọn đặc trưng textV: Bảng từ vựng có được từ tập văn bản Dc: lớp đang được quan tâmgiá trị A(t,c): một trong ba thủ tục tính toánBa kiểu thủ tục tính toán A(t,c)Thông tin tương hỗLựa chọn đặc trưng theo khi-bình phương (chi-square)Lựa chọn đặc trưng theo tần suất30Thu gọn đặc trưng: thông tin tương hỗCông thức MI (Mutual Information)Biến ngẫu nhiên U: từ khóa t xuất hiện/không xuất hiệnBiến ngẫu nhiên c: tài liệu thuộc/không thuộc lớp cƯớc lượng cho MIVí dụ: Bộ dữ liệu Reuter-RCV1Lớp poultry, từ khóa export3110 đặc trưng tốt nhất cho 6 lớp32Bộ dữ liệu Reuter-RCV1Thống kê khi-bình phương và tần sốThống kê khi-bình phươngCông thức xác suất: et, ec : như MI, các biến E là kỳ vọng, N là tần số quan sát được từ tập tài liệu DƯớc lượng cho MI: các giá trị N như MITần sốMột ước lượng xác suất33Thu gọn đặc trưng phân lớp text đa lớpBài toán phân lớp đa lớpTập C = {c1, c2, , cn)Cần chọ đặc trưng tốt nhất cho bộ phân lớp đa lớpPhương pháp thống kê khi-bình phươngMỗi từ khóaLập bảng xuất hiện/không xuất hiện các đặc trưng trong lớp văn bảnTính giá trị thống kê khi-bình phươngChọn k đặc trưng (từ khóa) Phương pháp lựa chon từng lớpTính bộ đặc trưng tốt cho từng phân lớp thành phầnKết hợp các bộ đặc trưng tốtTính toán giá trị kết hợp: trung bình (có trọng số xuất hiện) khi kết hợpChọn k-đặc trưng tốt nhất sau khi tính toán kết hợp34Biểu diễn WebĐồ thị WebWeb có cấu trúc đồ thịĐồ thị Web: nút  trang Web, liên kết ngoài  cung (có hướng, vô hướng).Bản thân trang Web cũng có tính cấu trúc cây (đồ thị)Một vài bài toán đồ thị WebBiểu diễn nội dung, cấu trúcTính hạng các đối tượng trong đồ thị Web: tính hạng trang, tính hạng cung..Nghiên cứu về đồ thị Web (xem trang sau)Đồ thị ngẫu nhiênTính ngẫu nhiên trong khai phá WebWWW có tính ngẫu nhiên: mới, chỉnh sửa, loại bỏHoạt động con người trên Web cũng có tính ngẫu nhiên Là nội dung nghiên cứu thời sự 35Một sơ đồ biểu diễn tài liệu Web36Dunja Mladenic' (1998). Machine Learning on Non-homogeneous, Distributed Text Data. PhD. Thesis, University of Ljubljana, Slovenia.Một sơ đồ biểu diễn tài liệu Web37Dunja Mladenic' (1998). Machine Learning on Non-homogeneous, Distributed Text Data. PhD. Thesis, University of Ljubljana, Slovenia.Một sơ đồ biểu diễn tài liệu Web38