BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC KINH TẾ TP. HỒ CHÍ MINH

MAI THỊ KIM NGÂN

ỨNG DỤNG KHAI THÁC DỮ LIỆU VÀO HỆ THỐNG
QUẢN TRỊ QUAN HỆ KHÁCH HÀNG

LUẬN VĂN THẠC SĨ KINH TẾ

Tp. Hồ Chí Minh, tháng 5 năm 2020


BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC KINH TẾ TP. HỒ CHÍ MINH

MAI THỊ KIM NGÂN

ỨNG DỤNG KHAI THÁC DỮ LIỆU VÀO HỆ THỐNG
QUẢN TRỊ QUAN HỆ KHÁCH HÀNG
Chuyên ngành: Công nghệ thiết kế thông tin và truyền thông
Mã ngành: 8340405

LUẬN VĂN THẠC SĨ KINH TẾ

NGƯỜI HƯỚNG DẪN KHOA HỌC:
PGS.TS. Quản Thành Thơ

Tp. Hồ Chí Minh, tháng 5 năm 2020

LỜI CAM ĐOAN
Do mới lần đầu tiếp cận với ngành nên tôi còn rất nhiều bỡ ngỡ về lý
thuyết và các phương pháp nghiên cứu. Tuy nhiên, sau hơn một năm học tại
Khoa đã giúp tôi hiểu biết thêm nhiều điều, tích lũy thêm nhiều kinh nghiệm
mà còn học hỏi được thêm nhiều kỹ năng quý báu trong việc phân tích vấn đề,
cung cấp thông tin và hỗ trợ ra quyết định.
Trước hết tôi xin gửi lời cảm ơn chân thành và sự tri ân sâu sắc đến
PGS.TS Quản Thành Thơ, thầy đã dành nhiều thời gian quan tâm, hướng
dẫn, chỉ bảo và giúp đỡ tôi trong suốt thời gian học tập. Thực sự qua những
bài giảng đó tôi đã hiểu kỹ hơn và sâu hơn những kiến thức liên quan; từ đó
làm nền tảng lý luận cho báo cáo và cũng như công việc sau này.
Tôi cam đoan đề tài luận văn “Ứng dụng khai thác dữ liệu vào hệ thống
quản trị quan hệ khách hàng” là công trình nghiên cứu của riêng cá nhân tôi
nhờ sự hỗ trợ từ giáo viên hướng dẫn PGS.TS Quản Thành Thơ. Các nội dung
trong luận văn hoàn toàn trung thực và đảm bảo chưa từng được công bố trong
bất kì công trình nghiên cứu nào.
Một lần nữa xin chân thành cảm ơn.
Tp. Hồ Chí Minh, tháng 03 năm 2020
Người thực hiện

Mai Thị Kim Ngân


MỤC LỤC

TRANG PHỤ BÌA
LỜI CAM ĐOAN
MỤC LỤC
BẢNG DANH MỤC CHỮ VIẾT TẮT
DANH MỤC CÁC BẢNG

DANH MỤC CÁC HÌNH
TÓM TẮT
ABSTRACT
CHƯƠNG 1: GIỚI THIỆU ............................................................................... 1
1.1 Giới thiệu đề tài ............................................................................................ 1
1.2 Mục tiêu nghiên cứu ..................................................................................... 3
1.3 Phạm vi nghiên cứu ...................................................................................... 3
CHƯƠNG 2: TỔNG QUÁT KHAI PHÁ DỮ LIỆU & CÁC GIẢI THUẬT
VÀ KHAI PHÁ ...................................................................................................... 4
2.1. Tóm tắt các công trình nghiên cứu trước đó ......................................................... 4
2.2. Tổng quan khai phá dữ liệu .......................................................................... 5
2.3. Giải thuật Apriori & FPGrowth .................................................................. 11
2.3.1. Chi tiết giải thuật Apriori ................................................................ 11
2.3.2. Chi tiết giải thuật FPGrowth ........................................................... 14
2.3.3. Các độ đo sử dụng ........................................................................... 15


2.4. Phân tích RFM ............................................................................................ 16
2.5. Thuật toán phân nhóm K-Means ................................................................ 17
2.6. Phân tích thành phần chính PCA ................................................................ 25
CHƯƠNG 3: TỔNG KẾT KẾT QUẢ KHẢO SÁT .......................................... 27
CHƯƠNG 4: THỰC HIỆN KHAI PHÁ TRÊN DỮ LIỆU NEEM .................. 35
4.1. Giới thiệu công ty Neem ............................................................................. 35
4.2. Tiền xử lý dữ liệu ........................................................................................ 35
4.3. Thực hiện các giải thuật Apriori và FPGrowth với tập dữ liệu .................. 47
4.4. Phân khúc khách hàng bằng phương pháp RFM và K-Means ................... 49
4.4.1. Phân khúc khách hàng bằng phương pháp RFM ............................ 49
4.4.2. Phân khúc khách hàng bằng phương pháp K-Means ...................... 51
4.5. Ứng dụng vào doanh nghiệp ....................................................................... 61
CHƯƠNG 5: KẾT LUẬN .................................................................................. 62

5.1. Tổng kết quá trình nghiên cứu .................................................................... 62
5.2. Hạn chế và Hướng phát triển ...................................................................... 63
TÀI LIỆU THAM KHẢO
PHỤ LỤC BẢNG CÂU HỎI KHẢO SÁT


BẢNG DANH MỤC CÁC CHỮ VIẾT TẮT
Chữ viết tắt

Từ tiếng Anh

Từ tiếng Việt

RFM

Recency-Frequency-

Lần mua gần nhất – Tần suất –

