Khai phá dữ liệu và kho dữ liệu 2012
MỤC LỤC
LỜI CÁM ƠN 1
LỜI MỞ ĐẦU 2
PHẦN 1: CƠ SỞ LÝ THUYẾT 4
1.4 Bài toán thu thập thông tin (Information retrieval - IR) 18
1.4.1 Khái niệm thu thập thông n: 18
1.4.2 Các phương pháp thu thập thông n: 19
1.4.2.1 Các phương pháp chuẩn: 20
1.4.2.1.1 Mô hình Boolean: 20
1.4.2.1.1.1 Các hàm so sánh: 20
1.4.2.1.1.2 Tìm kiếm tuần tự: 21
1.4.2.1.1.3 Thực hiện: 21
1.4.2.1.2 Mô hình không gian vec-tơ (Vector space model - VSM) 22
1.4.2.1.2.1 Tiếp cận phương thức TF * IDF: 23
1.4.2.1.2.2 Độ tương đồng (similarity) 24
1.4.2.1.2.3 Thực hiện: 25
1.4.2.2 Các phương pháp dựa trí tuệ nhân tạo (AI-based method): 26
1.4.2.2.1 Kỹ thuật mạng Nơ-ron (Neural network) 26
1.4.2.2.2 Tổng quan về mạng nơ-ron 27
1.4.2.2.3 Mô hình truyền ngược ba lớp 28
1.4.2.2.4 Chức năng của mạng: 30
PHẦN 2: MỘT SỐ ỨNG DỤNG KHAI PHÁ DỮ LIỆU VĂN BẢN 33
2.1 Ứng dụng phương pháp NAIVE BAYES trong bộ lọc thư rác tự động: 33
2.1.1 Các công nghệ lọc thư rác hiện nay 33
2.1.2 Quá trình hoạt động của bộ lọc thư rác Bayes 34
2.1.3 Sự hoạt động của các bộ lọc thư rác thực tế 35
2.1.4 Các ưu điểm của bộ lọc thư rác Bayes 35
2.2 Cài đặt và thử nghiệm ứng dụng khai phá dữ liệu văn bản trong một bệnh viện: 35
37
KẾT LUẬN 38

Bước sang thế kỷ 21, nhân loại đã chuyển từ xã hội công nghiệp sang xã hội thông
tin. Với mạng Internet tốc độ cao ngày càng được mở rộng trên toàn thế giới, với việc
ứng dụng công nghệ thông tin ngày càng sâu hơn trong nhiều lĩnh vực, nhu cầu và khả
năng kết nối, chia sẻ thông tin của con người đang trở nên lớn hơn bao giờ hết. Để không
bị tụt hậu lại phía sau, mọi quốc gia, mọi tổ chức kinh tế xã hội đều nhận thức được vai
trò quan trọng không thể thiếu của công nghệ thông tin trong việc nâng cao hiệu quả hoạt
động, thúc đẩy sự phát triển của quốc gia, tổ chức mình.
Tuy nhiên, trong thời đại của công nghệ thông tin nơi mà dữ liệu đa dạng và phong
phú. Người dùng thường bị choáng ngợp bởi lượng thông tin vô cùng to lớn và do đó
không thể tiếp nhận tất cả những lợi ích mà thông tin mang tới. Khoa học máy tính đã bị
thách thức để khám phá ra những cách tiếp cận mà có thể sắp xếp được lượng dữ liệu vô
tận hiện có và tìm ra những đặc trưng thiết yếu cần có để phục vụ cho lợi ích của người
dùng. Những cách tiếp cận này phải có thể xử lí những lượng lớn dữ liệu trong thời gian
nhanh và loại bỏ những dữ liệu không liên quan hay không chính xác để trích xuất ra
những thông tin, tri thức quý báu cho chúng ta.
Trong bối cảnh thông tin đang bùng nổ như hiện nay. Khai thác dữ liệu và phát hiện
tri thức sao cho có hiệu quả là điều cần thiết. Kỹ thuật khai phá dữ liệu và phát triển tri
thức đã và đang được các nhà khoa học nghiên cứu, ứng dụng trong nhiều lĩnh vực. Kỹ
thuật này có nhiều mô hình, giải thuật cũng như các phần mềm đã được nghiên cứu và
phát triển để khai phá dữ liệu và phát hiện tri thức tìm ẩn.
Ở Việt Nam, việc ứng dụng công nghệ thông tin nói chung và khai phá dữ liệu nói
riêng vẫn còn hạn chế, lý do chủ yếu có thể là do hạ tầng mạng, công nghệ của Việt Nam
còn chưa thực sự phát triển. Tuy nhiên trong những năm trở lại đây tình hình đã được cải
thiện rất tích cực.
2
GVHD: PGS.TS. Đỗ Phúc
Học viên: Võ Hồng Phương
Khai phá dữ liệu và kho dữ liệu 2012
Qua một thời gian tìm hiểu, em chọn đề tài cho bài thu hoạch của mình là: “Tìm hiểu,
xây dựng khai phá dữ liệu văn bản hồ sơ bệnh án của một bệnh viện và ứng dụng phương

