Đồ án tốt nghiệp K51
Ứng dụng luật kết hợp trong phân tích dữ liệu của mạng xã hội.
Phiếu Giao Nhiệm Vụ Đồ Án Tốt Nghiệp
1. Thông tin về sinh viên
Họ và tên sinh viên: Lê Minh Nghĩa
Điện thoại liên lạc: 0936 073 986 Email:
Lớp: Công Nghệ Phần Mềm K51 Hệ đào tạo: Đại học
Đồ án tốt nghiệp được thực hiện tại bộ môn CNPM, viện Công Nghệ Thông Tin và Truyền
Thông, Đại Học Bách Khoa Hà Nội.
Thời gian làm ĐATN: Từ ngày 1/ 1 /2011 đến 28 / 5 /2011
2. Mục đích nội dung của ĐATN
Nghiên cứu luật kết hợp ứng dụng để khai phá dữ liệu trong mạng xã hội chia sẻ đồ vật MiGi
3. Các nhiệm vụ cụ thể của ĐATN
- Nghiên cứu nắm vững lý thuyết và các thuật toán cơ bản về luật kết hợp
- Xây dựng mạng xã hội chia sẻ đồ vật MiGi
- Xây dựng mô hình khai phá dữ liệu cho mạng xã hội chia sẻ đồ vật MiGi
4. Lời cam đoan của sinh viên:
Tôi – Lê Minh Nghĩa - 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 kĩ sư Hoàng Anh Việt.
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.
Hà Nội, ngà 28 tháng 5 năm 2011
Tác giả ĐATN
Lê Minh Nghĩa
5. Xác nhận của giáo viên hướng dẫn về mức độ hoàn thành của ĐATN và cho phép bảo vệ
Hà Nội, ngày 28 tháng 5 năm 2011
Giáo viên hướng dẫn
Thạc Sỹ Hoàng Anh Việt
Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 1
Đồ án tốt nghiệp K51
Ứng dụng luật kết hợp trong phân tích dữ liệu của mạng xã hội.

nghiệm tốt hơn, cũng như những thông kê và phân tích hữu ích cho quản lý
và kinh doanh. Trong đồ án tốt nghiệp này, người viết luận văn tập trung
nghiên cứu luât kết hợp- một trong những lĩnh vực được ứng dụng rộng rãi
nhất của Data Mining. Đề từ đó góp phần tìm ra các thói quen chia sẻ đồ
vật của người dùng trong mạng chia sẻ đồ vật-MiGi. Nhằm làm cho hệ
thống có thể gợi ý thông minh hơn, giúp người chia sẻ dễ dàng tìm được
người thực sự cần những đồ vật mình cho đi.
Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 3
Đồ án tốt nghiệp K51
Ứng dụng luật kết hợp trong phân tích dữ liệu của mạng xã hội.
Abtract Thesis
Social Network becomes gradually the indispensable thing in the modern
life. It brings the opportunity for people to connect easily, to share their
interests, habits, and thoughts… Social Network has become a huge digital
database to record many different aspects of each users s’ life. It is also the
great chance for data analytic tools to discover useful information of users.
It makes website more intelligent, give better experience for users, and also
useful analytic and statistic for business and management. In this thesis,
author concentrates on Association Rules- one of the most important areas
in Data Mining. With purpose is to find sharing habits in the object sharing
network-MiGi. It makes system more intelligent in suggestion functions,
supports offering people find easily the person that really need the object
they shared.
Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 4
Đồ án tốt nghiệp K51
Ứng dụng luật kết hợp trong phân tích dữ liệu của mạng xã hội.
Mục Lục
Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 5
Đồ án tốt nghiệp K51
Ứng dụng luật kết hợp trong phân tích dữ liệu của mạng xã hội.

Bảng 3.9. Mô tả tính năng tạo request
Bảng3.10. Mô tả tính năng tạo request
Bảng 3.11 Bảng mô tả bảng dữ liệu tbl_Account
Bảng 3.12 Bảng mô tả bảng dữ liệu tbl_Offer
Bảng 3.13 Bảng mô tả bảng dữ liệu tbl_Request
Bảng 3.14 Bảng mô tả bảng dữ liệu tbl_RequestGiftTransaction
Bảng 3.15 Bảng mô tả bảng dữ liệu tbl_GiftRequestTransaction
Bảng 3.16 Bảng mô tả bảng dữ liệu tbl_Category
Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 7
Đồ án tốt nghiệp K51
Ứng dụng luật kết hợp trong phân tích dữ liệu của mạng xã hội.
Danh mục các hình vẽ và đồ thị.
Hình 2.1 Bảng dữ liệu mẫu cho ví dụ
Hình 2.2. Ví dụ về tìm tập mục thường xuyên
Hình 2.3: Code mẫu thuật toán Apriori
Hình 2.4 Ví dụ minh hoạt xây dựng cây FP Tree
Hình 3.1 Sơ đồ Use Case cho người dùng thông thường
Hình 3.2. Sơ đồ use case cho nhóm người tổ chức từ thiện
Hình 3.3. Sơ đồ use case cho nhóm người dùng admin
Hình 3.4. Kiến trúc tổng thể của hệ thống
Hình 3.5. Sơ đồ phụ thuộc của các package chính của hệ thống/
Hình 3.6: Sơ đồ các liên kết các lớp chính của hệ thống
Hình 3.7 Biều đồ diễn tiến chức năng đăng ký
Hình 3.8. Biểu đồ diễn tiến chức năng đăng nhập
Hình 3.9 Biểu đồ diễn tiến chức năng Offer
Hình 3.10 Biểu đồ diễn tiến chức năng tạo mới request đồ vật
Hình 3.11 Biểu đồ diễn tiến cho chức năng hiển thị danh sách offer đồ vật
Hình 3.12 Biểu đồ diễn tiến cho chức năng hiển thị danh sách các request đồ vật
Hình 3.13 Biểu đồ diễn tiến cho chức năng request tới một đồ vật được chia sẻ
Hình 3.14 Biểu đồ diễn tiến cho chức năng offer đồ vật cho một request

Mạng chia sẻ đồ vật là một web site cho phép người dùng đưa các thông tin về các
đồ vật mà người dùng không còn cần dùng nữa. Và những người đang cần tới chúng có
thể sử dụng mạng chia sẻ để dễ dàng liên lạc với người cho. Đó là dự án do người viết
luật văn xây dựng để tham gia cuộc thi Imagine Cup 2011 do Microsoft tổ chức. Với mục
tiêu tạo ra một cộng đồng giúp đỡ lẫn nhau phục vụ cho các mục tiêu thiên niên kỉ là xóa
đói giảm nghèo và bảo vệ môi trường.
Bố cục đề tài tốt nghiệp của NVLV gồm các phần chính sau:
• Chương 1: Trình bày về vai trò của các mạng xã hội với bài toán khai phá dữ liệu.
Lợi ích từ việc khai thác dữ liệu mạng chia sẻ đồ vật MiGi. Đồng thời trình bày
các lý thuyết cơ bản về luật kết hợp.
Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 9
Đồ án tốt nghiệp K51
Ứng dụng luật kết hợp trong phân tích dữ liệu của mạng xã hội.
• Chương 2: Trình bày về các giải thuật cơ bản của luật kết hợp, cùng một kỹ thuật
cài đặt và xử lý.
• Chương 3: Thiết kế và cài đặt mạng chia sẻ đồ vật phục vụ việc phân tích dữ liệu.
• Chương 4: Các kết quả đạt được
Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 10
Đồ án tốt nghiệp K51
Ứng dụng luật kết hợp trong phân tích dữ liệu của mạng xã hội.
Chương 1: Bài toán khai phá
dữ liệu từ mạng xã hội
Trong chương này sẽ trình bày về:
• Sự phát triển của các mạng xã hội
• Mạng xã hội và bài toán data mining
• Mạng xã hội chia sẻ đồ vật
Mạng xã hội đáng phát triển một cách bùng nổ. Nó trở thành một trào lưu mạnh mẽ,
thu hút hàng triệu người tham gia. Nó mang tới cơ hội cho người dùng có thể dễ dàng kết
nối với nhau, chia sẻ thông tin. Các mạng xã hội trở thành những kho lưu trữ số thông tin
của người dùng.

