TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
KHOA CÔNG NGHỆ THÔNG TIN
──────── * ───────
ĐỒ ÁN
TỐT NGHIỆP ĐẠI HỌC
NGÀNH CÔNG NGHỆ THÔNG TIN
XÂY DỰNG THỬ NGHIỆM TẬP MẪU VÀ
PHẦN MỀM PHÂN TỰ ĐỘNG PHÂN LOẠI
VĂN BẢN TIẾNG VIỆT
Sinh viên thực hiện : Trần Quý Giáp
Lớp CNPM
Giáo viên hướng dẫn: TS Huỳnh Quyết Thắng
Hà nội 5-2007
1
2
Xây dựng thử nghiệm tập mẫu và phần mềm tự động phân loại văn bản.
PHIẾU GIAO NHIỆM VỤ ĐỒ ÁN TỐT NGHIỆP
1. Định hướng đề tài tốt nghiệp
Nghiên cứu tập mẫu, công thức phân loại văn bản. Xây dựng thử nghiệm tập
mẫu tiếng việt và xây dựng phần mềm phân loại văn bản theo công thức cải tiến.
2. Các nhiệm vụ cụ thể của ĐATN
 Xây dựng tập mẫu tiếng việt với số lượng lớn về văn bản mẫu và nhiều về
phân lớp văn bản.
 Cài đặt chương trình tự động phân loại văn bản theo công thức cải tiến có tốc
độ xử lý nhanh.
 Đề xuất các giải pháp để tăng độ chính xác của chương trình.
3. Lời cám đoan của sinh viên:
Tôi – Trần Quý Giáp - cam kết ĐATN là công trình nghiên cứu của bản thân tôi
dưới sự hướng dẫn của TS. Huỳnh Quyết Thắng
Các kết quả nêu trong ĐATN là trung thực, không phải là sao chép toàn văn của bất
kỳ công trình nào khác.

about text collection, the dictionary and the formula to improve more the precision
of result in procesing.
Sinh viên thực hiện : Trần Quý Giáp K47 Lớp CNPM Trang
5
Xây dựng thử nghiệm tập mẫu và phần mềm tự động phân loại văn bản.
Lời mở đầu 8
Danh mục hình : 10
2 10
Danh mục bảng : 11
Danh mục từ viết tắt 12
3 Chương 1. Tổng quan về bài toán xử lý văn bản 13
3.1 Khai phá dữ liệu và phát hiện tri thức 13
3.1.1 Dữ liệu, thông tin và tri thức 13
3.1.2 Khai phá dữ liệu và phát hiện tri thức 14
3.2 Các Khái niệm trong xử lý văn bản 15
3.2.1 Từ khoá, Thuật ngữ, và Khái niệm 15
3.2.2 Từ dừng ( Stop word ) 16
3.2.3 Trọng số của thuật ngữ 16
3.2.4 Độ Liên quan giữa các văn bản 17
3.3 Các bài toán cơ bản trong xử lý văn bản 17
3.3.1 Tìm kiếm văn bản (Text Retrieval) 17
3.3.2 Phân lớp văn bản (Text Categorization, Text Classification) 18
3.3.3 Phân nhóm văn bản (Text Clustering) 18
3.3.4 Tóm tắt văn bản (Text Summarization) 18
3.3.5 Dẫn đường văn bản (Text Routing) 19
3.4 Kết chương 19
4 Chương 2. Bài toán phân loại văn bản 20
4.1 Giới thiệu bài toán phân lớp văn bản 20
4.2 Các thuật toán được sử dụng trong bài toán phân lớp văn bản 20
4.2.1 Các phương pháp phân chia (Partitionning Algorithms) 21