Moneytary

Số tiền mua hàng

Customer Relationship

Quản trị quan hệ khách hàng

CRM

Management

FMCG

Fast Moving Consumer
Goods

Hàng tiêu dùng nhanh


DANH MỤC CÁC BẢNG
Bảng 4.1 Các đặc trưng của bộ dữ liệu Neem ...................................................... 35
Bảng 4.2. So sánh kết quả giải thuật Apriori và FPGrowth.................................. 47
Bảng 4.3. Kết quả sau khi chạy giải thuật............................................................. 48
Bảng 4.4. Danh sách khách hàng với chỉ số RFM ................................................ 49
Bảng 4.5. Danh sách khách hàng với tổng điểm ................................................... 51
Bảng 4.6. Thống kê các nhóm số ngày gần nhất .................................................. 53
Bảng 4.7. Danh sách khách hàng phân nhóm theo tần suất .................................. 53
Bảng 4.8. Danh sách khách hàng phân nhóm theo tần suất .................................. 55
Bảng 4.9. Thống kê các nhóm có tần suất mua sắm ............................................. 55
Bảng 4.10. Danh sách khách hàng và nhóm tiền mua sắm ................................... 57
Bảng 4.11. Thống kê nhóm số tiền mua sắm ........................................................ 57
Bảng 4.12. Trung bình nhóm điểm theo RFM ...................................................... 58
Bảng 4.13. So sánh khác biệt giữa phân nhóm RFM và K-Means ....................... 59
Bảng 4.14. So sánh khác biệt giữa phân nhóm RFM và K-Means sau khi biến đổi
cluster .................................................................................................................... 60
Bảng 5.1. Kết quả chạy Apriori và FPGrowth ...................................................... 63


DANH MỤC CÁC HÌNH
Hình 1.1 Khía cạnh CRM và các mô hình khai phá dữ liệu ................................... 2
Hình 2.1. Quá trình khai phá tri thức ...................................................................... 6

Hình 2.2. Ví dụ dataset............................................................................................ 7
Hình 2.3. Khuỷu tay k ........................................................................................... 25
Hình 3.1. Thống kê chức vụ hiện tại của người tham gia khảo sát ....................... 26
Hình 3.2. Thống kê lĩnh vực hoạt động của người tham gia khảo sát .................. 27
Hình 3.3. Thống kê mức độ quan trọng của việc khai thác dữ liệu hệ thống quản
trị quan hệ khách hàng CRM ................................................................................ 28
Hình 3.4. Thống kê mục đích của việc khai thác dữ liệu hệ thống quản trị quan hệ
khách hàng CRM .................................................................................................. 29
Hình 3.5. Thống kê mức độ quan trọng với nghề nghiệp hiện tại của người tham
gia khảo sát............................................................................................................ 29
Hình 3.6. Thống kê mức độ quan trọng của việc khai thác dữ liệu hệ thống quản
trị quan hệ khách hàng CRM với bộ phận làm việc của người tham gia khảo sát 30
Hình 3.7. Thống kê mức độ quan trọng của việc khai thác dữ liệu hệ thống quản
trị quan hệ khách hàng CRM với lĩnh vực của người tham gia khảo sát .............. 31
Hình 3.8. Thống kê mục đích của việc khai thác dữ liệu hệ thống quản trị quan
hệ khách hàng CRM với chức vụ hiện tại của người tham gia khảo sát............... 32
Hình 3.9. Thống kê mục đích của việc khai thác dữ liệu hệ thống quản trị quan
hệ khách hàng CRM với lĩnh vực của người tham gia khảo sát ........................... 33
Hình 3.10. Thống kê mục đích của việc khai thác dữ liệu hệ thống quản trị quan
hệ khách hàng CRM với bộ phận của người tham gia khảo sát ........................... 34
Hình 4.1. Tỉ lệ doanh thu các sản phẩm Neem qua các năm ................................ 38


Hình 4.2. Tỉ lệ số lượng sản phẩm bán ra Neem qua các năm ............................. 38
Hình 4.3. Tỉ trọng sản phẩm qua các năm ............................................................ 39
Hình 4.4. Tình hình doanh thu qua các năm ......................................................... 39
Hình 4.5. Tình hình doanh thu cùng kì tháng giữa các năm 2019, 2020 .............. 40
Hình 4.6. Số lượng sản phẩm thống kê theo tỉnh/TP nhận hàng .......................... 41
Hình 4.7. Doanh thu sản phẩm thống kê theo tỉnh/TP nhận hàng ........................ 41
Hình 4.8. Top 10 các quận có số lượng đơn hàng qua các năm ........................... 42

Hình 4.9. Top 10 các quận có doanh thu qua các năm ......................................... 43
Hình 4.10. Phương thức thanh toán ...................................................................... 44
Hình 4.11. Thống kê doanh thu qua các chương trình khuyến mãi ...................... 45
Hình 4.12. Tương quan các thuộc tính .................................................................. 46
Hình 4.13. Thống kê ngày mua gần nhất .............................................................. 52
Hình 4.14. Số lượng nhóm dựa theo phương pháp elbow .................................... 52
Hình 4.15. Thống kê tần suất mua sắm ................................................................. 54
Hình 4.16. Số lượng nhóm dựa theo phương pháp elbow .................................... 54
Hình 4.17. Thống kê số tiền mua sắm .................................................................. 56
Hình 4.18. Số lượng nhóm dựa theo phương pháp elbow .................................... 56
Hình 4.19. Số lượng nhóm k từ 1 đến 25 .............................................................. 60
Hình 4.20. Phân cụm kết hợp K-Means ................................................................ 60
Hình 4.21. Phân cụm kết hợp PCA và K-Means .................................................. 61


