Chương 1 - TONG QUAN 1. Lý do chọn đề tài Trong đại số tuyến tính, ma trận thưa là ma trận rất đặc biệt, đó là ma trận mà hầu hết các phần tử đều bằng 0, rất thích hợp dé biểu diễn ma trận Terms — Document, trong đó câu truy van chứa một số từ khóa. Bên cạnh đó SVD, thuật toán phân rã trị suy biế , là một thuật toán rất mạnh dùng trên ma trận kiếm tài liệu tương ứng với biểu diễn ma trận Terms — Document SVD, còn được hiểu với tên là Singular Value Decomposition, là một thuật toán không mới, tuy nhiên SVD có lịch sử phát triển từ lâu đời và không ngừng được áp dụng rộng rãi cho đến ngày nay. Mục tiêu, đối tượng và phạm vi nghiên cứu + Mục tiêu của đề tài : e _ Nghiên cứu phương pháp phân rã trị suy biến kích thước ma trận lớn và minh hoạ trong tìm kiếm tài liệu.
e Ap dụng dé xây dựng công cụ tìm kiếm tài liệu trực tuyến tại thư viện trường DH Kinh tế - Luật e Ap dụng dé xây dựng công cụ phát hiện sao chép tài liệu © Ap dụng dé xây dựng công cụ tìm kiếm các Website theo từ khóa + Đối tượng nghiên cứu : Ma trận thưa, trị riêng, vector riêng và phân rã trị suy biến + Phạm vi nghiên cứu : Các thuật toán liên quan đến không gian Vector, ma trận thưa, thuật toán phân rã trị suy biến SVD có thể ứng dụng cho bài toán tìm tài liệu, xử lý tín hiệu, nén dữ liệu, nhận dang. Phương pháp nghiên cứu Đề tài vận dụng các phương pháp như phương pháp nghiên cứu định tính, phương pháp nghiên cứu định lượng, quan sát, xử lý thông tin, so sánh, phân tích tổng hợp. Đóng góp mới và ý nghĩa của đề tài Hiện thực hóa thuật toán phân rã trị suy biến trên ma trận thưa áp dụng cho tìm kiếm hiệu quả tài liệu tại thư viện trường, nơi tác giả đang công tác. Chương 2 - CƠ SỞ LÝ THUYET 2.
Khái niệm Vector Vector thường được ký hiệu bằng một ký tự chữ thường với một mũi tên bên trên ky tự đó, ví dụ y. Những con số chứa trong Vector được gọi là các thành phan, và số các thành phan bằng với số chiều của Vector. Chúng ta dùng một chỉ số dưới bên cạnh tên của Vector đề đề cập đến thành phần ở vị trí tương ứng. Ví dụ bên dưới, x là một Vector có số chiều là 6 (theo [11, tr 3]) 4 3 st II 2 = 8 2 5 7 Các Vector có thé được trình bày tương đương theo chiều ngang dé tiết kiệm không gian, chẳng hạn = (4,3,2,8,5,7) là một Vector tương đương với Vector ở trên 2.
Chiều dài Vector Chiều dài Vector được xác định bằng căn bậc 2 của tổng bình phương tất cả các thành phan của Vector đó (theo [11, tr 5]) Nếu vià một Vector, chiều dài của nó được ký hiệu là | ỳ |, một cách ngắn gọn hơn, ta ký hiệu như sau : trong đó vj; là thành phần của vector ở vị trí i của vector v Ví dụ nếu ve (2,9,3,7,3,4,5,2,8,2,6,11) thì lols VP40 +P 4743 4445424842 46 +10 = 20. Phép cộng hai Vector Cộng hai vector đồng nghĩa với việc cộng mỗi thành phần vector thứ nhất với mỗi thành phần của vector thứ hai ở các vị trí tương ứng (Hai vector có cùng số lượng thành phần, tức cùng số chiều) (theo [11, tr 6]) Ví dụ x = (8,6,3,5,-3,7,8,5,2-9)5 y = (-5,3,6,7,4,-8,3,2,6-1) Hai vector này có cùng số lượng thành phan là 10 thì + F = (8-5,6+3,3+6,5+7,-3+4,7-8,8+3,5+2,2+6,-9- 1) = (3,9,9,12,1,1,11,7,8,-10) Tổng quát hơn nếu x = (Xị, X, Xạ::. Xn) 3» = (VI, Yo, Y3:.: Yo) thi x + y = (K+ VI, Xo Yas Xot Vy. Tích vô hướng Vector với một số thực Tích vô hướng của một số thực với một vector là nhân lần lượt số thực đó với từng thành phần của vector đó kết quả là một vector (theo [11, tr 6]) Vi dụ cho số thực a = 1.8) Một cách tổng quát, nếu a là một số thực, x = (x), Xa, Xạ.
Xa) là một vector thì Bos =(a*Xi, a*X;, a*X. Tích vô hướng hai Vector Tích vô hướng 2 vector được xác định bằng tổng các phép nhân mỗi thành phần vector thứ nhất với mỗi thành phần của vector thứ hai ở các vị trí tương ứng (Hai vector có cùng số lượng thành phan, tức cùng số chiều) (theo [11, tr 7]) Ví dụ x = (5,6,3,5,-3,7,6,5,2,-2) ; y = (-1,3,6,7,3,-2,3,2,4,-1) Hai vector nay có cùng số lượng thành phan là 10 thì Tích vô hướng của vector x VỚi vector y được ký hiệu bằng (x,y) hay x y ky = 5S*(-1) + 6*3 + 3*6 + 5*7 4(-3)*3 + 7*(-2) + 6*3 + 5*2 + 2*4 +(-2)*(-1) =-5 + 18+ 18 + 35 -9-14+ 18+ 10+8+2=81 10 2. Tính trực giao của Vector Hai vector được gọi là trực giao với nhau nếu tích vô hướng của chúng bằng 0. Trong không gian 2 chiều điều này tương đương với việc chúng vuông góc với nhau hay góc giữa hai vector là 90° (theo [11, tr 7]) Ví dụ vector F = (5,2,-5,2,6,2,-2,-1) ; vector y = (-3,4,5,2,6,3,5,4).
Hai vector F và y là trực giao với nhau vi x. Vector trực giao (Vector đơn vị) Vector trực giao (hay còn gọi là vector đơn vị) là một vector có chiều dài là 1. Bất kỳ một vector có chiều dài dương (>0) có thể được trực giao hóa bằng cách chia mỗi thành phan trong vector cho chiều đài của vector đó. Ví dụ với vectorx = (1,2,4,6,7,3,5,2),IxI= VI? +2? +4? +6? +72 +32 +5 +2? =12 Khi đó » `.
5 là một vector trực giao vì 12632124126 = fp +q2) +q2 + > 1y Ố v2 242 +q@2) +g +2) +(ŒS) 72,22. Vector trực chuẩn Những vector đơn vị mà trực giao với nhau (vuông góc với nhau) được gọi là các vector trực chuẩn (theo [11, tr 7]) Ví dụ 124), (26H) x=( wir "S557 like Vos V65" Jos’ 65 F và yla hai vector trực chuân với nhau bởi : x là vector đơn vị với | xl = 11 y là vector don vị với | yl = ( Ti. Lý thuyết Ma trận (đặc biệt là ma trận thưa) Một ma trận thì tương tự như một bang dữ liệu, giống như hình 2.1, trình bày tổng số huy chương vàng, bạc, đồng của 10 quốc gia (country). HE United states of America 46 29 29 104 [ll People’s Republic of China 38 2 23 88 SHE Great Britain 29 7 19 65 IE Russian Federation 24 26 32 82 Republic of Korea 13 8 7 28 2 Germany +1 +9 14 44 BE France 11 11 12 34 RE nay 8 9 11 28 = hungary 8 4 5 17 8Ñ Austraiia V/ 16 12 35 Hình 2.1: Bảng xếp hạng huy chương Olympic 2012 Nguồn : http://www.vn Một bảng chứa các dòng (danh sách theo chiều ngang liên quan đến từng quốc gia, và các cột (danh sách theo chiều dọc liên quan đến số lượng từng loại huy chương và cột cuối cùng là tổng số huy chương các loại của một quốc gia) Chúng ta có thể biểu diễn bảng dữ liệu trên bằng ma trận như sau : 12 46 29 29 104] 38 27 23 88 29 17 19 65 24 26 32 82 13 8 7 28 11 19 14 44 11 11 12 34 8 9 11 28 8 4 5 17 7 16 12 35 Kích cỡ của ma trận được thé hiện dưới đạng số hàng nhân với số cột.
Với ma trận ở trên chúng ta viết là ma trận 10 x 4. Thông thường để biểu thị tên ma trận người thường dùng kí hiệu chữ hoa, ví dụ như ma trận A. Số dong lớn nhất của ma trận được ký hiệu bằng m, số cột lớn nhất của ma trận được ký hiệu bằng n. Các phần tử của ma trận (còn gọi là các thành phần của ma trận) được ký hiệu bằng một ky tự chữ thường đi kèm theo đó là chỉ số dong và chỉ số cột.
Chẳng hạn, trong ma trận ở trên số 32 nằm ở hàng 4 và cột 3, một cách khác chúng ta có thể biểu diễn phan tử 32 là a¿s = 32. Tổng quát hơn, nếu một phan tử ở hàng ¡ và cộtj được biểu diễn bằng aj và được gọi là phan tử ij hay thành phan ij 2. Định nghĩa ma trận Đặt m, n là hai số nguyên dương = 1. Đặt aj là một day các số thực ;I=1,2.n Một dãy các số thực Gy a,, | là một ma trận mxn và các số ai là các phần tử của A.
a li a nj a Day số A() = (an, ain. in) là hang thứ i của ma tran A. Day sé AG) = (aij, aạj. amj) là cột thứj của ma tran A Xét trường hợp đặc biệt khi ma trận là ma trận thưa : Ma trận có các phần tử chủ yếu là các phần tử bằng 0.
13 Ví dụ một ma trận thưa : Ta xét các tài liệu sau : Tài liệu I : Shipment of gold damaged in a fire Tai liêu 2 : Delivery of silver arrived in a silver truck Tài liệu 3 : Shipment of gold arrived in a truck Ma trận thưa mô tả số lượng từng từ khóa có trong từng tài liệu (Hình 2. Garcia trong tài liệu [6, tr 1] , các từ khóa theo hình 2.2 được xây dựng như sau: + Không phớt lờ các Stop word (các từ quá phô biến) - tham khảo [21] + Chỉ sử dụng từ đơn lẻ (bỏ qua các cụm từ có nghĩa) + Tập hợp các từ khóa là các từ đơn lẻ khác nhau từng đôi một lấy trong 3 tài liệu trên [my |Từkhóa Ps : P? P? vân j|L J 1 TERyPS Jel—=- — l e = - — l o = - e Hình 2.2: Ma trận thưa biểu diễn ma trận từ khóa — tài liệu Nguồn : Tài liệu [6] và chương trình ví dụ về SVD của tác giả 2. Ma trận vuông Một ma trận được gọi là vuông nếu nó có cùng số đỏng và số cột. Ma trận vuông cấp n được kí hiệu là A„xạ với A là tên của ma trận, n là kích cỡ cua ma trận đó (n là số nguyên >1) Vi dụ một ma trận vuông cấp 12 14 [l0 202 6 7 5 -7 6 5 -6 00 6 78007 7 6 5 478 5 7 6989 5 48 7 6 5 4 6 575 3 7259 90 0 00207 8 6 5 4 110 Ac-ll2 42445 4 3 4 3 22 3.3 Phép chuyển vị của ma trận Ma trận chuyển vị của một ma trận là một ma trận được tạo ra bằng cách đảo hàng thành cột, như vậy dòng | trở thành cột 1, dòng 2 trở thành cột 2.dòng n trở thành cột n.
Phép chuyển vị của ma trận được kí hiệu tên ma trận đi kèm với chữ T (HOA) viết ở đạng chỉ số trên.