...

ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THƠNG

PHAN VĂN TUN

NGHIÊN CỨU THUẬT TỐN CHARM
TRONG KHAI PHÁ TẬP MỤC THƯỜNG XUYÊN ĐÓNG

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Thái Ngun - 2011

Số hóa bởi Trung tâm Học liệu – ĐHTN




ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THƠNG

PHAN VĂN TUN

NGHIÊN CỨU THUẬT TỐN CHARM
TRONG KHAI PHÁ TẬP MỤC THƯỜNG XUYÊN ĐÓNG

CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH
MÃ SỐ: 60. 48. 01

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

NGƯỜI HƯỚNG DẪN KHOA HỌC
TS. NGUYỄN HUY ĐỨC

Thái Nguyên - 2011

Số hóa bởi Trung tâm Học liệu – ĐHTN




LỜI CẢM ƠN
Để hồn thành luận văn này tơi đã nhận được sự giúp đỡ tận tình của các
thầy cơ Trường Đại học Công nghệ Thông tin và Truyền thông – Đại học Thái
Nguyên, các thầy cô Viện công nghệ thông tin – Viện Khoa học và Công nghệ
Việt Nam, các anh chị lớp Cao học K8 - khóa 2009-2011. Đặc biệt là TS. Nguyễn
Huy Đức, người thầy trực tiếp hướng dẫn tơi trong q trình nghiên cứu và thực
hiện luận văn.
Nhân dịp này tôi xin được bày tỏ lời cảm ơn tới tất cả các thầy cô giáo
Viện Công nghệ thông tin – Viện Khoa học và Công nghệ Việt Nam, các thầy cô
ở Trường đại học Công nghệ Thông tin và Truyền thông – Đại học Thái Nguyên
đã giảng dạy và tạo mọi điều kiện thuận lợi giúp đỡ tơi trong q trình học tập,
nghiên cứu.
Tơi xin trân trọng cảm ơn TS. Nguyễn Huy Đức – Khoa Thông tin - Máy
tính, Trường Cao đẳng Sư phạm Trung ương, người thầy trực tiếp hướng dẫn,
đưa ra ý tưởng, định hướng, đóng góp các ý kiến chun mơn và tận tình giúp đỡ
tơi trong suốt q trình nghiên cứu và thực hiện luận văn này.
Tôi xin cảm ơn các bạn bè đồng nghiệp và gia đình đã giúp đỡ, đóng góp ý
kiến và động viên tơi trong suốt qua trình học, q trình nghiên cứu và hồn
thành luận văn này.


Tác giả
Phan Văn Tuyên

Số hóa bởi Trung tâm Học liệu – ĐHTN




LỜI CAM ĐOAN
Tơi xin cam đoan tồn bộ nội dung trong Luận văn hoàn toàn theo đúng
nội dung đề cương cũng như nội dung mà giáo viên hướng dẫn giao cho. Nội
dung luận văn, các phần trích lục các tài liệu hồn tồn chính xác. Nếu có sai sót
tơi hồn tồn chịu trách nhiệm.
Tác giả luận văn

Phan Văn Tun

Số hóa bởi Trung tâm Học liệu – ĐHTN




I

MỤC LỤC
Trang
Lời cảm ơn
Lời cam đoan
MỤC LỤC ..............................................................................................................................I

DANH MỤC CÁC KÝ HIỆU VÀ CÁC CHỮ VIẾT TẮT ................................................. III
DANH MỤC CÁC BẢNG .................................................................................................. IV
DANH MỤC HÌNH VẼ ....................................................................................................... V
MỞ ĐẦU ............................................................................................................................... 1
CHƢƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU ...................................................... 3
1.1. KHÁM PHÁ TRI THỨC VÀ KHAI PHÁ DỮ LIỆU ............................................... 3
1.2. KIẾN TRÚC CỦA HỆ THỐNG KHAI PHÁ DỮ LIỆU ........................................... 5
1.3. QUÁ TRÌNH KHAI PHÁ DỮ LIỆU ......................................................................... 6
1.4. CÁC KỸ THUẬT KHAI PHÁ DỮ LIỆU ................................................................. 8
1.4.1.Phân lớp dữ liệu ................................................................................................... 8
1.4.2.Phân cụm dữ liệu ................................................................................................. 8
1.4.3.Khai phá luật kết hợp........................................................................................... 8
1.4.4.Hồi quy ................................................................................................................ 9
1.4.5.Giải thuật di truyền .............................................................................................. 9
1.4.6.Mạng nơron ......................................................................................................... 9
1.4.7.Cây quyết định. .................................................................................................... 9
1.5. MỘT SỐ ỨNG DỤNG CỦA KHAI PHÁ DỮ LIỆU .............................................. 10
1.6. KHAI PHÁ TẬP MỤC THƢỜNG XUYÊN ........................................................... 11
1.6.1. Cơ sở dữ liệu giao tác ....................................................................................... 11
1.6.2. Tập mục thƣờng xuyên ..................................................................................... 13
1.6.3. Các cách tiếp cận khai phá tập mục thƣờng xuyên .......................................... 14
1.6.4. Một số thuật toán điển hình tìm tập mục thƣờng xuyên ................................... 16
1.6.4.1. Thuật toán Apriori ......................................................................................... 16
1.6.4.2. Thuật toán FP-Growth ................................................................................... 20
1.7. KẾT LUẬN CHƢƠNG 1......................................................................................... 28
CHƢƠNG 2: KHAI PHÁ TẬP MỤC THƢỜNG XUN ĐĨNG .................................... 29
2.1. CƠ SỞ TỐN HỌC ................................................................................................ 29
Số hóa bởi Trung tâm Học liệu – ĐHTN