5.3.1.6 Tổng kết về Reuter 21578 44
5.3.2 Tập mẫu RCV1 44
5.3.2.1 Tổng quan về tập mẫu RCV1 và RCV2 44
5.3.2.2 Mã hoá dữ liệu tập mẫu RCV1 44
5.3.2.3 Quá trình xây dựng RCV1 45
5.3.2.4 Cấu trúc của tập mẫu RCV1 47
5.3.2.5 Kết luận về RCV1 50
5.4 Kết chương 50
6 Chương 4. Bài toán phân loại văn bản tiếng việt và giải pháp 51
6.1 Tổng quan về xử lý ngôn ngữ tự nhiên 51
6.2 Đặc điểm chung của ngôn ngữ tiếng việt 51
6.2.1 Tính âm tiết 52
6.2.2 Từ trong tiếng việt 52
6.2.3 Ngũ pháp tiếng việt 54
6.2.3.1 Phó từ 55
6.2.3.2 Giới từ 55
6.2.3.3 Liên từ 56
6.2.4 Font được sử dụng trong tiếng việt 56
6.3 Bài toán phân lớp văn bản tiếng việt 57
6.4 Giải thuật phân loại văn bản – công thức cải tiến 57
6.4.1 Mô hình tiếp cận bài toán 57
6.4.1.1 Từ điển 58
6.4.1.2 Tách term và loại bỏ Stopword 59
6.4.1.3 Biểu diễn văn bản 60
6.4.1.4 Các công thức tính toán sử dụng trong thuật giải 61
6.4.1.5 Công thức cải tiến 63
6.4.1.6 Sử dụng thuật toán KNN để xác định thể loại của văn bản 64
6.5 Kết chương 67
7 Chương 5. Tập mẫu tiếng việt và giải pháp 68
7.1 Ý tưởng từ tập mẫu tiếng việt 68

quản lý chúng. Chương trình phân loại văn bản là chương trình đáp ứng được
yêu cầu đó. Thông qua phân loại văn bản chúng ta có thể phân loại, xắp xếp
chúng phù hợp với chủ đề tương ứng với độ chính xác cao. Phân loại văn bản
được ứng dụng trong rất nhiều lĩnh vực, đặc biệt trong lĩnh vực báo điện tử, hay
ở những cơ quan lưu trữ tài liệu…
Đã có nhiều nghiên cứu và các đề tài khoa học về vấn đề này, và chúng ta đã
đạt tới nhiều thành công. Nhưng dù vậy chúng ta vẫn chưa có một tập mẫu tiếng
việt chuẩn của chúng ta để kiểm nghiệm độ chính xác của các phần mềm phân
loại tiếng việt.
Trong đồ án này em đã tạo ra một tập mẫu tiếng việt thử nghiệm và được sử
dụng ngay trong chương trình phân loại phân bản tự đông, thực nghiệm cho thấy
nó cho kết quả tốt. Tuy nhiên vì kiến thức còn hạn chế và thời gian có hạn nên
chắc hẳn chương trình và tập mẫu của em còn nhiều sai sót, kính mong các thầy
cô góp ý để em có thể hoàn thiện đồ án của mình.
Và cuối cùng em xin chân thành gửi lời cảm ơn thầy Huỳnh Quyết Thắng đã
tận tình hướng dẫn làm đề tài và chị Đinh Thị Phương Thu đã cung cấp cho em
nhiều kiến thức và kinh nghiệm để em có thể hoàn thành đồ án của mình.
Hà nội, ngày 22 tháng 5 năm 2007

Sinh viên
Trần Quý Giáp
Sinh viên thực hiện : Trần Quý Giáp K47 Lớp CNPM Trang
8
Xây dựng thử nghiệm tập mẫu và phần mềm tự động phân loại văn bản.
Lời cảm ơn !
Sinh viên thực hiện : Trần Quý Giáp K47 Lớp CNPM Trang
9
Trước hết, em xin được chân thành gửi lời cảm ơn sâu sắc tới các
thầy cô giáo trong trường Đại học Bách Khoa Hà Nội nói chung và các
thầy cô trong khoa Công nghệ Thông tin, bộ môn Công nghệ phần mềm

11
Xây dựng thử nghiệm tập mẫu và phần mềm tự động phân loại văn bản.