lựa chọn yêu cầu, tiền xử lý, nhóm - lấy mẫu, và biến đổi nó ; để áp dụng phương pháp
khai phá dữ liệu (thuật toán) để liệt kê mẫu hình từ nó; và để đánh giá sản phẩm của khai
phá dữ liệu để nhận dạng tập hợp con của mẫu hình liệt kê cho là kiến thức.( Fayyad,
U.M et al. (1996). Advances in Knowledge Discovery and Data Mining. MIT Press).
Quá trình khám phá tri thức là một chuỗi lặp gồm các bước:
• Data cleaning (làm sạch dữ liệu)
• Data integration (tích hợp dữ liệu)
• Data selection (chọn lựa dữ liệu)
• Data transformation (biến đổi dữ liệu)
• Data mining (khai phá dữ liệu)
• Pattern evaluation (đánh giá mẫu)
• Knowledge presentation (biểu diễn tri thức)
Quá trình khám phá tri thức là một chuỗi lặp gồm các bước được thực thi với:
• Data sources (các nguồn dữ liệu)
• Data warehouse (kho dữ liệu)
• Task-relevant data (dữ liệu cụ thể sẽ được khai phá)
• Patterns (mẫu kết quả từ khai phá dữ liệu)
• Knowledge (tri thức đạt được)
5
GVHD: PGS.TS. Đỗ Phúc
Học viên: Võ Hồng Phương
Khai phá dữ liệu và kho dữ liệu 2012
Hình 2: Quá trình khám phá tri thức được thực thi
1.2 Khái niệm Text Mining:
1.2.1 Khai phá dữ liệu (Data Mining):
Khai phá dữ liệu là phân tích các dữ liệu và sử dụng các kỹ thuật để trích xuất tri thức
từ lượng dữ liệu rất lớn.
Tri thức đạt được từ quá trình khai phá:
• Tri thức đạt được có thể có tính mô tả hay dự đoán tùy thuộc vào quá trình khai
phá cụ thể.

• Thành phần chứa tri thức miền, được dùng để hướng dẫn quá trình tìm kiếm, đánh
giá các mẫu kết quả được tìm thấy.
• Tri thức miền có thể là các phân cấp khái niệm, niềm tin của người sử dụng, các
ràng buộc hay các ngưỡng giá trị, siêu dữ liệu, …
4. Data mining engine:
8
GVHD: PGS.TS. Đỗ Phúc
Học viên: Võ Hồng Phương
Khai phá dữ liệu và kho dữ liệu 2012
• Thành phần chứa các khối chức năng thực hiện các tác vụ khai phá dữ liệu.
5. Pattern evaluation module:
• Thành phần này làm việc với các độ đo (và các ngưỡng giá trị) hỗ trợ tìm kiếm và
đánh giá các mẫu sao cho các mẫu được tìm thấy là những mẫu được quan tâm bởi
người sử dụng.
• Thành phần này có thể được tích hợp vào thành phần Data mining engine.
6. User interface:
• Thành phần hỗ trợ sự tương tác giữa người sử dụng và hệ thống khai phá dữ liệu.
• Người sử dụng có thể chỉ định câu truy vấn hay tác vụ khai phá dữ liệu.
• Người sử dụng có thể được cung cấp thông tin hỗ trợ việc tìm kiếm, thực hiện khai
phá dữ liệu sâu hơn thông qua các kết quả khai phá trung gian.
• Người sử dụng cũng có thể xem các lược đồ cơ sở dữ liệu/kho dữ liệu, các cấu
trúc dữ liệu; đánh giá các mẫu khai phá được; trực quan hóa các mẫu này ở các
dạng khác nhau.
1.2.3 Ý nghĩa và vai trò của khai phá dữ liệu:
Hình 6: Sự tiến hóa của công nghệ hệ cơ sở dữ liệu
9
GVHD: PGS.TS. Đỗ Phúc
Học viên: Võ Hồng Phương
Khai phá dữ liệu và kho dữ liệu 2012
Công nghệ hiện đại trong lĩnh vực quản lý thông tin:

Các nghiên cứu mới chỉ dừng lại ở bước tìm hiểu, khảo sát, so sánh hai bài toán cụ
thể, đó là bài toán phân loại dữ liệu văn bản (Text categorization) và bài toán thu thập
thông tin (information retrieval) tạo tiền đề cho các nghiên cứu cụ thể sau này.
- Các khó khăn trong khai phá dữ liệu văn bản:
Tính đa chiều (high dimensonality): Số thuật ngữ trong một văn bản lớn dẫn đến số
chiều của không gian vector sẽ rất lớn.
Tính khả cỡ (scability): Các CSDL lớn thường chứa hàng trăm nghìn văn bản.
Tính chính xác (accuracy): Bất kỳ ngôn ngữ nào cũng đều có sự nhập nhằng.
Tri thức tiên nghiệm: Trong nhiều bài toán chẳng hạn như bài toán lập nhóm văn bản
thì người sử dụng phải xác định trước một số tham số đầu vào như số nhóm văn bản cần
lập.
- Với một hệ thống khai phá văn bản thường bao gồm ba bước chính:
- Bước tiền xử lý: hệ thống sẽ chuyển văn bản từ dạng phi cấu trúc về dạng có cấu
trúc. Ví dụ: với văn bản tòa nhà này to quá, hệ thống sẽ cố gắng phân tích thành tòa nhà|
này|to|quá. Các từ được lưu riêng rẽ một cách có cấu trúc để tiện cho việc xử lý.
- Loại bỏ các thông tin không cần thiết. Bộ phân tích tìm cách loại bỏ các thông tin
vô ích từ văn bản. Bước này phụ thuộc rất nhiều vào ngôn ngữ đang được phân tích và kỹ
thuật sẽ được dùng để phân tích ở bước tiếp theo. Ví dụ: nếu kỹ thuật phân tích văn bản
chỉ dựa vào xác suất xuất hiện từ khoá, khi đó ta có thể loại bỏ các từ phụ như: nếu, vậy,
tuy nhiên, như vậy…
- Khai phá dữ liệu đã được giản lược với các kỹ thuật khai phá dữ liệu (data mining)
truyền thống.
Có rất nhiều kỹ thuật và phương pháp tốt được sử dụng cho Text Mining để tìm ra
các kiến trúc mới, các mẫu mới, và các liên kết mới. Các bước tiền xử lý là các kỹ thuật
rất phức tạp nhằm phân tích một phân lớp đặc biệt thành các thuộc tính đặc biệt, sau đó
tiến hành áp dụng các phương pháp khai phá dữ liệu kinh điển tức là phân tích thống kê
11
GVHD: PGS.TS. Đỗ Phúc
Học viên: Võ Hồng Phương
Khai phá dữ liệu và kho dữ liệu 2012

