Phát hiện các quan hệ từ CSDL Text
MỤC LỤC
MỤC LỤC 1
MỞ ĐẦU 3
CHƯƠNG 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ KHAI PHÁ TEXT 5
1.1.Khai phá dữ liệu và phát hiện tri thức trong cơ sở dữ liệu 5
1.1.1Khái niệm 5
1.1.2.Các phương pháp khai phá dữ liệu 8
1.1.2.1.Các bài toán chủ yếu của khai phá dữ liệu 8
1.1.2.2.Các thành phần của thuật toán khai phá dữ liệu 9
1.1.2.3.Các phương pháp khai phá dữ liệu phổ biến 10
1.1.3. Ứng dụng của Khai phá dữ liệu 12
1.2. Khai phá dữ liệu Text 12
1.2.1. Giới thiệu 12
1.2.2. Các bài toán trong Khai phá Dữ liệu Text 14
1.2.3. Các vấn đề quan trọng trong Khai phá Dữ liệu Text 17
1.2.4. Phân loại các hệ thống Khai phá Text 18
1.3.Kết luận chương 1 26
CHƯƠNG 2. QUAN HỆ NGUYÊN NHÂN - KẾT QUẢ VÀ THUẬT TOÁN PHÁT
HIỆN QUAN HỆ NGUYÊN NHÂN - KẾT QUẢ 27
2.1. Giới thiệu 27
2.2. Các quan hệ ngữ nghĩa trong cơ sở tri thức ngữ nghĩa từ vựng 28
2.3. Quan hệ nguyên nhân - kết quả 29
2.4. Biểu diễn các quan hệ nguyên nhân - kết quả trong Tiếng Anh 32
2.4.1.Các cấu trúc nhân quả tường minh 33
2.4.1.1.Các từ nối chỉ nguyên nhân 33
2.4.1.2.Các động từ chỉ nguyên nhân 34
2.4.1.3.Các mệnh đề điều kiện 36
2.4.1.4.Các tính từ và trạng từ chỉ nguyên nhân 37
2.4.2.Các cấu trúc nhân quả không tường minh 38
2.4.2.1 Các danh từ phức biểu diễn quan hệ nguyên nhân - kết quả 38

2.4.2.2 Các động từ trong quan hệ nguyên nhân - kết quả không tường minh 39
2.4.2.3 Cấu trúc ngôn từ 40
2.5. Thuật toán phát hiện quan hệ nguyên nhân - kết quả 41
2.5.1. Các công trình liên quan 41
2.5.2. Thuật toán phát hiện quan hệ nguyên nhân - kết quả 41
-1-
Phát hiện các quan hệ từ CSDL Text
2.6.Kết luận chương 2 44
CHƯƠNG 3 : KẾT QUẢ THỬ NGHIỆM THUẬT TOÁN 44
3.1. Giới thiệu 44
3.2. Mô tả dữ liệu 45
3.3. Xây dựng chương trình 47
3.4. Kết quả thử nghiệm 50
3.5. Nhận xét 52
3.6. Kết luận chương 3 52
KẾT LUẬN 53
TÀI LIỆU THAM KHẢO 54
-2-
Phát hiện các quan hệ từ CSDL Text
MỞ ĐẦU
Trong những năm gần đõy, trên cơ sở phát triển và ứng dụng công nghệ
Internet, khối lượng dữ liệu trên máy tính đã tăng trưởng không ngừng theo cả phương
diện tạo mới và thu thập thông tin. Việc mở rộng các dữ liệu khoa học về khoa học địa
lý, địa chất, khí tượng do vệ tinh thu thập lại, việc giới thiệu quảng bá mã vạch đối với
hầu hết các sản phẩm thương mại, việc tin học hoá sâu rộng các thương vụ và giao
dịch, việc phát triển ứng dụng công nghệ thông tin trong quản lý hành chính nhà
nước đã phát sinh ra một khối lượng dữ liệu khổng lồ. Mặt khác, trong xã hội công
nghệ thông tin hiện nay, nhu cầu nhận được thông tin một cách nhanh chóng, chính
xác cũng như nhu cầu thu nhận được những tri thức hữu ích từ khối lượng thông tin
khổng lồ nói trên đã trở nên cấp thiết. Nói một cách hình ảnh là chúng ta đang “ngập”

trong dữ liệu nhưng lại “đúi” tri thức. Bối cảnh đó đã đòi hỏi phải có những phương
pháp tiếp cận mới, điển hình nhất là các phương pháp thuộc lĩnh vực khai phá dữ liệu.
Sự tăng trưởng hàng năm về số lượng các công trình nghiên cứu được công bố, các hội
thảo khoa học quốc tế liên quan đến việc giải quyết các bài toán điển hình thuộc lĩnh
vực này đã thể hiện đầy đủ sự phát triển vượt bậc của KPDL. Các phương pháp KPDL
đang ngày càng phát triển mạnh mẽ và thu hút nhiều sự quan tâm chú ý của các nhà
nghiên cứu trong các ứng dụng thực tiễn của nó như : khai phá text và khai phá web,
tin-sinh học, tài chính và thị trường chứng khoán
Khai phá Text là một trong những ứng dụng điển hình của KPDL, hiện đang
một lĩnh vực khá nổi bật và chủ yếu liên quan tới việc trớch rỳt cỏc khái niệm, các
quan hệ và các tri thức tiềm ẩn từ các tài liệu văn bản. Trạng thái nghệ thuật của khai
phá Text hiện nay dựa trên sự trình diễn các tài liệu văn bản đi cùng với các kỹ thuật
khai phá dữ liệu thống kê. Hướng tiếp cận này bị hạn chế do ngôn ngữ tự nhiên có độ
nhập nhằng rất cao. Luận văn này đi sâu nghiên cứu về mối quan hệ ngữ nghĩa nguyên
nhân - kết quả trong ngôn ngữ tự nhiên và trình bày một thuật toán khai phá nhằm phát
hiện các quan hệ này dựa trên tần suất xuất hiện của các cặp danh từ có quan hệ nhân
quả với nhau
Luận văn bao gồm phần mở đầu, ba chương nội dung và phần kết luận. Nội
dung các chương được trình bày như sau :
Chương 1: Trong chương này trình bày một cách khái quát nhất về khai phá
dữ liệu và khai phá Text, các bài toán chủ yếu, các phương pháp điển hình cũng như
các ứng dụng trong thực tiễn.
-3-
Phát hiện các quan hệ từ CSDL Text
Chương 2 : Nội dung chương hai giới thiệu sơ qua một số các quan hệ ngữ
nghĩa trong cơ sở tri thức ngữ nghĩa từ vựng và cụ thể đi sâu vào nghiên cứu quan hệ
ngữ nghĩa nguyờn nhõn-kết quả: nêu khái niệm, ý nghĩa và cấu trúc của các quan hệ
này biểu diễn trong tiếng Anh. Trong phần này cũng đã trình bày một thuật toán nhằm
phát hiện các cặp danh từ nguyên nhân và kết quả trong các mối quan hệ nguyên nhân
kết quả tường minh dựa trên trọng số của động từ chỉ nguyên nhân và tần suất xuất

hiện của các cặp danh từ trong các cấu trúc câu thể hiện quan hệ nguyên nhân - kết quả
đó.
Chương 3: Trình bày về hệ thống thử nghiệm của thuật toán phát hiện quan hệ
ngữ nghĩa nguyên nhân - kết quả được trình bày trong chương hai. Đưa ra một số kết
quả ban đầu, những nhận xét, kết luận và một số hướng phát triển nghiên cứu trong
tương lai.