Danh mục từ viết tắt
STT Từ Giải nghĩa
01 KNN K_Nearest Neighbor_ thuật toán k lớp văn bản láng giềng gần nhất
02 NNTN Ngôn ngữ tự nhiên
03 SGML Standard Generalized Markup Language
04 IRL
Information Retrieval Laboratory- thư viện lưu trữ thông tin
05 RCV
Reuters Corpus Volume – tập mẫu RCV
06 IDF
Inverse Document Frequency _ nghịch đảo tần suất văn bản.
07 IF Item Frequency- tần suất từ khoá
08 STING
Statistical Information Grid
09 W Weigh – trọng số
Sinh viên thực hiện : Trần Quý Giáp K47 Lớp CNPM Trang
12
Xây dựng thử nghiệm tập mẫu và phần mềm tự động phân loại văn bản.
3 Chương 1. Tổng quan về bài toán xử lý văn bản
3.1 Khai phá dữ liệu và phát hiện tri thức
3.1.1 Dữ liệu, thông tin và tri thức
Dữ liệu được hiểu là một chuỗi các bit, các con số hoặc các đối tượng mà
chúng ta thu thập được hàng ngày. Ví dụ: dữ liệu là các file trong máy tính, dữ liệu
là các văn bản giấy tờ mà chúng ta phải xử lý hàng ngày, các tín hiệu,
Thông tin là dữ liệu đã được loại bỏ đi nhiễu, sự dư thừa và đã được biểu diễn
dưới dạng mà con người có thể nhận thức được.Ví dụ: thông tin về tình hình chiến
sự tại Iraq, thông tin về nhiệt độ trong tháng,

liệu/mẫu), data archaeology (khảo cổ dữ liệu), data dredging (nạo vét dữ liệu)
.Hiện nay, thuật ngữ khai phá dữ liệu được dùng quen thuộc và thường đồng nhất
với một thuật ngữ khác là phát hiện tri thức trong cơ sở dữ liệu – Knowledge
Descovery in Database (KDD). Thực ra, khai phá dữ liệu chỉ là một bước trong các
quá trình của KDD.
Tiến trình khai phá dữ liệu và phát hiện tri thức (KDD) nói chung bao gồm
7 quá trình cơ bản sau đây:
1. Làm sạch dữ liệu: Loại bỏ nhiễu và các dữ liệu không cần thiết.
2. Tích hợp dữ liệu: Tích hợp các nguồn dữ liệu khác nhau.
3. Lựa chọn dữ liệu: Chọn lựa các dữ liệu liên quan tới quá trình phân tích.
4. Chuyển đổi dữ liệu: Các dữ liệu được chuyển đổi sang các dạng phù hợp cho
việc xử lý.
5. Khai phá dữ liệu: Là một trong những bước quan trọng nhất, ở đây sử dụng
những phương pháp thông minh để chắt lọc ra những mẫu dữ liệu.
6. Ước lượng mẫu: Quá trình này nhằm đánh giá các kết quả tìm được thông
qua các độ đo nào đó.
7. Biểu diễn tri thức: Sử dụng các kỹ thuật biểu diễn và thể hiện trực quan các
tri thức cho người dùng.
Sinh viên thực hiện : Trần Quý Giáp K47 Lớp CNPM Trang
14
Xây dựng thử nghiệm tập mẫu và phần mềm tự động phân loại văn bản.
Hình 1.1. Tiến trình khai phá dữ liệu và phát hiện tri thức
Việc áp dụng tiến trình KDD có thể thực hiện trên nhiểu kiểu loại dữ liệu khác
nhau với các hình thức tổ chức lưu trữ khác nhau. Hiện nay, có rất nhiều cách tổ
chức dữ liệu khác nhau: cơ sở dữ liệu văn bản, cơ sở dữ liệu quan hệ, cơ sở dữ liệu
hướng đối tượng, cơ sở dữ liệu không gian, cơ sở dữ liệu hướng thời gian,… Đối
với mỗi dạng cơ sở dữ liệu lại có các phương pháp xử lý khác nhau và mục đích
khai phá dữ liệu khác nhau tùy theo tính chất và đặc thù của dữ liệu.
Các kỹ thuật được sử dụng có thể là các phương pháp truyền thống như học
máy (Machine Learning), nhận dạng (Recognition), thống kê (Statistics), phân lớp