II

2.1.1. Ánh xạ đóng ..................................................................................................... 29
2.1.2. Tập đóng ........................................................................................................... 30
2.1.3. Kết nối Galois ................................................................................................... 30
2.1.4. Bao đóng của tập mục dữ liệu .......................................................................... 31
2.2. TẬP MỤC THƢỜNG XUYÊN ĐÓNG .................................................................. 32
2.2.1. Định nghĩa ....................................................................................................... 32
2.2.2. Các tính chất của tập mục thƣờng xun đóng................................................. 32
2.3. THUẬT TỐN CHARM ........................................................................................ 32
2.3.1. Giới thiệu thuật tốn CHARM ......................................................................... 32
2.3.2. Cây tìm kiếm và lớp tƣơng đƣơng .................................................................... 33
2.3.3. Các tính chất cơ bản của cặp tập mục - tập định danh: .................................... 34
2.3.4. Thiết kế thuật tốn ............................................................................................ 35
2.3.5. Ví dụ minh họa ................................................................................................. 37
2.3.6. Đánh giá thuật toán ........................................................................................... 39
2.4. KẾT LUẬN CHƢƠNG 2......................................................................................... 39
CHƢƠNG 3: CÀI ĐẶT THỰC NGHIỆM .......................................................................... 41
3.1. XÂY DỰNG CHƢƠNG TRÌNH ............................................................................. 41
3.2. GIAO DIỆN CỦA CHƢƠNG TRÌNH .................................................................... 43
3.3. KẾT QUẢ THỰC NGHIỆM ................................................................................... 44
3.4. NHẬN XÉT ............................................................................................................. 47
KẾT LUẬN.......................................................................................................................... 48
TÀI LIỆU THAM KHẢO ................................................................................................... 49
PHỤ LỤC ............................................................................................................................ 51

Số hóa bởi Trung tâm Học liệu – ĐHTN





III

DANH MỤC CÁC KÝ HIỆU VÀ CÁC CHỮ VIẾT TẮT

Diễn giải

Ký hiệu
Ck

Tập các k tập mục ứng viên

BFS

Breadth First Search

CSDL

Cơ sở dữ liệu

CHARM

Closed Asociation RuleMning

DB

Cơ sở dữ liệu giao tác


DFS

Depth First Search

FP -growth

Frequent -Pattern Growth

FP -tree

Frequent pattern tree

IT-tree

Itemset-Tidset tree

I

Tập các mục dữ liệu

k-itemset

Tập mục gồm k mục

KPDL

Khai phá dữ liệu

Minsup


Ngƣỡng hỗ trợ tối thiểu

Lk

Tập các k-tập mục thƣờng xuyên

Supp

Độ hỗ trợ (support)

TID

Định danh của giao tác

T

Giao tác (transaction)

Số hóa bởi Trung tâm Học liệu – ĐHTN




IV

DANH MỤC CÁC BẢNG
Bảng 1.1: Biểu diễn ngang của cơ sở dữ liệu giao tác .............................................11
Bảng 1.2: Biểu diễn dọc của cơ sở dữ liệu giao tác .................................................12
Bảng 1.3: Ma trận giao tác của cơ sở dữ liệu cho ở bảng 1.1 ..................................12
Bảng 1.4: Cơ sở dữ liệu giao tác minh họa thực hiện thuật toán Apriori.................19

Bảng 1.5: CSDL giao tác minh hoạ cho thuật toán FP- growth. ..............................22
Bảng 2.1: a) CSDL giao tác biểu diễn ngang ...........................................................31
Bảng 2.1: b) CSDL giao tác biểu diễn dọc ...............................................................31
Bảng 3.1: Đặc điểm các tệp dữ liệu thử nghiệm.......................................................41
Bảng 3.2: Kết quả thực nghiệm trên tệp dữ liệu Input1.txt ......................................46

Số hóa bởi Trung tâm Học liệu – ĐHTN




V

DANH MỤC HÌNH VẼ
Hình 1.1: Qúa trình phát hiện tri thức ........................................................................4
Hình 1.2: Kiến trúc của một hệ thống khai phá dữ liệu .............................................5
Hình 1.3. Quá trình KPDL .........................................................................................7
Hình 1.4: Phân loại các thuật toán khai phá tập mục thƣờng xuyên . .......................15
Hình 1.5: Cây FP-tree đƣợc xây dựng dần khi thêm các giao tác t1, t2, t3. ............23
Hình 1.6: Cây FP-tree của CSDL DB trong bảng 1.5 .............................................23
Hình 1.7 : FP-tree phụ thuộc của m ..........................................................................26
Hình 1.8 : Các FP-tree phụ thuộc của am, cm và cam .............................................27
Hình 2.1: Kết nối Galois ...........................................................................................30
Hình 2.2. Cây IT-tree tìm tập thƣờng xun đóng thoả ngƣỡng minsup =50% ......38
Hình 3.1: CSDL giao tác đã mã hóa chuẩn bị cho khai phá ....................................42
Hình 3.2: Giao diện chƣơng trình thực nghiệm sau khi khởi động ..........................43
Hình 3.3: Kết quả tìm tập mục thƣờng xuyên với ngƣỡng minsup = 10% ..............44
Hình 3.4: Kết quả tìm tập mục thƣờng xuyên đóng với ngƣỡng minsup = 10% .....45
Hình 3.5: So sánh thời gian thực hiện khai phá trên tệp Input1.txt .........................46
Hình 3.6: So sánh số tập mục kết quả khai phá trên tệp Input1.txt ..........................47


Số hóa bởi Trung tâm Học liệu – ĐHTN




1

MỞ ĐẦU
Chúng ta đang ở "thời đại thông tin", một thời đại đƣợc định hình bởi
một ngành khoa học cơng nghệ kỹ thuật rất trẻ phát triển nhƣ vũ bão, ảnh
hƣởng vô cùng sâu sắc và mãi mãi đến cuộc sống chúng ta, đó là ngành cơng
nghiệp "cơng nghệ thơng tin". Trong kinh doanh ai có nhiều thơng tin hơn
ngƣời đó sẽ làm chủ thị trƣờng, trong nghiên cứu ai càng nhiều thơng tin thì
cơ hội thành cơng của ngƣời đó càng lớn. Vì vậy việc thu thập thơng tin có
một vai trị đặc biệt quan trọng trong cơng việc và trong cuộc sống.
Khai phá dữ liệu và khám phá tri thức (Data Mining and Knowledge
Discovery) là một lĩnh vực quan trọng của ngành công nghệ thông tin. Đây là
một hƣớng nghiên cứu tập trung đƣợc hùng hậu các nhà khoa học trên thế
giới tham gia. Hội nghị quốc tế về khai phá dữ liệu và khám phá tri thức
đƣợc tổ chức hàng năm, luân phiên tại nhiều nƣớc trên thế giới, mỗi hội thảo
có hàng trăm nhà khoa học hàng đầu tham gia.
Tại Việt Nam, khai phá dữ liệu đã đƣợc các nhóm nghiên cứu tại Viện
Cơng nghệ Thơng tin thuộc Viện Khoa học và Công nghệ Việt Nam, các
nhóm nghiên cứu tại một số trƣờng đại học nhƣ Đại học Quốc gia Hà Nội,
Đại học Bách Khoa Hà Nội, Đại học Quốc gia thành phố Hồ Chí Minh thực
hiện và đã có nhiều kết quả đƣợc cơng bố.
Một trong các nội dung cơ bản nhất trong khai phá dữ liệu là bài toán
khai phá luật kết hợp. Khai phá luật kết hợp gồm hai bƣớc: Bƣớc một, tìm tất
cả các tập mục thờng xuyên. Bƣớc hai, dựa vào các tập mục thƣờng xuyên

tìm các luật kết hợp. Bƣớc thứ nhất địi hỏi sự tính tốn lớn, bƣớc thứ hai địi
hỏi tính tốn ít hơn, song gặp phải một vấn đề là: có thể sinh ra quá nhiều
luật, vƣợt khỏi sự kiểm soát của ngƣời khai phá hoặc ngƣời dùng, trong đó có
nhiều luật khơng cần thiết. Để giải quyết vấn đề đó, trong bƣớc thứ nhất,
khơng cần thiết phải khai phá tất cả các tập mục thƣờng xuyên mà chỉ cần

Số hóa bởi Trung tâm Học liệu – ĐHTN




2

khai phá các tập mục thƣờng xuyên đóng. Khai phá luật kết hợp dựa trên tập
mục thƣờng xuyên đóng cho hiệu quả hơn hẳn các cách khai phá khác. Nó
đảm bảo khơng tìm các tập mục thƣờng xun khơng cần thiết và cũng không
sinh ra các luật dƣ thừa.
Với ý nghĩa đó và với mục đích tìm hiểu về bài tốn tìm tập mục
thƣờng xun trong cơ sở dữ liệu lớn, em đã quyết định lựa chọn đề tài luận
văn: "NGHIÊN CỨU THUẬT TOÁN CHARM TRONG KHAI PHÁ TẬP MỤC
THƢỜNG XUYÊN ĐÓNG "

Nội dung luận văn gồm 3 chƣơng:
Chương 1: Tổng quan về khai phá dữ liệu.
Chương 2: Khai phá tập mục thƣờng xuyên đóng.
Chương 3: Cài đặt thực nghiệm.

Số hóa bởi Trung tâm Học liệu – ĐHTN





3

CHƢƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU
Trong thời đại ngày nay, với sự phát triển vƣợt bật của cơng nghệ thơng
tin, các hệ thống thơng tin có thể lƣu trữ một khối lƣợng lớn dữ liệu về hoạt
động hàng ngày của chúng. Từ khối dữ liệu này, các kỹ thuật trong Khai Phá
Dữ Liệu (KPDL) và máy học có thể dùng để trích xuất những thơng tin hữu
ích mà chúng ta chƣa biết. Các tri thức vừa học đƣợc có thể vận dụng để cải
thiện hiệu quả hoạt động của hệ thống thông tin ban đầu.
1.1. KHÁM PHÁ TRI THỨC VÀ KHAI PHÁ DỮ LIỆU

KPDL là việc rút trích tri thức một cách tự động và hiệu quả từ một khối
dữ liệu lớn. Tri thức đó thƣờng ở dạng các mẫu có tính chất khơng tầm
thƣờng, khơng tƣờng minh (ẩn), chƣa đƣợc biết đến và có tiềm năng mang lại
lợi ích. Có một số nhà nghiên cứu cịn gọi KPDL là phát hiện tri thức
trong cơ sở dữ liệu (Knowledge Discovery in Database - KDD). Ở đây
chúng ta có thể coi KPDL là cốt lõi của q trình phát hiện tri thức. Quá trình
phát hiện tri thức gồm các bƣớc [5], [9]:
Bƣớc 1: Trích chọn dữ liệu (data selection): 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).
Bƣớc 2: Tiền xử lý dữ liệu (data preprocessing): là bƣớc làm sạch dữ
liệu (xử lý 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 các phƣơng pháp thu gọn dữ liệu, histograms, lấy
mẫu,. v. v), rời rạc hoá dữ liệu (dựa vào histograms, entropy, 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
hoá.
Bƣớc 3: Biến đổi dữ liệu (data transformation): là bƣớc chuẩn hoá 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 thác ở bƣớc sau.
Số hóa bởi Trung tâm Học liệu – ĐHTN




4

Bƣớc 4: Khai phá dữ liệu (data mining): Đây là bƣớc quan trọng và
tốn nhiều thời gian nhất của quá trình khám phá tri thức, áp dụng các kỹ thuật
khai phá (phần lớn là các kỹ thuật của machine learning) để khai phá, trích
chọn đƣợc các mẫu (pattern) thơng tin, các mối liên hệ đặc biệt trong dữ liệu.
Bƣớc 5: Đánh giá và biểu diễn tri thức (knowledge representation &
evaluation): Dùng các kỹ thuật hiển thị dữ liệu để trình bày các mẫu thông
tin (tri thức) và mối liên hệ đặc biệt trong dữ liệu đã đƣợc khai thác ở bƣớc
trên biểu diễn theo 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.
Trong giai đoạn khai phá dữ liệu, có thể cần sự tƣơng tác của ngƣời
dùng để điều chỉnh và rút ra các tri thức cần thiết nhất. Các tri thức nhận đƣợc
cũng có thể đƣợc lƣu và sử dụng lại.
Các Tri thức
Các mẫu

Dữ liệu đã sạch
Dữ liệu đã chọn
5.Đánh giá và biểu diễn tri thức
knowledge representation
& evaluation


4.Khai phá dữ liệu
data mining

Kho dữ
liệu

3.Biến đổi dữ liệu
data transformation
2. Tiền xử lý dữ liệu
data preprocessing

1. Trích chọn dữ liệu
data selection

Hình 1.1: Qúa trình phát hiện tri thức

Số hóa bởi Trung tâm Học liệu – ĐHTN




5

Việc KPDL có thể đƣợc tiến hành trên một lƣợng lớn dữ liệu có
trong các CSDL, các kho dữ liệu hoặc trong các loại lƣu trữ thông tin khác.
Các mẫu đáng quan tâm có thể đƣợc đƣa đến ngƣời dùng hoặc đƣợc lƣu
trữ trong một cơ sở tri thức.
1.2. KIẾN TRÚC CỦA HỆ THỐNG KHAI PHÁ DỮ LIỆU


Kiến trúc của một hệ thống KPDL điển hình có thể có các thành
phần nhƣ hình 1.2 [5], [9].
- CSDL, kho dữ liệu hoặc các lƣu trữ thông tin khác (Databases,
Data warehouse,..): Đây là một hay một tập các CSDL, các kho dữ liệu, các
trang tính hay các dạng lƣu trữ thơng tin khác. Các kỹ thuật làm sạch dữ liệu
và tích hợp dữ liệu có thể đƣợc thực hiện trên những dữ liệu này.

( Graphical user interface)

Giao diện đồ họa cho
ngƣời dùng

( Pattern evaluation)

(Data mining engine)

Đánh giá mẫu
Cơ sở
tri thức

Máy khai phá dữ liệu

(Knowledge-base)
Máy chủ CSDL
hay kho dữ liệu

(Database or Warehouse Server)

Làm sạch ; tích hợp dữ liệu; lọc


Cơ sở dữ liệu

Kho dữ liệu

Các lƣu trữ
thơng tin khác

Hình 1.2: Kiến trúc của một hệ thống khai phá dữ liệu
Số hóa bởi Trung tâm Học liệu – ĐHTN




6

- Máy chủ CSDL hay máy chủ kho dữ liệu (Database or warehouse
server): Máy chủ này có trách nhiệm lấy những dữ liệu thích hợp dựa trên
các yêu cầu khai phá của ngƣời dùng.
- Cơ sở tri thức (Knowledge base): Đây là miền tri thức đƣợc dùng để
hƣớng dẫn việc tìm kiếm hay đánh giá độ quan trọng của các hình mẫu kết
quả.
- Máy KPDL (Data mining engine): Một hệ thống KPDL cần phải có
một tập các modun chức năng để thực hiện cơng việc nhƣ: đặc trƣng hố, kết
hợp, phân lớp, phân cụm, phân tích sự tiến hố.
- Modun đánh giá mẫu (Pattern evaluation): Bộ phận này tƣơng tác
với các modun KPDL để duyệt tìm các mẫu đáng đƣợc quan tâm. Nó có thể
dùng các ngƣỡng về độ quan tâm để lọc mẫu đã khám phá đƣợc. Cũng có thể
modun đánh giá mẫu đƣợc tích hợp vào modun khai phá, tuỳ theo sự cài đặt
của phƣơng pháp khai phá đƣợc dùng.
- Giao diện đồ họa ngƣời dùng (Graphical user interface): Bộ phận

này cho phép ngƣời dùng giao tiếp với hệ thống KPDL. Ngồi ra, bộ phận
này cịn cho phép ngƣời dùng xem các lƣợc đồ CSDL, lƣợc đồ kho dữ liệu
(hay các cấu trúc dữ liệu), các đánh giá mẫu và hiển thị các mẫu trong khuôn
dạng khác nhau.
1.3. QUÁ TRÌNH KHAI PHÁ DỮ LIỆU

Các giải thuật khai phá dữ liệu thƣờng đƣợc miêu tả nhƣ những chƣơng
trình hoạt động trực tiếp trên tệp dữ liệu. Với các phƣơng pháp học máy và
thống kê trƣớc đây, thƣờng thì bƣớc đầu tiên là các giải thuật nạp toàn bộ tệp
dữ liệu vào trong bộ nhớ. Khi chuyển sang các ứng dụng công nghiệp liên
quan đến việc khai phá các kho dữ liệu lớn, mơ hình này khơng thể đáp ứng

Số hóa bởi Trung tâm Học liệu – ĐHTN




7

đƣợc. Khơng chỉ bởi vì nó khơng thể nạp hết dữ liệu vào trong bộ nhớ mà cịn
vì khó có thể chiết xuất dữ liệu ra các tệp đơn giản để phân tích đƣợc.
Q trình khai phá dữ liệu đƣợc th hin bi mụ hỡnh sau [3]:

Thống
kê tóm
tắt
Xác định
nhiệm vụ

Xác định

dữ liệu
liên quan

Thu thập
và tiền
xử lý DL

Giải
thuật
khai phá
DL

Mẫu

Dữ
liệu
trực
tiếp

Hỡnh 1.3. Quỏ trình KPDL
+ Xác định nhiệm vụ: Xác định chính xác vấn đề cần giải quyết.
+ Xác định các dữ liệu liên quan dùng để xây dựng giải pháp.
+ Thu thập các dữ liệu có liên quan và xử lý chúng thành dạng sao cho
giải thuật khai phá dữ liệu có thể hiểu đƣợc. Ở đây có thể gặp một số vấn đề:
dữ liệu phải đƣợc sao ra nhiều bản (nếu đƣợc chiết suất vào các tệp), quản lý
tập các tệp dữ liệu, phải lặp đi lặp lại nhiều lần toàn bộ q trình (nếu mơ hình
dữ liệu thay đổi v.v...).
+ Chọn thuật tốn khai phá dữ liệu thích hợp và thực hiện việc khai phá
dữ liệu: nhằm tìm đƣợc các mẫu (pattern) có ý nghĩa dƣới dạng biểu diễn
tƣơng ứng với các ý nghĩa đó.


Số hóa bởi Trung tâm Học liệu – ĐHTN




8

1.4. CÁC KỸ THUẬT KHAI PHÁ DỮ LIỆU

Có nhiều kỹ thuật khác nhau đƣợc sử dụng để KPDL nhằm thực hiện
hai chức năng mơ tả và dự đốn. Với mỗi chức năng thì có các kỹ thuật
KPDL tƣơng ứng với nó.
- Kỹ thuật KPDL mơ tả: có nhiệm vụ mơ tả các tính chất hoặc các đặc
tính chung của dữ liệu trong CSDL hiện có. Một số kỹ thuật khai phá
trong nhóm này là: phân cụm dữ liệu (Clustering), tổng hợp
(Summarisation), trực quan hố (Visualization), phân tích sự phát triển
và độ lệch (Evolution and deviation analyst),….
- Kỹ thuật KPDL dự đốn: có nhiệm vụ đƣa ra các dự đốn dựa vào việc
suy diễn trên cơ sở dữ liệu hiện thời. Một số kỹ thuật khai phá trong
nhóm này là: phân lớp (Classification), hồi quy (Regression), cây quyết
định (Decision tree), thống kê (statictics), mạng nơron (neural network),
luật kết hợp (association rules),….
Một số kỹ thuật phổ biến thƣờng đƣợc sử dụng để KPDL hiện nay là :
1.4.1. Phân lớp dữ liệu
Mục tiêu của phân lớp dữ liệu là dự đoán nhãn lớp cho các mẫu dữ liệu.
Quá trình gồm hai bƣớc: xây dựng mơ hình, sử dụng mơ hình để phân lớp dữ
liệu. Mơ hình đƣợc sử dụng để dự đốn nhãn lớp khi mà độ chính xác của mơ
hình chấp nhận đƣợc.
1.4.2. Phân cụm dữ liệu

Mục tiêu của phân cụm dữ liệu là nhóm các đối tƣợng tƣơng tự nhau
trong tập dữ liệu vào các cụm, sao cho những đối tƣợng thuộc cùng một lớp là
tƣơng đồng nhau.
1.4.3. Khai phá luật kết hợp
Mục tiêu của phƣơng pháp này là phát hiện và đƣa ra mối liên hệ giữa các
giá trị dữ liệu trong cơ sở dữ liệu. Đầu ra của giải thuật luật kết hợp là tập luật
kết hợp tìm đƣợc. Phƣơng pháp khai phá luật kết hợp gồm có hai bƣớc:

Số hóa bởi Trung tâm Học liệu – ĐHTN




9

-

Bƣớc 1: Tìm ra tất cả các tập mục thƣờng xuyên. Một tập mục thƣờng

xuyên đƣợc xác định thông qua việc tính độ hỗ trợ và thoả mãn độ hỗ trợ
cực tiểu.
-

Bƣớc 2: Sinh ra các luật kết hợp mạnh từ tập mục thƣờng xuyên, luật

phải thoả mãn độ hỗ trợ và độ tin cậy cực tiểu.
1.4.4. Hồi quy
Phƣơng pháp hồi quy tƣơng tự nhƣ là phân lớp dữ liệu. Nhƣng khác ở
chỗ nó dùng để dự đốn các giá trị liên tục còn phân lớp dữ liệu dùng để dự
đoán các giá trị rời rạc.

1.4.5. Giải thuật di truyền
Là q trình mơ phỏng theo tiến hố của tự nhiên. Ý tƣởng chính của
giải thuật là dựa vào quy luật di truyền trong biến đổi, chọn lọc tự nhiên và
tiến hoá trong sinh học.
1.4.6. Mạng nơron
Đây là một trong những kỹ thuật KPDL đƣợc ứng dụng phổ biến hiện
nay. Kỹ thuật này phát triển dựa trên một nền tảng toán học vững vàng, khả
năng huấn luyện trong kỹ thuật này dựa trên mơ hình thần kinh trung ƣơng
của con ngƣời.
Kết quả mà mạng nơron học đƣợc có khả năng tạo ra các mơ hình dự báo,
dự đốn với độ chính xác và độ tin cậy cao. Nó có khả năng phát hiện ra đƣợc
các xu hƣớng phức tạp mà kỹ thuật thơng thƣờng khác khó có thể phát hiện ra
đƣợc. Tuy nhiên phƣơng pháp mạng nơ ron rất phức tạp và q trình tiến
hành nó gặp rất nhiều khó khăn: đòi hỏi mất nhiều thời gian, nhiều dữ liệu,
nhiều lần kiểm tra thử nghiệm.
1.4.7. Cây quyết định.
Kỹ thuật cây quyết định là một công cụ mạnh và hiệu quả trong việc
phân lớp và dự báo. Các đối tƣợng dữ liệu đƣợc phân thành các lớp. Các giá
trị của đối tƣợng dữ liệu chƣa biết sẽ đƣợc dự đoán, dự báo. Tri thức đƣợc rút
ra trong kỹ thuật này thƣờng đƣợc mô tả dƣới dạng tƣờng minh, đơn giản,
trực quan, dễ hiểu đối với ngƣời sử dụng.
Số hóa bởi Trung tâm Học liệu – ĐHTN




10

1.5. MỘT SỐ ỨNG DỤNG CỦA KHAI PHÁ DỮ LIỆU


KPDL đƣợc vận dụng trong nhiều lĩnh vực khác nhau nhằm khai thác
nguồn dữ liệu phong phú đƣợc lƣu trữ trong các hệ thống thông tin. Tuỳ theo
bản chất của từng lĩnh vực, việc vận dụng KPDL có những cách tiếp cận khác
nhau.
KPDL đƣợc vận dụng có hiệu quả để giải quyết các bài tốn phức tạp
trong những ngành địi hỏi kỹ thuật cao nhƣ: tìm kiếm mỏ dầu từ ảnh viễn
thám, xác định vùng gãy trong ảnh địa chất để dự đốn thiên tai, cảnh báo
hỏng hóc trong các hệ thống sản xuất.
Phân nhóm và dự đốn là những kỹ thuật rất cần thiết cho việc quy hoạch
và phát triển hệ thống quản lý và sản xuất trong thực tế nhƣ: dự đốn tái sử
dụng điện năng cho các cơng ty cung cấp điện, lƣu lƣợng viễn thông cho các
công ty điện thoại, mức độ tiêu thụ sản phẩm cho các nhà sản xuất, giá trị của
sản phẩm trên thị trƣờng cho các cơng ty tài chính hay phân nhóm khách hàng
tiềm năng.
Ngồi ra KPDL cịn đƣợc áp dụng trong việc giải quyết các vấn đề xã
hội nhƣ: phát hiện tội phạm hay tăng cƣờng an ninh xã hội và mang lại những
hiệu quả thiết thực cho các hoạt động trong đời sống hàng ngày.
Một số ứng dụng cụ thể nhƣ sau [5], [9] :
- KPDL đƣợc sử dụng để phân tích dữ liệu, hỗ trợ ra quyết định.
- Trong sinh học: nó dùng để tìm kiếm, so sánh các hệ gen và thơng tin di
truyền, tìm mối liên hệ giữa các hệ gen và chuẩn đoán một số bệnh di truyền.
- Trong y học: KPDL giúp tìm ra mối liên hệ giữa các triệu chứng, chuẩn
đốn bệnh.
- Tài chính và thị trƣờng chứng khốn: KPDL dùng để phân tích tình hình
tài chính, phân tích đầu tƣ, phân tích cổ phiếu.
- Khai thác dữ liệu web.

Số hóa bởi Trung tâm Học liệu – ĐHTN





11

- Trong thông tin kỹ thuật: KPDL dùng để phân tích các sai hỏng, điều
khiển và lập lịch trình.
- Trong thơng tin thƣơng mại: dùng để phân tích dữ liệu ngƣời dùng, phân
tích dữ liệu marketing, phân tích đầu tƣ, phát hiện các gian lận.
-

Trong công nghiệp viễn thông: Phân tích nhu cầu và phân tích các mẫu

gian lận và xác định các mẫu khác thƣờng.
1.6. KHAI PHÁ TẬP MỤC THƢỜNG XUYÊN [3], [6], [16]

1.6.1. Cơ sở dữ liệu giao tác
Định nghĩa:
Cho tập các mục (item) I = {x1, x2,...,xn}. Một giao tác (transaction) T
là một tập con của I, T  I. Cơ sở dữ liệu giao tác là một tập các giao tác DB
= {T1, T2,...,Tm). Mỗi giao tác đƣợc gán một định danh TID. Một tập mục con
X  I, gồm k mục phân biệt đƣợc gọi là một k-tập mục. Giao tác T gọi là
chứa tập mục X nếu X  T.
Biểu diễn cơ sở dữ liệu giao tác:
Cơ sở dữ liệu giao tác thƣờng đƣợc biểu diễn ở dạng biểu diễn ngang,
biểu diễn dọc và biểu diễn bởi ma trận giao tác.
Biểu diễn ngang: Mỗi cơ sở dữ liệu là một danh sách các giao tác.
Mỗi giao tác có một định danh giao tác (TID) và một danh sách những mục
dữ liệu trong giao tác đó.
Bảng 1.1:Biểu diễn ngang của cơ sở dữ liệu giao tác
Định danh giao tác

T1
T2
T3
T4
T5
T6
Số hóa bởi Trung tâm Học liệu – ĐHTN

Các mục dữ liệu
A, B, C, E
C, D, E
A, B, C, E
A, C, D, E
A, B, C, D, E
B, C, D




12

Biểu diễn dọc: Trong cách biểu diễn dọc, một cơ sở dữ liệu là một
danh sách những mục dữ liệu, với mỗi mục dữ liệu có một danh sách tất cả
các định danh của các giao tác chứa mục dữ liệu này.
Bảng 1.2 Biểu diễn dọc của cơ sở dữ liệu giao tác
Mục dữ liệu

Định danh các giao tác

A


T1, T3, T4, T5

B

T1, T3, T5, T6

C

T1, T2, T3, T4, T5, T6

D

T2, T4, T5, T6

E

T1, T2, T3, T4, T5

Ma trận giao tác: Cơ sở dữ liệu giao tác DB = {T1, T2,...,Tm) trên tập
các mục (item) I = (x1, x2, ..., xn}. Đƣợc biểu diễn bởi ma trận nhị phân,
M = (mij)mxn ở đó:

1 khi xj  Ti
mij  
0 khi xj  Ti

Bảng 1.3 Ma trận giao tác của cơ sở dữ liệu cho ở bảng 1.1
A


B

C

D

E

T1

1

1

1

0

1

T2

0

0

1

1


1

T3

1

1

1

0

1

T4

1

0

1

1

1

T5

1


1

1

1

1

T6

0

1

1

1

0

Số hóa bởi Trung tâm Học liệu – ĐHTN




13

1.6.2. Tập mục thƣờng xuyên [10]
Độ hỗ trợ (support):
Cho tập mục X  I. Ta gọi độ hỗ trợ (Support) của X trong cơ sở dữ

liệu giao tác DB, ký hiệu supp(X), là tỷ lệ phần trăm các giao tác chứa X trên
T{T  DB | T  X}
tổng số các giao tác trong DB, tức là: supp(X) 
DB
Ta có: 0 ≤ supp(X) ≤ 1 với mọi tập mục X  I.
Với cơ sở dữ liệu cho ở bảng 1.1 ta có:
Supp(A) = 60%, Supp(CA) = 60%, Supp(CE) = 80%
Định nghĩa tập mục thường xuyên:
Cho tập mục X  I và ngƣỡng hỗ trợ tối thiểu (minimum support)
minsup  [0, 1] (đƣợc xác định trƣớc bởi ngƣời sử dụng). X đƣợc gọi là tập
mục thƣờng xuyên (frequent itemset hoặc large itemset) với độ hỗ trợ tối
thiểu minsup nếu supp(X)  minsup, ngƣợc lại X gọi là tập mục không
thƣờng xuyên.
Với cơ sở dữ liệu giao tác cho ở bảng 1.1 ta có:
 A, B, D, CA, CB, CD, EA, EB, ED: là các tập mục thƣờng xuyên theo
ngƣỡng minsup = 60%.
 C, E, CE: là các tập mục thƣờng xuyên theo ngƣỡng minsup = 80%.
Tính chất của tập mục thƣờng xuyên
Tính chất 1
Với hai tập mục thƣờng xuyên X, Y với X  Y thì supp(X)  supp(Y)
Tính chất 2
Mọi tập con của một tập mục thƣờng xuyên đều là tập mục thƣờng
xuyên.
Nghĩa là, X là tập mục thƣờng xuyên và Y  X thì supp(Y)  supp(X)
 minSupp.
Số hóa bởi Trung tâm Học liệu – ĐHTN





14

Tính chất 3
Mọi tập cha của một tập mục khơng thƣờng xuyên là tập mục không
thƣờng xuyên.
Nghĩa là: X là tập khơng thƣờng xun và Y  X thì supp(Y) 
supp(X)  minSupp.
1.6.3. Các cách tiếp cận khai phá tập mục thƣờng xuyên
Các nghiên cứu về khai phá tập mục thƣờng xun tập trung vào tìm
các thuật tốn mới hoặc đề xuất giải pháp nâng cao hiệu quả các thuật tốn đã
có. Phần này sẽ trình bày khái qt các kỹ thuật chính để khai phá tập mục
thƣờng xun.
Bài tốn khai phá tập mục thƣờng xuyên có thể chia thành hai bài tốn
nhỏ: tìm các tập mục ứng viên và tìm các tập mục thƣờng xuyên. Tập mục
ứng viên là tập mục mà ta hy vọng nó là tập mục thƣờng xun, phải tính độ
hỗ trợ của nó để kiểm tra. Tập mục thƣờng xuyên là tập mục có độ hỗ trợ lớn
hơn hoặc bằng ngƣỡng hỗ trợ tối thiểu cho trƣớc. Đã có rất nhiều thuật tốn
tìm tập mục thƣờng xun đƣợc cơng bố, ta có thể phân chúng theo hai tiêu
chí sau :
- Phƣơng pháp duyệt qua khơng gian tìm kiếm.
- Phƣơng pháp xác định độ hỗ trợ của tập mục.
Phƣơng pháp duyệt qua khơng gian tìm kiếm đƣợc phân làm hai cách :
duyệt theo chiều rộng (Breadth First Search – BFS) và duyệt theo chiều sâu
(Depth First Search – DFS).
Duyệt theo chiều rộng là duyệt qua cơ sở dữ liệu gốc để tính độ hỗ trợ
của tất cả các tập mục ứng viên có (k-1) mục trƣớc khi tính độ hỗ trợ của các
tập mục ứng viên có k mục. Với cơ sở dữ liệu có n mục dữ liệu, lần lặp thứ k
phải kiểm tra độ hỗ trợ của tất cả Cnk 

Số hóa bởi Trung tâm Học liệu – ĐHTN


n!
tập mục ứng viên có k mục.
k !( n  k )!




15

Duyệt theo chiều sâu là duyệt qua cơ sở dữ liệu đã đƣợc chuyển đổi
thành cấu trúc cây, quá trình duyệt gọi đệ quy theo chiều sâu của cây.
Với cơ sở dữ liệu có n mục dữ liệu, khơng gian tìm kiếm có tất cả 2n
tập con, rõ ràng đây là bài tốn khó, do vậy cần phải có phƣơng pháp duyệt
thích hợp, tỉa nhanh các tập ứng viên.
Phƣơng pháp xác định độ hỗ trợ của tập mục X đƣợc chia làm hai cách:
cách thứ nhất là đếm số giao tác chứa X trong cơ sở dữ liệu và cách thứ hai là
tính phần giao của các tập chứa định danh của các giao tác chứa X.
Các thuật toán khai phá có thể phân loại nhƣ hình 1.4 [3]:
Các thuật tốn
BFS

DFS

Đếm

Đếm

Giao


Giao

AIS
Apriori
Dic

Eclat

FPPartit growth
ion

Hình 1.4: Phân loại các thuật tốn khai phá tập mục thƣờng xuyên.
Phần tiếp theo mô tả chi tiết nội dung hai thuật toán tiêu biểu cho hai
phƣơng pháp: duyệt theo chiều rộng và duyệt theo chiều sâu. Thuật toán
Apriori tiêu biểu cho phƣơng pháp duyệt theo chiều rộng; Thuật toán FPgrowth, đại diện cho phƣơng pháp duyệt theo chiều sâu.

Số hóa bởi Trung tâm Học liệu – ĐHTN




16

1.6.4. Một số thuật tốn điển hình tìm tập mục thƣờng xuyên
1.6.4.1. Thuật toán Apriori
Apriori là thuật toán khai phá tập mục thƣờng xuyên do R. Agrawal và
R. Srikant đề xuất vào năm 1993 [3], [7]. Ý tƣởng của thuật toán Apriori cũng
là nền tảng cho việc phát triển nhiều thuật toán khai phá tập mục thƣờng
xuyên khác về sau.
Ý tƣởng chính của thuật tốn nhƣ sau: sinh ra các tập mục ứng viên từ

các tập mục thƣờng xuyên ở bƣớc trƣớc, sử dụng kỹ thuật “tỉa” để bỏ đi
những tập mục ứng viên không thỏa mãn ngƣỡng hỗ trợ cho trƣớc. Cơ sở của
kỹ thuật này là tính chất 3: Bất kỳ tập con nào của tập mục thường xuyên
cũng phải là tập mục thường xuyên. Vì vậy các tập mục ứng viên gồm k mục
có thể đƣợc sinh ra bằng cách kết nối các tập mục thƣờng xuyên có (k-1) mục
và loại bỏ tập mục ứng viên nếu nó có chứa bất kỳ một tập con nào khơng
phải là thƣờng xuyên.
Giả sử các mục dữ liệu trong mỗi giao tác đƣợc lƣu theo trật tự từ điển.
Thuật toán sử dụng các ký hiệu sau đây :
Tập k mục

Chức năng
Tập các k-tập mục thƣờng xuyên (với độ hỗ trợ tối thiểu
minsup). Mỗi phần tử của tập này có 2 trƣờng :

Lk

i) Tập mục (itemsets)
ii) Độ hỗ trợ (count)
Tập các k-tập mục ứng viên (các tập mục thƣờng xuyên tiềm
năng). Mỗi phần tử của tập này có 2 trƣờng:

Ck

i) Tập mục (itemsets)
ii) Độ hỗ trợ (count)

Số hóa bởi Trung tâm Học liệu – ĐHTN