- Khai phá văn bản đầy đủ: Không giống như loại liên kết thông thường thực hiện
thao tác mù quáng trên các chú dẫn của văn bản, kỹ thuật này sử dụng lợi thế của nội
dung nguyên mẫu của các văn bản. Kỹ thuật này được gọi là “trích văn bản nguyên mẫu”.
1.3. Bài toán phân loại văn bản (Text categorization):
1.3.1 Khái niệm phân loại văn bản:
Phân loại văn bản (Text categorization) là xử lý nhóm các tài liệu thành các lớp khác
nhau hay các phân nhóm (categories). Đây là một tác vụ phân lớp liên quan đến việc ra
quyết định xử lý. Với mỗi xử lý phân nhóm, khi đưa ra một tài liệu, một quyết định được
đưa ra có thuộc một lớp nào hay không. Nếu nó thuộc một phân lớp nào đó thì phải chỉ ra
phân lớp mà nó thuộc vào. Ví dụ: đưa ra một chủ đề về thể thao, cần phải đưa ra quyết
định rằng chủ đề đó thuộc các phân lớp cờ vua, quần vợt, cầu lông, bơi lội hay bất cứ một
môn thể thao nào khác. Các hệ thống phân loại văn bản thường làm việc với một thuật
toán tự học (learning algorithm). Thuật toán đó được cung cấp một tập mẫu để phục vụ
cho việc dạy học. Tập mẫu này bao gồm một tập các thực thể có gán nhãn được phân lớp
trước có dạng (x, y) ở đó x là thực thể được phân lớp, y là nhãn (hay phân lớp) được gán
cho nó. Với cơ cấu cơ sở như vậy, khi một thực thể được cung cấp cho hệ thống, nó sẽ cố
gắng suy ra một hàm toán học từ tập đào tạo mẫu và ánh xạ thực thể mới đó vào một
phân lớp. Phân lớp văn bản là bài toán hay và đang có những bước phát triển hết sức
quan trọng mà nguyên nhân chủ yếu do sự phát triển mạnh mẽ gần đây của các thông tin
trực tuyến.
1.3.2 Các phương pháp phân loại văn bản:
1.3.2.1 Nguyên mẫu:
Nguyên mẫu (prototype) có thể là phương pháp đơn giản nhất được áp dụng trong
phân loại văn bản. Mỗi văn bản đầu vào là một vector (w
1
, w
2
,… w
k
) trong đó mỗi

(word) trong D.
l là tổng số từ w trong tài liệu D
Giá trị lớn nhất của xác suất P(C
i
| D) được đưa ra bởi nguời làm công tác phân loại.
Tài liệu D sẽ được gán cho loại văn bản nào có xác suất hậu nghiệm cao nhất nên được
biểu diễn bằng công thức:
trong đó N là tổng số tài liệu.
14
GVHD: PGS.TS. Đỗ Phúc
Học viên: Võ Hồng Phương
Khai phá dữ liệu và kho dữ liệu 2012
1.3.2.3 Phương pháp dựa trên cây quyết định
Hình 7: Một ví dụ về cây quyết định
Đây là phương pháp học xấp xỉ các hàm mục tiêu có giá trị rời rạc. Cây quyết định
này được tổ chức như sau: Các nút trung gian được gán nhãn bởi các thuật ngữ, nhãn của
các cung tương ứng với trọng số của thuật ngữ trong tài liệu mẫu, nhãn của các lá tương
ứng với nhãn của các lớp. Cho một tài liệu dj, ta sẽ thực hiện so sánh các nhãn của cung
xuất phát từ một nút trung gian (tương ứng với một thuật ngữ nào đó) với trọng số của
thuật ngữ này trong d
j
, để quyết định nút trung gian nào sẽ được duyệt tiếp. Quá trình này
được lặp từ nút gốc của cây, cho tới khi nút được duyệt là một lá của cây. Kết thúc quá
trình này, nhãn của nút lá sẽ là nhãn của lớp được gán cho văn bản.
Các giải thuật ID3 và cải tiến của nó là C45 được đánh giá là hiệu quả và được sử
dụng phổ biến nhất.
1.3.2.4 Phương pháp phân loại văn bản K-NN (K – Nearest Neighbor)
Tư tưởng chính của giải thuật này là tính toán độ phù hợp của văn bản đang xét với
từng nhóm chủ đề dựa trên K văn bản mẫu có độ tương tự gần nhất. Giải thuật này còn
được sử dụng trong bài toán tìm kiếm văn bản và bài toán tóm tắt văn bản.

16
GVHD: PGS.TS. Đỗ Phúc
Học viên: Võ Hồng Phương
Khai phá dữ liệu và kho dữ liệu 2012
1.3.2.6 Sử dụng từ điển phân cấp chủ đề:
Một phương pháp thống kê phân lớp văn bản được điều khiển bởi một từ điển chủ đề
có phân cấp được đề xuất. Phương pháp này sử dụng một từ điển với một cấu trúc đơn
giản. Từ điển này có thể dạy được dễ dàng trên một tập hợp tài liệu được phân lớp bằng
tay và có thể dịch được tự động sang nhiều ngôn ngữ khác nhau.
Có một vấn về xuất hiện là độ tối ưu, hay độ hợp lý, độ chi tiết cho phân loại như
vậy. Ví dụ: khi phân loại tin tức trên internet với một người đọc “bình thường”, những
phân loại như các loài động vật hoặc nghành công nghiệp thì khá phù hợp, trong khi phân
lớp các chủ đề về động vật học giống như một cuốn từ điển như vậy sẽ đưa ra một câu
trả lời chung chung rằng tất cả các chủ đề đó đều nói về động vật. Hay nói cách khác, với
một người đọc tin tức trên internet bình thường, thật không thích hợp dùng để phân loại
những tài liệu với những chủ đề chi tiết hơn như những động vật có vú, động vật có
xương sống, động vật thân nhiệt…
- Giải thuật phân lớp và phân cấp chủ đề:
Vào năm 1997 và 1998, hai ông Guzmán và Arenas đề xuất việc sử dụng một từ điển
có phân cấp để xác định những đề tài chính của một tài liệu. Về mặt kỹ thuật, một từ điển
gồm 2 phần: các nhóm từ khóa đại diện cho các chủ đề riêng biệt và một biểu diễn phân
cấp cho chủ đề này.
Một nhóm từ khóa là một danh sách từ hoặc các biểu thức liên quan đến tình trạng
tham chiếu bởi tên của chủ đề. Ví dụ: chủ đề về tôn giáo liệt kê các từ như: nhà thờ, chùa,
thầy tu, kinh thánh, phật tử … Những từ này không được liên kết với đầu mục tôn giáo
hay liên kết với nhau bởi bất kỳ quan hệ ngữ nghĩa nào.
Cây chủ đề được tổ chức thành một phân cấp hay nói chung tổ chức thành một mạng
(khi đó một số chủ đề có thể thuộc một vài nút của cây phân cấp).
17
GVHD: PGS.TS. Đỗ Phúc

Khai phá dữ liệu và kho dữ liệu 2012
Hình 8: Mô hình thu thập thông tin chuẩn
Khi thu thập dữ liệu, chúng ta thường cố gắng tìm kiếm các dữ liệu chính xác. Trong
các trường hợp khác, chúng ta kiểm tra để xem một thông tin có trong một tập tin hay
không. Khi thu thập thông tin, kết quả chính xác thường được quan tâm, nhưng thông
thường chúng ta muốn tìm kiếm một cách tương đối chính xác với một thông tin đặc biệt
được đưa vào. Sau đó chúng ta sẽ tự chọn thông tin phù hợp nhất từ các kết quả của phép
xử lý trước đó. Trong thu thập thông tin, một phép tìm kiếm nhằm tìm ra tài liệu mà
người dùng đang cần. Các hệ thống thu thập thông tin (IR systems) được sử dụng để thu
thập các tài liệu liên quan đến các yêu cầu rõ ràng. Vấn đề thu thập thông tin là việc xử lý
các văn bản có nội dung liên quan nội tại với đến các văn bản được sử dụng trước đó.
Việc thu thập thông tin có thể được định nghĩa cho bất cứ một loại thông tin nào ví
dụ: kiểu văn bản, hình ảnh, âm thanh…
Các kỹ thuật thu thập thông tin có thể chia ra làm 2 loại:
- Các kỹ thuật chuẩn.
- Các kỹ thuật có áp dụng trí tuệ nhân tạo.
Nhóm 1 dựa trên các phương thức thuật toán và toán học truyền thống để thu thập thông
tin. Nhóm còn lại thu thập tri thức dựa trên các kỹ thuật trí tuệ nhân tạo để đạt được kết
quả tốt hơn.
1.4.2 Các phương pháp thu thập thông tin:
Ngày nay, internet đã trở thành nơi lưu trữ trực tuyến rất lớn, quản lý và đặc biệt là
nơi thu nhận thông tin nhanh chóng và tiện lợi. Các thông tin thu thập được từ Internet
phù hợp với nhu cầu người dùng.
Các phương pháp thu thập thông tin được phát triển rất nhiều và kết quả mà chúng
đem lại khá tốt. Trong đó có rất nhiều phương pháp tồn tại ở dạng chuẩn. Các phương
19
GVHD: PGS.TS. Đỗ Phúc
Học viên: Võ Hồng Phương
Dừng lại
Khai phá dữ liệu và kho dữ liệu 2012