nhiều hơn so với thuật ngữ “số hóa”. Một tiêu chuẩn để xem xét mức độ liên quan
là xác xuất đồng xuất hiện của cặp khái niệm – thuật ngữ trong các văn bản. Khi
thuật ngữ “máy tính” xuất hiện nhiều trong các văn bản chứa thuật ngữ “tin học”
thì có nghĩa là độ liên quan (hay độ phụ thuộc) giữa cặp “tin học”-“máy tính” càng
cao. Một lý do để giải thích suy luận này là mức độ thay thế.
3.2.2 Từ dừng ( Stop word )
Có thể quan sát thấy rằng trong các ngôn ngữ tự nhiên, rất nhiều từ được dùng
để biểu diễn cấu trúc câu nhưng hầu như không mang ý nghĩa về mặt nội dung,
chẳng hạn các loại từ: giới từ, liên từ,… Các loại từ này xuất hiện thường xuyên
trong các văn bản nhưng không hề mang bất cứ một thông tin nào về nội dung hay
chủ đề của văn bản. Việc loại bỏ các từ như vậy cũng đồng nghĩa với việc giảm số
chiều của văn bản, những từ đó được gọi là từ dừng (stop words).
Từ dừng (Stop Words): là các từ mang ít ý nghĩa trong xử lý văn bản vì nó
xuất hiện trong hầu hết các văn bản. Ví dụ: “Có thể”, “nếu”, “vì vậy”, “sau khi”,
“thì”, “một số”, “với lại”, “quả thật”, “hầu như”
Có một số phương pháp để xác định các từ dừng.
Xây dựng một thuật toán phát hiện các từ dừng. Trong thuật toán này cần đưa
ra một ngưỡng để phát hiện từ dừng, ví dụ nếu phát hiện thấy một từ xuất hiện trong
quá 50% số văn bản thì có thể coi đó là từ dừng.
Sử dụng so sánh với một từ điển từ dừng. Từ điển từ dùng là một từ điển đã
được nghiên cứu và xây dựng sẵn từ trước.
3.2.3 Trọng số của thuật ngữ
Trọng số của thuật ngữ là độ quan trọng hay hàm lượng thông tin mà thuật
ngữ đó mang lại cho văn bản. Nó là đại lượng dùng để đo sự khác biệt giữa văn bản
Sinh viên thực hiện : Trần Quý Giáp K47 Lớp CNPM Trang
16
Xây dựng thử nghiệm tập mẫu và phần mềm tự động phân loại văn bản.
chứa nó với các văn bản khác. Đại lượng này thường được xác định bằng tay hoặc
đánh giá bằng số lần xuất hiện của thuật ngữ trong văn bản và số lần xuất hiện của
thuật ngữ đó trong các văn bản khác. Khi số lần xuất hiện của thuật ngữ trong văn

3.3.1 Tìm kiếm văn bản (Text Retrieval)
Tìm kiếm văn bản (Text Retrieval) là quá trình tìm các văn bản trong một kho
lưu trữ theo các yêu cầu của người dùng. Ở đây, các yêu cầu là các truy vấn và
thường được biểu diễn dưới dạng thuật ngữ hay biểu thức logic giữa các thuật ngữ.
Sinh viên thực hiện : Trần Quý Giáp K47 Lớp CNPM Trang
17
Xây dựng thử nghiệm tập mẫu và phần mềm tự động phân loại văn bản.
Ví dụ: truy vấn “Text Mining” AND (“Categorization” OR “Classification”).
Ứng với truy vấn này search engine của hệ thống sẽ tìm tất cả các tài liệu về “Text
Mining” có liên quan đến “Categorization” hoặc “Classification”. Trên thực tế thì
hầu hết các hệ thống chỉ được thiết kế để hiểu các truy vấn tương tự như “Text
Mining” OR “Categorization” OR “Classification”. Với câu truy vấn này hệ thống
sẽ tìm kiếm các tài liệu theo mức phù hợp với cả ba thuật ngữ “Text Mining”,
“Categorization”, và “Classification”.
Kết quả đầu ra của một phép truy vấn là danh sách các tài liệu được sắp xếp
giảm dần theo mức độ phù hợp với câu truy vấn đầu vào.
3.3.2 Phân lớp văn bản (Text Categorization, Text Classification)
Phân lớp văn bản được định nghĩa như quá trình gán các văn bản vào một hay
nhiều lớp văn bản đã được xác định trước dựa trên nội dung của văn bản đó.
Người ta 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 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
khi số lượng văn bản lớn nên không khả thi. Do vậy cần 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 phương pháp học máy
trong trí tuệ nhân tạo. Khi phân lớp, văn bản được gán vào một lớp theo một giá trị
ngưỡng nào đó. Ngưỡng đặt ra tùy thuộc vào thuật toán và yêu cầu người dùng.
3.3.3 Phân nhóm văn bản (Text Clustering)
Phân nhó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ự về
nội dung của các văn bản. Số lượng các nhóm văn bản ở đây là chưa biết trước, chẳng hạn
số nhóm có thể là 2,3 5, Người dùng có thể chỉ ra số lượng các nhóm cần phân nhóm
hoặc hệ thống sẽ tự phân nhóm.