TÓM TẮT
Với sự bùng nổ và phát triển của công nghệ thông tin đã mang lại nhiều
hiệu quả đối với các hoạt động kinh doanh của doanh nghiệp, đặc biệt là đối với
việc khai phá dữ liệu từ hệ thống quản trị quan hệ khách hàng. Dữ liệu trong hệ
thống quản trị quan hệ khách hàng chứa đựng nhiều thông tin hữu ích, giá trị, đòi
hỏi phải có những kĩ thuật khai phá nhanh, phù hợp chính xác hiệu quả. Khai phá
dữ liệu khách hàng giúp doanh nghiệp hiểu khách hàng hơn từ đó có các chiến
lược, chương trình chăm sóc khách hàng phù hợp.
Các kĩ thuật trong khai phá dữ liệu gồm: trực quan hóa dữ liệu, phân nhóm,
phổ biến là phát hiện luật kết hợp. Với phương pháp trực quan hóa dữ liệu, doanh
nghiệp có thể rút trích được những thông tin đa dạng. Ngoài ra kĩ thuật phân nhóm
K-Means giúp doanh nghiệp có thể phân cụm, phân nhóm khách hàng để chăm
sóc tốt hơn. Đặc biệt khai phá luật kết hợp nhằm tìm ra các tập phần tử thường
xuất hiện đồng thời trong cơ sở dữ liệu và rút ra các luật về ảnh hưởng của một
tập phần tử dẫn đến sự xuất hiện của một (hoặc một tập) phần tử khác như thế nào.

Bên cạnh đó, nhu cầu khai phá khi dữ liệu gia tăng là rất cần thiết hiện nay bởi
kích thước lưu trữ dữ liệu ngày càng nhiều nên đòi hỏi tốc độ xử lý cũng như dung
lượng bộ nhớ hệ thống phải đảm bảo. Vì thế, yêu cầu cần có những thuật toán hiệu
quả cho việc phát hiện luật kết hợp.
Việc dự đoán trước sản phẩm khách hàng mua kèm sẽ giúp doanh nghiệp
có thể tăng số lượng bán và doanh thu. Cũng như việc phân nhóm khách hàng cụ
thể sẽ giúp doanh nghiệp có chiến lược chăm sóc riêng biệt, Tuy nhiên khó khăn
ở việc biểu diễn thông tin ở đầu ra để người dùng có thể thấy được ý nghĩa từ
những thông tin đó.
Hiện nay việc phân nhóm phổ biến nhất là dùng K-Means tuy nhiên trong
luận văn này ngoài phương pháp K-Means tác giả còn dùng phương pháp phân tích
RFM để phân cụm khách hàng. Ngoài ra, hai giải thuật phổ biến cho luật kết hợp là
Apriori và FPGrowth, được dùng trong bài toán phân tích sản phẩm khách hàng hay
mua kèm theo.


ABSTRACT

The study was conducted with the sample data from Customer relationship
management system of Neem. Through data mining dimesions as visualization,
clustering, association to help the enterprises to understand customers better to give
them the right promotions and suitable benfits.
With the method of data visualization, businesses can extract diverse
information. In addition, K-Means technique helps businesses to cluster customers
to take care of them better. Specifically, the association rules to find the set of
elements that often appear simultaneously in the database and draw rules about the
effect of an element set leading to the appearance of one (or a set) of parts. Besides,
the need for mining when data is increasing is necessary today because the size of
data storage is increasing, so the processing speed as well as the amount of system
memory must be guaranteed. Therefore, the effective algorithms are required for

association rule detection.
Currently, the most popular clustering is using K-Means but in this thesis, in
addition to the K-Means method, the author also uses the RFM analysis method to
cluster customers. In addition, the two common algorithms for association rules are
Apriori and FPGrowth, which are used in the problem of analyzing customer
products or purchased together.
Keywords: RFM, Association rules, K-Means, CRM data mining, customer
relationship management data mining


1

CHƯƠNG 1: GIỚI THIỆU
1.1

GIỚI THIỆU ĐỀ TÀI:

CRM là viết tắt của từ Customer Relationship Management - Quản trị quan hệ
khách hàng. Đó là chiến lược của các công ty trong việc phát triển quan hệ gắn
bó với khách hàng qua nghiên cứu, tìm hiểu kỹ lưỡng nhu cầu và thói quen của
khách hàng, tiếp cận và giao tiếp với khách hàng một cách có hệ thống và hiệu
quả, quản lý các thông tin của khách hàng như thông tin về tài khoản, nhu cầu,
liên lạc… nhằm phục vụ khách hàng tốt hơn.
Thông qua hệ thống quan hệ khách hàng, các thông tin của khách hàng sẽ được
cập nhật và được lưu trữ trong hệ thống quản lý cơ sở dữ liệu. Vì thế, ứng dụng
khai thác dữ liệu để phân tích hình thành danh sách khách hàng tiềm năng và lâu
năm để đề ra những chiến lược chăm sóc khách hàng hợp lý.
Swift đã mô tả các khía cạnh CRM như hình dưới đây gồm: nhận dạng khách
hàng, thu hút khách hàng, giữ chân khách hàng và phát triển khách hàng. CRM
bắt đầu với việc nhận diện khách hàng. Bước đầu tiên này là về việc khám phá