người.
Thành công đến với Facebook nhanh hơn mong đợi khi số lượng thành viên của
mạng xã hội này lần lượt chạm mốc 200 triệu vào tháng 4, 300 triệu vào tháng 9 năm
2009, 400 triệu vào tháng 2 năm 2010. Mới đây nhất, Facebook đã vượt mốc 500 triệu
người dùng.
1.1.2. Mạng xã hội Twitter
Twitter cũng là một trong những mạng xã hội lớn nhất thế giới. Nó còn được biết đến
như một mạng “tiểu” blog khi mà mỗi người dùng chỉ được phép đăng một tin (tweet) có
đồ dài không vượt quá 104 kí tự. Mặc dù vậy, nhưng Twitter đáp ứng đúng yêu cầu của
người dùng trong một xã hội ngày càng “vội vã”.
Ngày 21/3 vừa qua Twitter kỉ niệm sinh nhật lần thứ 5 của mình. Đó một dấu mốc
quan trọng trong sự phát triển nhiều thăng trầm mạng tiểu blog này. Đã có thời Twitter
phải chật vật để níu giữ người dùng. Nhưng ngày nay witter đã trở nên trưởng thành hơn
và giữ một vai trò quan trọng trong xã hội, chính trị, truyền thông, thể thao và nhiều lĩnh
vực khác.
Người dùng Twitter hiện nay gửi đi 140 triệu đoạn tweet mỗi ngày. Trước đây,
Twitter đã mất 3 năm, 2 tháng và 1 ngày để đạt được 1 tỷ tweet đầu tiên, nhưng giờ đây,
cứ 8 ngày thì có 1 tỷ tweet được gửi đi.
Tương tự, Twitter đã mất 18 tháng để có 500 ngàn người dùng, nhưng giờ đây, mỗi
ngày lại có thêm 500 ngàn tài khoản mới được đăng ký.
1.1.3. Mạng xã hội Zing Me
Đáp ứng xu thế mạng xã hội, tại Việt Nam đã có hàng loạt mạng xã hội ra đời. Tiêu
biểu trong số đố là mạng xã hội Zing Me do tập VNG làm chủ. Đây có thể nói là mạng xã
Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 12
Đồ án tốt nghiệp K51
Ứng dụng luật kết hợp trong phân tích dữ liệu của mạng xã hội.
hội lớn nhất Việt Nam. Chỉ sau hơn một năm phát triển Zing Me đã có hơn 5 triệu người
dùng.
Với giao diện được việt hóa thân thiện, cùng sự tích hợp nhiều ứng dụng và dịch vụ
khác nhau, Zing Me đã nhanh chóng thu hút được một lượng lớn người dùng. Đặc biệt là

Đồ án tốt nghiệp K51
Ứng dụng luật kết hợp trong phân tích dữ liệu của mạng xã hội.
loại đồ vật nào. Ví dụ người X cho vật B thì thường sẽ cho thêm vật C, hoặc người lại
người Y khi xin một đồ vật D thì thường sẽ có nhu cầu đối với vật E. Những luật đó gọi
là các luật kết hợp.
Để tìm được các luật kết hợp đó, đòi hỏi phải tìm được tập các đồ vật mà người
dùng thường chia sẻ cùng nhau, hoặc tập các đồ vật mà người dùng thường yêu cầu. Đó
là trọng tâm của tất cả các thuật toán tìm luật kết hợp.
1.2. Các lợi ích từ việc khai thác dữ liệu mạng chia sẻ đồ vật MiGi
Việc khai thác dữ liều từ mạng chia sẻ đồ vật mang lại nhiều thông tin hữu ích cho
nhiều lính vực khác nhau. Có thể kể ra một số hướng có thể khai thác được từ dữ liệu
người dùng của mạng MiGi là:
• Xác định được thói quen chia sẻ đồ vật của người dùng: biết được những món
đồ mà người dùng thường cho đi, các nhu cầu thường đi cùng với nhau. Để từ
đó xây dựng các hệ gợi ý thông minh. Ví dụ: người A cho một cái điện thoại cũ,
người B cần chiếc đoạn thoại đó, thì có thể sẽ cần một chiếc xác điện thoại của
một người X nào đó cũng cho đi.
• Phân tích sở thích của người dùng để phục vụ mục đích quảng cáo. Qua các
đồ vật người đó cho đi có thể biết phần nào là sở thích người dùng là gì. Ví dụ
nhãn hiệu quần áo mà người ta quan tâm. Đó là cơ sở để quảng cáo các sản
phẩm phù hợp.
• Điều tra thị trường: Qua những đồ vật mà cộng đồng cho đi có thể xác định
nhu cầu tiêu thụ của một khu vực nào đó. Thông thường, nếu mặt hàng nào đó
càng bán chạy thì càng có nhiều đồ được “thải” ra. Dựa trên MiGi cũng có thể
lập được một bản đồ số phân bố theo nhu cầu
1.3. Tổng quan về khai phá dữ liệu
Data Mining là một lĩnh vực rộng lớn, nó được chia thành nhiều lĩnh vực nhỏ để giải
quyết nhiều bài toán khác nhau. Trong phạm vi đề tài, người viết luận văn chỉ cố gắng
tìm hiểu để nắm bắt những ý tưởng chính để phục vụ cho bài toán đề xuất. Chính vì thế,
để tập trung cho phần trình bày, trong chường này chỉ xin trình bày về những lý thuyết cơ

(3)
• Luât có độ tin cậy c (confidency) trong tập giao dịch D nếu c% các giao dịch
trong D khi đã chứa X thì cũng chứa Y:
hay (4)
• Một ngưỡng s min được sử dụng để loại bỏ các luật mà tập mục có độ hỗ trợ nhỏ
hơn s min, và một ngưỡng c min dùng để loại bỏ các luật không có đủ độ chắc
chắn c min.
d. Tập mục thường xuyên.
Các tập mục với độ hỗ trợ lớn hơn độ hỗ trợ tối thiểu được gọi là các tập mục
thường xuyên (frequent itemset) hay các tập mục lớn (large itemsets). Tập các k-itemset
thường được ký hiệu là Lk.
Ví dụ: Cơ sở dữ liệu giao dịch
Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 15
Đồ án tốt nghiệp K51
Ứng dụng luật kết hợp trong phân tích dữ liệu của mạng xã hội.
TID Items
1 Bread, Milk
2 Bread, Diaper, Beer, Eggs
3 Milk, Diaper, Beer, Coke
4 Bread, Milk, Diaper, Beer
5 Bread, Milk, Diaper, Coke
Tập {Milk, Bread, Diaper} là tập 3-items, có:
• Độ hỗ trợ tuyệt đối:
• Độ hỗ trợ tương đối:
• Luật kết hợp {Milk, Diaper}=> {Beer}
e. Tập mục đóng, tập mục thường xuyên cực đại
• Tập mục X được gọi là đóng (closed itemset) nếu không tồn tại tập mục Y, sao
cho và . Một tập mục thường xuyên và đóng được gọi là tập mục thường xuyên
đóng (closed frequent itemset).
• Một tập mục X được gọi là tập mục thường xuyên cực đại (maximal frequent

là thường sinh ra rất nhiều tập mục thường xuyên, đặc biệt trong trường hợp ngưỡng
minsup nhỏ. Điều này là bởi vì một tập mục là thường xuyên thì các tập mục bộ phận của
nó (sub-itemset) cũng là thường xuyên. Chẳng hạn như một tập mục thường xuyên có
-kích thước 100 {a
0
, a
1
, …, a
100
} sẽ chứa tập 1-mục, tập 2-mục thường xuyên… Điều
này dẫn đến số tập mục thường xuyên được chứa trong tập mục thường xuyên kích thước
100 là:

Là quá lớn cho máy tính tính toán và lưu trữ.
Zaki[2] đã chứng minh bài toán phát hiện tất cả các tập mục thường xuyên là bài toán
NP-khó. Bởi vì với CSDL có d tập mục, số ứng viên phải là c
d
là hàm mũ.
Đã có nhiều thuật toán và kĩ thuật khác nhau được đề xuất để làm tăng hiệu năng
của hệ thống, trong đó tập trung vào việc cắt tỉa các transaction không phục vụ quá trình
tìm luật kết hợp, cắt bỏ các mục không có ý nghĩa, sử dụng các cấu trúc dữ liệu bảng băm
để lưu trữ nhằm giảm số lần duyệt cơ sở dữ liệu.
b. Khó khăn trong phát hiện luật kết hợp có giá trị
Bên cạnh vấn đề về việc phải tính toán trên quá trình tập mục thường xuyên, một
vấn đề khác trong phát hiện luật kết hợp là có thể bỏ sót những luật có ý nghĩa. Lấy ví dụ
như với cách tiếp cận thông thường, các tập mục có cùng một ngưỡng hỗ trợ. Khi đó, nếu
đặt ngưỡng này đủ lớn để loại đi được nhiều tập mục không thường xuyên, thì có những
tập mục có bản chất ít xuất hiện trong giao dịch sẽ không được phát hiện trong luật. Tuy
nhiên, nhiều khi những luật liên quan tới các mặt hàng ít xuất hiện này lại có giá trị. Cụ
thể như trong CSDL giao dịch, những tập mục liên quan tới các mặt hàng tiêu dùng như

Chương 2: Luật kết hợp
và các kĩ thuật xử lý
Trong chương này sẽ trình bày:
• Thuật toán Apriori
• Thuật toán PHP
• Thuật toán FP Tree
Như đã trình bày ở trên, khó khăn của bài toán tìm luật kết hợp nằm ở việc tìm được
các tập mục thường xuyên. Nó là bước chiếm nhiều hiệu năng nhất của hệ thống. Tất cả
các thuật toán tìm luật kết hợp đều xoay quanh viên tìm kiếm các tập mục thường xuyên
sao cho nhanh nhất và hiệu quả nhất có thể.
Trong phân tích luật kết hợp, có hai loại cơ sở dữ liệu là cơ sở dữ liệu đơn chiều và
cơ sở dữ liệu đa chiều. CSDL đơn chiều chỉ có một chiều. Ví dú như cơ sở dữ liệu giao
dịch, chỉ có chiều “mặt hàng”, trong đó mỗi bản ghi là một giao dịch, ghi nhận các mặt
hàng được mua bởi người dùng trong giao dịch đó. CSDL đa chiều có nhiều chiều, như
bên cạnh chiều mặt hàng thì còn có thêm các chiều thuộc tính khác của mặt hàng. Ví dụ:
màu sắc, nhãn hiệu, giá cả… Dưới là trình bày vắn tắt các giải thuật cơ bản để tìm các tập
mục thường xuyên trong cơ sở dữ liệu đơn chiều.
2.1. Thuật toán Apriori
Giải thuật Apriori là một giải thuật được R.Agrawal và R.Srikant được ra vào năm
1994. Đên nay nó vẫn được coi là một giải thuật nổi tiếng nhất trong việc tìm luật kết
hợp. Tên của giải thuật dựa trên thực tế giải thuật sử dụng kiến thức tiên nghiệm các tập
mục thường xuyên để xác định các tập mục thường xuyên có kích cỡ lớn hơn. Apriori sử
dụng phương pháp search mở rộng theo mức, trong đó tập k-muc (k-itemset) được sử
dụng để tìm các tập mục k+1. Đầu tiên các tập 1 mục (1-itemsets) được tìm thấy bằng
việc quét toàn bộ database, đồng thời xác định độ hỗ trợ tương ứng. Kết quá ta được tập
L1. L1 được sử dụng để tìm tập L2 là các tập 2 mục (2-itemsets), rồi từ L2 tìm được
L3… Quá trình tiếp diễn cho tới khi không tìm được thêm tập mục nào nữa.
Để tăng tính hiệu quả của quá trình search theo cấp độ (wise level search) giải thuật
Priori sử dụng thuộc tính tiên nghiệm, nhằm loại bỏ các tập sinh ra, giúp giảm không gian
search. Thuộc tính tiên nghiệm được định nghĩa như sau:

k
là tập lớn chứa tập
L
k
. Trong đó chứa các các tập k-mục thường xuyên, và cả các tập không phải
thường xuyên. Để xác định, thì phải tiến hành quét database. Nhưng số lượng
tập mục thuộc C
k
là rất lớn. Chi phí quét cho toàn bộ là rất tốn kém. Để giảm
không gian search thì lúc này thuộc tính tiên nghiệm được sử dụng. Bất cứ
tập hợp nào thuộc C
k
mà có tập con k-1 không phải tập mục thường xuyên
đều bị loại bỏ. Từ đó mà không gian search sẽ giảm xuống.
Ví dụ:
Cơ sở dữ liệu gốc:
Hình 2.1 Bảng dữ liệu mẫu cho ví dụ
Quá trình tìm kiếm các tập mục thường xuyên với ngưỡng độ hỗ trợ là 2.
Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 20
Đồ án tốt nghiệp K51
Ứng dụng luật kết hợp trong phân tích dữ liệu của mạng xã hội.
Hình 2.2. Ví dụ về tìm tập mục thường xuyên
Dưới đây là code mô tả thuật toán:
Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 21
Đồ án tốt nghiệp K51
Ứng dụng luật kết hợp trong phân tích dữ liệu của mạng xã hội.
Hình 2.3: Code mẫu thuật toán Apriori
2.2. Thuật toán PHP- Perfect Hashing and Prunning
Giải thuật PHP(Perfect Hashing and Prunning) là giải thuật được phát triển lên từ
giải thuật Apriori nhằm cải thiện hiệu năng. Giải thuật PHP sử dụng các kĩ thuật bảng

Như đã trình bày ở trên, việc phát hiện các tập mục thường xuyên có ý nghĩa quyết
định đối với việc sinh ra các tập luật kết hợp. Đối với giải thuật Apriori thì việc tìm các
tập mục thường xuyên đòi hỏi phải sinh ra các tập ứng viên. Nhưng ngay cả khi đã áp
dụng các kĩ thuật cải tiến thì số tập ứng viên sinh ra vẫn quá lớn. Đó chính là nguyên
nhân chính ảnh hưởng tới hiệu năng của thuật toán.
Nhóm nghiên cứu của Han đã đề xuất sử dụng cấu trúc cây trên ba khía canh sau:
• Thứ nhất: Sử dụng cấu trúc dữ liệu nén truyền thống được gọi là cây mẫu
thường xuyên FP-Tree (Frequent pattern tree) được xây dưng. Nó là sự mở
rộng của cây tiền tố để lưu trữ các thông tin chủ yếu về cây mẫu thường
xuyên. Chỉ những mục thường xuyên mới có các nút trong cây, và nút của
cây được sắp xếp theo ý tưởng nút nào xuất hiện thường xuyên hơn sẽ có
cơ hội hơn để chia sẻ nút đó.
• Thứ hai: Quá trnnh phát hiện tập mục thường xuyên dựa trên FP-Tree
được phát triển bắt đầu từ mẫu thường xuyên kích thước 1 (như một mẫu
hậu tổ khởi đầu), chỉ kiểm tra cơ sở mẫu điều kiện(một cơ sở dữ liệu con
chứa tập các mục thường xuyên cùng xuất hiện với mẫu hậu tổ), xây dựng
FP-Tree điều kiện và thực hiện khai phá đệ quy với cây. Tăng trưởng mẫu
đạt được thông qua thao tác kết nối mẫu hậu tố với mẫu hậu tố mới được
Lê Minh Nghĩa-Lớp Công Nghệ Phần Mềm K51 23
Đồ án tốt nghiệp K51
Ứng dụng luật kết hợp trong phân tích dữ liệu của mạng xã hội.
sinh ra từ cây FP-Tree điều kiện. Thao tác chính ở đây là đếm bộ tích lũy và
điều chính bộ đếm tiền tố, do đó sẽ ít tốn kém hơn so với việc sinh ra các
ứng viên và so khớp mẫu được thực hiện trong thuật toán Apriori.
• Thứ ba: Kỹ thuật tìm kiếm thực hiện dựa trên phân đoạn, chia và trị chứ
không phải là kết hợp sinh ra các tập mục thường xuyên từ dưới lên theo
kiểu Apriori, do đó giảm kích thước cơ sở mẫu điều kiện sinh ra ở mức tiếp
sau của việc tìm kiếm.
2.3.1 Cây mẫu thường xuyên
Định nghĩa: FP-Tree là một cây mẫu thường xuyên có cấu trúc như sau: