LỜI NÓI ĐẦU
Trong những năm gần đây, sự phát triển mạnh mẽ của CNTT và ngành công
nghiệp phần cứng đã làm cho khả năng thu thập và lưu trữ thông tin của các hệ
thống thông tin tăng nhanh một cách chóng mặt. Bên cạnh đó việc tin học hoá một
cách ồ ạt và nhanh chóng các hoạt động sản xuất, kinh doanh cũng như nhiều lĩnh
vực hoạt động khác đã tạo ra cho chúng ta một lượng dữ liệu lưu trữ khổng lồ. Với
một lượng thông tin như vậy thì vấn đề đặt ra là phải làm sao sử dụng chúng vào
đúng mục đích và hiệu quả nhất thì cũng là một vấn đề đặt ra hiện nay. Mặt khác,
trong môi trường cạnh tranh , người ta ngày càng cần có nhiều thông tin với tốc độ
nhanh để trợ giúp việc ra quyết định và ngày càng có nhiều câu hỏi mang tính chất
định tính cần phải trả lời dựa trên một khối lượng dữ liệu khổng lồ đã có. Với
những lý do như vậy, cần phải có các công cụ hỗ trợ để giúp cho việc tìm kiếm
thông tin được nhanh và hiệu quả. Vì vậy mục tiêu của luận văn này nhằm tìm hiểu
và xây dựng một hệ thống tìm kiếm thông tin cụ thể là tìm kiếm tài liệu văn bản trên
cơ sở phân cụm dữ liệu. Nhằm đáp ứng nhu cầu cấp thiết của thời đại.
Bố cục của luận văn gồm các phần sau:
+ CHƯƠNG 1 - TỔNG QUAN: Giới thiệu chung về hệ thống thông tin đa
phương tiện.
+ CHƯƠNG 2 - HỆ TÌM KIẾM THÔNG TIN: Giới thiệu về hệ thống tìm
kiếm thông tin (IR), sự khác nhau giữa hệ thống tìm kiếm thông tin và các hệ thống
thông tin khác, các mô hình th ường gặp trong hệ thống tìm kiếm thông tin.
+ CHƯƠNG 3 - KỸ THUẬT PHÂN CỤM DỮ LIỆU VÀ ỨNG DỤNG :
Khái quát chung v phân cụm, các kiểu dữ liệu trong phân cụm và ứng dụng kỹ
ề
thuật phân cụm dữ liệu trong tìm kiếm thông tin.
+ CHƯƠNG 4 - CHƯƠNG TRÌNH DEMO: Cài đặt một chương trình tìm
kiếm thông tin trên cơ sở lý thuyết đã trình bày.
+ KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN: Trình bày các k quả đạt được
ết
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
và nêu phương hướng phát triển của đề án trong tương lai.
+ TÀI LIỆU THAM KHẢO
MỤC LỤC
LỜI NÓI ĐẦU . 4
CHƯƠNG 1: TỔNG QUAN 7
1.1. ĐẶT VẤN ĐỀ . 7
1.2. HỆ THỐNG THÔNG TIN ĐA PHƯƠNG TIỆN: 8
1.2.1. Khái niệm về đa phương tiện 8
1.2.2. Media .9
1.2.3. Multimedia . 10
1.2.4. CSDL và Hệ quản trị CSDL . 10
1.2.5. Truy tìm thông tin tài liệu văn bản 10
1.2.6. Chỉ mục và truy tìm đa phương tiện 11
1.2.7. Trích chọn đặc trưng, Biểu diễn nội dung và Xây dựng chỉ mục .11
1.3. SỰ CẦN THIẾT PHẢI CÓ MIRS . 11
1.3.1. Mô tả sơ lược dữ liệu MM và các tính chất của chúng 12
1.3.2. Hệ thống IR và vai trò của chúng trong truy tìm đa phương tiện .13
1.3.3. Tích hợp truy tìm và chỉ số hóa thông tin đa phương tiện . 13
1.4. KHÁI QUÁT VỀ MIRS . 14
1.5. KHẢ NĂNG MONG ĐỢI VÀ CÁC ỨNG DỤNG CỦA MIRS . 15
CHƯƠNG 2: HỆ TÌM KIẾM THÔNG TIN . 18
2.1. KHÁI QUÁT CHUNG VỀ TÌM KIẾM THÔNG TIN 18
2.1.1. Hệ thống truy tìm thông tin – IR . 20
2.1.2. Các thành phần của một hệ tìm kiếm thông tin . 24
2.1.3. So sánh hệ thống IR với các hệ thống thông tin khác 25
2.1.4. Các hệ tìm kiếm văn bản được đánh giá cao hiện nay 27
2.2. HỆ TÌM KIẾM THÔNG TIN 28
2.2.1. Kiến trúc của hệ tìm kiếm thông tin. . 28
2.2.2. Một số mô hình để xây dựng một hệ tìm kiếm thông tin . 30
2.2.3. Các bước để xây dựng hệ thống truy tìm thông tin – IR 38
2.3. LẬP CHỈ MỤC TÀI LIỆU 39
2.3.1. Khái quát về hệ thống lập chỉ mục 40
2.3.2. Cấu trúc tệp mục lục . 41
2.3.3. Phương pháp lập chỉ mục . 45
2.3.4. Lập chỉ mục tự động cho tài liệu tiếng Anh 47
2.3.5. Lập chỉ mục cho tài liệu tiếng Việt . 48
2.4. THƯỚC ĐO HIỆU NĂNG 51
CHƯƠNG 3: KỸ THUẬT PHÂN CỤM DỮ LIỆU VÀ ỨNG DỤNG 53
3.1. KHÁI QUÁT VỀ PHÂN CỤM DỮ LIỆU . 53
3.1.1. Khái niệm: 53
3.1.2. Mục tiêu của phân cụm dữ liệu trong tìm kiếm thông tin 54
3.1.3. Các yêu cầu của phân cụm 56
3.2. CÁC KIỂU DỮ LIỆU TRONG PHÂN CỤM . 58
3.2.1. Phân loại kiểu dữ liệu dựa trên kích thước miền . 59
3.2.2. Phân loại kiểu dữ liệu dựa trên hệ đo 59
3.3. CÁC PHÉP ĐO ĐỘ TƯƠNG TỰ VÀ KHOẢNG CÁCH ĐỐI VỚI CÁC
KIỂU DỮ LIỆU . 60
3.3.1. Khái niệm tương tự và phi tương tự 60
3.3.2. Thuộc tính khoảng 61
3.3.3. Thuộc tính nhị phân 65
3.3.4. Thuộc tính định danh 66
3.3.5. Thuộc tính có thứ tự . 67
3.3.6. Thuộc tính tỉ lệ . 67
3.4. MỘT VÀI KỸ THUẬT TIẾP CẬN TRONG PHÂN CỤM DỮ LIỆU . 68
3.4.1. Phương pháp phân cụm phân hoạch 68
3.4.2. Phương pháp phân cụm phân cấp . 74
3.4.3. Ứng dụng trong tìm kiếm văn bản đa phương tiện 78
CHƯƠNG 4: CHƯƠNG TRÌNH DEMO 81
4.1. MỤC TIÊU CỦA HỆ THỐNG TÌM KIẾM VĂN BẢN: . 81
4.2. CHỨC NĂNG CỦA HỆ THỐNG 81
4.3. CÀI ĐẶT CHƯƠNG TRÌNH 82
4.3.1. Lập chỉ mục 82
4.3.2. Tìm kiếm tài liệu 87
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN . 88
TÀI LIỆU THAM KHẢO 90
91 trang |
Chia sẻ: maiphuongtl | Lượt xem: 1549 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Luận văn Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
khi
truy tìm, véctơ truy vấn được so sánh với lần lượt 11 trọng tâm cụm. Nếu tìm thấy
trọng tâm cụm 2 gần giống véctơ truy vấn nhất thì ta tính khoảng cách giữa véctơ
truy vấn với từng véctơ đặc trưng trong cụm 2. Tổng số tính toán khoảng cách đòi
hỏi phải nhỏ hơn nhiều tổng các véctơ đặc trưng trong CSDL.
Trong phương pháp truy tìm trên cơ sở cụm trên đây, mức độ tương tự được
tính toán giữa câu truy vấn và từng trọng tâm và với từng véctơ đặc trưng trong cụm
lựa chọn. Khi tổng số cụm mà lớn, ta sử dụng cụm nhiều tầng để làm giảm tính toán
mức độ tương tự giữa truy vấn và trọng tâm. Các cụm tương tự nhau được nhóm để
hình thành cụm lớn hơn (super-cluster). Trong khi truy tìm, trước hết so sánh véctơ
truy vấn với trọng tâm của cụm cha sau đó so sánh với từng trọng tâm các cụm bên
trong cụm cha, cuối cùng so sánh với các véctơ đặc trưng của cụm con. Hãy xem
xét không gian đặc trưng trên hình 3.1, ta có thể hình thành cụm cha n hư hình 3.2.
Trong khi truy tìm, so sánh véctơ truy vấn với từng trọng tâm của 4 cụm cha. Nếu
tìm thấy trọng tâm của cụm cha 1 là gần véctơ truy vấn nhất, hãy so sánh véctơ truy
vấn với ba trọng tâm cụm con trong cụm cha 1. Trong thí dụ cụm hai mức này, tổng
số tính toán khoảng cách đòi hỏi giữa véctơ truy vấn và trọng tâm (của các cụm cha
và cụm con) là 7 (4+3), nhỏ hơn 11 tính toán khi sử dụng cụm một tầng.
Cụm 1
Cụm 2
Cụm 3
Trọng tâm cụm
Véctơ đặc trưng
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
56
Hình 3.2: Hình thành cụm cha
Cụm không chỉ làm truy tìm hiệu quả mà còn làm dễ dàng cho việc duyệt và
dẫn đường. Với duyệt và dẫn đường, một mục đại diện mà có véctơ đặc trưng gần
trọng tâm cụm của nó thì được hiển thị cho mỗi cụm. Nếu người sử dụng quan tâm
đến mục đại diện thì họ có thể quan sát các mục khác trong cụm.
Các kỹ thuật cụm được sử dụng chung với các cấu trúc dữ liệu để tìm kiếm
hiệu quả hơn. Các mục tương tự được nhóm thành cụm. Trọng tâm các cụm hoặc/và
các mục trong mỗi cụm được tổ chức nhờ cấu trúc dữ liệu nào đó để tìm kiếm hiệu
quả.
3.1.3. Các yêu cầu của phân cụm
Phân cụm là một thách thức trong lĩnh vực nghiên cứu ở chỗ những ứng
dụng tiềm năng của chúng được đưa ra ngay chính trong những yêu cầu đặc biệt của
chúng.
Có khả năng mở rộng: Nhiều thuật toán phân cụm làm việc tốt với những
tập dữ liệu nhỏ chứa ít hơn 200 đối tượng, tuy nhiên, một CSDL lớn có thể chứa tới
hàng triệu đối tượng. Việc phân cụm với một tập dữ liệu lớn có thể làm ảnh hưởng
tới kết quả. Vậy làm cách nào để chúng ta có thể phát triển các thuật toán phân cụm
Cụm 1
Cụm 2
Cụm 3
Trọng tâm cụm con
Véctơ đặc trưng
Trọng tâm cụm cha
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
57
có khả năng mở rộng cao đối với các CSDL lớn?
Khả năng thích nghi với các kiểu thuộc tính khác nhau: Nhiều thuật toán
được thiết kế cho việc phân cụm dữ liệu có kiểu khoảng (kiểu số). Tuy nhiên, nhiều
ứng dụng có thể đòi hỏi việc phân cụm với nhiều kiểu dữ liệu khác nhau, như kiểu
nhị phân, kiểu tường minh (định danh - không thứ tự), và dữ liệu có thứ tự hay dạng
hỗn hợp của những kiểu dữ liệu này.
Khám phá các cụm với hình dạng bất kỳ : Nhiều thuật toán phân cụm xác
định các cụm dựa trên các phép đo khoảng cách Euclidean và khoảng cách
Manhattan. Các thuật toán dựa t rên các phép đo như vậy hướng tới việc tìm kiếm
các cụm hình cầu với mật độ và kích cỡ tương tự nhau. Tuy nhiên, một cụm có thể
có bất cứ một hình dạng nào. Do đó, việc phát triển các thuật toán có thể khám phá
ra các cụm có hình dạng bất kỳ là một việc làm quan trọng.
Tối thiểu lượng tri thức cần cho xác định các tham số đầu vào: Nhiều thuật
toán phân cụm yêu cầu người dùng đưa vào những tham số nhất định trong phân
tích phân cụm (như số lượng các cụm mong muốn). Kết quả của phân cụm thường
khá nhạy cảm với các tham số đầu vào. Nhiều tham số rất khó để xác định, nhất là
với các tập dữ liệu có lượng các đối tượng lớn. Điều này không những gây trở ngại
cho người dùng mà còn làm cho khó có thể điều chỉnh được chất lượng của phân
cụm.
Khả năng thích nghi với dữ liệu nhiễu: Hầu hết những CSDL thực đều
chứa dựng dữ liệu ngoại lai, dữ liệu lỗi, dữ liệu chưa biết hoặc dữ liệu sai. Một số
thuật toán phân cụm nhạy cảm với dữ liệu như vậy và có thể dẫn đến chất lượng
phân cụm thấp.
Ít nhạy cảm với thứ tự của các dữ li ệu vào: Một số thuật toán phân cụm
nhạy cảm với thứ tự của dữ liệu vào, ví dụ như với cùng một tập dữ liệu, khi được
đưa ra với các thứ tự khác nhau thì với cùng một thuật toán có thể sinh ra các cụm
rất khác nhau. Do đó, việc quan trọng là phát triển các thuật toán mà ít nhạy cảm
với thứ tự vào của dữ liệu.
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
58
Số chiều lớn: Một CSDL hoặc một kho dữ liệu có thể chứa một số chiều
hoặc một số các thuộc tính. Nhiều thuật toán phân cụm áp dụng tốt cho dữ liệu với
số chiều thấp, bao gồm chỉ từ hai đến 3 chiều. Người ta đánh giá việc phân cụm là
có chất lượng tốt nếu nó áp dụng được cho dữ liệu có từ 3 chiều trở lên. Nó là sự
thách thức với các đối tượng dữ liệu cụm trong không gian với số chiều lớn, đặc
biệt vì khi xét những không gian với số chiều lớn có thể rất thưa và có độ nghiêng
lớn.
Phân cụm ràng buộc : Nhiều ứng dụng thực tế có thể cần thực hiện phân
cụm dưới các loại ràng buộc khác nhau. Giả sử rằng công việc của bạn là lựa chọn
vị trí cho một số trạm rút tiền tự động ở một thành phố. Để quyết định dựa trên điều
này, bạn có thể phân cụm những hộ gia đình trong khi xem xét các mạng lưới sông
và đại lộ, và những yêu cầu khách hàng của mỗi vùng như những sự ràng buộc. Một
nhiệm vụ đặt ra là đi tìm những nhóm dữ liệu có trạng thái phân cụm tốt và thỏa
mãn các ràng buộc.
Dễ hiểu và dễ sử dụng: Người sử dụng có thể chờ đợi những kết quả phân
cụm dễ hiểu, dễ lý giải và dễ sử dụng. Nghĩa là, sự phân cụm có thể cần được giải
thích ý nghĩa và ứng dụng rõ ràng. Việc nghiên cứu cách để một ứng dụng đạt được
mục tiêu là rất quan trọng, có thể gây ảnh hưởng tới sự lựa chọn các phương pháp
phân cụm.
3.2. CÁC KIỂU DỮ LIỆU TRONG PHÂN CỤM
Trong phân cụm, các đối tượng dữ liệu thường được diễn tả dưới dạng các
đặc tính hay còn gọi là thuộc tính (khái niệm “các kiểu dữ liệu” và “các kiểu thuộc
tính dữ liệu” được xem là tương đương với nhau). Các thuộc tính này là các tham số
cho giải quyết vấn đề phân cụm và sự lựa chọn chúng có tác động đáng kể đến kết
quả phân cụm. Phân loại các kiểu thuộc tính khác nhau là vấn đề cần giải quyết đối
với hầu hết các tập dữ liệu nhằm cung cấp các phương tiện thuận lợi để nhận dạng
sự khác nhau của các phần tử dữ liệu. Có hai đặc trưng để phân loại: kích thước
miền và hệ đo.
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
59
Cho một CSDL D chứa n đối tượng trong không gian k chiều; x, y, z là các
đối tượng thuộc D:
x = (x1, x2,...,xk); y = (yl, y2,..., yk); z = (zl, z2,..., zk)
Trong đó xi, yi, zi với ki ,1= là các đặc trưng hoặc thuộc tính tương ứng của
các đối tượng x, y, z; như vậy sẽ có các kiểu dữ liệu sau:
3.2.1. Phân loại kiểu dữ liệu dựa trên kích thước miền
• Thuộc tính liên tục: Nếu miền giá trị của nó là vô hạn không đếm được,
nghĩa là giữa hai giá trị tồn tại vô số giá trị khác (ví dụ, các thuộc tính màu, nhiệt độ
hoặc cường độ âm thanh,...).
• Thuộc tính rời rạc: Nếu miền giá trị của nó là tập hữu hạn, đếm được (ví
dụ, các thuộc tính số, ...); trường hợp đặc biệt của thuộc tính rời rạc là thuộc tính nhị
phân mà miền giá trị chỉ có hai phần tử (ví dụ: Yes/no, True/False, On/Off...)
3.2.2. Phân loại kiểu dữ liệu dựa trên hệ đo
• Thuộc tính định danh: Là dạng thuộc tính khái quát hóa của thuộc tính nhị
phân, trong đó miền giá trị là rời rạc không phân biệt thứ tự và có nhiều hơn hai
phần tử. Nếu x và y là hai đối tượng thuộc tính thì chỉ có thể xác định là x ≠ y hoặc
x = y.
• Thuộc tính có thứ tự: Là thuộc tính định danh có thêm tính thứ tự , nhưng
chúng không được định lượng. Nếu x và y là hai thuộc tính thứ tự thì có thể xác
định là x ≠ y hoặc x = y hoặc x > y hoặc x < y.
• Thuộc tính khoảng: Để đo các giá trị theo xấp xỉ tuyến tính, với thuộc tính
khoảng có thể xác định một thuộc tính là đứng trước hoặc đứng sau thuộc tính khác
với một khoảng là bao nhiêu. Nếu xi > yi thì có thể nói x cách y một khoảng xi - yi
tương ứng với thuộc tính thứ i.
• Thuộc tính tỉ lệ: Là thuộc tính khoảng nhưng được xác định một cách tương
đối so với điểm mốc đầy ý nghĩa.
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
60
Trong các thuộc tính trình bày ở trên, thuộc tính định danh và thuộc tính có
thứ tự gọi chung là thuộc tính hạng mục, còn thuộc tính khoảng và thuộc tính tỉ lệ
được gọi là thuộc tính số.
Đặc biệt, còn có dữ liệu không gian là loại dữ liệu có thuộc tính số khái quát
trong không gian nhiều chiều, dữ liệu không gian mô tả các thông tin liên quan đến
không gian chứa đựng các đối tượng (ví dụ, thông tin về hình học,...). Dữ liệu
không gian có thể là dữ liệu liên tục hoặc rời rạc.
• Dữ liệu không gian liên tục: Bao chứa một vùng không gian.
• Dữ liệu không gian rời rạc: Có thể là một điểm trong không gian nhiều
chiều và cho phép xác định được khoảng cách giữa các đối tượng dữ liệu trong
không gian.
Thông thường, các t huộc tính số được đo bằng các đơn vị xác định như
kilogams hay centimeters. Tuy nhiên, việc thay đổi các đơn vị đó có ảnh hưởng đến
kết quả phân cụm (ví dụ, thay đổi đơn vị đo cho thuộc tính chiều cao từ centimeters
sang inches có thể mang lại kết quả khác nhau trong phân cụm). Để khắc phục điều
này phải chuẩn hóa dữ liệu được thực hiện bằng cách thay thế mỗi một thuộc tính
bằng thuộc tính số hoặc thêm các trọng số cho các thuộc tính.
3.3. CÁC PHÉP ĐO ĐỘ TƯƠNG TỰ VÀ KHOẢNG CÁCH ĐỐI VỚI
CÁC KIỂU DỮ LIỆU
3.3.1. Khái niệm tương tự và phi tương tự
Khi các đặc tính của dữ liệu được xác định, phải tìm cách thích hợp để xác
định “khoảng cách” giữa các đối tượng, hay là phép đo tương tự dữ liệu. Đây là các
hàm để đo sự giống nhau giữa các cặp đối tượng dữ liệu, thông thường các hàm này
hoặc là để tính độ tương tự hoặc là tính độ phi tương tự giữa các đối tượng dữ liệu.
Giá trị của hàm tính độ đo tương tự càng lớn thì sự giống nhau giữa các đối tượng
càng lớn và ngược lại còn hàm tính độ phi tương tự tỉ lệ nghịch với hàm tính độ
tương tự. Độ tương tự hoặc phi tương tự có nhiều cách để xác định, chúng thường
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
61
được đo bằng khoảng cách giữa các đối tượng. Tất cả các cách đo độ tương tự đều
phụ thuộc vào kiểu thuộc tính mà người sử dụng phân tích. Ví dụ, đối với thuộc tính
hạng mục thì không sử dụng độ đo khoảng cách mà sử dụng một hướng hình học
của dữ liệu.
Tất cả các độ đo dưới đây được xác định trong không gian metric. Bất kỳ
một metric nào cũng là một độ đo, nhưng điều ngược lại không đúng. Để tránh sự
nhầm lẫn, thuật ngữ độ đo ở đây đề cập đến hàm tính độ tương tự hoặc hàm tính độ
phi tương tự. Một không gian metric là một tập trong đó có xác định "khoảng cách"
giữa từng cặp phần tử, với những tính chất thông thường của khoảng cách hình học.
Nghĩa là, một tập X (các phần tử của nó có thể là những đối tượng bất kỳ) các đối
tượng dữ liệu trong CSDL D đề cập ở trên được gọi là một không gian metric nếu:
• Với mỗi cặp phần tử x, y thuộc X đều xác định theo một quy tắc nào đó,
một số thực δ(x, y) được gọi là khoảng cách giữa x và y.
• Quy tắc nói trên thỏa mãn hệ tính chất sau:
δ(x, y) > 0 nếu x ≠ y;
δ(x, y) = 0 nếu x = y;
δ(x, y) = δ(y, x) với mọi x, y;
δ(x, y) ≤ δ(x, z)+ δ(z, y)
Hàm δ(x, y) được gọi là một metric của không gian. Các phần tử của X được
gọi là các điểm của không gian này.
3.3.2. Thuộc tính khoảng
Một thành phần quan trọng trong thuật toán phân cụm là phép đo khoảng
cách giữa hai điểm dữ liệu. Nếu thành phần của vectơ thể hiện dữ liệu thuộc trong
cùng một đơn vị giống nhau thì nó tồn tại khoảng cách Euclidean có thể xác định
được nhóm dữ liệu tương tự. Tuy nhiên, không phải lúc nào khoảng cách Euclidean
cũng cho kết quả chính xác. Hình 3.3 minh họa ví dụ về phép đo chiều cao và chiều
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
62
ngang của một đối tượng được thực hiện trong một đơn vị vật lí giống nhau nhưng
khác nhau về tỉ lệ.
Hình 3.3: Các tỉ lệ khác nhau có thể dẫn tới các cụm khác nhau
Tuy nhiên chú ý rằng đây không chỉ là vấn đề đồ thị: vấn đề phát sinh từ
công thức toán học được sử dụng để kết hợp khoảng cách giữa các thành phần đơn
đặc tính dữ liệu vectơ vào trong một độ đo khoảng duy nhất mà có thể được sử dụng
cho mục đích phân cụm: các công thức khác nhau dẫn tới những cụm khác nhau.
Các thuật toán cần có các phép đo khoảng cách hoặc độ tương tự giữa hai đối
tượng để thực hiện phân cụm. Kiến thức miền phải được sử dụng để trình bày rõ
ràng phép đo khoảng thích hợp cho mỗi ứng dụng. Hiện nay, phép đo có nhiều mức
độ khác nhau tùy theo từng trường hợp.
Khoảng cách Minkowski được định nghĩa như sau:
1,),(
/1
1
≥
−= ∑
=
qyxyxdist
qqn
i
iiq ;
trong đó, x và y là hai đối tượng với n là số lượng thuộc tính, x = (x1, x2,…, xn) và y
= (y1, y2,…, yn); dist là kích thước của dữ liệu.
Khoảng cách Euc1idean:
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
63
( )
2
1
),( ∑
=
−=
n
i
iiq yxyxdist ;
là khoảng cách giữa hai đối tượng trong trường hợp đặc biệt q = 2.
Khoảng cách Manhattan:
−= ∑
=
n
i
iiq yxyxdist
1
),( ;
là khoảng cách trung bình giữa hai đối tượng trong trường hợp đặc biệt q = 1.
Khoảng cách Chebychev:
ii
n
i yxyxdist −= =∞ 1max),( ;
trong trường hợp q = ∞, hữu ích để định nghĩa các đối tượng phi tương tự nếu
chúng khác nhau chỉ trong một kích thước biến đổi.
Bình phương khoảng cách Euclidean.
( )
2
1
),( ∑
=
−=
n
i
iiq yxyxdist (1)
Tỉ lệ khác nhau. Giả sử các biến là tuyệt đối.
( )( ) iyxNumberyxdist /),( ≠= (2)
Khoảng cách Euclidean được sử dụng phổ biến để do độ tương tự của
khoảng cách Minkowski. Giả sử có hai trường hợp, C1 và C2, có các biến liên tục x
và y, lấy lần lượt các giá trị (x1, yl) và (x2, y2) tương ứng, có thể vẽ đồ thị hai trường
hợp trong không gian x-y (Hình 3.4):
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
64
Hình 3.4: Khoảng cách Euclidean
Tuy nhiên không có nguyên tắc tổng quát để chọn phép đo áp dụng cho bất
cứ bài toán nào. Một cách đơn giản để đo độ tương tự giữa các nhóm trong khung
tương tự bằng cách thay thế nhóm cho thuộc tính thứ i của đối tượng đo chẳng hạn
như khoảng cách Euc1idean, khoảng cách Manhattan, hoặc bình phương
Mahalanobis. Ví dụ, giả sử rằng nhóm A có vectơ trung bình [ ]anaa xxxA ,...,, 21= và
nhóm B có vectơ trung bình [ ]bnbb xxxB ,...,, 21= , thì cách đo bằng khoảng cách
Euclidean giữa hai nhóm có thể được định nghĩa là:
( )
2/1
1
2
),(
−= ∑
=
n
i
biai xxBAdist (3)
Cách tiếp cận khác để khoảng cách giữa phần tử gần nhất hoặc phần tử xa
nhất. Cách tiếp này sử dụng các thuật toán phân cụm phân cấp chẳng hạn như là liên
kết đơn và liên kết đầy đủ. Vấn đề chính với hai cách tiếp cận này giống nhau là
không cảm nhận được mâu thuẫn định lượng và không tính toán cho các yếu tố của
các phần tử trong một nhóm.
Cách tiếp cận khác, là trung bình nhóm, có thể sử dụng phép đo tương tự
giữa các nhóm. Cách tiếp cận này, sự giống nhau giữa các nhóm được đo bằng cách
lấy giá trị trung bình của tất cả các phép đo giữa các đối tượng cho từng cặp đối
tượng trong các nhóm khác nhau. Ví dụ, trung bình phi tương tự giữa nhóm A và B
có thể được định nghĩa là:
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
65
( ) nyxdBAdist
x bn
i
n
j
ii /,),(
1 1
= ∑∑
= =
(4)
trong đó, n là tổng số các đối tượng cũng cặp, n = nx × ny, nx và ny lần lượt là số các
đối tượng trong đối tượng xi và yi, và d(xi, yi) là phi tương tự của một cặp đối tượng
xi và yi, xi ∈ A, yi ∈ B. Hàm phi tương tự có thể dễ dàng chuyển đổi sang hàm tương
tự bằng cách thay đổi cho nhau.
3.3.3. Thuộc tính nhị phân
Tất cả các phép đo được định nghĩa ở trên là đa số thích hợp cho các biến
liên tục. Cho các biến danh nghĩa, “phép đo khoảng cách” là 0 nếu các trường hợp
có cùng giá trị danh nghĩa, và 1 nếu các trường hợp có các giá trị danh nghĩa khác
nhau, hoặc với độ đo tương tự 1 (nếu các trường hợp có cùng giá trị danh nghĩa) và
0 (nếu không giống nhau).
Do đó nếu xem xét p biến định danh, có thể đánh giá độ tương tự của các
trường hợp bằng số các biến mà có giá trị giống nhau. Nói chung định nghĩa với
một biến nhị phân mới từ mỗi biến danh nghĩa, bằng việc nhóm các nhãn danh
nghĩa thành hai lớp, một nhãn là 1, và nhãn khác là 0. Xây dựng và xem xét bảng
ngẫu nhiên các sự kiện có thể xảy ra và định nghĩa các thuộc tính của đối tượng x, y
bằng các biến số nhị phân 0 và 1:
Bảng 3.1: Bảng tham số
y
1 0
x
1 a b a+b
0 c d c+d
a+c b+d p=a+b+c+d
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
66
a là tổng số các thuộc tính có giá trị 1 trong hai đối tượng x, y
b là tổng số các thuộc tính có giá trị 1 trong x và giá trị 0 trong y
c là tổng số các thuộc tính có giá trị 0 trong x và giá trị 1 trong y
d là tổng số các thuộc tính có giá trị 0 trong hai đối tượng x, y
p là tổng tất các thuộc tính của hai đối tượng x, y
Các phép đo độ tương tự của các trường hợp với dữ liệu thuộc tính nhị phân
được thực hiện bằng các cách sau:
Hệ số đối sánh đơn giản:
p
dayxd +=),( ; cả hai đối tượng có vai trò
như nhau, nghĩa là chúng đối xứng và có cùng trọng số.
Hệ số Jaccard:
cba
ayxd
++
=),( ; tham số này bỏ qua số các đối sánh
0-0. Công thức này sử dụng trong trường hợp mà trọng số của các thuộc tính có giá
trị 1 của đối tượng dữ liệu cao hơn nhiều so với các thuộc tính có giá trị 0, như vậy
thuộc tính nhị phân ở đây là không đối xứng.
p
ayxd =),(
cb
ayxd
+
=),(
cba
ayxd
++
=
2
),(
Các giá trị được định nghĩa trong khoảng [0, 1] và có thể biến đổi sang độ đo
phi tương tự bằng biểu thức: ds(x, y) = 1- d(x, y).
3.3.4. Thuộc tính định danh
Độ đo phi tương tự giữa hai đối tượng x và y được định nghĩa như sau:
p
mpyxd −=),(
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
67
trong đó, m là số thuộc tính đối sánh tương ứng trùng nhau, và p là tổng số
các thuộc tính.
3.3.5. Thuộc tính có thứ tự
Phép đo độ phi tương tự giữa các đối tượng dữ liệu với thuộc tính thứ tự
được thực hiện như sau: Giả sử i là thuộc tính thứ tự có Mi giá trị (M i là kích thước
miền giá trị):
Các trạng thái Mi được sắp thứ tự như nhau: [1...Mi], có thể thay thế mỗi giá
trị của thuộc tính bằng giá trị cùng loại ri với ri ∈ {1...Mi}.
Mỗi một thuộc tính có thứ tự có các miền giá trị khác nhau, vì vậy phải
chuyển đổi chúng về cùng miền giá trị [0, 1] bằng cách thực hiện phép biến đổi sau
cho mỗi thuộc tính:
1
1)()(
−
−
=
i
f
ij
i M
rZ .
Sử dụng công thức tính độ phi tương tự của thuộc tính khoảng đối với các
giá trị )( jiZ , đây cũng chính là độ phi tương tự của thuộc tính có thứ tự.
3.3.6. Thuộc tính tỉ lệ
Có nhiều cách khác nhau để tính độ tương tự giữa các thuộc tính tỉ lệ. Một
trong những số đó là sử dụng công thức tính logarit cho mỗi thuộc tính xi, ví dụ q i =
log(xi), lúc này qi đóng vai trò như thuộc tính khoảng. Phép biến đổi logarit này
thích hợp trong trường hợp các giá trị của thuộc tính là số mũ.
Trong thực tế, khi tính độ độ tương tự dữ liệu, chỉ xem xét một phần các
thuộc tính đặc trưng đối với các kiểu dữ liệu hoặc là đánh trọng số cho tất cả các
thuộc tính dữ liệu. Trong một số trường hợp, loại bỏ đơn vị đo của các thuộc tính dữ
liệu bằng cách chuẩn hóa chúng, hoặc gán trọng số cho mỗi thuộc tính giá trị trung
bình, độ lệch chuẩn. Các trọng số này có thể sử dụng trong các độ đo khoảng cách
trên, ví dụ với mỗi thuộc tính dữ liệu đã được gán trọng số tương ứng wi (1 ≤ i ≤ k),
độ tương đồng dữ liệu được xác định như sau:
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
68
∑
=
−=
n
i
iii yxwyxd
1
2)(),(
Có thể chuyển đổi giữa các mô hình cho các kiểu dữ liệu trên, ví dụ dữ liệu
kiểu hạng mục có thể chuyển đổi thành dữ liệu nhị phân hoặc ngược lại. Thế nhưng,
giải pháp này rất tốn kém về chi phí tính toán, do vậy, cần phải cân nhắc khi áp
dụng cách thức này.
Tóm lại, tùy từng trường hợp dữ liệu cụ thể mà có thể sử dụng các mô hình
tính độ tương tự khác nhau. Việc xác định độ tương đồng dữ liệu thích hợp, chính
xác, đảm bảo khách quan là rất quan trọng, góp phần xây dựng thuật toán PCDL có
hiệu quả cao trong việc đảm bảo chất lượng cũng như chi phí tính toán.
3.4. MỘT VÀI KỸ THUẬT TIẾP CẬN TRONG PHÂN CỤM DỮ LIỆU
Các kỹ thuật phân cụm có rất nhiều cách tiếp cận và các ứng dụng trong thực
tế. Các kỹ thuật phân cụm đều hướng tới hai mục tiêu chung: chất lượng của các
cụm khám phá được và tốc độ thực hiện của thuật toán. Tuy nhiên có thể phân loại
thành từng loại cơ bản dựa trên phân loại các phương pháp. Hiện nay, các kỹ thuật
phân cụm có thể phân loại theo các cách tiếp cận chính sau:
3.4.1. Phương pháp phân cụm phân hoạch
Kỹ thuật này phân hoạch một tập hợp dữ liệu có n phần tử thành k nhóm cho
đến khi xác định số các cụm được thiết lập. Số các cụm được thiết lập là các đặc
trưng được lựa chọn trước. Phương pháp này là tốt cho việc tìm các cụm hình cầu
trong không gian Euc1idean. Ngoài ra, phương pháp này cũng phụ thuộc vào
khoảng cách cơ bản giữa các điểm để lựa chọn các điểm dữ liệu nào có quan hệ là
gần nhau với mỗi điểm khác và các điểm dữ liệu nào không có quan hệ hoặc có
quan hệ là xa nhau so với mỗi điểm khác. Tuy nhiên, phương pháp này không thể
xử lí các cụm có hình dạng kỳ quặc hoặc các cụm có mật độ các điểm dầy đặc. Các
thuật toán phân hoạch dữ liệu có độ phức tạp rất lớn khi xác định nghiệm tối ưu
toàn cục cho vấn đề PCDL, do nó phải tìm kiếm tất cả các cách phân hoạch có thể
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
69
được. Chính vì vậy, trên thực tế thường đi tìm giải pháp tối ưu cục bộ cho vấn đề
này bằng cách sử dụng một hàm tiêu chuẩn để đánh giá chất lượng của cụm cũng
như để hướng dẫn cho quá trình tìm kiếm phân hoạch dữ liệu. Với chiến lược này,
thông thường bắt đầu khởi tạo một phân hoạch ban đầu cho tập dữ liệu theo phép
ngẫu nhiên hoặc Heuristic, và liên tục tinh chỉnh nó cho đến khi thu được một phân
hoạch mong muốn, thỏa mãn ràng buộc cho trước. Các thuật toán phân cụm phân
hoạch cố gắng cải tiến tiêu chuẩn phân cụm, bằng cách tính các giá trị đo độ tương
tự giữa các đối tượng dữ liệu và sắp xếp các giá trị này, sau đó thuật toán lựa chọn
một giá trị trong dãy sắp xếp sao cho hàm tiêu chuẩn đạt giá trị tối thiểu. Như vậy, ý
tưởng chính của thuật toán phân cụm phân hoạch tối ưu cục bộ là sử dụng chiến
lược ăn tham (Greedy) để tìm kiếm nghiệm.
Thuật toán k-means
K-means là thuật toán phân cụm mà định nghĩa các cụm bởi trọng tâm c ủa
các phần tử. Phương pháp này dựa trên độ đo khoảng cách của các đối tượng dữ
liệu trong cụm. Trong thực tế, nó đo khoảng cách tới giá trị trung bình của các đối
tượng dữ liệu trong cụm. Nó được xem như là trung tâm của cụm. Như vậy, nó cần
khởi tạo một tập trung tâm các trung tâm cụm ban đầu, và thông qua đó nó lặp lại
các bước gồm gán mỗi đối tượng tới cụm mà trung tâm gần, và tính toán tại tung
tâm của mỗi cụm trên cơ sở gán mới cho các đối tượng. Quá trình lặp này dừng khi
các trung tâm hội tụ.
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
70
Hình 3.5: Các thiết lập để xác định các ranh giới các cụm ban đầu
Trong phương pháp k-means, chọn một giá trị k và sau đó chọn ngẫu nhiên k
trung tâm của các đối tượng dữ liệu. Tính toán khoảng cách giữa đối tượng dữ liệu
và trung bình mỗi cụm để tìm kiếm phần tử nào là tương tự và thêm vào cụm đó. Từ
khoảng cách này có thể tính toán trung bình mới của cụm và lặp lại quá trình cho
đến khi mỗi các đối tượng dữ liệu là một bộ phận của các cụm k.
Mục đích của thuật toán k-means là sinh k cụm dữ liệu {C1, C2,..., Ck} từ một
tập dữ liệu chứa n đối tượng trong không gian d chiều Xi = {xi1, xi2,..., xid}, i = 1 ÷
n, sao cho hàm tiêu chuẩn:
∑∑
=
∈
−=
k
i
Cx ii
mxDE
1
2 )( đạt giá trị tối thiểu,
trong đó: mi là trọng tâm của cụm Ci, D là khoảng cách giữa hai đối tượng.
Hình 3.6: Tính các toán trọng tâm của các cụm mới
Trọng tâm của một cụm là một vectơ, trong đó giá trị của mỗi phần tử của nó
là trung bình cộng của các thành phần tương ứng của các đối tượng vectơ dữ liệu
trong cụm đang xét. Tham số đầu vào của thuật toán là số cụm k, và tham số đầu ra
của thuật toán là các trọng tâm của các cụm dữ liệu. Độ đo khoảng cách D giữa các
đối tượng dữ liệu thường được sử dụng là khoảng cách Euclidean vì đây là mô hình
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
71
khoảng cách nên dễ lấy đạo hàm và xác định các cực trị tối thiểu. Hàm tiêu chuẩn
và độ đo khoảng cách có thể được xác định cụ thể hơn tùy vào ứng dụng hoặc các
quan điểm của người dùng. Thuật toán k-means bao gồm các bước cơ bản sau:
Input: Số cụm k và các trọng tâm cụm{ }k
jj
m
1=
.
Output: Các cụm C[i] (1 ≤ i ≤ k) và hàm tiêu chuẩn E đạt giá trị tối thiểu.
Begin
Bước 1 : Khởi tạo
Chọn k trọng tâm { }k
jj
m
1=
ban đầu trong không gian Rd (d là số chiều của dữ
liệu). Việc lựa chọn này có thể là ngẫu nhiên hoặc theo kinh nghiệm.
Bước 2: Tính toán khoảng cách
Đối với mỗi điểm Xi (1 ≤ i ≤ n), tính toán khoảng cách của nó tới mỗi trọng
tâm mj (1 ≤ j ≤ k). Sau đó tìm trọng tâm gần nhất đối với mỗi điểm.
Bước 3: Cập nhật lại trọng tâm
Đối với mỗi 1 ≤ j ≤ k, cập nhật trọng tâm cụm mj bằng cách xác định trung
bình cộng các vectơ đối tượng dữ liệu.
Điều kiện dừng:
Lặp lại các bước 2 và 3 cho đến khi các trọng tâm của cụm không thay đổi.
End.
K-means biểu diễn các cụm bởi các trọng tâm của các đối tượng trong
cụm đó. Thuật toán k-means chi tiết được trình bày như sau:
BEGIN
Nhập n đối tượng dữ liệu
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
72
Nhập k cụm dữ liệu
MSE = +∞
For i = 1 to k do mi = xi+(i-l)*[n/k]; //khởi tạo k trọng tâm
Do {
OldMSE = MSE;
MSE' = 0;
For j = 1 to k do
{m'[j] = 0; n’[j] = 0}
Endfor
For i = 1 to n do
For j = 1 to k do
Tính toán khoảng cách Euc1idean bình phương:
D2(x[i]; m[j])
Endfor
Tìm trọng tâm gần nhất m[h] tới X[i]
m’[h] = m’[h] + X[i]; n’[h] = n’[h] + l;
MSE' = MSE' + D2(x[i]; m[j]);
Endfor
n[j] = max(n'[j], 1); m[j] = m’[j]/n[j];
MSE = MSE'
} While (MSE < OldMSE)
END.
Các khái niệm biến và hàm sử dụng trong thuật toán k-means:
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
73
MSE (Mean Squared Error): Được gọi là sai số bình phương trung
bình hay còn gọi là hàm tiêu chuẩn. MSE dùng để lưu giá trị của hàm tiêu chuẩn và
được cập nhật qua mỗi lần lặp. Thuật toán dừng ngay khi giá trị MSE tăng lên so
với giá trị MSE cũ của vòng lặp trước đó;
D2(xi, mj): Là khoảng cách Euclide từ đối tượng dữ liệu thứ i tới trọng tâm j;
OldMSE, m'[j], n'[j]: Là các biến tạm lưu giá trị cho trạng thái trung gian
cho các biến tương ứng: giá trị hàm tiêu chuẩn, giá trị của vectơ tổng của các đối
tượng trong cụm thứ j , số các đối tượng của cụm thứ j.
Thuật toán k-means tuần tự trên được chứng minh là hội tụ và có độ phức tạp
tính toán là ))3(( flopTnkdO τ . Trong đó, n là số đối tượng dữ liệu, k là số cụm dữ
liệu, d là số chiều, τ là số vòng lặp, flopT là thời gian để thực hiện một phép tính cơ
sở như phép tính nhân, chia,... Trong khi thi hành, một vấn đề là làm sao gỡ các nút
thắt trong các trường hợp mà ở đó có nhiều trung tâm với cùng khoảng cách đó từ
một đối tượng. Trong trường hợp này, có thể gán các đối tượng ngẫu nhiên cho một
trong các cụm thích hợp hoặc xáo trộn các đối tượng để vị trí mới của nó không gây
ra các nút thắt. Như vậy, do k -means phân tích phân cụm đơn giản nên có thể áp
dụng đối với tập dữ liệu lớn.Tuy nhiên, nhược điểm của k-means là chỉ áp dụng với
dữ liệu có thuộc tính số và khám phá ra các cụm có dạng hình cầu, k-means còn rất
nhạy cảm với nhiễu và các phần tử ngoại lai trong dữ liệu. Hình 3.7 dưới đây mô
phỏng về một số hình dạng cụm dữ liệu được khám phá bởi k-means:
Hình 3.7: Ví dụ về một số hình dạng cụm dữ liệu được khám phá bởi k-means
Hơn nữa, chất lượng PCDL của thuật toán k-means phụ thuộc nhiều vào các
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
74
tham số đầu vào như: số cụm k và k trọng tâm khởi tạo ban đầu. Trong trường hợp
các trọng tâm khởi tạo ban đầu mà quá lệch so với các trọng tâm cụm tự nhiên thì
kết quả phân cụm của k-means là rất thấp, nghĩa là các cụm dữ liệu được khám phá
rất lệch so với các cụm trong thực tế. Trên thực tế chưa có một giải pháp tối ưu nào
để chọn các tham số đầu vào, giải pháp thường được sử dụng nhất là thử nghiệm
với các giá trị đầu vào k khác nhau rồi sau đó chọn giải pháp tốt nhất.
3.4.2. Phương pháp phân cụm phân cấp
Phương pháp này xây dựng một phân cấp trên cơ sở các đối tượng dữ liệu
đang xem xét. Nghĩa là sắp xếp một tập dữ liệu đã cho thành một cấu trúc có dạng
hình cây, cây phân cấp này được xây dựng theo kỹ thuật đệ quy. Có hai cách tiếp
cận phổ biến của kỹ thuật này: hòa nhập nhóm, thường được gọi là tiếp cận Bottom-
Up, và phân chia nhóm, thường được gọi là tiếp cận Top-Down.
Kỹ thuật tiếp cận Bottom-Up: Bắt đầu xuất phát với mỗi đối tượng dữ liệu
được khởi tạo tương ứng với các cụm riêng biệt và sau đó tiến hành hòa nhập nhóm
các đối tượng theo một độ đo tương tự (như khoảng cách giữa hai trung tâm của hai
nhóm), quá trình này được thực hiện cho đến khi tất cả các nhóm được hòa nhập vào
một nhóm (mức cao nhất của cây phân cấp) hoặc cho đến khi các diều kiện kết thúc
thỏa mãn. Cách tiếp cận này sử dụng chiến lược ăn tham trong quá trình phân cụm.
Kỹ thuật tiếp cận Top-Down: Bắt đầu với tất cả các đối tượng dữ liệu được
sắp xếp trong cùng một cụm và kỹ thuật này tiến hành chia nhỏ các cụm.
Bottom-Up
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
75
Hình 3.8: Các chiến lược phân cụm phân cấp
Mỗi vòng lặp thành công, một cụm được tách ra thành các cụm nhỏ hơn theo
giá trị của một phép đo tương tự nào đó cho đến khi mỗi đối tượng dữ liệu là một
cụm riêng biệt hoặc cho đến khi điều kiện dừng thỏa mãn. Cách tiếp cận này sử
dụng chiến lược chia để trị.
Thực tế áp dụng, có nhiều trường hợp kết hợp cả hai phương pháp phân cụm
phân hoạch và phân cụm phân cấp, nghĩa là kết quả thu được của phương pháp phân
cấp có thể cải tiến thông qua bước phân cụm phân hoạch. Phân cụm phân hoạch và
phân cụm phân cấp là hai phương pháp PCDL cổ điển, hiện đã có rất nhiều thuật
toán cải tiến dựa trên hai phương pháp này đã được áp dụng phổ biến.
Thuật toán BIRCH
Thuật toán phân cụm khác cho tập dữ liệu lớn, được gọi là BIRCH. Ý tưởng
của thuật toán là không cần lưu toàn bộ các đối tượng dữ liệu của các cụm trong bộ
nhớ mà chỉ lưu các đại lượng thống kê. Thuật toán đưa ra hai khái niệm mới để theo
dõi các cụm hình thành, phân cụm đặc trưng là tóm tắt thông tin về một cụm và cây
phân cụm đặc trưng (cây CF) là cây cân bằng được sử dụng lưu trữ cụm đặc trưng
(được sử dụng để mô tả cụm tóm tắt). Trước tiên được gọi là cụm đặc trưng, là một
bộ ba (n, LS, SS), trong đó n là số các điểm trong phân hoạch cụm con, LS là tổng
số các giá trị thuộc tính và SS là tổng bình phương của các điểm đó. Đặc trưng tiếp
theo là cây CF, mà đơn giản là cây cân bằng mà lưu bộ ba này. Hình 3.9 dưới đây
biểu thị một ví dụ về cây CF. Có thể thấy rằng, tất cả các nút trong của cây lưu tổng
các đặc trưng cụm CF, các nút con, trong khi đó các nút là lưu trữ các đặc trưng của
các cụm dữ liệu.
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
76
Hình 3.9: Cây CF được sử dụng bởi thuật toán BIRCH
Cây CF chứa các nút trong và nút lá, nút trong là nút chứa các nút con và nút
lá thì không có con. Nút trong lưu trữ tổng các đặc trưng cụm (CF) của các nút co n
của nó. Một cây CF được đặc trưng bởi hai tham số:
Yếu tố nhánh (Branching Factor - B): Nhằm xác định số tối đa các nút con
của một nút lá trong của cây.
Ngưỡng (Threshold - T): Khoảng cách tối đa giữa bất kỳ một cặp đối tượng
trong nút lá của cây, khoảng cách này còn gọi là đường kính của các cụm con được
lưu tại các nút lá.
Hai tham số này có ảnh hưởng đến kích thước của cây CF. Thuật toán
BIRCH thực hiện gồm hai giai đoạn sau:
Giai đoạn 1: BIRCH quét tất cả các đối tượng trong CSDL để xây dựng cây
CF khởi tạo, mà được lưu trữ trong bộ nhớ. Trong giai đoạn này, các đối tượng lần
lượt được chèn vào nút lá gần nhất của cây CF (nút lá của cây đóng vai trò là cụm
con), sau khi chèn xong thì tất cả các nút trong cây CF được cập nhật thông tin. Nếu
đường kính của cụm con sau khi chèn là lớn hơn ngưỡng T, thì nút lá được tách.
Quá trình này lặp cho đến khi tất cả các đối tượng đều được chèn vào trong cây. Ở
đây cho thấy rằng, mỗi đối tượng trong cây chỉ được đọc một lần, để lưu toàn bộ
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
77
cây CF trong bộ nhớ thì cần phải điều chỉnh kích thước của cây CF thông qua điều
chỉnh ngưỡng T.
Giai đoạn 2: BIRCH lựa chọn một thuật toán phân cụm (như thuật toán phân
cụm phân hoạch chẳng hạn) để thực hiện phân cụm cho các nút lá của cây CF.
Thuật toán BIRCH thực hiện qua các bước cơ bản như sau:
Các đối tượng dữ liệu lần lượt được chèn vào cây CF, sau khi chèn hết
các đối tượng thì thu được cây CF khởi tạo. Một đối tượng được chèn vào
nút lá gần nhất tạo thành cụm con. Nếu đường kính của cụm con này lớn hơn
T thì nút lá được tách ra. Khi một đối tượng thích hợp được chèn vào nút lá,
tất cả các nút trỏ tới gốc của cây được cập nhật với các thông tin cần thiết.
Nếu cây CF hiện thời không có đủ bộ nhớ trong khi tiến hành xây dựng
một cây CF nhỏ hơn: Kích thước của cây CF được điều khiển bởi tham số T
và vì vậy việc chọn một giá trị lớn hơn cho nó sẽ hòa nhập một số cụm con
thành một cụm, điều này làm cho cây CF nhỏ hơn. Bước này không cần yêu
cầu đọc dữ liệu lại từ đầu nhưng vẫn đảm bảo hiệu chỉnh cây dữ liệu nhỏ
hơn.
Thực hiện phân cụm: Các nút lá cây CF lưu trữ các đại lượng thống kê
của các cụm con. Trong bước này, BIRCH sử dụng các đại lượng thống kê
này để áp dụng một số kỹ thuật phân cụm, ví dụ như k-means và tạo ra một
khởi tạo cho phân cụm.
Phân phối lại các đối tượng dữ liệu bằng cách dùng các đối tượng trọng
tâm cho các cụm được khám phá từ bước 3: Đây là một bước tùy chọn để
duyệt lại tập dữ liệu và gán lại nhãn cho các đối tượng dữ liệu tới các trọng
tâm gần nhất. Bước này nhằm để gán nhãn cho các dữ liệu khởi tạo và loại
bỏ các đối tượng ngoại lai.
Với cấu trúc cây CF được sử dụng, BIRCH có tốc độ thực hiện PCDL nhanh
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
78
và có thể áp dụng đối với tập CSDL lớn, BIRCH cũng có hiệu quả khi áp dụng với
tập dữ liệu tăng trưởng theo thời gian. BIRCH thực hiện tính toán khá tốt, độ phức
tạp tính toán của BIRCH là tuyến tính tỉ lệ với số các đối tượng, do BIRCH chỉ
duyệt toàn bộ dữ liệu một lần với một lần quét thêm tùy chọn (thực hiện phân cụm
lại các nút lá của cây CF), có thể được đo trong thời gian O(n) với n là số đối tượng
dữ liệu. Thuật toán này kết hợp các cụm gần nhau và xây dựng lại cây CF, tuy nhiên
mỗi nút trong cây CF có thể chỉ lưu trữ một số hữu hạn bởi kích thước của nó.
BIRCH vẫn có một hạn chế: thuật toán này có thể không xử lí tốt nếu các cụm
không có dạng hình cầu , bởi vì nó sử dụng khái niệm bán kính hoặc đường kính để
kiểm soát ranh giới các cụm và chất lượng của các cụm được khám phá không được
tốt. Nếu BIRCH sử dụng khoảng cách Euc1ide, nó thực hiện tốt chỉ với các dữ liệu
số. Mặt khác, tham số vào T có ảnh hưởng rất lớn tới kích thước và tính tự nhiên
của cụm. Việc ép các đối tượng dữ liệu làm cho các đối tượng của cụm có thể là đối
tượng kết thúc của cụm khác, trong khi các đối tượng gần nhau có thể bị hút bởi các
cụm khác nếu chúng được biểu diễn cho thuật toán theo một thứ tự khác. BIRCH
không thích hợp với dữ liệu đa chiều.
3.4.3. Ứng dụng trong tìm kiếm văn bản đa phương tiện
Giả sử ta có tập các tài liệu được lưu trữ trong máy tính kí hiệu là D1, D2,
…, Dn và câu truy vấn Q , mỗi tài liệu và câu truy vấn gồm rất nhiều từ kí hiệu là
term1, term2, …, termm. Coi mỗi tài liệu được biểu diễn bằng một vectơ và một
véctơ biểu diễn cho câu hỏi.
Sử dụng công thức tính trọng số trong mô hình không gian vectơ , thành lập
được bảng trọng số của các từ trong tập tài liệu và trong câu hỏi.
Quay lại ví dụ trong chương 2, gồm có 3 tài liệu D1: “ani gnu ani bee”,
D2: “dog bee dog hog dog ani dog gnu”, D3: “bee cat gnu dog eel fox” và câu
truy vấn Q: “ani dog”. Xây dựng được bảng trọng số của các từ trong tài liệu:
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
79
Tài liệu
Từ
D1 D2 D3
ani 0.3522 0.1761 0
bee 0 0 0
cat 0 0 0.4771
dog 0 0.7044 0.1761
eel 0 0 0.4771
fox 0 0 0.4771
gnu 0 0 0
hog 0 0.4771 0
Bảng trọng số của câu truy vấn:
Truy vấn
Từ
Q
ani 0.1761
bee 0
cat 0
dog 0.1761
eel 0
fox 0
gnu 0
hog 0
Sau đó đối sánh Q với Di bằng cách sử dụng phép tính cosin θ để tìm ra
những tài liệu tương đồng với câu truy vấn ta được kết quả là: D1, D2, D3.
Ví dụ trên chỉ gồm có 3 tài liệu nên có thể sử dụng cosinθ để tính khoảng
cách giữa các vectơ Di và Q. Nhưng trong thực tế Dn, Tm là rất lớn không thể dùng
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
80
cosinθ để tính được vì mất rất nhiều thời gian, do đó sử dụng phương pháp phân
cụm để tìm kiếm.
Giả sử có D1, D2, …, D10 tài liệu và câu truy vấn Q sau khi được phân tích
thành Tm từ, sử dụng mô hình không gian vectơ để tính trọng số của các Tm trong
các tài liệu và câu truy vấn (hình thành được bảng trọng số).
Từ bảng trọng số đó sử dụng thuật toán phân cụm để nhóm các tài liệu vào
cụm, giả sử tách làm 3 cụm.
Cụm thứ nhất gồm các tài liệu D1, D4, D10; cụm thứ 2 gồm các tài liệu D2,
D5, D6, D9 và cụm thứ 3 gồm tài liệu D3, D7, D8. Trong mỗi cụm ta tìm ra 1 tài
liệu đại diện hay là tâm của cụm. Sau đó tính độ tương quan giữa câu truy vấn Q và
các đại diện của từng cụm, nếu thấy câu truy vấn Q gần với tâm củ a cụm nào thì
tiếp tục tính độ tương quan giữa câu truy vấn Q với các tài liệu còn lại trong cụm
đó.
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
81
CHƯƠNG 4: CHƯƠNG TRÌNH DEMO
4.1. MỤC TIÊU CỦA HỆ THỐNG TÌM KIẾM VĂN BẢN:
Đầu vào: Có rất nhiều tệp lài liệu được lưu trữ trong máy tính, các tài liệu
đều không nén.
Nhiệm vụ: Tìm ra những tài liệu nào có chứa từ hoặc một cụm từ cho trước
trong câu truy vấn.
Đầu ra: Danh sách các tệp thoả mãn yêu cầu
Chương trình tìm kiếm thực hiện qua các bước như sau
Lập chỉ mục các từ tạo nên tài liệu
Tính trọng số của các từ trong tài liệu và trong câu truy vấn
Tính độ tương quan giữa câu hỏi và câu truy vấn sau đó sắp xếp
các tài liệu tìm được theo độ tương quan giảm dần.
Hiển thị các tài liệu tìm được
4.2. CHỨC NĂNG CỦA HỆ THỐNG
- Người quản trị:
LË p chØ môc
Admin
CË p nhË p chØ môc
- Người sử dụng:
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
82
User T×m kiÕm
4.3. CÀI ĐẶT CHƯƠNG TRÌNH
Ngôn ngữ lập trình: C#
Công cụ lập trình: Microsoft Visual Studio .NET 2005
Lưu trữ dữ liệu: tập tin nhị phân
Ứng dụng: Xây dựng hệ thống tìm kiếm thông tin dựa trên nội dung
Hệ thống tìm kiếm sẽ được xây dựng theo mô hình không gian
Vector.
Chương trình tìm kiếm được xây dựng trên 2 modul chính
4.3.1. Lập chỉ mục
Các funtion chính
Tách và lọc các từ dùng làm chỉ mục
Chức năng: Tách từ và loại bỏ các từ không có nghĩa lấy các từ có giá trị để
lập chỉ mục
* Thuật toán
//Tham số truyền vào là một thư mục chứa tập tài liệu cần chỉ mục, Mảng các
định dạng file dùng để chỉ mục
Arrylist BreakWords(String content)
{
Arraylist words
//Chuyển chuỗi content thành các mảng từ nhờ khoảng trắng
//và các kí tự đặc biệt
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
83
Regex regEx = new Regex("([ \\t{}():;.,| \n\r\\s*])");
string [] strArray = regEx.Split(sString.ToLower());
foreach(string term in strArray)
{
if( term không có trong StopList)
words.add(term);
else
Loại bỏ
}
Return words;
}
Thêm tài liệu
* Thuật toán
Void AddDocument(Document doc,String content)
{
+ Tách từ: Gọi phương thức BreakWords cho tài liệu cần thêm
+ Nối (combine) mảng từ vừa tách được với mảng từ tách được của
các tài liệu trước đó thành một mảng từ chung của tập tài liệu
+ Sắp xếp lại mảng từ vừa nối
+ Xây dựng từ điển cho tài liệu
}
Tập hợp tài liệu
Funtion này có chức năng tập hợp các tài liệu dùng làm chỉ mục tìm kiếm.
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
84
Tách từ từ các tài liệu riêng rẽ và tạo thành một danh sách từ tạo nên toàn bộ các tài
liệu.
Kết quả trả về cho funtion này là danh sách tất cả các từ tạo nên các tài liệu
* Thuật toán
Arraylist CollectDocuments(Directory path)
{
String [ ] patterns = new {Các định dạng file tài liệu. Vd :
*.doc,*.htm};
foreach(String pattern in patterns)
{
+ Lấy danh sách tài liệu có định dạng là pattern
foreach(Danh sách tài liệu)
{
Gọi phương thức AddDocument()
}
}
}
Tạo chỉ mục
void CreateDocumentIndex(Document doc,String content)
{
+ Gọi phương thức BreakWords để tách từ từ nội dung tài liệu
+ Tính toán tần suất xuất hiện của các từ xuất hiện trong tài liệu.Giá
trị này dùng làm trọng số để chỉ mục
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
85
+ Duyệt tất cả các từ từ danh sách tất cả các từ trong tập tài liệu
So sánh tất cả các từ trong tài liệu.
Nếu từ nào có thì thêm trọng số được tính ở trên
Nếu không có thì gán trọng số là 0
+ Trả về vecto chỉ mục của tài liệu đang xét
}
Giao diện của màn hình lập chỉ mục
Hình 4.1: Giao diện màn hình lập chỉ mục
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
86
Giao diện màn hình cập nhập chỉ mục
Hình 4.2: Giao diện màn hình cập nhập chỉ mục
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
87
4.3.2. Tìm kiếm tài liệu
Giao diện màn hình tìm kiếm
Hình 4.2: Giao diện màn hình tìm kiếm
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
88
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
KẾT LUẬN
Mục đích của việc nghiên cứu tìm kiếm thông tin là nhằm tìm ra các giải
pháp giúp cho người sử dụng có thể tìm thấy các thông tin mình cần trong một khối
lượng thông tin khổng lồ như hiện nay.
Để hiển thị ra được thông tin người sử dụng cần thì hệ thống tìm kiếm thông
tin phải thực hiện qua những bước sau:
Phân tích tài liệu thành các từ riêng biệt và lập chỉ mục cho văn bản
Sử dụng mô hình không gian vector để tính toán độ tương quan giữa
câu hỏi và tài liệu bằng cách tính trọng số và độ tương quan giữa câu
hỏi (câu truy vấn) người dùng yêu cầu với các tài liệu đã được cập
nhật để tạo chỉ mục.
Sử dụng thuật toán phân cụm để nhóm các mục thông tin tương tự
nhau thành các cụm. Mỗi cụm được biểu diễn bởi 1 vectơ đặc trưng
của cụm. Sau đó sẽ tính toán độ tương tự giữa vectơ truy vấn với từng
vectơ đặc trưng trong cụm được tính toán và k mục gần nhất được xếp
hạng và được xem như kết quả cho lại.
Hệ thống có một số ưu điểm sau:
Đơn giản dễ dàng sử dụng, giao diện thân thuộc
Tìm kiếm được các định dạng tệp thông dụng như của các file word,
file excel, file html, file txt
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
89
Sau bước lập chỉ mục. Dùng chỉ mục đó để tìm kiếm chương trình tìm
kiếm khá nhanh và cho kết quả chính xác
Tuy nhiên hệ thống còn các khuyết điểm:
Lập chỉ mục còn khá chậm do đặc tính của hệ thống tìm kiếm nói
chung đó là phải duyệt từng từ để chọn các từ có giá trị làm chỉ mục.
Nhưng đây là quá trình xử lý offline trước khi người sử dụng sử dụng
chương trình tìm kiếm nên không ảnh hưởng lớn đến tính hiệu quả
trong quá trình tìm kiếm
Hệ thống mới chỉ sử dụng một mô hình tìm kiếm đó là mô hình vectơ
nên không so sánh được hiệu quả của các mô hình
Hệ thống vẫn chưa có khả năng tự cập nhập định kì và chưa có khả
năng tự thu thập tài liệu.
Hệ thống chưa tìm kiếm được dữ liệu bằng thuật toán phân cụm dữ
liệu
HƯỚNG PHÁT TRIỂN
Đây là một đề tài có tính thực tế. Với nhiệm vụ là nghiên cứu luận văn đã
đáp ứng được một số yêu cầu cơ bản của hệ thống. Tuy nhiên để trở thành một ứng
dụng thực tế cho người sử dụng thì đòi hỏi cần thêm nhiều chức năng mở rộng để
chương trình hoàn thiện hơn. Do đó hướng phát triển của ứng dụng như sau:
Nghiên cứu cách tách từ và chỉ mục tài liệu tiếng Việt. Hệ thống hiện
tại vẫn chưa có khả năng tách từ tiếng Việt theo nghĩa.
Thêm chức năng tự thu thập tài liệu định kì và cập nhập chỉ mục
Tăng tốc độ lập chỉ mục
Sử dụng thuật toán phân cụm để làm tăng tốc độ tìm kiếm.
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
90
TÀI LIỆU THAM KHẢO
Tiếng Việt
1. Đặng Văn Đức (2004/05), “Multimedia Database Management
System” Chương 1, Chương 4.
2. Đặng Văn Đức (2007), “Nâng cao hiệu năng MMDMS (Multimedia
Database Management System)”, Bài 8.
Tiếng Anh
1. C.J. van Rijsbergen, “Information Retrieval”
2. C.Ordonez, “Clustering binary data streams with k-means”. ACM
DMKD Workshop, 2003.
3. David Hand, Heikki Mannila and Padhraic Smyth: “Principles of
Data Mining”, The MIT Press, 2001
4. Gerard Salton, Michael J.McGill, “Introduction to Modern
Information Retrieval”
5. K. Mali and S.Mitra, “Clustering of Symbolic Data and its
validation”, AFSS 2002.
6. Mark S. Aldenderfer, Roger K. Blashfield, “Cluster Analysis”
Website
1. Từ điển bách khoa toàn thư
Nghiên cứu phát triển hệ thống đa phương tiện trên cơ sở phân cụm dữ liệu
Học viên: Lưu Thị Hải Yến
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
91
2. Các trang giáo dục
3. Trang mã nguồn mở
Các file đính kèm theo tài liệu này:
- 3LV08_CNTTLuuThiHaiYen.pdf