Dẫn đường văn bản là sự tổ hợp giữa bài toán tìm kiếm văn bản và phân lớp,
nhóm văn bản. Giống như phân lớp, nhóm văn bản, bài toán dẫn đường cũng đưa
các văn bản về các lớp, nhóm khác nhau và việc xử lý này yêu cầu trong thời gian
thực. Tuy nhiên, nó cũng giống như bài toán tìm kiếm, mỗi lớp, nhóm văn bản được
gán với các thông tin cần thiết của một hay nhiều nhóm người dùng. Mỗi người
dùng có thể thay đổi thêm bớt các yêu cầu của mình. Quá trình phản hồi có thể
được sử dụng để nâng cao chất lượng tìm kiếm văn bản.
Một ứng dụng điểu hình của bài toán dẫn đường văn bản là trong các trang tin
điện tử. Khi đọc một tin mới, hệ thống sẽ tìm cách đưa ra danh sách các tin khác có
liên quan đến đoạn tin đang đọc. Ứng dụng của bài toán này được sử dụng hết sức
rộng rãi trên báo điện tử. Khi đọc một bài báo, phía dưới mỗi trang web sẽ có các
liên kết đến các bài báo khác có liên quan về mặt nội dung Bạn đọc có thể theo các
thông tin dẫn đường này để theo dõi toàn bộ diễn biến của sự kiện
3.4 Kết chương
Trong chương này chúng ta đã tìm hiểu về các bài toán xử lý văn bản và các
khái niệm trong bài toán phân loại văn bản. Những khái niệm trong bài toán phân
loại văn bản là những khái niệm thường xuyên sử dụng giúp chúng ta hiểu rõ hơn
về chương trình đồ án sẽ được tác giả trình bày ở các chương sau.
Sinh viên thực hiện : Trần Quý Giáp K47 Lớp CNPM Trang
19
Xây dựng thử nghiệm tập mẫu và phần mềm tự động phân loại văn bản.

4 Chương 2. Bài toán phân loại văn bản.
4.1 Giới thiệu bài toán phân lớp văn bản
Bài toán phân lớp văn bản là việc gán các chủ đề có trước cho các văn bản dựa
trên nội dung của chúng. Người ta có thể phân lớp văn bản một cách thủ công, hoặc
sử dụng các phương pháp phân lớp tự động.
Để phân lớp được văn bản tự động thường sử dụng các kỹ thuật học máy có
giám sát (supervised learning). Trong kỹ thuật này, dữ liệu được chia ra thành
hai phần: tập huấn luyện hay tập mẫu (training set) và tập kiểm thử (test set).

hành chia chúng ngay từ đầu thành k nhóm. Sau đó, liên tục cải tiến, xác định lại
các nhóm bằng cách di chuyển các đối tượng dữ liệu ở nhóm này sang nhóm khác
cho đến khi thỏa mãn một số điều kiện.
Thuật toán k-means do J.MacQueen đưa ra vào năm 1967 và các biến thể của
nó (k-means chia đôi -bisecting K-Means, ) được biết đến như là các thuật toán
phân chia nổi tiếng. Chúng thường khác nhau trong việc xác định k trọng tâm ban
đầu, tính toán độ tương tự và phương pháp tính toán trọng tâm để giảm thời gian
tính toán.

Hình 2.2. Ví dụ mô tả giải thuật k-means
4.2.2 Phương pháp phân nhóm dựa trên hàm mật độ (Density-Based)
Phương pháp phân nhóm dựa trên mật độ là các phương pháp dựa trên một
ý tưởng: các nhóm ban đầu là các vùng dầy đặc trong không gian dữ liệu sẽ được
tách ra bằng các vùng có mật độ đối tượng thấp hơn. Tiếp tục phát triển đối với các
nhóm mới tách ra cho đến khi mật độ vùng lân cận vượt qua giá trị ngưỡng. Nói
cách khác, với mỗi điểm bất kì trong một nhóm, mật độ điểm địa phương xung
quanh điểm đó phải không vượt quá ngưỡng. Một nhóm sẽ được xác định dựa trên
3 tiêu chí: mật độ (density), các kết nối với những điểm khác (connectivity) và
đường biên (boundary).
Sinh viên thực hiện : Trần Quý Giáp K47 Lớp CNPM Trang
21
Xây dựng thử nghiệm tập mẫu và phần mềm tự động phân loại văn bản.
Có hai cách tiếp cận đối với các phương pháp phân nhóm dựa trên mật độ :
• Density-Based Connectivity: bao gồm các giải thuật được biết đến như
DBSCAN, GDBSCAN, OPTICS, và DBCLASD. Hướng tiếp cận này dựa
trên giá trị mật độ và các kết nối giữa các điểm dữ liệu.
• Density Functions: ví dụ giải thuật DENCLUE, tiếp cận theo hàm mật độ.
4.2.3 Phương pháp phân nhóm dựa trên lưới (Grid-Based Method)
Các phương pháp phân nhóm dựa trên lưới thực hiện lượng tử hóa không
gian thành số lượng hữu hạn các ô (cell) để tạo thành cấu trúc lưới. Sau đó tất cả