các thực thể có xu hướng trở thành khách hàng hoặc người mang lại lợi nhuận
nhất cho công ty. Sau khi xác định được phân khúc khách hàng tiềm năng, các
công ty cố gắng vận dụng nỗ lực và các nguồn lực để thu hút khách hàng tiềm
năng. Ngoài ra, nó còn chứa các phân tích khách hàng sắp rời bỏ công ty và làm
thế nào để giành lại họ.
Trong CRM, giữ chân khách hàng là mối quan tâm chính. Sự hài lòng của khách
hàng, có nghĩa là so sánh nhu cầu của khách hàng và nhu cầu của họ là bao nhiêu,
là yếu tố chính để giữ chân khách hàng. Các thành phần giữ chân khách hàng
gồm các chương trình khách hàng thân thiết, tiếp thị trực tiếp và giải quyết khiếu
nại. Phát triển khách hàng gồm phân tích mật độ giao dịch, giá trị giao dịch.
Thành phần của phát triển khách hàng gồm bán chéo, báo nhiều hơn và phân tích
giỏ hàng. Ahmed mô tả các bước của CRM như nhận diện khách hàng, thu hút
khách hàng, phát triển khách hàng và giữ chân khách hàng và các mô hình khai


2

thác dữ liệu như tương ứng như Liên kết (Association), Phân loại
(Classification), Gom nhóm (Clustering), Dự báo (Forecasting), Hồi quy
(Regression), Khám phá tuần tự (Sequence Discovery) và Trực quan hóa dữ liệu
(Visualization).

Hình 1.1. Khía cạnh CRM và các mô hình khai phá dữ liệu
Nguồn: Ahmed, S. R.; “Applications of data mining in retail
business,"Information Technology: Coding and Computing, 2, 455–459,
2004
Trong các vấn đề nêu trên, luận văn quan tâm đến việc nhận diện khách hàng và
phát triển khách hàng cũng như tìm hiểu về nhu cầu của các công ty ở Việt Nam
trong việc ứng dụng khai thác dữ liệu hệ thống quản trị quan hệ khách hàng để
phân tích.

Luận văn sẽ chia làm hai phần: Phần đầu là tìm hiểu về nhu cầu các công ty ở
Việt Nam trong việc ứng dụng khai thác dữ liệu hệ thống quản trị quan hệ khách
hàng để phân tích và phần sau là ứng dụng khai thác dữ liệu Neem gồm có: phân
tích RFM (Recency, Frequency, Moneytary), thuật toán Kmeans để phân khúc
khách hàng và sử dụng giải thuật Apriori và FP-Growth để tìm luật kết hợp các


3

sản phẩm mà khách hàng thường mua cùng nhau.
Dữ liệu dùng trong luận văn này được lấy từ công ty Neem. Dữ liệu gồm 5624
dòng tương ứng với 2939 khách hàng và 14 cột.
1.2

MỤC TIÊU NGHIÊN CỨU:

Mục tiêu cụ thể:
-

Nghiên cứu nhu cầu khai thác dữ liệu hệ thống quản trị khách hàng của

các công ty ở Việt Nam
-

Dùng RFM, K-Means phân khúc khách hàng để nhận diện khách hàng và

chăm sóc khách hàng tốt hơn
-

Dùng giải thuật Apriori, FPGrowth tạo ra luật kết hợp nhằm gia tăng việc


mua hàng của khách hàng
1.3. ĐỐI TƯỢNG VÀ PHẠM VI NGHIÊN CỨU:
-

Đối tượng nghiên cứu: Các phương pháp, mô hình khai phá dữ liệu K-

Means, thuật toán Apriori, FP-Growth từ hệ thống quản trị quan hệ khách hàng
công ty Neem .
-

Phạm vi nghiên cứu: Dữ liệu nghiên cứu và xây dựng mô hình thực

nghiệm được thu thập từ công ty Neem trong khoảng thời gian từ năm 2018 đến
năm tháng 04-2020


4

CHƯƠNG 2: TỔNG QUÁT KHAI PHÁ DỮ LIỆU & CÁC GIẢI THUẬT VÀ
KHAI PHÁ
2.1. TÓM TẮT CÁC CÔNG TRÌNH NGHIÊN CỨU TRƯỚC ĐÓ
Thành phần chính của CRM là hiểu nhu cầu khách hàng và duy trì nhóm khách
hàng có khả năng sinh lợi cao. Với việc ứng dụng kĩ thuật như là phân nhóm,
gom nhóm đóng vai trò quan trọng trong việc biến dữ liệu thành thông tin có ích
cho doanh nghiệp. Dưới đây là tóm tắt các công trình nghiên cứu trước đó:
Dokuz Eylul University đã có nghiên cứu Hệ củng cố quyết định quản trị quan
hệ khách hàng Decision Support System for a Customer Relationship
Management Case Study. Nghiên cứu dùng thuật toán Naiive Bayes để phân loại
khách hàng có đăng ký tiền gửi có kì hạn hay không. Để xác định độ chính xác

bằng cross validation – xác nhận chéo. Kết quả đã chứng minh khả năng ứng
dụng và hiệu quả của mô hình đề xuất. Và mục tiêu của nghiên cứu chính là dự
đoán khách hàng có gửi tiết kiệm có kì hạn hay không.
Mặc khác trong lĩnh vực ngân hàng cũng đã có một số nghiên cứu về kĩ thuật
khai phá dữ liệu như nghiên cứu của nhóm các tác giả Sheela Singhal và
Dr.G.N.Singh đã đề xuất phương pháp phân nhóm khách hàng bằng việc khai
phá luật kết hợp Classification Based Association rules, trong nghiên cứu của
mình, các tác giả đã sử dụng luật kết hợp để tìm ra các dịch vụ ngân hàng mà
khách hàng thường hay sử dụng kèm với một dịch vụ ngân hàng khác. Trong
một nghiên cứu khác, luận án tiến sỹ của Al-Shawabkeh, Abdallah, kỹ thuật phân
nhóm đã được sử dụng để hỗ trợ ngân hàng trong việc nâng cao chất lượng dịch
vụ khách hàng tại ngân hàng Jodanians.
Chen et al. (2005a) đã dùng các biến như hành vi khách hàng, RFM, nhân khẩu
học và dữ liệu giao dịch để nghiên cứu ra phương pháp ước tính giá trị của khách
hàng đối với doanh nghiệp. Kĩ thuật luật kết hợp được dùng để tìm mối liên hệ
giữa khách hàng và sản phẩm họ mua.


