Khóa luận Sử dụng phương pháp xếp hạng trong bài toán phân cụm tiếng Việt
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Phạm Thị Tâm
SỬ DỤNG PHƯƠNG PHÁP XẾP HẠNG TRONG
BÀI TOÁN PHÂN CỤM TIẾNG VIỆT
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin
\
HÀ NỘI - 2009
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Phạm Thị Tâm
SỬ DỤNG PHƯƠNG PHÁP XẾP HẠNG TRONG
BÀI TOÁN PHÂN CỤM TIẾNG VIỆT
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin
Cán bộ hướng dẫn: Th.S Trần Thị Oanh
Cán bộ đồng hướng dẫn: CN Nguyễn Minh Tuấn
HÀ NỘI - 2009
Lời cảm ơn
Trước tiên, tôi xin gửi lời cảm ơn và lòng biết ơn sâu sắc nhất tới Phó Giáo sư
Tiến sĩ Hà Quang Thụy, Thạc sĩ Trần Thị Oanh và Cử nhân Nguyễn Minh Tuấn,
những người đã tận tình chỉ bảo và hướng dẫn tôi trong suốt quá trình thực hiện khóa
luận tốt nghiệp.
Tôi chân thành cảm ơn các thầy cô đã tạo cho tôi những điều kiện thuận lợi để
học tập và nghiên cứu tại trường đại học Công nghệ.
Tôi xin gửi lời cảm ơn tới các anh chị và các bạn sinh viên trong phòng Công
nghệ tri thức và tương tác người máy – trường ĐH Công nghệ - ĐHQGHN đã tạo điều
kiện và giúp tôi tiến hành thực nghiệm của khóa luận.
Cuối cùng, tôi muốn gửi lời cảm ơn vô hạn tới gia đình, bạn bè luôn bên cạnh và
động viên cũng như tạo những điều kiện tốt nhất cho tôi trong suốt quá trình thực hiện
khóa luận tốt nghiệp.
Sinh viên
Phạm Thị Tâm
Tóm tắt
Cùng với sự gia tăng nhanh chóng về số lượng các trang Web thì nhu cầu về khai
phá dữ liệu Web ngày càng nhận được sự quan tâm của các nhà khoa học và các nhóm
nghiên cứu. Trong lĩnh vực khai phá Web thì phân cụm Web là một trong những bài
toán cơ bản và quan trọng. Đây cũng là thành phần chịu nhiều ảnh hưởng của các đặc
trưng ngôn ngữ.
Khóa luận này tập trung nghiên cứu về bài toán phân cụm Web sử dụng phương
pháp xếp hạng. Trên cơ sở lý thuyết phân cụm Web và lựa chọn các đặc trưng của
tiếng Việt, khóa luận đã sử dụng phương pháp xếp hạng các cụm từ quan trọng vào
phân cụm các tài liệu Web tiếng Việt và tiến hành thực nghiệm. Kết quả thực nghiệm
đánh giá theo các đặc trưng TFDF, độ dài (LEN), tương tự nội tại (ICS), entropy nội
tại cụm văn bản (CE) cho thấy đặc trưng TFIDF và LEN có ảnh hưởng lớn hơn so với
các đặc trưng khác.
i
Mục lục
Tóm tắt..............................................................................................................................i
Mục lục........................................................................................................................... ii
Danh sách các bảng ....................................................................................................... iv
Danh sách các hình..........................................................................................................v
Lời mở đầu.......................................................................................................................1
Chương 1. Khái quát về phân cụm Web .........................................................................2
1.1. Giới thiệu về phân cụm Web.......................................................................2
1.1.1. Đặc điểm bài toán phân cụm web......................................................3
1.1.2. Các yêu cầu đối với phân cụm web...................................................4
1.1.3. Một số độ đo độ đánh giá ..................................................................5
1.2. Một số thuật toán phân cụm web ................................................................6
1.2.1. Thuật toán phân cụm bottom-up (HAC - Hierarchical
Agglomeraltive Clustering) ...............................................................7
1.2.2. Thuật toán phân cụm top-down.........................................................9
1.3. Đánh giá các thuật toán phân cụm ............................................................18
Chương 2: Phân cụm văn bản tiếng Việt.......................................................................19
2.1. Đặc trưng của tiếng Việt và tách từ trong tiếng việt.................................19
2.1.1. Đặc trưng của tiếng Việt..................................................................19
2.1.2. Tách từ tiếng Việt............................................................................21
2.2. Một số nghiên cứu về phân cụm tiếng Việt ..............................................23
2.2.1. Phân cụm từ tiếng Việt bằng phương pháp học máy cấu trúc.........23
2.2.2. Đánh giá chất lượng phân cụm trong máy tìm kiếm tiếng Việt ......24
2.2.3. Gom cụm đồ thị và ứng dụng vào việc rút trích nội dung chính của
khối thông điệp trên diễn đàn thảo luận...........................................26
ii
Chương 3. Phân cụm văn bản sử dụng..........................................................................27
phương pháp xếp hạng cụm từ quan trọng....................................................................27
3.1. Khái quát bài toán .....................................................................................27
3.1.1. Nhu cầu về phân cụm các kết quả tìm kiếm....................................27
3.1.2. Mô tả bài toán và thuật toán ............................................................29
3.2. Trích các cụm từ quan trọng .....................................................................31
3.2.1. Đặc trưng TFIDF.............................................................................32
3.2.2. Đặc trưng độ dài ..............................................................................33
3.2.3. Đặc trưng tương tự nội tại cụm .......................................................33
3.2.4. Đặc trưng entropy nội tại cụm.........................................................34
3.2.5. Đặc trưng độc lập cụm từ ................................................................34
3.3. Xếp hạng các cụm từ quan trọng...............................................................35
3.3.1. Hồi qui tuyến tính............................................................................35
3.3.2. Hồi qui logistic ................................................................................36
3.3.3. Hồi qui hỗ trợ vector (Support vector regression)...........................36
Chương 4. Thực nghiệm và đánh giá ............................................................................38
4.1. Dữ liệu của thực nghiệm...........................................................................38
4.2. Cài đặt thực nghiệm ..................................................................................39
4.2.1. Phần cứng ........................................................................................39
4.2.2. Phần mềm ........................................................................................40
4.3. Phương pháp đánh giá...............................................................................40
4.4. Kết quả thực nghiệm và đánh giá..............................................................40
Kết luận..........................................................................................................................44
Tài liệu tham khảo.........................................................................................................46
iii
Danh sách các bảng
Bảng 1: Kết quả phân cụm với truy vấn “Việt Nam” [15] .............................................4
Bảng 2: Các tài liệu chứa cụm từ ở các node ...............................................................16
Bảng 3: So sánh một số đặc điểm của tiếng Việt và tiếng Anh.....................................21
Bảng 4: Các truy vấn trong tập huấn luyện ..................................................................38
Bảng 5: Số cụm từ và số giá trị y=1 trong tập dữ liệu huấn luyện...............................39
Bảng 6: Độ chính xác khi sử dụng từng đặc trưng để xếp hạng...................................41
Bảng 7: Độ chính xác của từng truy vấn.......................................................................42
iv
Danh sách các hình
Hình 1: Minh họa để tính cosin của hai vector...............................................................6
Hình 2: Cây hậu tố mở rộng..........................................................................................16
Hình 3: Kết quả sau khi trộn các tài liệu ......................................................................17
Hình 4: Thống kê về tách từ tiếng Hoa và tiếng Việt [12]............................................22
Hình 5: Hệ thống phân cụm từ tiếng Việt theo phương pháp học máy cầu trúc ..........24
Hình 6: Ví dụ với truy vấn “Việt Nam” trên máy tìm kiếm google[14]........................28
Hình 7: Ví dụ với truy vấn “Việt Nam” trên máy tìm kiếm Vivisimo[15] ....................28
Hình 8: Biểu đồ độ chính xác khi sử dụng từng đặc trưng để xếp hạng.......................41
Hình 9: Biểu đồ độ chính xác của từng truy vấn...........................................................42
v
Lời mở đầu
Internet được phát triển nhanh chóng và sinh ra một khối lượng khổng lồ các dữ
liệu dạng siêu văn bản (dữ liệu Web), đã trở thành một kênh quan trọng về mọi thông
tin của đời sống. Chính vì vậy, lĩnh vực khai phá Web có tốc độ phát triển vượt bậc,
nhận được nhiều sự quan tâm của các nhà khoa học và các nhóm nghiên cứu. Một
trong những bài toán quan trọng trong lĩnh vực khai phá Web chính là phân cụm Web
[6]. Số lượng các trang Web là rất lớn và luôn luôn thay đổi, mỗi tài liệu không chỉ
liên quan đến một khía cạnh mà còn đề cập đến nhiều khía cạnh khác nhau dẫn đến sự
trùng lặp thông tin giữa các tài liệu. Xuất phát từ những đặc điểm này mà phân cụm
Web chỉ nên thực hiện trên các tài liệu Web của một truy vấn trả về từ máy tìm kiếm.
Sau đó kết quả sẽ được tổ chức lại cho người dùng theo các cụm.
Khóa luận với đề tài “Sử dụng phương pháp xếp hạng trong bài toán phân cụm
tiếng Việt” nghiên cứu về phân cụm Web, phân cụm trong tiếng Việt và bài toán phân
cụm tài liệu Web dựa vào việc xếp hạng các cụm từ quan trọng. Khóa luận cũng trình
bày kết quả và đánh giá ban đầu về thực nghiệm ứng dụng kỹ thuật phân cụm trên
trong các tài liệu web tiếng Việt.
Khóa luận gồm 4 chương với nội dung các chương được miêu tả như dưới đây:
Chương 1: Khái quát về phân cụm Web. Chương 1 trình bày những nét cơ bản
nhất về bài toán phân cụm Web gồm: định nghĩa và đặc điểm của bài toán, một số độ
đo độ đánh giá, các phương pháp phân cụm phổ biến, đánh giá về các phương pháp.
Chương 2: Phân cụm văn bản tiếng Việt. Chương này sẽ trình bày về các đặc
điểm của tiếng Việt và các hướng tiếp cận trong việc tách từ tiếng Việt, đồng thời cũng
nêu ra một số đề tài đã được nghiên cứu về phân cụm trong tiếng Việt.
Chương 3: Phân cụm văn bản sử dụng phương pháp xếp hạng cụm từ quan
trọng. Nội dung chính của chương này là kỹ thuật phân cụm các kết quả trả về của
máy tìm kiếm dựa vào việc xếp hạng các cụm từ quan trọng. Chương này đưa ra nhu
cầu về phân cụm kết quả tìm kiếm, mô tả về bài toán và thuật toán cũng như những
tính toán để giải quyết bài toán.
Chương 4: Thực nghiệm và đánh giá trình bày các bước tiến hành thực nghiệm
trên các tài liệu Web tiếng Việt, việc thu thập dữ liệu huấn luyện, cài đặt thực nghiệm.
Sau đó đưa ra kết quả của thực nghiệm và đánh giá các kết quả này.
1
Chương 1. Khái quát về phân cụm Web
1.1. Giới thiệu về phân cụm Web
Trong thời gian gần đây, sự phát triển nhanh chóng của mạng Internet đã tạo nên
một khối lượng khổng lồ các dữ liệu dạng siêu văn bản. Vì vậy, nội dung khai phá
Web rất được quan tâm. Và một trong những bài toán quan trọng trong lĩnh vực khai
phá Web chính là bài toán phân cụm Web. [6] Phân cụm Web - nói một cách khái quát
- là việc tự động sinh ra các lớp tài liệu dựa vào sự tương tự của các tài liệu. Các lớp
tài liệu ở đây là chưa biết trước, người dùng có thể chỉ yêu cầu số lượng các lớp cần
phân loại, hệ thống sẽ đưa ra các tài liệu theo từng tập hợp, từng cụm, mỗi tập hợp
chứa các tài liệu tương tự nhau.
Phân cụm Web – hiểu một cách đơn giản - là phân cụm trên tập các tài liệu được
lấy từ Web. Theo [6] có hai tình huống phân cụm tài liệu, đó là:
• Tình huống thứ nhất là việc phân cụm trên toàn bộ một cơ sở dữ liệu (CSDL)
có sẵn gồm rất nhiều tài liệu Web. Thuật toán phân cụm cần tiến hành việc
phân cụm toàn bộ tập dữ liệu thuộc CSDL đó. Tình huống này thường được
gọi là phân cụm không trực tuyến (off-line).
• Tình huống thứ hai thường được áp dụng trên một tập tài liệu nhỏ là tập hợp
các tài liệu do máy tìm kiếm trả về theo một truy vấn của người dùng. Trong
trường hợp này, giải pháp phân cụm được tiến hành kiểu trực tuyến (on-line)
theo nghĩa việc phân cụm tiến hành theo từng bộ phận các tài liệu nhận được.
Khi đó, thuật toán phải có tính chất “gia tăng” để tiến hành phân cụm ngay
khi chưa có đủ tài liệu và phân cụm tiếp theo cần không tiến hành với dữ liệu
đã được phân cụm. Do tập tài liệu trên Web là vô cùng lớn cho nên cách phân
cụm trực tuyến là thích hợp hơn và phải đòi hỏi tính "gia tăng" của thuật toán
phân cụm.
Việc xử lý truy vấn cũng như xếp hạng các kết quả trả về của máy tìm kiếm phụ
thuộc vào sự tính toán độ tương tự giữa tài liệu và truy vấn, giữa các tài liệu với nhau.
Mặc dù các truy vấn liên quan phần nào đến các tài liệu cần tìm, nhưng nó thường quá
ngắn và dễ xảy ra sự nhập nhằng. Như đã biết, trung bình các truy vấn trên Web chỉ
gồm hai đến ba từ do đó gây nên độ nhập nhằng. Chẳng hạn, truy vấn star dẫn đến sự
nhập nhằng rất cao, các tài liệu lấy được liên quan đến astronomy, plants, animals,
2
popular media and sports figures… Độ tương tự giữa các tài liệu của một truy từ đơn
như vậy là khác nhau rất lớn. Vì lẽ đó, nếu máy tìm kiếm phân cụm các kết quả theo
từng chủ đề thì người dùng có thể hiểu truy vấn nhanh chóng hoặc tìm vào một chủ đề
xác định.
1.1.1. Đặc điểm bài toán phân cụm web
Việc phân cụm trực tuyến các tài liệu Web kết quả trả về từ máy tìm kiếm là rất
khác so với việc phân cụm các tài liệu thông thường. Một đặc điểm của phân cụm tài
liệu web chính là số lượng các tài liệu Web là vô cùng lớn và nội dung luôn luôn thay
đổi. Ngoài ra một vấn đề nữa là các hệ thống tìm kiếm thông tin là tương tác người
dùng cho nên thời gian đáp ứng của hệ thống phải đủ nhanh, cụ thể bài toán ở đây cần
thời gian đáp ứng cần tính bằng giây [6]. Mỗi tài liệu Web không chỉ liên quan đến
một khía cạnh cụ thể nào đó mà đề cập đến nhiều khía cạnh khác nhau. Chẳng hạn như
tài liệu nói về “Việt Nam” cũng có thể đề cập đến cuộc đời và sự nghiệp của “Các
danh nhân Việt Nam”. Cho nên tồn tại sự trùng lặp thông tin giữa các tài liệu, có
nghĩa là một tài liệu có thể liên quan đến nhiều nội dung khác nhau.
Xuất phát từ những đặc điểm đó nên việc phân cụm chỉ nên được thực hiện trên
tập các tài liệu Web của mỗi truy vấn trả về từ máy từ máy tìm kiếm. Sau đó kết quả
sẽ được tổ chức lại cho người sử dụng. Thông thường một máy tìm kiếm phục vụ hàng
triệu truy vấn một ngày cho nên việc phân phối CPU cũng như bộ nhớ cho mỗi truy
vấn cần được rút ngắn tối đa. Cho nên việc phân cụm có thể được thực hiện trên một
máy tách riêng tại đó chỉ nhận các kết quả của máy tìm kiếm như đầu vào, tạo ra các
cụm và biểu diễn chúng cho người sử dụng [6].
3
Với câu truy vấn “Việt Nam” máy tìm kiếm Vivisimo [15] trả về 254 kết quả tìm kiếm
với 41 cụm:
Tên cụm
Số kết quả
Sản
7
Tin tức
Giáo
27
22
21
24
20
…
Học
Viet Nam
Nghiệp
…
Bảng 1: Kết quả phân cụm với truy vấn “Việt Nam” [15]
1.1.2. Các yêu cầu đối với phân cụm web
Để có thể phân các tài liệu Web thành các cụm, việc đầu tiên là cần phải tính
được độ tương tự (hay độ tương đồng) giữa các tài liệu trên cơ sở biểu diễn tài liệu
Web và xem xét các đo độ tương tự giữa chúng. Thuật toán phân cụm cần đưa ra các
điều kiện dừng và gắn nhãn cho các cụm một các thích hợp nhất. Căn cứ đặc điểm và
yêu cầu của bài toán phân cụm Web thì phương pháp phân cụm được lựa chọn cần đáp
ứng được các yêu cầu sau [6]:
• Tính phù hợp: Phương pháp phải tạo nên các cụm trong đó nhóm tài liệu phù
hợp với truy vấn của người dùng tách riêng với các nhóm không phù hợp khác.
• Tổng hợp phải dễ đọc: Tránh trường hợp thay vì người dùng không phải xem
xét danh sách các tài liệu được phân hạng lại phải xem xét danh sách tài liệu trong
một cụm. Do đó phương pháp phải cung cấp mô tả ngắn gọn và chính xác của các
cụm.
• Tính đa hình: Vì các tài liệu có nhiều chủ đề, nên tránh việc hạn chế một tài
liệu chỉ thuộc về một cụm.
• Sử dụng các mẩu thông tin: Phương pháp phải tạo ra các cụm tốt thậm chí chỉ
sử dụng các mẩu thông tin được trả về bởi máy tìm kiếm (thông thường các máy tìm
4
kiếm chỉ trả về các mẩu thông tin mô tả về tài liệu). Điều này tránh cho việc người
dùng phải chờ đợi hệ thống tải toàn bộ tài liệu gốc từ Web, tải toàn bộ tài liệu gốc là
rất tốn thời gian.
• Tốc độ: Một người sử dụng dù kiên nhẫn cũng chỉ có thể xem xét khoảng
100 tài liệu trong danh sách các tài liệu được phân hạng. Hệ thống cần cho phép
người dùng có thể đọc qua một tập đủ lớn các tài liệu trong một thời gian chấp nhận
được. Vì vậy cần một phương pháp phân cụm khoảng 1000 mẩu thông tin trong vài
giây.
• Tính gia tăng: Để tiết kiệm thời gian, phương pháp nên xử lý từng mẩu thông
tin ngay khi lấy được từ Web để có được kết quả tức thời ứng với mỗi thời điểm.
1.1.3. Một số độ đo độ đánh giá
Độ đo đánh giá thuật toán phân cụm là một tiêu chuẩn được chỉ ra bởi một tập n
tài liệu D và một tập các truy vấn Q. Với mỗi q Є Q, một tập của các tài liệu phù hợp
là Dq Є D được xác định bằng tay. Giả sử có một truy vấn được gửi đến hệ thống, một
danh sách được phân hạng các tài liệu (d1, d2, … dn) được trả về. Các hệ thống tìm
kiếm thông thường chỉ hiển thị một số mục đầu tiên của danh sách này. Tương ứng với
danh sách như vậy, có thể tính một danh sách phù hợp (r1, r2,…rn) bởi các số (0/1)
trong đó ri =1 nếu di Є Dq và bằng 0 trong các trường hợp khác. Dưới đây là một số độ
đo độ đánh giá được trình bày như trong [6].
• Độ hồi tưởng: Với truy vấn q, độ hồi tưởng (recall) tại hạng k ≥ 1 được xác
định là tỷ số của tất cả các tài liệu phù hợp bên trong (d1, d2, … dk):
1
Recall (k) =
ri
∑
D
1≤ i ≤ k
q
• Độ chính xác và độ chính xác trung bình
- Độ chính xác (precision) tại hạng k là tỷ số của k tài liệu trên cùng tập tài
liệu mà thật sự phù hợp:
1
Precision (k) =
ri
∑
k
1≤ i ≤ k
- Một cách đo khác là độ chính xác trung bình (Average Precision): Độ chính
xác trung bình là tổng của độ chính xác tại mỗi vị trí phù hợp trong danh
sách đáp ứng chia cho tổng số các tài liệu phù hợp được chọn. Độ chính xác
5
trung bình bằng 1 khi lấy được toàn bộ các tài liệu phù hợp và xếp loại
chúng lên trên tất cả các tài liệu không phù hợp.
1
r × precision (k )
Average Precision =
∑
k
D q
1≤ k ≤ D
• Đo độ tương tự
- Độ trùng lặp: Độ trùng lặp dùng để đo độ tương tự của một tài liệu này với
tài liệu khác hay với một truy vấn. Cách trực tiếp nhất là đo phần giao nhau
của các đặc trưng tương ứng, ở đây là trùng lặp của các từ khóa. Đại lượng
này cũng được gọi là mức kết hợp (coordination level):
CoordLevel(q, d) = (Kq ∩ Kd )
- Độ tương tự Cosin: Một phương pháp khác có thể được sử dụng để đo độ
tương tự giữa các tài liệu là độ tương tự cosin. Kỹ thuật cosin là một kỹ
thuật (hay một phương pháp tính) được bắt nguồn từ tính toán vector. Trong
thu nhận thông tin, công thức tính toán cosin được sử dụng để chỉ ra (để đo)
mức độ tương tự giữa hai tài liệu hoặc giữa tài liệu và truy vấn, (xem hình
minh họa).
θ
Hình 1: Minh họa để tính cosin của hai vector
Hai vector d j và Q càng gần nhau khi góc θ càng nhỏ hay cosin của góc đó càng
lớn. Có thể dùng cosin của góc θ làm độ tương tự của hai vector, trong đó cosin của
góc giữa hai vector được xác định như sau:
v.w
cos θ =
v . w
1.2. Một số thuật toán phân cụm web
Một phương pháp nhằm thi hành thuật toán phân cụm là phân hoạch tập tài liệu
vào k tập con hoặc các cụm D1, …, Dk để làm cực tiểu khoảng cách bên trong cụm
6
δ (d , d )
hoặc làm cực đại sự tương tự bên trong cụm
∑ i∑
∑i∑
1
2
d1 , d 2∈ Di
ρ(d1 , d2 )
[].
d1 , d2∈Di
Nếu một biểu diễn bên trong của các tài liệu là có giá trị thì biểu diễn này cũng
được dùng để xác định một biểu diễn của các cụm liên quan đến cùng mô hình. Chẳng
hạn, nếu các tài liệu được biểu diễn sử dụng mô hình không gian vector, một cụm của
các tài liệu có thể được biểu diễn bởi trọng tâm (trung bình) của các tài liệu vector.
Khi một biểu diễn cụm là có giá trị, một mục tiêu có thể phân hoạch D thành D1, …,Dk
ρ
ρ
δ (d , Di )
ρ (d , D )
để cực tiểu hóa
hoặc cực đại hóa
trong
∑i∑
∑i ∑
i
d∈Di
d∈Di
đó Di là biểu diễn vector của cụm i. Có thể xem xét tới việc gán tài liệu d cho cụm i
như việc đặt một giá trị Boolean zd,i là 1. Điều này có thể phát sinh ra việc phân cụm
mềm tại đó zd,i là một số thực từ 0 đến 1. Trong bối cảnh như vậy, ta có thể muốn tìm
ρ
ρ
δ(d, Di )
ρ(d, D )
z để cực tiểu hóa
d,i
hoặc cực đại hóa
.
∑ ∑d∈D
∑i ∑d∈D
i
i
i
i
Việc phân hoạch có thể thực hiện theo hai cách. Bắt đầu với mỗi tài liệu trong
một nhóm của nó và kết hợp các nhóm tài liệu lại với nhau cho đến khi số các phân
hoạch là phù hợp; cách này gọi là phân cụm bottom-up. Cách khác là có thể khai báo
số các phân hoạch mong muốn và gán các tài liệu vào các phân hoạch; cách này gọi là
phân cụm top-down [6].
Có thể xem xét một kỹ thuật phân cụm bottom-up dựa vào quá trình lặp lại việc
trộn các nhóm của các tài liệu tương tự nhau cho đến khi đạt được số cụm mong muốn,
và một kỹ thuật top-down sẽ làm mịn dần bằng cách gắn các tài liệu vào các cụm được
thiết đặt trước. Kỹ thuật bottom-up thường chậm hơn, nhưng có thể được sử dụng trên
một tập nhỏ các mẫu để khởi tạo các cụm ban đầu trước khi thuật toán top-down tiến
hành.
1.2.1. Thuật toán phân cụm bottom-up (HAC - Hierarchical Agglomeraltive
Clustering)
Mặc dù có rất nhiều các công thức của vấn đề phân cụm, một cách nhận thức đơn
giản để tìm ra các cụm là bắt đầu với tất cả các tài liệu và từng bước kết nối chúng
thành các nhóm ở đó độ tương tự các tài liệu bên trong mỗi nhóm là cao, và ngừng lại
khi đạt được số cụm mong muốn[6].
7
HAC (Hierarchical Agglomerative Clustering) được sử dụng rất rộng rãi trong
phân cụm và các ứng dụng truy xuất thông tin. Dưới đây là đoạn mã giả của thuật toán
HAC [6].
1. Đặt mỗi tài liệu d là một nhóm đơn {d}
2. Đặt G là tập tất cả các nhóm
3. while |G| > 1 do
4. Chọn Ґ, Δ Є G thông qua độ đo tính tương tự s(Ґ, Δ)
5. Loại bỏ Ґ, Δ khỏi G
6. Đặt Ф= Ґ ∪ Δ
7. Thêm Ф vào G
8. end while
Quá trình trộn theo cấp bậc tạo thành cây gọi là cây lược đồ. Thông thường, việc
trộn giữa các nhóm với độ tương tự s(Ґ ∪ Δ) lớn sẽ thực hiện trước. Giá trị này sẽ
ngày càng nhỏ hơn cho các lần trộn sau. Người dùng có thể cắt qua cây lược đồ tại
mức thích hợp để lấy được số cụm mong muốn. Các thuật toán khác nhau ở cách
chúng tính các giá trị mong muốn để trộn Ґ và Δ. Một độ đo phổ biến được sử dụng là
độ tương tự nội tại của Ґ ∪ Δ. Độ tương tự nội tại của một nhóm các tài liệu Ф được
định nghĩa là trung bình độ tương tự của từng cặp tài liệu trong Ф[6] .
2
s(φ ) =
s(d , d )
∑
1
2
φ ( φ − 1)
d1 , d 2∈φ
Trong đó độ đo cosin TFIDF được sử dụng phổ biến cho các độ tương tự s(d1, d2)
của các tài liệu bên trong. Ngoài ra còn tồn tài nhiều điều kiện trộn khác. Một cách
khác để trộn các cặp của các cụm (Ґ, Δ) là maximizes mind1Є Ґ,d2Є Δ s(d1, d2) hay
(
s ( d 1 , d )) /( Γ . Δ )
maxd1Є Ґ,d2Є Δ s(d1,d2) hay
∑
2
d 1∈ Γ , d 2 ∈ Δ
Giả sử tài liệu d được biểu diễn trong không gian vector là d (dùng luôn ký hiệu
d để biểu diễn vector của tài liệu d). Nếu các tài liệu đã được chuẩn hóa thì s(d1, d2)
được dùng là tích vô hướng của (d1, d2). Với bất kỳ cụm Ф các tài liệu, thuật toán duy
trì một vector đại diện cho cụm và tính
.
p (φ ) =
d
∑
d ∈φ
Độ tích tụ của một cụm được tính theo công thức sau:
8
p(φ), p(φ) − φ
φ (φ −1)
s(φ) =
và
p(Ґ ∪ Δ) = <p(Ґ), p(Ґ)> + <p(Δ), p(Δ)> + 2<p(Ґ), p(Δ)>
Vì vậy để tính s(Ґ ∪ Δ) từ p(Ґ) và p(Δ) tại bước 4 của thuật toán HAC (ở trên)
chỉ phải mất thời gian để tính toán các tích vô hướng.
Ngoài ra còn một số phương pháp phân cụm bottom up khác như là: Single-link,
Group-average, Complete-link [1][9]:
• Single-link: với phương pháp này, khoảng cách giữa hai cụng được định
nghĩa là khoảng cách giữa những đối tượng giống nhau nhất giữa hai nhóm
D(r,s) = Min (d(i,j)) với i thuộc ra và j thuộc s. Với hai cụm bất kỳ, ta tính tất
cả các khoảng cách giữa hai phần tử thuộc hai cụm, từ đó suy ra khoảng cách
nhỏ nhất tìm được chính là khoảng cách giữa hai cụm. Tại mỗi bước, hai cụm
gần nhau nhất sẽ được chọn để ghép lại với nhau.
• Complete-link: Phương pháp này đối ngược với single-link, khoảng cách giữa
các cụm được định nghĩa là: D(r,s) = Max(d(i,j)) với i thuộc r, j thuộc s. Hai
cụm có khoảng cách nhỏ nhất sẽ được chọn để nhóm làm một cụm.
• Group-average: phân cụm bằng group-average đánh giá chất lượng phân cụm
dựa vào độ tương tự giữa tất cả các cụm, nó tránh được thiếu sót của hai
phương pháp single-link và complete-link. Nó tính độ tương tự trung bình
sim-ga của tất cả các cặp văn bản, bao gồm cả các cặp trong cùng một cụm,
nhưng những độ tương tự tính trong một cùng một cụm không chứa trong
phép trung bình.
1.2.2. Thuật toán phân cụm top-down
Nếu kỹ thuật phân cụm bottom-up dựa vào quá trình lặp việc trộn các cụm tài
liệu tương tự nhau đến khi đạt được số cụm mong muốn thì kỹ thuật top-down lại
ngược lại, gán các tài liệu vào các cụm được lập từ trước. Dưới đây sẽ trình bày hai
thuật toán phân cụm theo kỹ thuật top-down là k-means và Sufix Tree Clustering.
a. Thuật toán k-means
¾K-means với gán “cứng”
Theo các nghiên cứu được công bố, kỹ thuật phân cụm Bottom-up được sử dụng
trực tiếp tốn thời gian và không gian O(n2) và không thích hợp cho các tập dữ liệu lớn.
9
Nếu coi như đặt trước số cụm là k, kỹ thuật phân hoạch Top-down thường được sử
dụng vì hiệu quả hơn [6]. Một thuật toán nổi tiếng nhất sử dụng kỹ thuật này là thuật
toán K-means. Tồn tại hai dạng của thuật toán k-means là dạng cứng và dạng mềm[6].
Dạng “cứng” ánh xạ tài liệu tới các cụm theo một trong hai giá trị 0 hoặc 1, dạng
“mềm” ánh xạ tài liệu tới các cụm theo một giá trị trong khoảng 0 và 1.
Trong dạng tổng quát, thuật toán k-means sử dụng các biểu diễn nội tại cho các
đối tượng được phân cụm và chính các cụm. Sử dụng phương pháp biểu diễn vector
cho tài liệu và dùng vector trọng tâm các tài liệu thuộc cụm để thể hiện cho cụm.
Khởi tạo một cấu hình ban đầu tùy ý (hoặc được chọn từ một tính toán từ trước)
cho thuật toán k-means, chứa đựng tập các tài liệu được chia thành k cụm với k vector
trọng tâm tương ứng đã được tính. Quá trình thực hiện thuật toán theo mô tả sau
đây[6]:
1. Khởi tạo các trọng tâm của cụm từ các vector được chọn
2. while có thể tốt hơn do
3. for mỗi tài liệu d do
4. Tìm cụm c tại đó trọng tâm của cụm là gần nhất với d
5. Gán d cho cụm c
6. end for
7. for mỗi cụm c do
8. Tính lại trọng tâm của cụm c dựa vào các tài liệu đã gán cho nó.
9. end for
10. end while
Bước cơ bản (vòng lặp while) trong thuật toán k-means được gọi là move-to-
nearest. Tồn tại một số cách thức đặt điều kiện cho việc dừng vòng lặp. Một điều kiện
dừng vòng lặp while ("có thể tốt hơn") thường được dùng là sau khi thực hiện thân
vòng lặp while mà các cụm là không thay đổi (hoặc sự thay đổi là không đáng kể),
hoặc trọng tâm của cụm di chuyển các khoảng không đáng kể trong các lần lặp tiếp
theo.
¾Thuật toán K-means với gán “mềm”
Thay vì chỉ rõ việc gán các tài liệu cho các cụm, dạng “mềm” của k-means biểu
diễn mỗi cụm c sử dụng một vector μc trong không gian. Do không có một sự rõ ràng
10
trong việc gán các tài liệu cho các cụm, μc không trực tiếp liên hệ với các tài liệu – ví
dụ nó không cần thiết là trọng tâm của các tài liệu. Mục đích của k-means “mềm” là
2
tìm một μc cho mỗi cụm c để tối thiểu hóa lỗi lượng tử d minc d − μc . Một chiến
∑
lược đơn để giảm lỗi là đưa ra các vector trung bình là khoảng cách từ các tài liệu đến
cụm gần nhất[6]. Ta sẽ lập lại việc quét qua các tài liệu, và với mỗi tài liệu d, tích lũy
một Δμc cho cụm μc gần d nhất:
nếu μc gần d nhất
η(d −μ )
⎧
c
Δ =
⎨
∑
μC
các trường hợp khác
0
⎩
d
Sau khi quét một lần qua tất cả các tài liệu, tất cả các μc được cập nhật đồng loạt
bởi công thức μc Å μc + Δμc trong đó η được gọi là learning rate. Nó duy trì một số dữ
liệu của quá khứ và làm ổn định hệ thống. Chú ý mỗi tài liệu d chỉ chuyển vào một μc
trong mỗi đợt. Việc phân bố tài liệu d không bị giới hạn đến chỉ một μc mà gần nó
nhất. Việc phân bố có thể được chia sẻ giữa nhiều tài liệu, việc phân chia cho cụm c
quan hệ trực tiếp đến độ tương tự hiện thời giữa μc và d. Ví dụ để có thể làm mềm công
thức tính Δμc ở trên như sau:
2
1/ d − μc
Δμc =η
(d − μc )
2
1/ d − μ
∑
γ
γ
Hoặc
2
exp(− d − μc
)
Δμc =η
(d − μc )
2
exp(− d − μ
)
∑
γ
γ
Tồn tại nhiều quy tắc cập nhật khác có thể được sử dụng. Gán “mềm” không làm
mất đi liên kết chặt trong việc tạo nên phân bố các tài liệu cho một cụm đơn đạt được
một cách tỉ mỉ[6].
b. Thuật toán STC (Suffix Tree Clustering)
Theo [11][13] STC là thuật toán phân cụm dựa vào việc nhận dạng các cụm từ
thường xuyên xuất hiện trong một nhóm văn bản. Trong hoàn cảnh của chúng ta, một
cụm từ là một chuỗi có trình tự của một hoặc nhiều hơn một từ. Chúng ta định nghĩa
11
một base cluster (cụm cơ sở) là một tập hợp các văn bản cùng chia sẻ một cụm từ nào
đó.
Thuật toán gồm ba bước: (1) “làm sạch” tài liệu (document “learning”), (2) xác
định các cụm cơ sở (base clusters) sử dụng cây hậu tố, (3) trộn các cụm cơ sở tạo
thành các cụm.
(1)Trong bước làm sạch tài liệu, xóa tất cả các hậu tố và tiền tố của các từ nếu có,
đưa toàn bộ số nhiều về số ít, loại bỏ các ký tự không phải là một từ (như các thẻ
HTML, hệ thống dấu chấm câu), các từ trong tài liệu được giữ nguyên vị trí.
(2) Xác định các cụm cơ sở: Theo định nghĩa trong [13] thì cây hậu tố T là một
cây có hướng có gốc, biểu diễn một chuỗi s bất kỳ có chiều dài m với đúng m nút lá.
Mỗi cạnh trên cây hậu tố đều được gán nhãn bằng một chuỗi con khác rỗng của chuỗi
s. Các nhãn của hai cạnh bất kỳ xuất phát từ một nút chung phải bắt đầu bằng các ký
tự khác nhau. Đối với nút lá của cây hậu tố, việc kết các nhãn của các nút nằm trên con
đường đi từ gốc đến nút lá đó sẽ tạo thành một hậu tố của chuỗi s.
Như tên của nó, cây hậu tố sẽ biểu diễn các chuỗi hậu tố của 1 từ hoặc một cụm từ.
Chuỗi hậu tố là tập hợp các đơn vị từ hoặc chữ cái cạnh nhau đi sau từ hoặc cụm từ.
Đơn vị từ ở đây có thể là chữ cái nếu xây dựng cây hậu tố cho từ, và là từ nếu xây
dựng cây hậu tố cho 1 cụm
Lấy ví dụ: Từ misisippi có các hậu tố là
T1 = mississippi
T2 = ississippi
T3 = ssissippi
T4 = sissippi
T5 = issippi
T6 = ssippi
T7 = sippi
T8 = ippi
T9 = ppi
T10 = pi
12
T11 = i
Ta có thể sắp xếp lại từ tự dãy hậu tố trên như sau:
T11 = i
T8 = ippi
T5 = issippi
T2 = ississippi
T1 = mississippi
T10 = pi
T9 = ppi
T7 = sippi
T4 = sissippi
T6 = ssippi
T3 = ssissippi
Việc xây dựng như trên giúp ta xây dựng một cây với đặc điểm là:
• Không có 2 nút nào cùng là con của một nút có nhãn cạnh như nhau.
• Và có thể đưa ra tất cả các tập con với các đơn vị từ liên tiếp có đơn vị cuối là
đơn vị cuối của từ, cụm từ được đưa vào phân tích.
• Có một nút gốc sinh ra cây
• Mỗi nút trong có ít nhất 2 nút con
• Các nhãn được đặt phải có liên kết với nhau.
• Với mỗi hậu tố của s, tồn tại một nút có nhãn là s.
Cây hậu tố được tổ chức thành cây gồm nhiều nút. Mỗi nút sẽ lưu trữ tất cả các thông
tin về các cụm từ ( tần số xuất hiện trong tập văn bản, tần số xuất hiện trong từng văn
bản) trong khi quan hệ giữa chúng lại nói lên sự tồn tại của các cụm từ
Trong phân cụm, người ta sử dụng cây hậu tố mở rộng để phân tích các câu: [11] Cây
hậu tố mở rộng là cây hậu tố nhằm kết tất cả các hậu tố của các câu trong văn bản.
13
Tức là ta phân tích văn bản bằng cây hậu tố, mỗi câu được coi là một hậu tố, mỗi hậu
tố của câu cũng là một hậu tố. Mỗi nút có thể là 1 tử, hoặc là 1 cụm từ đi liền. Sau đó
xét tất cả các cụm được coi là hậu tố và xét quan hệ của chúng với nhau để nhóm lại
thành một cây.
Ví dụ một cây hậu tố với tập hợp các string là 3 câu: “cat ate cheese”, "mouse ate
cheese too" , "cat ate mouse too". Phân tích với cây hậu tố với mỗi đơn vị là một từ. Ở
trong văn bản gồm 3 câu này sẽ có các cụm từ được đưa ra lần lượt như sau:
1. cat [2]( 1 3)
2. cat ate [2]( 1 3)
3. cat ate cheese [1]( 3)
4. cat ate mouse [1]( 1)
5. cat ate mouse too [1]( 1)
6. ate [3]( 1 2 3) (ate xuất hiện 3 lần trong cả 3 câu)
7. ate cheese [2]( 2 3)
8. ate cheese too [1]( 2)
9. ate mouse [1]( 1)
10.ate mouse too [1]( 1)
11.cheese [2]( 2 3)
12.cheese too [1]( 2)
13.mouse [2]( 1 2)
14.mouse ate cheese [1]( 2)
15.mouse ate cheese too [1]( 2)
16.mouse too [1]( 1)
17.too [2]( 1 2]
14
và cây hậu tố chúng ta xây dựng được sẽ là
tree1>|---cat ate cheese
|---ate cheese
|---cheese
Tree2>|---mouse ate cheese too
|---ate cheese too
|--- cheese too
|--- too
Tree3>|---cat ate mouse too
|---ate mouse too
|--- mouse too
|---too
Coi mỗi hậu tố là một vector. Ta so sánh độ tương đồng giữa các vetor và dùng các
thuật toán gom cụm để gom các câu trong văn bản lại và tổng hợp đưa ra vector đặc
trưng cho câu. Cây cuối cùng được đưa ra là
TreeÆ|---cat ate|---cheese
|
|
|----mouse
|---ate|---cheese|---too
|--- $
|---mouse too
|
|
|
|
|---mouse|---too
|
|---ate cheese too
|---cheese|---too
|
|---$
|---too
15
Hình 2: Cây hậu tố mở rộng
Trong đó Node(a, b):
a= hậu tố thuộc câu
b= số thứ tự của lần xuất hiện
chúng ta gán nhãn cho tất cả các nút trong của cây. Mỗi nhãn này tương đương với
một từ hoặc một cụm từ nhận được từ các cạnh liền nhau từ gốc đến nhãn đó. Sau đó
đánh giá các nút này.
Node Cụm từ
Văn bản
1, 3
a
b
c
d
e
F
Cat ate
Ate
1, 2, 3
1, 3
Cheese
Mouse
Too
2, 3
2, 3
Ate cheese 1, 2
Bảng 2: Các tài liệu chứa cụm từ ở các node
Và bằng cách này, cụm cơ sở được đưa ra dựa vào số văn bản mà cụm từ này xuất hiện
và số từ trong cụm. Công thức:
S(B) = |B| * f
16
Trong đó: |B| là số văn bản trong cụm cơ sở B
|P| số lượng từ hợp pháp trong cụm P (have non zero score)
zero score words: stopwords, quá ít(<3) hoặc quá nhiều( >40%)
hàm f không xác định với các cụm từ có độ dài bằng 1, là một hàm tuyến tính với
những cụm từ có độ dài từ 2 đến 6 và sẽ không đổi với những cụm từ dài hơn 6.
(3)Một vấn đề đặt ra là các văn bản có thể chứa nhiều cụm từ giống nhau. Vì thế
với cách phân cụm cơ sở như trên thì việc 2 cụm cơ sở có chia sẻ chung một số văn
bản có xác suất khá lớn. Để tránh việc trùng lấp này chúng ta trộn những cụm có chứa
số văn bản dùng chung lại thành một cụm. Giả sử Bm and Bn là 2 cụm phân biệt. Gọi
|Bm∩Bn| là tập hợp các văn bản thuộc cả 2 cụm trên.
Chúng ta định nghĩa độ tương tự giữa 2 cụm là 1 nếu:
|Bm∩Bn|/|Bm| >0.5 và
|Bm∩Bn|/|Bn| > 0.5.
Và là 0 trong trường hợp còn lại
Hình 3: Kết quả sau khi trộn các tài liệu
Xét trong ví dụ trên. Các thông số được thể hiện như hình trên. Mỗi nút là một
cụm và mỗi cạnh nối với nhau thể hiện rằng độ tương tự giữa 2 cụm là lớn hơn 1 tức là
các cụm có tồn tại một cạnh nối có thể hợp lại với nhau thành một cụm. như vậy sơ đồ
trên thể hiện duy nhất một cụm.
17
Xét trong trường hợp của ví dụ này. Ta thấy b (ate) là một stopword, nút b sẽ
được đánh giá là 0. Như vậy các cạnh nối từ b cũng bị bỏ đi và chúng ta có 3 cụm
được đưa ra là “mouse too” “cat ate” “ate cheese”
1.3. Đánh giá các thuật toán phân cụm
Như đã được giới thiệu, thuật toán AHC thường chậm khi áp dụng cho các tập tài
liệu lớn. Các thuật toán khác theo hướng này như Single-link và Group-average có
thời gian thực hiện là O(n2), đồng thời thời gian kết nối hoàn toàn (complete-link) là
O(n3). Các thuật toán theo hướng này là quá chậm so với yêu cầu của bài toán phân
cụm Web. Một điểm đáng chú ý nữa đối với các thuật toán HAC là điều kiện dừng. Đã
có rất nhiều đề xuất về điều kiện dừng được đưa ra nhưng chủ yếu là dựa trên việc
điều kiện dừng đã được xác định trước (chẳng hạn, dừng khi chỉ còn 5 cụm). Điều kiện
dừng đối với các thuật toán này (HAC) là cực kỳ quan trọng. Nếu như thuật toán trộn
các cụm “tốt” với nhau có thể tạo ra kết quả không theo mong muốn của người dùng.
Trên Web, với kết quả trả về theo truy vấn là vô cùng đa dạng (về số lượng, độ lớn,
kiểu và sự phù hợp của các tài liệu) thì điều kiện dừng không tốt sẽ làm cho kết quả trở
nên nghèo nàn [6].
Thuật toán k-means thuộc vào lớp các thuật toán phân cụm thời gian tuyến tính
và là những lựa chọn tốt nhất để đáp ứng yêu cầu về tốc độ của bài toán phân cụm on-
line. Thời gian thực hiện của các thuật toán này là O(nk) trong đó k là số các cụm
mong muốn [6]. Thêm một ưu điểm của thuật toán K-means so với HAC là việc đáp
ứng các yêu cầu của bài toán phân cụm Web là nó có thể tạo ra các cụm có sự giao
thoa. Điểm yếu chính của thuật toán này là nó chạy hiệu quả nhất chỉ khi các cụm
mong muốn là các miền hình cầu đối với độ đo tương tự được dùng. Không có lý do gì
để tin rằng các tài liệu sẽ thuộc vào các miền cầu. Vì vậy thuật toán có thể làm mất đi
các thông tin có giá trị.
Các thuật toán như HAC hay K-means đều không là các thuật toán gia tăng. Một
số thuật toán gia tăng đã được phát triển như thuật toán phân cụm cây hậu tố (Suffix
Tree Clustering - STC), với thời gian thực hiện O(n) trong đó n là kích thước của tập
tài liệu[6].
18
Chương 2. Phân cụm văn bản tiếng Việt
2.1. Đặc trưng của tiếng Việt và tách từ trong tiếng việt
Có thể nói, khai phá web là giao thoa của khai phá dữ liệu, xử lý ngôn ngữ tự
nhiên và Word-Wide-Web. Vì vậy để có thể làm việc được với các tài liệu web tiếng
Việt cần phải tìm hiểu về các đặc trưng của tiếng Việt và việc tách từ tiếng Việt.
2.1.1. Đặc trưng của tiếng Việt
Tiếng Việt thuộc ngôn ngữ đơn lập, tức là mỗi một tiếng (âm tiết) được phát âm
tách rời nhau và được thể hiện bằng một chữ viết. Đặc điểm này thể hiện rõ rệt ở tất cả
các mặt ngữ âm, từ vựng, ngữ pháp. Dưới đây trình bày một số đặc điểm của tiếng
Việt theo các tác giả ở Trung tâm ngôn ngữ học Việt Nam đã trình bày Error!
Reference source not found..
a. Đặc điểm ngữ âm
Tiếng Việt có một loại đơn vị đặc biệt gọi là "tiếng", về mặt ngữ âm, mỗi tiếng là
một âm tiết. Hệ thống âm vị tiếng Việt phong phú và có tính cân đối, tạo ra tiềm năng
của ngữ âm tiếng Việt trong việc thể hiện các đơn vị có nghĩa. Nhiều từ tượng hình,
tượng thanh có giá trị gợi tả đặc sắc. Khi tạo câu, tạo lời, người Việt rất chú ý đến sự
hài hoà về ngữ âm, đến nhạc điệu của câu văn.
b. Đặc điểm từ vựng:
Mỗi tiếng nói chung là một yếu tố có nghĩa. Tiếng là đơn vị cơ sở của hệ thống
các đơn vị có nghĩa của tiếng Việt. Từ tiếng, người ta tạo ra các đơn vị từ vựng khác
để định danh sự vật, hiện tượng..., chủ yếu nhờ phương thức ghép và phương thức
láy.
Việc tạo ra các đơn vị từ vựng ở phương thức ghép luôn chịu sự chi phối của quy
luật kết hợp ngữ nghĩa, ví dụ: đất nước, máy bay, nhà lầu xe hơi, nhà tan cửa nát...
Hiện nay, đây là phương thức chủ yếu để sản sinh ra các đơn vị từ vựng. Theo phương
thức này, tiếng Việt triệt để sử dụng các yếu tố cấu tạo từ thuần Việt hay vay mượn từ
các ngôn ngữ khác để tạo ra các từ, ngữ mới, ví dụ như tiếp thị, karaoke, thư điện tử
(e-mail), thư thoại (voice mail), phiên bản (version), xa lộ thông tin, siêu liên kết văn
bản, truy cập ngẫu nhiên, v.v.
19
Việc tạo ra các đơn vị từ vựng ở phương thức láy thì quy luật phối hợp ngữ âm
chi phối chủ yếu việc tạo ra các đơn vị từ vựng, chẳng hạn như chôm chỉa, chỏng chơ,
đỏng đa đỏng đảnh, thơ thẩn, lúng lá lúng liếng, v.v.
Vốn từ vựng tối thiểu của tiếng Việt phần lớn là các từ đơn tiết (một âm tiết, một
tiếng). Sự linh hoạt trong sử dụng, việc tạo ra các từ ngữ mới một cách dễ dàng đã tạo
điều kiện thuận lợi cho sự phát triển vốn từ, vừa phong phú về số lượng, vừa đa dạng
trong hoạt động. Cùng một sự vật, hiện tượng, một hoạt động hay một đặc trưng, có
thể có nhiều từ ngữ khác nhau biểu thị. Tiềm năng của vốn từ ngữ tiếng Việt được phát
huy cao độ trong các phong cách chức năng ngôn ngữ, đặc biệt là trong phong cách
ngôn ngữ nghệ thuật. Hiện nay, do sự phát triển vượt bậc của khoa học-kĩ thuật, đặc
biệt là công nghệ thông tin, thì tiềm năng đó còn được phát huy mạnh mẽ hơn.
c. Đặc điểm ngữ pháp
Từ của tiếng Việt không biến đổi hình thái. Đặc điểm này sẽ chi phối các đặc
điểm ngữ pháp khác. Khi từ kết hợp từ thành các kết cấu như ngữ, câu, tiếng Việt rất
coi trọng phương thức trật tự từ và hư từ.
Việc sắp xếp các từ theo một trật tự nhất định là cách chủ yếu để biểu thị các
quan hệ cú pháp. Trong tiếng Việt khi nói “Anh ta lại đến” là khác với “Lại đến anh
ta”. Khi các từ cùng loại kết hợp với nhau theo quan hệ chính phụ thì từ đứng trước
giữ vai trò chính, từ đứng sau giữ vai trò phụ. Nhờ trật tự kết hợp của từ mà "củ cải"
khác với "cải củ", "tình cảm" khác với "cảm tình". Trật tự chủ ngữ đứng trước, vị ngữ
đứng sau là trật tự phổ biến của kết cấu câu tiếng Việt.
Phương thức hư từ cũng là phương thức ngữ pháp chủ yếu của tiếng Việt. Nhờ
hư từ mà tổ hợp “anh của em” khác với tổ hợp “anh và em”, “anh vì em”. Hư từ cùng
với trật tự từ cho phép tiếng Việt tạo ra nhiều câu cùng có nội dung thông báo cơ bản
như nhau nhưng khác nhau về sắc thái biểu cảm. Ví dụ, so sánh các câu sau đây:
- Ông ấy không hút thuốc.
- Thuốc, ông ấy không hút.
- Thuốc, ông ấy cũng không hút.
Ngoài trật tự từ và hư từ, tiếng Việt còn sử dụng phương thức ngữ điệu. Ngữ điệu
giữ vai trò trong việc biểu hiện quan hệ cú pháp của các yếu tố trong câu, nhờ đó nhằm
đưa ra nội dung muốn thông báo. Trên văn bản, ngữ điệu thường được biểu hiện bằng
20
dấu câu. Sự khác nhau trong nội dung thông báo được nhận biệt khi so sánh hai câu
sau:
- Đêm hôm qua, cầu gãy.
- Đêm hôm, qua cầu gãy.
Qua một số đặc điểm nổi bật vừa nêu trên đây, chúng ta có thể hình dung được
phần nào bản sắc và tiềm năng của tiếng Việt
2.1.2. Tách từ tiếng Việt
Các tác giả [6][12]rút ra một số đặc điểm của từ tiếng Việt như sau:
- là đơn vị có ranh giới trùng với hình vị và âm tiết
- không có sự biến đổi hình thái trong quá trình sử dụng
- là đơn vị có sẵn, được tái hiện trong khi nói
- có tính định hình hoàn chỉnh
- Có thể chia từ tiếng việt thành hai loại: từ đơn và từ phức
Chính từ những đặc điểm này mà tách từ là một khó khăn chính trong việc xử lý
các văn bản tiếng Việt. Mặc dù được viết bằng các ký tự La tinh mở rộng, tiếng Việt
cũng có những đặc tính chung với các ngôn ngữ Đông Nam Á khác như khó xác định
ranh giới giữa các từ và có các điểm khác biệt về phonetic, văn phạm và ngữ nghĩa so
với tiếng Anh. Do đó, rất khó có thể áp dụng các kỹ thuật và hướng tiếp cận đã được
nghiên cứu và thử nghiệm thành công trên tiếng Anh cho tiếng Việt nếu không xây
dựng thành công giải pháp cho việc tách từ trong văn bản tiếng Việt. Dưới đây là một
số điểm khác biệt chính giữa tiếng Việt và tiếng Anh được trình bày trong [12].
Đặc điểm
Đơn vị cơ bản
Tiền tố/Hậu tố
Từ loại
Tiếng việt
Tiếng
Tiếng Anh
Từ
Có
Không có
Not unanimous
Được định nghĩa rõ
Tổ hợp có nghĩa dựa vào
ngữ cảnh của các tiếng
Khoảng trắng hoặc
dấu câu
Ranh giới từ
Bảng 3: So sánh một số đặc điểm của tiếng Việt và tiếng Anh
21
Những đặc điểm này làm cho việc tách từ tiếng việt trở nên khó khăn hơn. Dưới
đây là kết quả khảo sát về tách từ trong văn bản tiếng hoa và thống kê về tách từ tiếng
Việt được công bố hiện tại [12].
Hình 4: Thống kê về tách từ tiếng Hoa và tiếng Việt [12]
Các hướng tiếp cận dựa trên “từ”: được chia thành 3 nhóm: dựa vào thống kê,
dựa vào từ điển và nhóm lai, nhằm tách từ trọng vẹn trong câu. Các giải pháp dựa theo
hướng tiếp cận vào thống kê cần phải dựa vào thông tin thống kê như term, từ hay tần
số ký tự. hay xác suất cùng xuất hiện trong một tập dữ liệu cơ sở. Do đó, tính hiệu quả
của các giải pháp này chủ yếu dựa vào dữ liệu huấn luyện cụ thể được sử dụng. Trong
hướng tiếp cận dựa vào từ điển, các đoạn văn bản được đối sánh dựa vào từ điển. Việc
xây dựng từ điển các từ và ngữ pháp tiếng việt hoàn chỉnh là không khả thi. Hướng
tiếp cận lai áp dụng nhiều cách khác nhau để tận dụng ưu điểm của các giải pháp. Các
hướng tiếp cận để phân loại văn bản tiếng việt dựa vào từ chỉ khả thi khi có một bộ từ
vựng tốt.
22
Tải về để xem bản đầy đủ
55 trang
28/04/2025
140
Bạn đang xem 30 trang mẫu của tài liệu "Khóa luận Sử dụng phương pháp xếp hạng trong bài toán phân cụm tiếng Việt", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.
File đính kèm:
- khoa_luan_su_dung_phuong_phap_xep_hang_trong_bai_toan_phan_c.pdf