Item set)
Có nhiều giải thuật xác định tập các thuật ngữ xuất hiện thường xuyên nổi tiếng
như:
 Thuật toán AIS
 Thuật toán STM
 Thuật toán Apriori, AprioriTid
 Thuật toán FP Growth
Chúng ta sẽ x xét hai thuật toán hay được sử dụng Apriori và FP Growth
4.2.4.1.1Giải thuật Apriori
Thuật toán này sử dụng các k-itemset (tập thuật ngữ gồm k item) để thăm dò
(k+1)-itemset và qua đó khai thác được toàn bộ các tập thuật ngữ thường xuyên
(FIs) trong tập dữ liệu.
 Đầu tiên tính 1-itemsets, 2-itemsets và sau đó là 3-itemsets…
 Khi tính toán (k+1)-itemsets, chỉ xét những (k+1)-itemsets mà tất cả các tập con
có độ dài k đã được xác định là thường xuyên ở bước trước.
Mô tả giải thuật Apriori:
Biến C
k
: Các tập thuật ngữ ứng cử có kích thước k.
Biến L
k
: Các tập thuật ngữ thường xuyên kích thước k.
Sinh viên thực hiện : Trần Quý Giáp K47 Lớp CNPM Trang
23
Xây dựng thử nghiệm tập mẫu và phần mềm tự động phân loại văn bản.
L
1
= {Các thuật ngữ thường xuyên mức 1};
For (k=1; L
k

L
k
Ví dụ:
Hình 2.4. Ví dụ về thuật toán Apriori
Phương pháp tạo và kiểm tra của giải thuật Apriori làm việc tốt. Tuy nhiên, một
số lượng lớn itemset được tạo ra. Nếu có m tập 1-FIs (m tập 1-item frequent) thì có
đến m*(m-1)/2 tập 2-FIs được tạo ra. Ngoài ra, thuật toán đòi hỏi quét nhiều lần
toàn bộ dữ liệu để kiểm tra thuật ngữ thường xuyên, nó đòi hỏi (n+1) lần quét với n
là số lượng k-FIs lớn nhất. Đây cũng là nhược điểm của giải thuật này.
4.2.4.1.2 Giải thuật FP Growth
Sinh viên thực hiện : Trần Quý Giáp K47 Lớp CNPM Trang
24
Xây dựng thử nghiệm tập mẫu và phần mềm tự động phân loại văn bản.
Thuật toán FP-growth thông qua ý tưởng chia để trị (divide & conquer
approach) để cực tiểu số lượng itemset tạo ra. FP-growth giảm bớt số lần quét toàn
bộ cơ sở dữ liệu và khai thác cấu trúc dữ liệu thành cây FP để tìm kiếm tất cả FI.
Ví dụ: Xây dựng cây FP với Min_support = 0.5
Bảng 2.1. Dữ liệu đầu vào để xây dựng cây FP
DocID Items Frequent items
100 {f, a, c, d, g, i, m, p} {f, c, a, m, p}
200 {a, b, c, f, l, m, o} {f, c, a, b, m}
300 {b, f, h, j, o} {f, b}
400 {b, c, k, s, p} {c, b, p}
500 {a, f, c, e, l, p, m, n} {f, c, a, m, p}
Các bước tiến hành:
1. Quét cơ sở dữ liệu, tìm ra các tập thuật ngữ thường xuyên ở mức 1.
2. Sắp xếp các thuật ngữ thường xuyên theo thứ tự giảm dần.
3. Quét cơ sở dữ liệu lại và xây dựng cây FP.

Hình 2.5. Ví dụ về xây dựng cây FP