5

2.2. TỔNG QUAN KHAI PHÁ DỮ LIỆU
2.1.1. Khái niệm:
Khai phá dữ liệu (data mining) hay Khám phá tri thức từ dữ liệu (knowledge
discovery from data) là việc xuất trích được các mẫu hoặc tri thức quan trọng (không
tầm thường, chưa được biết đến và có thể hữu ích) từ một lượng dữ liệu (rất) lớn.
Các tên gọi khác:
- Khám phá tri thức trong các cơ sở dữ liệu (Knowledge discovery in databases
KDD).
- Trích rút tri thức (knowledge extraction).
- Phân tích mẫu/dữ liệu (data/pattern analysis).

2.1.2. Các bước trong quá trình khai phá:
Quá trình được thực hiện qua 9 bước:
1-

Hiểu rõ bài toán cần giải quyết như mục đích của bài toán, các kiến thức cụ

thể của lĩnh vực phân tích.
2-

Tạo nên (thu thập) dữ liệu phù hợp với nhu cầu bước 1.

3-

Làm sạch và tiền xử lý dữ liệu.

4-

Chuyển đổi dữ liệu để rút trích thêm thông tin, giảm kích thước của dữ liệu

xác định các thuộc tính quan trọng, giảm số chiều (số thuộc tính) giữ lại các thuộc
tính quan trọng.
5-

Sau khi dữ liệu đã làm sạch, ta tiến hành lựa chọn chức năng khai phá dữ liệu

gồm: dự báo, gom cụm, phân loại, luật kết hợp
6-

Nhằm cho việc khai phá dữ liệu chính xác hơn, ta tiến hành thử nghiệm phát


triển các giải thuật khai phá
7-

Tiến hành khai phá dữ liệu.

8-

Sau khi đã có kết quả, ta tiến hành biểu diễn tri thức nhằm mang lại cho người

xem dễ hiểu hơn bằng cách hiển thị hóa, chuyển đổi, bỏ đi các mẫu dư thừa.
9-

Sử dụng tri thức được khai phá. Quá trình khám phá tri thức theo cách nhìn


6

của giới nghiên cứu về các hệ thống dữ liệu và kho dữ liệu về quá trình khám phá tri
thức.

Hình 2.1. Quá trình khai phá tri thức.
Nguồn: Han và Kamber – Data mining: Concepts and Techniques
Chuẩn bị dữ liệu (data preparation), bao gồm các quá trình làm sạch dữ liệu (data
cleaning), tích hợp dữ liệu (data integration), chọn dữ liệu (data selection), biến đổi
dữ liệu (data transformation).
Khai thác dữ liệu (data mining): xác định nhiệm vụ khai thác dữ liệu và lựa chọn kỹ
thuật khai thác dữ liệu. Kết quả cho ta một nguồn tri thức thô.
Đánh giá (evaluation): dựa trên một số tiêu chí tiến hành kiểm tra và lọc nguồn tri
thức thu được.
Triển khai (deployment).: Quá trình khai thác tri thức không chỉ là một quá trình tuần

tự từ bước đầu tiên đến bước cuối cùng mà là một quá trình lặp và có quay trở lại các
bước đã qua.
2.1.3. Ứng dụng của khai phá dữ liệu
Trong lĩnh vực kinh tế: tài chính, tiếp thị bán hàng, bảo hiểm, thương mại, ngân hàng
bằng việc đưa ra các bản báo cáo giàu thông tin, phân tích rủi ro trước khi đưa ra các


7

chiến lược kinh doanh, sản xuất, phân khúc khách hàng nhằm phân định thị trường,
thị phần
Trong lĩnh vực khoa học: thiên văn học dự đoán đường đi của các thiên thể, hành tinh
Trong lĩnh vực công nghệ sinh học: tìm ra các gen mới, cây con giống mới
Trong lĩnh vực web: ứng dụng tối ưu vào công cụ tìm kiếm
2.2. TIỀN XỬ LÝ DỮ LIỆU
Quá trình tiền xử lý dữ liệu, đầu tiên phải nắm được dạng dữ liệu, thuộc tính, mô tả
của dữ liệu thao tác. Sau đó tiến hành 4 giai đoạn chính: làm sạch, tích hợp, biến đổi,
thu giảm dữ liệu.
2.2.1. Dữ liệu
a) Tập dữ liệu
- Một tập dữ liệu (dataset) là một tập hợp các đối tượng (object) và các thuộc tính của
chúng.
- Mỗi thuộc tính (attribute) mô tả một đặc điểm của một đối tượng.

Hình 2.2. Ví dụ dataset
Nguồn: Tan, Steinbach, Kumar – Introduction to Data Mining
Ví dụ: Các thuộc tính Refund, Marital Status , Taxable Income, Cheat
b) Các kiểu tập dữ liệu
- Bản ghi (record): Các bản ghi trong cơ sở dữ liệu quan hệ. Ma trận dữ liệu. Biểu



8