-4-
Phát hiện các quan hệ từ CSDL Text
CHƯƠNG 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ
KHAI PHÁ TEXT
1.1.Khai phá dữ liệu và phát hiện tri thức trong cơ sở dữ liệu
1.1.1Khái niệm
Xu thế “bựng nổ thông tin” hiện nay với sự tăng trưởng vượt bậc cả về số
lượng lẫn về dung lượng của các hệ thống dữ liệu (bao gồm cơ sở dữ liệu (CSDL)
thương mại, khoa học trong các tổ chức thuộc phạm vi quốc gia hay liên quốc gia và
hệ thống tài liệu Internet) ngày càng nhiều. Do nhu cầu trích lọc các dữ liệu đó thành
các thông tin và tri thức có ích cho các ứng dụng rộng rãi như phân tích thị trường,
quản trị doanh nghiệp, hỗ trợ quyết định ngày càng tăng, các hệ thống dữ liệu đòi hỏi
một thế hệ mới các kỹ thuật và công cụ phân tích dữ liệu tự động và thông minh. Các
kỹ thuật và công cụ như vậy thuộc vào một lĩnh vực nghiên cứu và triển khai nhanh
chóng trở thành nổi bật và ngày càng được quan tâm trong ngành công nghệ thông tin
những năm gần đõy, đó là lĩnh vực phát hiện tri thức trong CSDL (Knowledge
Discovery in Databases : KDD).
Định nghĩa [1]: Phát hiện tri thức trong cơ sở dữ liệu (KDD – Knowledge
Discovery in Database) là một quá trình không tầm thường nhận ra những mẫu có giá
trị, mới, hữu ích tiềm năng và hiểu được trong dữ liệu. (William J Frawley, Gregory
Piatetsky-Shapiro, và Christopher J Matheus 1991 [FSSU96])
Trong định nghĩa trên:
Dữ liệu là một tập F gồm các sự kiện ( tức là F gồm nhiều trường hợp) và

tương ứng với tập F là một ngôn ngữ L được sử dụng để biểu diễn sự kiện theo tập con
của F.
Mẫu là một biểu thức E trong ngôn ngữ L được dùng để biểu diễn sự kiện
trong một tập con F
E
của F. Biểu thức này phải đơn giản hơn là việc liệt kê tất cả các
sự kiện trong F.
Thông thường, quá trình KDD bao gồm nhiều bước, thường là các bước
chuẩn bị dữ liệu, tìm kiếm mẫu, ước lượng tri thức, tinh chế tương tác nội tại sau khi
biến đổi dạng trình bày. Quá trình được thừa nhận là không tầm thường (non-trivial)
theo nghĩa là quá trình đó bao hàm tìm kiếm tự động ở mức độ nhất định.
Mẫu cần phải cú các tính chất sau :
-5-
Phát hiện các quan hệ từ CSDL Text
Tính có giá trị : mẫu được phát hiện cần có giá trị đối với dữ liệu sẽ bổ sung
(mới) theo một mức độ chân thực nào đấy. Độ đo chân thực c của biểu thức E trong
L : c = C(E,F).
Tính mới : mẫu là mới nếu có các thay đổi trong dữ liệu khi so sánh giá trị
hiện tại với giá trị cũ hoặc giá trị dự đoán, hoặc cho thấy các giá trị mới tìm được liên
quan thế nào với các giá trị cũ, đo bằng hàm N(E,F).
Tính hữu ích tiềm năng : Mẫu cần có khả năng chỉ dẫn tới cỏc tác động hữu
dụng và được đo bởi một hàm tiện ích U(E,F).
Tính hiểu được : tạo ra các mẫu cho con người hiểu dễ dàng hơn các dữ liệu
cơ sở. Độ đo dễ dàng : S(E,F).
Điều quan trọng là tính hấp dẫn, thường được cho như độ đo tổng thể về mẫu :
tính giá trị, tính mới, tính hữu ích và tính dễ hiểu và có thể được đo bằng một hàm I
trong không gian đo được M
i
: i= I(E,F,C,N,U,S). Mẫu E∈ L được gọi là tri thức nếu
với ngưỡng i do người dùng định nghĩa ta có I(E,F,C,N,U,S) >i.

Khai phá dữ liệu (data mining) được định nghĩa như là một quá trình chắt lọc
hay khai phá tri thức từ một lượng lớn dữ liệu. Một ví dụ hay được sử dụng là là việc
khai thác vàng từ đá và cát, Khai phá dữ liệu được ví như công việc “Đói cỏt tỡm
vàng” trong một tập hợp lớn các dữ liệu cho trước. Thuật ngữ Khai phá dữ liệu ám chỉ
việc tìm kiếm một tập hợp nhỏ có giá trị từ một số lượng lớn các dữ liệu thô. Có nhiều
thuật ngữ hiện được dùng cũng có nghĩa tương tự với từ Khai phá dữ liệu như Khai
phá tri thức (Knowledge Mining ), chắt lọc tri thức (knowledge extraction), phân tích
dữ liệu/mẫu (data/patern analysis), khảo cổ dữ liệu (data archaeoloogy), nạo vét dữ
liệu (data dredging ),
Tóm lại, có rất nhiều định nghĩa về khai phá dữ liệu, các định nghĩa này đều
mang tính mô tả, tuy nhiên có thể tạm hiểu rằng Khai phá dữ liệu như là một công
nghệ tri thức giúp khai thác những thông tin hữu ích từ những kho dữ liệu được tích
trữ trong suốt quá trình hoạt động của một công ty, tổ chức nào đó. Dưới đõy tôi xin
đưa ra một trong số các định nghĩa về khai phá dữ liệu như sau:
Định nghĩa [27] : Khai phá dữ liệu là một tập hợp các kỹ thuật được sử dụng
để tự động khai thác và tìm ra các mối quan hệ lẫn nhau của dữ liệu trong một tập
hợp dữ liệu khổng lồ và phức tạp, đồng thời cũng tìm ra các mẫu tiềm ẩn trong tập dữ
liệu đó.
-6-
Phát hiện các quan hệ từ CSDL Text
Nhìn chung, quá trình phát hiện tri thức là một chuỗi nối tiếp và lặp lại các
bước còn khai phá dữ liệu là một trong các bước đó :
1.Làm sạch dữ liệu : xử lý các dữ liệu có lỗi, bị nhiễu, thiếu dữ liệu hoặc dữ
liệu không thích hợp.
2.Tích hợp dữ liệu : các nguồn dữ liệu bị lặp lại, không đồng nhất có thể được
tích hợp làm một.
3.Chọn lọc dữ liệu : là bước trích chọn những tập dữ liệu cần được khai phá từ
các tập dữ liệu lớn (databases, data warehouses, data repositories) ban đầu theo một số
tiêu chí nhất định.
4.Tiền xử lý dữ liệu : là bước làm sạch dữ liệu (xử lý với dữ liệu không đầy

đủ, dữ liệu nhiễu, dữ liệu không nhất quán, .v.v.), rút gọn dữ liệu (sử dụng hàm nhóm
và tính tổng, các phương pháp nén dữ liệu, sử dụng histograms, lấy mẫu, .v.v.), rời rạc
hóa dữ liệu (rời rạc hóa dựa vào histograms, dựa vào entropy, dựa vào phân khoảng,
.v.v.). Sau bước này, dữ liệu sẽ nhất quán, đầy đủ, được rút gọn, và được rời rạc hóa.
5.Biến đổi dữ liệu : đây là bước chuẩn hóa và làm mịn dữ liệu để đưa dữ liệu
về dạng thuận lợi nhất nhằm phục vụ cho các kỹ thuật khai phá ở bước sau.
6.Khai phá dữ liệu : đây là bước áp dụng những kỹ thuật khai phá (phần nhiều
là các kỹ thuật của machine learning) để khai phá, trích chọn được những mẫu
(patterns) thông tin, những mối liên hệ (relationships) đặc biệt trong dữ liệu. Đây được
xem là bước quan trọng và tốn nhiều thời gian nhất của toàn quá trình KDD.
7.Trình diễn và đánh giá tri thức: những mẫu thông tin và mối liên hệ trong dữ
liệu đã được khai phá ở bước trên được chuyển dạng và biểu diễn ở một dạng gần gũi
với người sử dụng như đồ thị, cây, bảng biểu, luật, .v.v. Đồng thời bước này cũng
đánh giá những tri thức khám phá được theo những tiêu chí nhất định.
-7-
Phát hiện các quan hệ từ CSDL Text
Hình 1.Các bước trong quá trình KDD
1.1.2.Các phương pháp khai phá dữ liệu
Thành phần khai phá dữ liệu của quá trình KDD thường bao gồm việc áp dụng
từng phần lặp của các phương pháp khai phá dữ liệu riêng. Chúng ta sử dụng thuật ngữ
mẫu và mô hình mở rộng xuyên suốt trong mục này : một mẫu có thể được suy nghĩ
như là một thuyết minh của một mô hình, tức là f(x) = 3x
2
+ x là một mẫu trong khi
f(x) = ax
2
+bx được coi là một mô hình.
Hầu hết các phương pháp khai phá dữ liệu dựa theo các nội dung từ vấn đề
học máy, tổ chức mẫu và thống kê : phân lớp, tách đoạn, thống kê, mô hình đồ thị v.v.
1.1.2.1.Các bài toán chủ yếu của khai phá dữ liệu

• Phân lớp : là việc học một hàm ánh xạ (các lớp) của các tên gọi dữ liệu vào
một trong số lớp đã biết trước. (Hand 1981; Weiss và Kulikowsk 1991; Maclachlan
1992). Quá trình này phân tích một tập dữ liệu huấn luyện (tức là một tập các đối
tượng mà ta đã biết tên lớp của nó) và xây dựng một mô hình cho mỗi lớp dựa trên các
đặc tính trong dữ liệu. Một cây quyết định hoặc một tập các luật phân lớp được tạo ra
từ quá trình phân lớp đú, nó có thể được dùng để hiểu rõ hơn mỗi lớp trong cơ sở dữ
liệu và để phân loại dữ liệu trong tương lai.
Ví dụ, người ta có thể phân loại các bệnh và giúp dự đoán bệnh dựa trên các
triệu chứng của bệnh nhân. Phân lớp được dùng trong việc phân nhóm khách hàng, mô
hình hóa doanh nghiệp và phân tích tín dụng
• Hồi quy : là việc học máy một hàm ánh xạ từ một tên dữ liệu sang một biến
khẳng định giá trị thực. Có rất nhiều các ứng dụng khai phá dữ liệu với nhiệm vụ hồi
-8-
Phát hiện các quan hệ từ CSDL Text
quy, ví dụ như đỏnh giá khả năng tử vong của bệnh nhân dựa trên các kết quả xét
nghiệm chẩn đoán, dự đoán nhu cầu tiêu thụ một sản phẩm mới bằng một hàm chi tiêu
quảng cáo.
• Phân cụm : là bài toán mô tả chung để tìm ra một tập hữu hạn các loại
hoặc các đoạn để mô tả dữ liệu. (Titterington, Smith và Makov 1985; Jain và Dubes
1988). Cỏc nhúm có thể tách rời hoặc phân cấp hoặc chồng chéo lên nhau (vừa thuộc
nhóm này vừa thuộc nhúm khỏc). Cỏc ứng dụng khai phá dữ liệu có nhiệm vụ phân
nhóm như phát hiện tập khách hàng có phản ứng giống nhau trong cơ sở dữ liệu tiếp
thị, xác định các loại quang phổ từ các phương pháp đo tia hồng ngoại.
• Tóm lược : bao gồm các phương phỏp tỡm một mô tả cô đọng đối với một
tập con dữ liệu. Ví dụ điển hình là bảng kỳ vọng và độ lệch chuẩn của mọi trường. Kỹ
thuật tóm lược thường được áp dụng trong việc phân tích dữ liệu tương tác có tính
thăm dò và báo cáo tự động.
• Mô hình hoá phụ thuộc : bao gồm việc tìm một mô hình mô tả sự phụ
thuộc có ý nghĩa giữa các biến. Các mô hình phụ thuộc gồm hai mức, mức cấu trúc
của mô hình (thường dưới dạng đồ thị) mô tả những biến nào là phụ thuộc cục bộ với

nhau và mức định lượng của một mô hình mô tả sức mạnh sự phụ thuộc theo một
thước đo nào đó.
• Phát hiện sự thay đổi và độ lệch : tập trung vào việc phát hiện hầu hết sự
thay đổi có ý nghĩa dưới dạng độ đo đã biết trước hoặc giá trị chuẩn (Bemdt và
Clifort, Bassen ville và Nikitov 1993 )
Các bài toán khác nhau này đỏi hỏi số lượng và dạng thông tin khác nhau nên
chúng thường ảnh hưởng đến việc thiết kế và chọn thuật toán khai phá dữ liệu khác
nhau.
1.1.2.2.Các thành phần của thuật toán khai phá dữ liệu
Ba thành phần chủ yếu trong một thuật toán khai phá dữ liệu là trình diễn mô
hình, đỏnh giá mô hình và phương pháp tìm kiếm.
Trình diễn mô hình : là việc xây dựng ngôn ngữ L để miêu tả các mẫu có thể
được khám phá. Nếu sự mô tả này bị giới hạn quá thì sẽ không xây dựng được mô
hình chính xác cho dữ liệu, vì thế người phân tích dữ liệu phải hiểu đầy đủ các khả
năng tiêu biểu của phương pháp được dùng. Ngoài ra người thiết kế thuật toán cũng
cần chỉ rõ giả thiết mô tả nào được tạo bởi thuật toán nào.Sự trình diễn càng mạnh thì
-9-
Phát hiện các quan hệ từ CSDL Text
độ nguy hiểm đối với mô hình càng tăng bao trùm lên kết quả dữ liệu dạy, giảm bớt độ
chính xác dự báo trên dữ liệu chưa biết và còn làm cho việc tìm kiếm trở nên phức tạp
và việc giải thích mô hình khó hơn.
Đỏnh giá mô hình : ước lượng các mẫu riêng (mô hình và các tham số của
nó) là tốt đến mức độ nào theo tiêu chuẩn của quá trình KDD. Việc đánh giá độ chính
xác của dự báo dựa trên sự đỏnh giỏ chéo. Đỏnh giá chất lượng dự báo bao gồm độ
chính xác dự báo, tính mới, tính tiện ích, và tính dễ hiểu của mô hình phù hợp. Cả hai
tiêu chuẩn logic và thống kê có thể được dùng để đỏnh giá mô hình.
Phương pháp tìm kiếm : bao gồm hai thành phần là tìm kiếm tham số và tìm
kiếm mô hình. Trong tìm kiếm tham số, thuật toán bắt buộc tìm kiếm tham số sao cho
tối ưu mô hình theo tiêu chuẩn đỏnh giá được cho theo dữ liệu quan sát và cách trình
bày mô hình đã định. Trong tìm kiếm mô hình, miêu tả mô hình được thay đổi để xét

một họ các mô hình mới. Với mỗi cách biểu diễn mô hình, phương pháp tìm kiếm
tham số được áp dụng để đỏnh giá chất lượng mô hình. Các phương pháp tìm kiếm mô
hình thường sử dụng các kỹ thuật tìm kiếm heristic do kích thước lớn của không gian
các mô hình thường cản trở việc tìm kiếm toàn diện.
1.1.2.3.Các phương pháp khai phá dữ liệu phổ biến
Có rất nhiều các phương pháp khai phá dữ liệu, mỗi phương phỏp có đặc điểm
riêng về trình diễn mô hình, đỏnh giá mô hình và cách tìm kiếm, phù hợp với một lớp
các bài toán với các dạng dữ liệu và miền dữ liệu nhất định. Dưới đõy là một số
phương pháp phổ biến thường dùng :
 Cây quyết định và luật : sử dụng sự phân chia đa dạng có một trình bày
đơn giản, tạo ra các mô hình phỏng đoán dễ dàng liên quan tới hiểu biết
của người sử dụng.
 Phương pháp phân lớp và hồi quy phi tuyến : các phương pháp này
bao gồm một họ các kỹ thuật để quyết định là một tổ hợp tuyến tính hoặc
phi tuyến của các hàm cơ sở (sigma, đa thức, ) theo tổ hợp của các biến
vào.
 Phương pháp dựa trên ví dụ :dựng các ví dụ đại diện từ một CSDL để
xấp xỉ một mô hình, chẳng hạn, dự đoỏn các ví dụ mới nhận được từ các
tính chất của các ví dụ “tương tự” trong mô hình đã biết để dự báo. Các
kỹ thuật là : kỹ thuật phân lớp người láng giềng gần nhất và thuật toán
-10-
Phát hiện các quan hệ từ CSDL Text
hồi quy (Dasarathy, 1991) và hệ lập luận dựa theo trường hợp riêng
(Kolodner, 1993).
 Mô hình phụ thuộc đồ thị xác suất : Mô hình đồ thị định rõ sự phụ
thuộc xác suất làm cơ sở của mô hình bộ phận sử dụng cấu trúc đồ thị
(Pearl 1988; Whittaker 1990).
 Mô hình học quan hệ : trong khi cây quyết định và các quy tắc (luật)
cho một sự trình bày bị hạn chế bởi logic mệnh đề, học quan hệ (còn
được gọi là chương trình logic đệ quy) sử dụng ngôn ngữ mẫu mềm dẻo

hơn của logic thứ tự bậc một.
Một số phương phỏp khác :
 Phương pháp quy nạp
 Phát hiện luật kết hợp
 Phân nhóm và phân cụm
 Mạng nơron
 Thuật toán di truyền
 v.v.
Các thuật toán khai phá dữ liệu tự động vẫn mới chỉ ở giai đoạn phát triển ban
đầu. Người ta vẫn chưa đưa ra được một tiêu chuẩn nào trong việc quyết định sử dụng
phương pháp nào và trong trường hợp nào thì có hiệu quả.
Hầu hết các kỹ thuật khai phá dữ liệu đều mới mẻ đối với lĩnh vực kinh doanh.
Hơn nữa lại có rất nhiều kỹ thuật, mỗi kỹ thuật được sử dụng cho nhiều bài toán khác
nhau. Mỗi phương pháp đều có điểm mạnh và điểm yếu của núm nhưng hầu hết các
điểm yếu đều có thể khắc phục được, vì vậy cần tìm cách áp dụng mỗi kỹ thuật một
cách đơn giản, dễ sử dụng để không cảm thấy những phức tạp vốn có của kỹ thuật đó.
Nhiều công ty đã đưa ra những sản phẩm sử dụng kết hợp nhiều kỹ thuật khai
phá dữ liệu khác nhau với hy vọng nhiều kỹ thuật thì sẽ tốt hơn. Nhưng thực tế cho
thấy nhiều kỹ thuật chỉ thêm nhiều rắc rối và gõy khú khăn cho việc so sánh giữa các
phương pháp và các sản phẩm. Theo nhiều đỏnh giá cho thấy khi đã hiểu được các kỹ
thuật và nghiên cứu tính giống nhau giữa chúng, người ta thấy rằng nhiều kỹ thuật lúc
đầu thì có vẻ khác nhau nhưng thực chất khi hiểu ra được các kỹ thuật này thì thấy
chúng hoàn toàn giống nhau. Tuy nhiên, đỏnh giá này cũng chỉ để tham khảo vì cho
-11-
Phát hiện các quan hệ từ CSDL Text
đến nay, khai phá dữ liệu vẫn còn là kỹ thuật mới chứa nhiều tiềm năng mà người ta
vẫn chưa khai thác hết.
1.1.3. Ứng dụng của Khai phá dữ liệu
Khai phá dữ liệu tuy là một lĩnh vực mới nhưng thu hút được rất nhiều sự
quan tâm của các nhà nghiên cứu nhờ vào những ứng dụng thực tiễn của nó. Chúng ta

có thể liệt kê ra đây một số ứng dụng điển hình:
 Phân tích dữ liệu và hỗ trợ ra quyết định
 Điều trị y học : mối liên hệ giữa triệu chứng, chẩn đoán và phương pháp
điều trị (chế độ dinh dưỡng, thuốc men, phẩu thuật, …).
 Khai phá Text (Text Mining) và Khai phá Web (Web mining): phân lớp
văn bản và các trang web, tóm tắt văn bản, .v.v.
 Tin-sinh học : tìm kiếm, đối sỏnh cỏc hệ gene và thông tin di truyền,
mối liên hệ giữa một số hệ gene và một số bệnh di truyền, .v.v.
 Tài chính và thị trường chứng khoán : phân tích tình hình tài chính và
dự báo giá của các loại cổ phiếu trong thị trường chứng khoán, .v.v.
 Bảo hiểm.
 Nhận dạng mẫu .
 .v.v.
Như đã đề cập ở trên, Khai phá Text là một trong những ứng dụng quan trọng
của Datamining. Trong phần tiếp theo sẽ đi sâu hơn vào bài toán này, cụ thể là sẽ định
nghĩa về Khai phá Text, trình bày một số bài toán chủ yếu trong khai phá Text và đưa
ra một cái nhìn tổng quan về các kỹ thuật phổ biến nhất trong lĩnh vực này.
1.2. Khai phá dữ liệu Text
1.2.1. Giới thiệu
Xử lý ngôn ngữ tự nhiên không chuyên sâu (shallow) dựa trên các kỹ thuật
thống kê đã chứng tỏ sự thiếu hụt về những cải thiện quan trọng trong phép phân tích
văn bản tự động, trong khi đó để hiểu văn bản một cách toàn diện thì vẫn còn là một
mục tiêu khó khăn trong Trí tuệ nhân tạo. Đến giữa những năm 90, tình trạng này đó
giỳp tìm ra phương pháp mới trong phân tích văn bản ngôn ngữ tự nhiên, phương pháp
này là trung gian giữa xử lý ngôn ngữ tự nhiên ngữ nghĩa nông và sâu, vì thế tìm ra
được ý nghĩa và các tri thức ẩn giấu bên trong các tài liệu text. Phương pháp này được
-12-
Phát hiện các quan hệ từ CSDL Text
gọi là Khai phá Dữ liệu Text (Text Data Mining – TDM) và nó quan tâm đến việc
trớch rỳt cỏc mối quan hệ hay các kết hợp mới và không tường minh giữa nhiều thực

thể text khác nhau từ các cơ sở dữ liệu text lớn. Khái niệm Khai phá text là việc thúc
đẩy các nguồn tài nguyên text hiện hành có kích thước lớn để khám phá, phát hiện ra
các tri thức mới được suy luận ra từ rất nhiều mẫu tương quan của các tài liệu khác
nhau. Các suy luận này sau đó sẽ sử dụng trong các ứng dụng có liên quan. Một tính
năng quan trọng của khai phá Text là nó biến đổi các văn bản ngôn ngữ tự nhiên
không có cấu trúc thành dạng biểu diễn có cấu trúc để có thể khai phá các mối quan hệ
mới và hay. Các văn bản ngôn ngữ tự nhiên ở dạng trình bày có cấu trúc càng được tổ
chức tốt thì càng khám phá ra nhiều thông tin mới mẻ và thú vị hơn.
Trong khi lượng dữ liệu có cấu trúc là rất lớn và phát triển với nhịp độ nhanh
chóng thỡ cỏc con số thống kê lại cho thấy chỉ một phần nhỏ (5- 10%) dữ liệu thu thập
lại là đã từng được phân tích. Điều này khiến cho nhiều nhiệm vụ quan trọng trở nên
rất khó khăn thậm chí là không thể thực hiện được, chẳng hạn như việc tạo quyết định
(decision-making). Vì thế, trong thập kỷ trước đõy, việc phân tích dữ liệu từ tuyển tập
lớn các dữ liệu có cấu trúc tạo ra sự phát triển đáng kể trong lĩnh vực Khám phá Tri
thức trong Cơ sở dữ liệu.
Trong những năm đầu 1990, nghiên cứu về cơ sở dữ liệu cho thấy rằng có thể
lấy được các thông tin mới và hay bằng việc đỏnh giá sự sắp xếp các giá trị thuộc tính
hoặc các kết hợp giữa các mục khác nhau trong một cơ sở dữ liệu, sử dụng nhiều kỹ
thuật khác nhau, theo thứ tự từ các thống kê đơn giản đến các phép phân tích dữ liệu
phức tạp trình độ cao. Cách tiếp cận mới lạ này giỳp cỏc kỹ thuật tiến hành được trên
một khối lượng dữ liệu rất rộng lớn. Ý tưởng về việc khởi đầu với chỉ một phần nhỏ
dữ liệu (dữ liệu huấn luyện- training data) sử dụng nhiều các kỹ thuật thống kê khác
nhau được áp dụng. Vì thế, có thể khám phá ra các mẫu và sự tương quan mới, có
nghĩa. Các mẫu này sau đó sẽ được test và lọc trên một tập khác gọi là tập dữ liệu test
(test data). Ngoài các tập huấn luyện và tập test, còn sử dụng một tập kiểm định
(validation set) để ước lượng các lỗi thường gặp phải và xác định mức độ thi hành của
các kiểu mẫu trong các ứng dụng thực tế.
Ví dụ, trong tình huống một ứng dụng cho vay ngân hàng, ngân hàng sẽ quan
tâm vào con người nhiều hơn để xem cú nờn cho họ vay tiền hay không. Một bản phân
tích chi tiết dữ liệu của ngân hàng có thể phát hiện ra các thông tin về loại danh mục

mọi người yêu thích nhất trong từng kiểu ngân hàng cho vay riêng. Với kiểu ứng dụng
này, cơ sở dữ liệu gồm có các bản ghi về lượng khách của ngân hàng trong một số
-13-
Phát hiện các quan hệ từ CSDL Text
năm qua cùng với nhiều thông tin về từng khách như : tuổi tác, giới tính, tình trạng
hôn nhân, nghề nghiệp, con cái, vân vân. Sử dụng tập huấn luyện, các thuật toán thống
kê khác nhau nhận dạng các đặc trưng phân biệt những khách hàng vay tiền của một
loại ngân hàng cho vay riêng biệt với những khách hàng không vay tiền ngân hàng đú.
Trên cơ sở những kết hợp như vậy có thể nhận ra được những khách hàng nào có khả
năng sẽ là triển vọng tốt cho ngân hàng. Bằng cách này, ngân hàng có thể xác định
được rủi ro khi cấp một khoản tiền cho vay cho một khách hàng cụ thể nào đó. Nếu
mức độ rủi ro thấp thì chương trình (program) sẽ đề nghị người quản lý tiền chấp nhận
cho khách vay.
Còn có thể sử dụng phép phân tích này để phân loại cơ sở dữ liệu thành cỏc
nhúm người có nhiều thuộc tính tương tự nhau với hy vọng sẽ khám phá ra nhiều mẫu
không mong đợi và quan trọng cho các nhiệm vụ tạo quyết định khác nhau. Các mẫu
này sau đó sẽ được trình bày thông qua việc sử dụng các mođun ảo. Kiểu phân tích
này cũng rất hữu ích trong các lĩnh vực khác ngoài lĩnh vực khám phá tri thức như :
đỏnh giá xu hướng, dự đoán thị trường, và phân loại sở thích của khách hàng
Mặc dù có một lượng lớn thông tin được trình bày dưới dạng có cấu trúc,
nhưng trong thực tế, lượng thông tin được biểu diễn dưới dạng text còn lớn hơn rất
nhiều. Theo Gartner Group, “ngày nay, có tới 80% công việc kinh doanh được quản lý
bởi các thông tin không có cấu trỳc”. Vì thế, Khai phá Dữ liệu Text, một lĩnh vực mới
của Khai phá Dữ liệu, phân tích dữ liệu Text lớn để trích rút ra các mẫu tri thức không
tầm thường và quan trọng.
Trên cơ sở áp dụng thành công các phương pháp thống kê Khai phá Dữ liệu
vào CSDL, một số nghiên cứu tập trung chú ý vào phân tích các tài liệu Text nhằm
phát hiện ra các mẫu mới, quan trọng và có ích cho các ứng dụng tìm hiểu văn bản
khác nhau.
1.2.2. Các bài toán trong Khai phá Dữ liệu Text.

Trong các dữ liệu hiện nay thì văn bản là một trong những dữ liệu phổ biến
nhất, nó có mặt ở khắp mọi nơi và chúng ta thường xuyên bắt gặp do đó các bài toán
về xử lý văn bản đã được đặt ra khỏ lõu và hiện nay vẫn là một trong những vấn đề
trong khai phá dữ liệu Text, trong đó có những bài toán đáng chú ý như Tìm kiếm
thông tin (Information Retrieval -IR), Phân lớp và Phân cụm văn bản (Text
Classification and Clustering), và Trích lọc thông tin (Information Extraction - IE)
Tìm kiếm văn bản
-14-
Phát hiện các quan hệ từ CSDL Text
Tìm kiếm văn bản là quá trình tìm kiếm văn bản theo yêu cầu của người dùng.
Các yêu cầu được thể hiện dưới dạng các câu hỏi (query), dạng câu hỏi đơn giản nhất
là các từ khóa. Có thể hình dung hệ tìm kiếm văn bản sắp xếp văn bản thành hai lớp:
Một lớp cho ra những các văn bản thỏa mãn với câu hỏi đưa ra và một lớp không hiển
thị những văn bản không được thỏa mãn. Các hệ thống thực tế hiện nay không hiển thị
như vậy mà đưa ra các danh sách văn bản theo độ quan trọng của văn bản tuỳ theo các
câu hỏi đưa vào, cỏc mỏy tỡm tin như Google, Altavista,…là các hệ thống tìm kiếm
văn bản như vậy.
Quá trình tìm tin được chia thành bốn quá trình chính :
Đánh chỉ số (indexing) : Các văn bản ở dạng thô cần được chuyển sang một
dạng biểu diễn nào đó để xử lý. Quá trình này còn được gọi là quá trình biểu diễn văn
bản, dạng biểu diễn phải có cấu trúc và dễ dàng khi xử lý.
Định dạng câu hỏi: Người dùng phải mô tả những yêu cầu về lấy thông tin
cần thiết dưới dạng câu hỏi. Các câu hỏi này phải được biểu diễn dưới dạng phổ biến
cho các hệ tìm kiếm như nhập vào các từ khóa cần tìm. Ngoài ra cũn cú cỏc phương
pháp định dạng câu hỏi dưới dạng ngôn ngữ tự nhiên hoặc dưới dạng các ví dụ, đối với
các dạng này thì cần có các kỹ thuật xử lý phức tạp hơn. Trong các hệ tìm tin hiện nay
thì đại đa số là dùng câu hỏi dưới dạng các từ khóa.
So sánh: Hệ thống phải có sự so sánh rõ ràng và hoàn toàn các câu hỏi của
người dùng với các văn bản được lưu trữ trong CSDL. Cuối cùng hệ đưa ra một quyết
định phân loại các văn bản có độ liên quan gần với câu hỏi đưa vào và thứ tự của nó.

Hệ thống sẽ hiển thị một phần hoặc toàn bộ văn bản.
Phản hồi: Nhiều khi kết quả được trả về ban đầu không thỏa mãn yêu cầu của
người dùng, do đó cần phải có quá trình phản hồi để người dùng có thể thay đổi hoặc
nhập mới các yêu cầu của mình. Mặt khác, người dùng có thể tương tác với các hệ về
các văn bản thỏa mãn yêu cầu của mình và hệ có chức năng cập nhật các văn bản đó.
Quá trình này được gọi là quá trình phản hồi liên quan (Relevance feeback).
Phân lớp văn bản
Phân lớp văn bản được xem như là quá trình gỏn cỏc văn bản vào một hay
nhiều lớp văn bản đã xác định từ trước. Có thể phân lớp các văn bản một cách thủ
công, tức là đọc từng văn bản một và gỏn nó vào một lớp nào đó. Cách này sẽ tốn rất
nhiều thời gian và công sức đối với nhiều văn bản và do đó không khả thi. Do vậy mà
phải cú cỏc phương pháp phân lớp tự động. Để phân lớp tự động người ta sử dụng các
-15-
Phát hiện các quan hệ từ CSDL Text
phương pháp học máy trong trí tuệ nhân tạo (Cây quyết định, Bayes, k người láng
giềng gần nhất)
Một trong những ứng dụng quan trọng nhất của phân lớp văn bản là trong tìm
kiếm văn bản. Từ một tập dữ liệu đã phân lớp các văn bản sẽ được đánh chỉ số đối với
từng lớp tương ứng. Người dùng có thể xác định chủ đề hoặc phân lớp văn bản mà
mình mong muốn tìm kiếm thông qua các câu hỏi.
Một ứng dụng khác của phân lớp văn bản là trong lĩnh vực tìm hiểu văn bản.
Phân lớp văn bản có thể được sử dụng để lọc các văn bản hoặc một phần các văn bản
chứa dữ liệu cần tìm mà không làm mất đi tính phức tạp của ngôn ngữ tự nhiên.
Trong phân lớp văn bản, một lớp có thể được gán giá trị đúng sai (True hay
False hoặc văn bản thuộc hay không thuộc lớp) hoặc được tính theo mức độ phụ thuộc
(văn bản cú mụt mức độ phụ thuộc vào lớp). Trong trường hợp có nhiều lớp thì phân
loại đúng sai sẽ là việc xem một văn bản có thuộc vào một lớp duy nhất nào đó hay
không
Quá trình phân lớp văn bản. tuân theo các bước sau:
Đánh chỉ số: Quá trình đánh chỉ số văn bản cũng giống như trong quá trình

đánh chỉ số của tìm kiếm văn bản. Trong phần này thì tốc độ đánh chỉ số đóng vai trò
quan trọng vì một số các văn bản mới có thể cần đươc xử lý trong thời gớan thực
Xác định bộ phân lớp: Cũng giống như trong tìm kiếm văn bản, phân lớp văn
bản yêu cầu quá trình diễn tả việc xác định văn bản đó thuộc lớp nào đó như thế nào,
dựa trên cấu trúc biểu diễn của nó. Đối với hệ phân lớp văn bản, chúng ta gọi quá trình
này là bộ phân lớp (Categorization hoặc classifier). Nó đóng vai trò như những câu hỏi
trong hệ tìm kiếm. Nhưng trong khi những câu hỏi mang tính nhất thời, thì bộ phân
loại được sử dụng một cách ổn định và lâu dài cho quá trình phân loại.
So sánh: Trong hầu hết các bộ phân loại, mỗi văn bản đều được yêu cầu gán
đúng sai vào một lớp nào đó. Sự khác nhau lớn nhất đối với quá trình so sánh trong hệ
tìm kiếm văn bản là mỗi văn bản chỉ được so sánh với một số lượng các lớp một lần và
việcc họn quyết đnịh phù hợp còn phụ thuộc vào mối quan hệ giữa các lớp văn bản.
Phản hồi (Hay thích nghi): Quá trình phản hồi đóng vai trò trong hệ phân lớp
văn bản. Thứ nhất là khi phân loại thì phải cú mụt số lượng lớn các văn bản đã được
xếp loại bằng tay trước đó, các văn bản này được sử dụng làm mẫu huấn luyện để hỗ
trợ xây dựng bộ phân loại. Thứ hai là đối với việc phân loại văn bản này không dễ
dàng thay đổi các yêu cầu như trong quá trình phản hồi của tìm kiếm văn bản , người
-16-
Phát hiện các quan hệ từ CSDL Text
dùng có thể thông tin cho người bảo trì hệ thống về việc xóa bỏ, thêm vào hoặc thay
đổi các phân lớp văn bản nào đó mà mình yêu cầu.
Phân cụm văn bản
Phân cụm văn bản là việc tự động sinh ra các lớp văn bản dựa vào sự tương tự
của các văn bản. Các lớp văn bản ở đõ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ệ sẽ đưa ra các văn bản theo từng tập hợp, từng
cụm, mỗi tập hợp chứa các văn bản tương tự nhau.
Trích lọc thông tin
Là quá trình scan tập văn bản tỡm cỏc thông tin về các nhiệm vụ hay sự kiện
đã xác định để fill vào một khuôn mẫu thích hợp. Ví dụ như việc lấy ra các thông tin
xác định trước về sự kiện khủng bố có thể là kẻ khủng bố, nạn nhân, hay dụng cụ ném

bom dùng để tấn công, v.v…
1.2.3. Các vấn đề quan trọng trong Khai phá Dữ liệu Text.
Các nhà nghiên cứu đã xác định ba vấn đề chớnh cú ảnh hưởng lớn đến sự thi
hành của các hệ thống Khai phá Text như sau :
1. Sự trình diễn nào là phù hợp nhất cho Khai phá Text ?
2. Các kỹ thuật phát hiện mẫu nào là thành công nhất ?
3. Hiển thị các kết quả như thế nào để phép phân tích có ảnh hưởng tốt
hơn ?
Có thể giải thích sự thành công của các kỹ thuật Khai phá dữ liệu trong việc
phân tích các nguồn dữ liệu có cấu trúc lớn bằng thực tế dựa trên cấu trúc tường minh
của cơ sở dữ liệu quan hệ đặc trưng bởi các trường hoàn toàn xác định (well defined)
và các ID của các cặp giá trị - thuộc tính . Hơn nữa, trong CSDL, ý nghĩa của mỗi
trường là hoàn toàn xác định và đã biết trước.
Các tài liệu ngôn ngữ tự nhiên lưu trữ thông tin rất đa dạng, phong phú nên là
rất khó để có thể tự động biểu diễn trong một form. Một trong những vấn đề quan
trọng nhất của Khai phá Dữ liệu Text là xác định cách trình bày nội dung văn bản sao
cho phù hợp nhất để có thể tự động dò tìm ra các tri thức mới và đáng quan tâm. Điều
này có nghĩa là sự tổ chức của cách trình bày có cấu trúc của văn bản ngôn ngữ tự
nhiên càng tốt thì càng khám phá được nhiều thông tin mới, quan trọng.
-17-
Phát hiện các quan hệ từ CSDL Text
Vấn đề quan trọng thứ hai của Khai phá Text là tìm hiểu đâu là các kỹ thuật
xử lý văn bản tốt nhất có thể tìm ra nhiều tri thức được mã hoá hoàn toàn trong cách
trình bày văn bản. Một ghi chú quan trọng đó là có một mối tương quan rất lớn giữa
cách trình bày văn bản và các kỹ thuật dùng để khai phá các thông tin hữu ích. Các kỹ
thuật này phải thích ứng với cách trình bày nội dung của văn bản, vì thông tin không
được lấy ra từ cách trình bày thì cũng không thể được biểu diễn trong các kết quả cuối
cùng.
Bước cuối trong quá trình Khai phá Text là việc trực quan hoỏ cỏc quan hệ đã
được khai phá. Bước này rất quan trọng vì nội dung của các tài liệu text có thể thay đổi

rất nhiều, và nó thường hoàn lại các lỗi phát sinh trong bước xử lý, giúp cho người
phân tích hiểu được những gì sẽ xảy ra và nhìn bức tranh tổng thế một cách tốt hơn. Vì
người phân tích không biết những gì sẽ được khám phá nên rất khó để áp dụng output
của hệ thống vào một vấn đề thương mại hoàn toàn xác định. Có quá nhiều cách để
trình bày mô hình bằng đồ hoạ. Vì thế, nên chọn sử dụng mô hình trực quan hoá dựa
theo yêu cầu của người dùng .
1.2.4. Phân loại các hệ thống Khai phá Text
Có thể phân loại các hệ thống khai phá thành ba kiểu chính dựa vào các cấu
trúc sử dụng cho việc tổ chức văn bản và các phương pháp khai phá áp dụng trờn cỏc
cấu trúc này như sau:
A. Các hệ thống quan tâm tới các phương pháp Khai phá Dữ liệu
B. Các hệ thống phối hợp giữa các phương pháp Khai phá Dữ liệu và các
kỹ thuật ngữ nghĩa từ vựng (lexical semantic techniques)(phương pháp lai).
C. Các hệ thống chỉ dựa vào các phương pháp ngữ nghĩa từ vựng
Thông thường, mỗi hệ thống thường làm ba nhiệm vụ chính :
• Xử lý văn bản
• Các kỹ thuật khai phá để phát hiện các mẫu, và
• Trực quan hoỏ cỏc kết quả
A. Từ Khai phá Dữ liệu tới Khai phá văn bản
Xử lý văn bản
Nhiều hệ thống Khai phá Text dựa vào các kỹ thuật Khai phá Dữ liệu để tìm ra
các mẫu thông tin quan trọng trong một cấu trúc từ hay cụm từ.
-18-
Phát hiện các quan hệ từ CSDL Text
Trên cơ sở những tiến bộ đạt được những năm đầu 1990 trong Tìm kiếm
Thông tin và Phân lớp văn bản [2][3], các nhà nghiên cứu Khai phá Text cho rằng
cách trình bày shallow các thông tin đúng theo nguyên bản có thể cung cấp một
framework tốt, hoàn toàn phù hợp với nhiều nhiệm vụ truy xuất thông tin khác nhau.
Sử dụng các kỹ thuật Phân lớp văn bản, các tài liệu sẽ được phân vào các lớp xác định
trước và được gán với các thuật ngữ để nhận dạng nội dung của chúng [8], [9], [7],

[19]. Sau đú các thuật ngữ sẽ được sắp xếp vào các cấu trúc khác nhau đã có từ trước,
chẳng hạn như biểu đồ xoắn trực tiếp (directed acyclic graphs) hoặc các template
Trớch rỳt thông tin có khả năng tổng quát hoá và chuẩn bị dữ liệu cho việc ứng dụng
các kỹ thuật Khai phá Dữ liệu. Ví dụ, Feldman và Dagan [7] sử dụng các hệ đẳng cấp
khái niệm đã xác định trước cho hệ thống KDT của họ, các hệ đẳng này dựa trên các
thuộc tính thừa kế trong đó thuộc tính cha biểu thị khái niệm tổng quát hơn thuộc tính
con (ví dụ : “Nhật -> G7-> Nước” )
Hệ đẳng cấp khái niệm hết sức đơn giản, thường có hai hoặc ba mức. Cỏc nỳt
biểu diễn các lớp phân loại miền cụ thể đã xác định trước (ví dụ : “countries”, “G7”,
“topics”) và cỏc lỏ biểu diễn các thẻ từ khoá (ví dụ, “Germany”, “Japan”, “Mexico”,
“algriculture”, và “metals”).
Hình 2.Một ví dụ về hệ đẳng cấp khái niệm sử dụng bởi hệ thống KDT[6]
Để giữa các từ khoỏ cú sự kết hợp tổng quát hơn, cỏc nỳt biểu diễn các lớp
tổng quát hơn và thường ghi nhãn các tài liệu. Ví dụ, khi tính toán tỷ lệ của các tài liệu
được gỏn nhón “agriculture” cho các nước G7, lớp “G7” được dùng để thay thế cho
danh sách tất cả các nước là thành viên của G7 (hình 2).
-19-
Phát hiện các quan hệ từ CSDL Text
Khi các tài liệu đã được chú thích bởi các từ khóa đã có trong hệ đẳng cấp,
bước tiếp theo là áp dụng các kỹ thuật thống kê để khám phá ra các mẫu quan trọng.
Ta coi hệ đẳng cấp khái niệm là một sác xuất phân loại (sự phân loại có khả năng xảy
ra ), có thể nhận biết được một vài kiểu phân loại khi so sánh với một hệ khái niệm
cho trước. Ví dụ, phân loại topic của mỗi nước thành viên của G7 có thể đem so sánh
với sự phân loại trung bình của topic cho tất cả các nước G7. Phân tích này phát hiện
ra các topic phổ biến nhất có tương quan lớn với các nước G7, và còn cả các đặc trưng
quan trọng nhất cụ thể với mỗi nước.
Một cách khác để biểu diễn tập văn bản cho mục đích Khai phá Text là dựng
cỏc template đã xác định trước cùng với các phương phỏp trớch rỳt thông tin. Một hệ
thống như vậy (DiscoTEX) được thi hành tại Trường đại học của Texas tại Austin năm
2000 [24]. DiscoTEX tích hợp giữa các phương phỏp Trớch lọc Thông tin và các kỹ

thuật Khai phá Dữ liệu để lấy ra được các quan hệ cần thiết trong lĩnh vực của các
công việc liên quan tới máy tính. Vì Khai phá Dữ liệu truyền thống đòi hỏi dữ liệu
phải được trình bày dưới dạng có cấu trúc, do đó hệ thống tận dụng được những thuận
lợi của Trích lọc thông tin cho từng phần tổ chức thông tin vào các template xác định
trước, như đã chỉ ra trong bảng 1
Bảng 1. Ví dụ về template IE chứa thông tin về các công việc liên quan tới máy tính
Tước vị : Kỹ sư phần mềm
Công ty : Newmilan
Lương : $70k
Thành phố : Dallas
Bang : Texas
Ngôn ngữ : Java, C, Shell Scripts
Ứng dụng : Photoshop
Lĩnh vực : Đồ hoạ
Các khe template IE được lấp đầy bằng các thông tin trích lọc sử dụng các
mẫu được nghiên cứu bởi hệ thống học máy (machine learning system) gọi là RAPIER
-20-
Phát hiện các quan hệ từ CSDL Text
[3]. RAPIER là một hệ thống nghiên cứu luật quan hệ bottom- up, nó tìm được các
luật từ một corpus của các mẫu huấn luyện được gỏn nhón bằng cách sử dụng các
thông tin cú pháp có giới hạn (ví dụ như từ loại). Để phát hiện các luật dự báo, các cặp
giá trị - khe trong các template xác định trước được coi như là các thuộc tính nhị phân
không trùng lặp giống như “graphics
∈
area” (“đồ hoạ ∈ lĩnh vực ”). Sử dụng một từ
điển đồng nghĩa nhỏ trong miền được chỉ định, tương tự như các thông tin lấp đầy khe
được thu thập lại trong một dạng chuẩn. Ví dụ, các cụm từ kiểu như “Windows95,
Win95, MSWin95” coi như là cùng nói tới một nội dung như nhau. Sau khi các
template đã được lấp đầy, DiscoTEX sử dụng phương pháp quy nạp luật C4.5RULES
[10] để nghiên cứu cỏc cõy quyết định được biến đổi thành các luật xén bớt (pruned).

Sử dụng cách này có thể khám phá ra các quan hệ quan trọng. Ví dụ, mẫu “Java
∈
ngôn ngữ & Đồ hoạ
∈
lĩnh vực => Photoshop
∈
ứng dụng” cho thấy nếu một công
việc liên quan tới máy tính đòi hỏi kiến thức về Java trong lĩnh vực đồ hoạ thỡ nó cũn
yêu cầu cả các kiến thức về Photoshop.
Các kỹ thuật khai phá để phát hiện mẫu:
Hầu hết các kỹ thuật sử dụng trong Text Mining đều vay mượn từ Data
Mining (từ Khai phá Dữ liệu) và Machine Learning (Học Mỏy). Cỏc tài liệu Text có
thể được xem như là các cơ sở dữ liệu và một tập các từ hay cụm danh từ được coi như
là các bản ghi.
1.Các kết hợp
Các kết hợp được giới thiệu trong Data Mining vào năm 1993 bởi Agrawal et
al. [11] trong tình huống cơ sở dữ liệu quản lý kinh doanh cửa hàng tạp hoỏ. Cỏc luật
kết hợp nhận dạng sự tương quan giữa các bản ghi CSDL dựa vào hai tham số :
support (hỗ trợ) và confidence (tin cậy).
Hãy xem xét một tập tài liệu D = {D
1
,…, D
n
} được chú dẫn bởi tập các từ khoá
W = {w
1
,…,w
m
}, trong đó : mỗi D
i

kết hợp với một tập con của W, ký hiệu là D
i
(W).
Cho trước một tập con S
w
⊂
W, tập tất cả các tài liệu D
i
trong D sao cho
S
w
⊂
D
i
(W) được gọi là kỳ hạn của S
w
([S
w
]).
Một luật kết hợp, R : (S
w
→ w), là bất kỳ một cặp (S
w
, w) nào sao cho S
w

⊂
W
là một tập các từ khoá và w
∈

W \ S
w
.
Cho trước một luật kết hợp R : (S
w
→ w), các tham số sau được định nghĩa :
a. Support của R đối với tập D
-21-
Phát hiện các quan hệ từ CSDL Text
( |X| biểu thị là độ lớn của X)
b. Confidence của R đối với tập D
C(R,D) là một sấp xỉ (ước lượng giống nhau tối đa) của các điều kiện có khả
năng xảy ra đối với một văn bản chú dẫn bằng từ khoá w nếu nó đã được chú thích
bằng tập từ khoá S
w
rồi. Confidence đo cường độ của luật trong khi đó support đo mức
độ thường xuyờn nó nờn xuất hiện trong CSDL.
Một luật kết hợp R phát sinh từ tập văn bản D thoả món cỏc ràng buộc về độ
hỗ trợ và độ tin cậy
σ
và
γ
nếu :
S(R,D)
≥

σ
và C(R,D)
≥


γ
Hai bước đòi hỏi phải rút ra các luật kết hợp : thứ nhất, phát sinh tất cả các tập
từ khoá với độ hỗ trợ thấp nhất
σ
(S
w
≥

σ

) (các tập thường xuyên); thứ hai, phát sinh
tất cả các luật kết hợp xuất phát từ các tập thường xuyên đã xác định và thoả mãn ràng
buộc về độ tin cậy
γ
.
2. Các luật Episode
Một episode là một thuật ngữ Khai phá Dữ liệu nói tới các giá trị tạm thời và
các mục dữ liệu. Khi áp dụng vào văn bản [2], kỹ thuật này xác định sự xuất hiện và vị
trí của mỗi từ hay cụm từ trong tài liệu. Không yêu cầu bắt buộc phải hiểu rõ văn bản
vỡ nó tìm kiếm các từ hay cụm từ cùng xuất hiện. Ví dụ, luật epsilode cho cụm danh
từ “ Java programming for Unix” (“Lập trình Java cho Unix”) có thể là “Java,
programming [3] – Unix [5] : 80%” chỉ ra rằng trong 80% (độ tin cậy) các trường hợp
khi “Java” và “programming” xuất hiện trong một cửa sổ nhỏ kích thước là 3, từ
“Unix” xuất hiện trong khoảng cách 5 từ. Khi có độ tin cậy càng cao thỡ cỏc mẫu càng
quan trọng hơn.
3.Cây quyết định và học luật
Các kỹ thuật Học máy như cây quyết đinh (C4.5, C5.0) và học luật (FOIL )
được áp dụng trong Text Khai phá cho nhiều ứng dụng khác nhau.
-22-
Phát hiện các quan hệ từ CSDL Text

Một số hệ thống Khai phá Text [16], [17] sử dụng các thuật toán cây quyết
định như C4.5, C5.0. Sử dụng Hoovers.com trực tuyến lưu trữ thông tin về cỏc công
ty, Ghani et al. [16] khám phá ra các quy tắc quan trọng trong dữ liệu. Với các kiến
thức thực tế về các công ty trên khắp thế giới, họ áp dụng phương pháp Học Máy để
lấy ra được sự kết hợp mới giữa các công ty. Bắt đầu với một danh sách các miêu tả
như links-to, mention, perform-activity, officers, locations, v.v (liên kết- tới, đề cập,
phạm vi hoạt động – thi hành, viên chức, vị trí), hệ thống của họ thực hiện tìm kiếm
đơn giản các từ khoá, ví dụ, “Microsoft, Seattle, WA.” (cho miêu tả location). Hơn
nữa, chỳng trớch rỳt cỏc miêu tả sector dựa trên Naùve Bayer [58]. Để áp dụng các
thuật toán Học Mỏy, cỏc thuộc tính liên tiếp được xét và ánh xạ vào các hàm logic.
Kết quả trả về một số lượng lớn các thuộc tính được biểu diễn bằng các vectơ rải rác.
Hệ thống sử dụng C5.0 (mở rộng của C4.5) để sinh ra cỏc cõy quyết định cho các tập
dữ liệu đã xét đến. Để phát hiện ra các mẫu, tạo một tập luật từ tất cả các luật đã biết
cho mỗi phần từ gốc đến một lá trong cây quyết định. Vì thế, cây quyết định dùng để
dự đoỏn các khu vực kinh tế miêu tả trong trang web của Hoovers. Một ví dụ cho
trường hợp này là dũ tỡm cỏc khu vực ngân hàng tại nước Mỹ.
Sử dụng các miêu tả như “compete” và “sectors” (“cạnh tranh” và “khu vực”),
các học quan hệ ( relational learner ), FOIL, tìm kiếm để phát hiện ra các quy tắc trong
cơ sở tri thức quan hệ. FOIL là một thuật toán Machine Learning, nghiên cứu các
mệnh đề HORN tự do hàm (function-free) sử dụng tìm kiếm leo đồi. FOIL dựng cỏc
mẫu trong các quan hệ giữa các công ty để dò tìm ra các quy tắc quan trọng như : “cơ
quan đầu não của các công ty nằm ở NewYork, không nằm trong vùng công nghiệp
hơi đốt tự nhiên hoặc khu vực công nghệ mà nằm trong vùng công nghiệp phương tiện
truyền thông đại chúng” [16].
B.Phương pháp lai trong Khai phá dữ liệu Text
Các hệ thống Khai phá Text dựa trên các tài liệu text trình bày nông (shallow)
đạt được những kết quả rất có giá trị. Vào đầu năm 2000, các nhà nghiên cứu [17],
[25], [14], [15] nhận thấy rằng cần quan tâm chú ý nhiều hơn đến việc hiểu và trình
bày văn bản trong Khai phá Text. Các tập văn bản phức tạp được so sánh với các cơ sở
dữ liệu vì thông tin chỳng mó hoỏ có thể được biểu diễn bằng nhiều cách khác nhau.

Hệ thống khai phá Text IBM
Theo cách này, hai nhà nghiên cứu IBM, Nasukawa và Nagano, phát minh ra
một hệ thống gọi là TAKMI [25] năm 2001sử dụng các miêu tả ngữ nghĩa phức tạp
-23-
Phát hiện các quan hệ từ CSDL Text
hơn trong tìm hiểu văn bản một cách tự động. Họ tập trung vào phân tích chi tiết hơn
các thông tin được mó hoỏ trong mỗi tài liệu để lấy ra được các mẫu đỏng giá từ các
tài liệu phức tạp.
Hệ thống TAKMI sử dụng ba miêu tả ngữ nghĩa trong các mođun trình bày
văn bản của nó :
• Các miêu tả ngữ nghĩa cho các từ hay cụm từ quan trọng.
• Các khái niệm gợi mở và các vị ngữ dựa vào các quy tắc ngữ pháp và
thông tin từ vựng
• Các cặp từ hay cụm từ phụ thuộc.
Các đặc trưng ngữ nghĩa (Semantic features)
Vỡ các tài liệu sử dụng bởi hệ thống TAKMI là lĩnh vực chỉ định trước, nên hệ
thống tự động lấy ra danh sách các từ được sắp xếp theo thứ tự tần số xuất hiện của
chúng trong các tài liệu. Danh sách này sau đó sẽ được đưa tới các nhà chuyên môn
trong lĩnh vực đó để gỏn cỏc loại ngữ nghĩa một cách thủ công và xác định các diễn
đạt đồng nghĩa. Ví dụ, danh từ “battery” được gán với loại ngữ nghĩa là “hardware”.
Phân tích khái niệm (Intention analysis)
Sau khi phân tích chi tiết các tài liệu biểu diễn các bản ghi text về các điểm
gặp gỡ của khách hàng, Nasukawa và Nagano nhận thấy ngữ cảnh nên trình bày sao
cho phản ánh được tính đa nghĩa của thông tin, đặc biệt là trong cỏc cõu văn biểu thị
các khái niệm gợi mở, chẳng hạn như :
• X did fail. => fail [complaint]
(X đã trượt. => trượt [kêu ca, phàn nàn])
• X did not fail => not fail [commendation]
(X đã không trượt => không trượt [khen ngợi])
• Did X fail ? => fail [question]

(X có trượt không ? => trượt [câu hỏi])
Để tự động tìm ra các diễn đạt như trên, văn bản được xử lý, phải gán thẻ từ
loại và phân tích cú pháp nông, và sau đó tìm ra các luật được áp dụng. Ví dụ, “please
+ VERB => VERB [request]” (“please + Động từ => Động từ [câu cầu khiến]”).
Phân tích sự phụ thuộc ( Dependence analysis).
-24-
Phát hiện các quan hệ từ CSDL Text
Điều này có nghĩa là có thể rút ra được các dấu hiệu của khái niệm bằng việc
phân tích ngữ pháp nhằm tìm ra sự phụ thuộc cục bộ giữa các nhóm động từ và nhóm
danh từ đã tìm ra trong bước phân tích khái niệm. Ví dụ, cặp chủ ngữ - vị ngữ trong
cùng một câu văn được coi như là có sự phụ thuộc lẫn nhau nếu không có nhóm động
từ hay liên từ ở giữa chúng :
“Program A is good, but Program B is bad”
“Program A [sofware]… good[commendation], Program B [software]
… bad[complaint]”
(“Chương trình A chạy tốt, nhưng Chương trình B chạy dở”
“Chương trình A [phần mềm]… tụt[khen ngợi], Chương trình B [phần
mềm] … dở[phàn nàn]”)
Các mô tả ngữ nghĩa cho phép hệ thống phân tích nội dung văn bản từ các
điểm nhìn của các lớp ngữ nghĩa khác nhau và tìm ra các mô tả quan trọng cho một số
topic thông qua việc phân tích sự kết hợp giữa các khái niệm.
Một trong những bất lợi chính của phương pháp này bắt nguồn từ các ứng
dụng của phương pháp thống kê trong cách trình bày các tài liệu Text không chuyên
sâu. Thông tin rút ra chủ yếu biểu diễn dưới dạng túi các từ (bag- of- words) kết hợp
với rất ít thông tin ngữ nghĩa. Bởi vậy, thậm chí là các tài liệu nói về các lĩnh vực cụ
thể, ứng dụng các kỹ thuật Khai phá dữ liệu vẫn phát sinh rất nhiều lỗi do tính đa
nghĩa của ngôn ngữ, và làm giảm đi giá trị của các mẫu đã phát hiện được. Ví dụ,
Ghani et al. [16] chỉ ra rằng trong một số cuộc thí nghiệm Khai phá Dữ liệu trờn cỏc
thông tin từ trang Web, có khoảng 90% các luật kết hợp đã khám phá được là không
đúng do hiểu sai ngữ nghĩa.

Một vấn đề nữa trong các hệ thống này phát sinh do ứng dụng các luật kết
hợp. Các luật này là kết quả của một trong những kỹ thuật thường dùng nhất trong
Khai phá Dữ liệu, do vậy mà trong Khai phá Dữ liệu Text chỉ biểu thị những tương
quan có thực giữa các mục văn bản khác nhau mà không đề cập tới tính chất của kết
hợp. Có thể giải thích vấn đề này là do rất khó khăn để phân biệt được sự khác nhau
giữa các tương quan và các quan hệ hoàn toàn xác định khác, do đó cần sử dụng các
phương pháp thống kê.
C.Khai phá Text bằng cơ sở tri thức ngữ nghĩa từ vựng
-25-