này được gọi là mức đồng sắp xếp và có thể được sử dụng như một hàm so sánh.
Ví dụ: các từ khoá K1, K2, K3 được liên kết với các tài liệu D1, D2, D3, D4 theo
cách sau:
K1 liên kết với D1, D2, D3, D4
K2 liên kết vơi D1, D2
K3 liên kết với D2, D3
và Q = K1 AND K2 AND K3
Với truy vấn Q, chúng ta sẽ có các mức đồng sắp xếp như sau:
3 D2
20
GVHD: PGS.TS. Đỗ Phúc
Học viên: Võ Hồng Phương
Khai phá dữ liệu và kho dữ liệu 2012
2 D1, D3
1 D4
1.4.2.1.1.2 Tìm kiếm tuần tự:
Kỹ thuật tìm kiếm tuần tự là cơ sở của mô hình Boolean. Tuy nhiên ngày nay nó rất
thường xuyên được sử dụng mặc dù nó khá chậm. Nhưng với bất cứ cách nào, nó cho
thấy cách mà các hàm so sánh được sử dụng.
Đưa ra một tập các tài liệu và một truy vấn {D
1
, D
2
, ,D
N
} và một truy vấn Q, chúng
ta đi tính N giá trị của hàm so sánh M(Q,D
i
). Để nhận được các tài liệu liên quan, chúng
ta cần sắp xếp các tài liệu giảm dần của hàm so sánh và bỏ đi tất cả các tài liệu ứng với

trọng số ứng với từng thuật ngữ cụ thể. Trong trường hợp này, m là tổng số thuật ngữ
được định nghĩa để xác định nội dung của tài liệu. Trọng số được tính bởi xác suất xuất
hiện và độ quan trọng của từ khoá.
D=(w
1
, w
2
, , w
N
)
Trong mô hình này, một truy vấn được đối xử như một tài liệu. Hay nói cách khác,
chúng ta sẽ biểu câu truy vấn bởi một vec-tơ trọng số của các thuật ngữ. Sau khi thực
hiện việc phân tích câu truy vấn ta sẽ thu được một vec-tơ. Việc thực hiện câu truy vấn
này thực chất là việc so sách vec-tơ của câu truy vấn với các vec-tơ đại diện cho các tài
liệu theo một tiêu chuẩn nào đó. Kết quả ta sẽ thu được một danh sách các tài liệu có
quan hệ “gần” với câu truy vấn đã đưa ra. Tất nhiên, các tài liệu đó sẽ được sắp xếp theo
trình tự giảm dần và sẽ bị cắt ở một ngưỡng nào đó.
22
GVHD: PGS.TS. Đỗ Phúc
Học viên: Võ Hồng Phương
Khai phá dữ liệu và kho dữ liệu 2012
Hình 9: Đồ thị biểu diễn quan hệ giữa truy vấn (query) và các tài liệu D1, D2.
Để tính vec-tơ biểu diễn một tài liệu, các từ riêng biệt trong tài liệu được tổ hợp lại.
Trên thực tế, việc thực hiện được thực hiện theo cách sau:
- Các từ phụ được xoá đi.
- Phân biệt các từ bởi khoảng trắng.
Đối với Anh ngữ hoặc Pháp ngữ, mỗi từ được tách biệt bởi các khoảng trắng. Nhưng
ngôn ngữ tiếng Việt lại nảy sinh vấn đề từ đơn và từ ghép. Đây cũng là một vấn đề khó
khăn khi phân tách từ trong tiếng Việt. Ví dụ: với từ hospital trong tiếng Anh, ứng với nó
là từ bệnh viện trong tiếng Việt. Do vấn đề về từ ghép nên gay nhiều hiểu nhầm trong