diễn văn bản, dữ liệu giao dịch
- Đồ thị (graph): Mạng internet, hoặc mạng xã hội
- Dữ liệu có trật tự: Dữ liệu không gian (ví dụ: bản đồ). Dữ liệu thời gian (ví dụ: timeseries data). Dữ liệu chuỗi (ví dụ: chuỗi giao dịch).
c) Các kiểu giá trị thuộc tính:
- Kiểu định danh/chuỗi (norminal): không có thứ tự. Ví dụ: Các thuộc tính như :
Name, Profession
- Kiểu nhị phân (binary): là một trường hợp đăc biệt của kiểu định danh. Tập các giá
trị chỉ gồm có 2 giá trị (Y/N, 0/1, T/F).
- Kiểu có thứ tự (ordinal): Integer, Real, lấy giá trị từ một tập có thứ tự giá trị. Ví dụ:
Các thuộc tính lấy giá trị số như : Age, Height. Hay lấy một tập xác định, thuộc tính
Income lấy giá trị từ tập {low, medium, high}.
- Kiểu thuộc tính rời rạc (discrete-valued attributes): có thể là tập các giá trị của một
tập hữu hạn. Bao gồm thuộc tính có kiểu giá trị là các số nguyên, nhị phân.
- Kiểu thuộc tính liên tục (continuous-valued attributes): Các giá trị là số thực.
d) Các đặc tính mô tả của dữ liệu:
- Giúp hiểu rõ về dữ liệu có được: chiều hướng chính/trung tâm, sự biến thiên, sự
phân bố.
- Sự phân bố của dữ liệu (data dispersion):
+ Giá trị cực tiểu/cực đại (min/max).
+ Giá trị xuất hiện nhiều nhất (mode).
+ Giá trị trung bình (mean). + Giá trị trung vị (median).
+ Sự biến thiên (variance) và độ lệch chuẩn (standard deviation) .
+ Các ngoại lai (outliers).
2.2.2. Làm sạch dữ liệu (data cleaning)
Đối với dữ liệu thu thập được, cần xác định các vấn đề ảnh hưởng là cho nó không
sạch. Bởi vì, dữ liệu không sạch (có chứa lỗi, nhiễu, không đầy đủ, có mâu thuẫn) thì



9

các tri thức khám phá được sẽ bị ảnh hưởng và không đáng tin cậy, sẽ dẫn đến các
quyết định không chính xác. Do đó, cần gán các giá trị thuộc tính còn thiếu; sửa chữa
các dữ liệu nhiễu/lỗi; xác định hoặc loại bỏ các ngoại lai (outliers); giải quyết các
mâu thuẫn dữ liệu.
a) Các vấn đề của dữ liệu Trên thực thế dữ liệu thu có thể chứa nhiễu, lỗi, không hoàn
chỉnh, có mâu thuẫn.
- Không hoàn chỉnh (incomplete): Thiếu các giá trị thuộc tính hoặc thiếu một số
thuộc tính. Ví dụ: salary = .
- Nhiễu/lỗi (noise/error): Chứa đựng những lỗi hoặc các mang các giá trị bất thường.
Ví dụ: salary = “-525” , giá trị của thuộc tính không thể là một số âm.
- Mâu thuẫn (inconsistent): Chứa đựng các mâu thuẫn (không thống nhất). Ví dụ:
salary = “abc” , không phù hợp với kiểu dữ liệu số của thuộc tính salary.
b) Nguồn gốc/lý do của dữ liệu không sạch
- Không hoàn chỉnh (incomplete): Do giá trị thuộc tính không có (not available) tại
thời điểm được thu thập. Hoặc các vấn gây ra bởi phần cứng, phần mềm, hoặc người
thu thập dữ liệu.
- Nhiễu/lỗi (noise/error): Do việc thu thập dữ liệu, hoăc việc nhập dữ liệu, hoặc việc
truyền dữ liệu.
- Mâu thuẫn (inconsistent): Do dữ liệu được thu thập có nguồn gốc khác nhau. Hoặc
vi phạm các ràng buộc (điều kiện) đối với các thuộc tính.
c) Giải pháp khi thiếu giá trị của thuộc tính
- Bỏ qua các bản ghi có các thuộc tính thiếu giá trị. Thường áp dụng trong các bài
toán phân lớp. Hoặc khi tỷ lệ % các giá trị thiếu đối với các thuộc tính quá lớn.
- Một số người sẽ đảm nhiệm việc kiểm tra và gán các giá trị thuộc tính còn thiếu,
nhưng đòi hỏi chi phí cao và rất tẻ nhạt.
- Gán giá trị tự động bởi máy tính:
+ Gán giá trị mặc định



10

+ Gán giá trị trung bình của thuộc tính đó.
+ Gán giá trị có thể xảy ra nhất – dựa theo phương pháp xác suất.
d) Giải pháp khi dữ liệu chứa nhiễu/lỗi
- Phân khoảng (binning): Sắp xếp dữ liệu và phân chia thành các khoảng (bins) có
tần số xuất hiện giá trị như nhau. Sau đó, mỗi khoảng dữ liệu có thể được biểu diễn
bằng trung bình, trung vị, hoặc các giới hạn của các giá trị trong khoảng đó.
- Hồi quy (regression): Gắn dữ liệu với một hàm hồi quy.
- Phân cụm (clustering): Phát hiện và loại bỏ các ngoại lai (sau khi đã xác định các
cụm).
- Kết hợp giữa máy tính và kiểm tra của con người: Máy tính sẽ tự động phát hiện ra
các giá trị nghi ngờ. Các giá trị này sẽ được con người kiểm tra lại.
2.2.3. Tích hợp dữ liệu (data integration)
Tích hợp dữ liệu là quá trình trộn dữ liệu từ các nguồn khác nhau vào một kho dữ liệu
có sẵn cho quá trình khai phá dữ liệu. Khi tích hợp cần xác định thực thể từ nhiều
nguồn dữ liệu để tránh dư thừa dữ liệu. Ví dụ: Bill Clinton = B.Clinton. Việc dư thừa
dữ liệu là thường xuyên xảy ra, khi tích hợp nhiều nguồn. Bởi cùng một thuộc tính
(hay cùng một đối tượng) có thể mang các tên khác nhau trong các nguồn (cơ sở dữ
liệu) khác nhau. Hay các dữ liệu suy ra được như một thuộc tính trong một bảng có
thể được suy ra từ các thuộc tính trong bảng khác. Hay sự trùng lắp các dữ liệu. Các
thuộc tính dư thừa có thể bị phát hiện bằng phân tích tương quan giữa chúng.
Phát hiện và xử lý các mâu thuẫn đối với giá trị dữ liệu: Đối với cùng một thực thể
trên thực tế, nhưng các giá trị thuộc tính từ nhiều nguồn khác nhau lại khác nhau. Có
thể cách biểu diễn khác nhau, hay mức đánh giá, độ do khác nhau. Yêu cầu chung đối
với quá trình tích hợp là giảm thiểu (tránh được là tốt nhất) các dư thừa và các mâu
thuẫn. Giúp cải thiện tốc độ của quá trình khai phá dữ liệu và nâng cao chất lượng
của các kết quả tri thức thu được.

2.2.4. Biến đổi dữ liệu (data transformation)
Biến đổi dữ liệu là việc chuyển toàn bộ tập giá trị của một thuộc tính sang một tập


11

các giá trị thay thế, sao cho mỗi giá trị cũ tương ứng với một trong các giá trị mới.
Các phương pháp biến đổi dữ liệu:
- Làm trơn (smoothing): Loại bỏ nhiễu/lỗi khỏi dữ liệu.
- Kết hợp (aggregation): Sự tóm tắt dữ liệu, xây dựng các khối dữ liệu.
- Khái quát hóa (generalization): Xây dựng các phân cấp khái niệm.
- Chuẩn hóa (normalization): Đưa các giá trị về một khoảng được chỉ định.
+ Chuẩn hóa min-max, giá trị mới nằm khoảng [new_mini , new_maxi]
+ Chuẩn hóa z-score, với μi , σi : giá trị trung bình và độ lệch chuẩn của thuộc tính i
2.3. GIẢI THUẬT APRIORI VÀ FP-GROWTH
2.3.1 Chi tiết giải thuật
Apriori là thuật toán khả sinh được đề xuất bởi R. Agrawal và R. Srikant vào năm
1993 để khai thác các tập item đối với các luật kết hợp kiểu bool. Tên của thuật toán
dựa trên việc thuật toán sử dụng tri thức trước (prior knowledge) của các thuộc tính
tập item phổ biến, chúng ta sẽ thấy sau đây. Apriori dùng cách tiếp cận lặp được biết
đến như tìm kiếm level-wise, với các tập k item được dùng để thăm dò các tập (k+1)
item. Đầu tiên, tập các tập 1 item phổ biến được tìm thấy bằng cách quét cơ sở dữ
liệu để đếm số lượng từng item, và thu thập những item thỏa mãn độ hỗ trợ tối thiểu.
Tập kết quả đặt là L1. Tiếp theo, L1được dùng để tìm L2, tập các tập 2 item phổ biến,
nó được dùng để tìm L3, và cứ thế tiếp tục, cho tới khi tập k item phổ biến không thể
tìm thấy. Việc tìm kiếm cho mỗi Lk đòi hỏi một lần quét toàn bộ cơ sở dữ liệu.
Itemset- Itemset là tập hợp của những item trong cơ sở dữ liệu mà nó được xác định
bởi I= {i1, i2, …. in}, trong đó n là số lượng item.
Transaction- Transaction là một thành phần cơ sở dữ liệu mà nó bao gồm tập hợp các
item. Transaction được ký hiệu là T và T


I. Một Transaction chứa tâp hợp các

item T = {i1, i2, …. in}.
Minimum support – Minimum support là điều kiện cần được đáp ứng bởi các item đề
ra để có thể tiến hành xử lý item kế tiếp có thể. Minimum support có thể được xem


12

như là một điều kiện giúp loại bỏ các tâp không phổ biến trong bất kỳ cơ sở dữ liệu.
Thường sử dụng Minimum support cho mô hình tỷ lệ phần trăm.
Frequent itemset (tập phổ biến) - các Itemset đáp ứng các tiêu chí điều kiện minimum
support thì được gọi là tập phổ biến. Nó được ký hiệu là Li trong đó i chỉ i-itemset.
Candidate itemset (ứng viên tập phổ biến) - ứng viên tập phổ biến là các item chỉ
được xem xét xử lý. Ứng viên tập phổ biến là tất cả các kết hợp có thể có của tập phổ
biến. Nó thường được ký hiệu Ci trong đó I chỉ i-itemset.
Support – Độ hữu dụng của một luật có thể được đo với sự giúp đỡ của ngưỡng hỗ
trợ. Support giúp chúng ta đo như thế nào các giao tác có tập phổ biến mà nó phù hợp
với ý nghĩa cả hai khía cạnh trong luật kết hợp.
Xem xét hai item A và b. Để tính toán support của A->B theo công thức như
sau:

Confidence – độ tin cậy chỉ sự chắc chắn của các luật. Thông số này cho phép chúng
ta đếm mức độ thường xuyên một giao tác của tập phổ biến phù hợp với ý nghĩa cả
phía cạnh bên trái với phía cạnh bên phải. các tập phổ biến không đáp ứng các điều
kiện trên có thể được loại bỏ.
Xem xét hai item A và B. Để tính toán confidence của A->B theo công thức
sau:


Chú ý: Conf(A->B) có thể không bằng conf(B->A)
Apriori dùng cách tiếp cận lặp được biết đến như tìm kiếm level-wise, với các
tập k item được dùng để thăm dò các tập (k+1) item.
Đầu tiên, tập (frequent 1- itemsets) phổ biến 1 được tìm thấy ký hiệu là C1
Bước tiếp theo là tính support có nghĩa là sự xuất hiện của các item trong cơ sở dữ
liệu. Điều này đòi hỏi phải duyệt qua toàn bộ cơ sở dữ liệu.


13

Sau đó, bước cắt tỉa được thực hiện trên C1 trong đó những item được so sánh với
thông số minimum support. Những item thỏa điều kiện minimum support mới được
xem xét cho tiến trình tiếp theo ký hiệu là L1.
Sau đó, bước phát sinh các bộ ứng viên được thực hiện trong đó tập phổ biến 2 được
tạo ra ký hiệu là C2.
Một lần nữa, cở sở dữ liệu được duyệt để tính toán support của 2 tập phổ biến. Theo
minimum support, các bộ ứng viên tạo ra được kiểm tra và chỉ những tập phổ biến
nào thỏa điều kiện minimum support thì tiếp tục được sử dụng tạo ra bô ứng viên tập
phổ biến 3.
Bước trên tiếp tục cho đến khi không có tập phổ biến hoặc bộ ứng viên có thể được
tạo ra.
2.3.2. Giải thuật FPGrowth:
Thuật toán tăng trưởng FP là một phương pháp khai thác hiệu quả tất cả các mục
thường xuyên mà không cần tạo ứng viên. Tăng trưởng FP sử dụng kết hợp bố trí cơ
sở dữ liệu dọc và ngang để lưu trữ cơ sở dữ liệu trong bộ nhớ chính. Thay vì lưu trữ
bìa cho mọi mục trong cơ sở dữ liệu, nó lưu trữ các giao dịch thực tế từ cơ sở dữ liệu
trong cấu trúc cây và mỗi mục có một danh sách được liên kết đi qua tất cả các giao
dịch có chứa mục đó Mỗi nút lưu trữ thêm một bộ đếm, theo dõi số lượng giao dịch
chia sẻ chi nhánh thông qua nút đó. Ngoài ra, một liên kết được lưu trữ, chỉ ra sự xuất
hiện tiếp theo của mục tương ứng trong cây FP, sao cho tất cả các lần xuất hiện của

một mục trong cây FP được liên kết với nhau. Ngoài ra, một tiêu đề bảng được lưu
trữ chứa từng mục riêng biệt cùng với sự hỗ trợ của nó và liên kết đến lần xuất hiện
đầu tiên của mục trong cây FP. Trong cây FP, tất cả các mục được sắp xếp theo thứ
tự giảm dần, bởi vì theo cách này, hy vọng rằng biểu diễn cơ sở dữ liệu này được giữ
càng nhỏ càng tốt vì tất cả các mục thường xuyên hơn được sắp xếp gần gốc của FPtree và do đó có nhiều khả năng được chia sẻ.
Thuật toán khai thác các mục thường xuyên bằng cách sử dụng chiến lược phân chia
và chinh phục như sau: Trước tiên, tăng trưởng FP sẽ nén cơ sở dữ liệu đại diện cho


14

các mục thường xuyên thành cây mô hình thường xuyên, hoặc cây FP, cũng giữ lại
thông tin liên kết của các mục. Bước tiếp theo là chia cơ sở dữ liệu nén thành tập hợp
các điều kiện
Tất cả các nút tương ứng với các mục có một bộ đếm.
Tăng trưởng FP đọc 1 giao dịch tại một thời điểm và ánh xạ nó tới một đường dẫn
Thứ tự cố định được sử dụng, do đó các đường dẫn có thể chồng lấp khi cơ sở dữ liệu
(một loại cơ sở dữ liệu dự kiến đặc biệt), mỗi đường dẫn được liên kết với một mục
thường xuyên. Cuối cùng, khai thác từng cơ sở dữ liệu riêng biệt. Đặc biệt, việc xây
dựng cây FP và khai thác cây FP là những bước chính trong thuật toán tăng trưởng
FP
Tăng trưởng FP: cho phép bạn khám phá các mục thường xuyên mà không cần tạo
mục ứng viên. Nó bao gồm hai bước tiếp cận:
Bước 1: Xây dựng cấu trúc dữ liệu nhỏ gọn gọi là cây FP
Được xây dựng bằng cách sử dụng 2 lần vượt qua tập dữ liệu.
Bước 2: Trích xuất các mục thường xuyên trực tiếp từ cây FP
Truyền qua cây FP
Cấu trúc dữ liệu chung của cây FP
Giao dịch chia sẻ các mục (khi chúng có cùng tiền tố).
Trong trường hợp này, bộ đếm được tăng lên. Con trỏ được duy trì giữa các nút chứa

cùng một mục, tạo danh sách liên kết đơn (đường chấm chấm)
Càng nhiều đường dẫn trùng nhau, độ nén càng cao. Cây FP có thể vừa trong bộ nhớ.
Các mục thường xuyên được trích xuất từ Cây FP.
Dưới đây là những ví dụ rõ ràng về cách thức hoạt động của Tăng trưởng FP: