Luận văn Thạc sĩ Công nghệ thông tin: Phương pháp phân vùng phân cấp trong khai thác tập phổ biến

Chia sẻ: Hứa Tung | Ngày: | Loại File: PDF | Số trang:69

Thêm vào BST

Báo xấu

47
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn Thạc sĩ Công nghệ thông tin: Phương pháp phân vùng phân cấp trong khai thác tập phổ biến được thực hiện với mục tiêu nhằm tìm hiểu việc khai thác các tập phổ biến (frequent item sets) trong cơ sở dữ liệu lớn, dựa trên cấu trúc dữ liệu mới hay gọi là danh sách mẫu phổ biến PL (requent Pattern List). Mời các bạn cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Công nghệ thông tin: Phương pháp phân vùng phân cấp trong khai thác tập phổ biến

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC CÔNG NGHỆ TP. HCM --------------------------- HOÀNG TRUNG THÔNG PHƢƠNG PHÁP PHÂN VÙNG PHÂN CẤP TRONG KHAI THÁC TẬP PHỔ BIẾN LUẬN VĂN THẠC SĨ Chuyên ngành: Công Nghệ Thông Tin Mã số ngành: 60480201 TP. HỒ CHÍ MINH, tháng 03 năm 2015
BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC CÔNG NGHỆ TP. HCM --------------------------- HOÀNG TRUNG THÔNG PHƢƠNG PHÁP PHÂN VÙNG PHÂN CẤP TRONG KHAI THÁC TẬP PHỔ BIẾN LUẬN VĂN THẠC SĨ Chuyên ngành: Công Nghệ Thông Tin Mã số ngành: 60480201 CÁN BỘ HƢỚNG DẪN KHOA HỌC: PGS.TS. LÊ TRỌNG VĨNH TP. HỒ CHÍ MINH, tháng 03 năm 2015
CÔNG TRÌNH ĐƢỢC HOÀN THÀNH TẠI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ TP. HCM Cán bộ hƣớng dẫn khoa học : PGS.TS. LÊ TRỌNG VĨNH (Ghi rõ họ, tên, học hàm, học vị và chữ ký) Luận văn Thạc sĩ đƣợc bảo vệ tại Trƣờng Đại học Công nghệ TP. HCM ngày 11 tháng 04 năm 2015 Thành phần Hội đồng đánh giá Luận văn Thạc sĩ gồm: (Ghi rõ họ, tên, học hàm, học vị của Hội đồng chấm bảo vệ Luận văn Thạc sĩ) TT Họ và tên Chức danh Hội đồng 1 PGS.TS. Đỗ Phúc Chủ tịch 2 TS. Võ Đình Bảy Phản biện 1 3 TS. Lƣ Nhật Vinh Phản biện 2 4 PGS.TS. Lê Hoàng Thái Ủy viên 5 TS. Lê Tuấn Anh Ủy viên, Thƣ ký Xác nhận của Chủ tịch Hội đồng đánh giá Luận sau khi Luận văn đã đƣợc sửa chữa (nếu có). Chủ tịch Hội đồng đánh giá LV
TRƢỜNG ĐH CÔNG NGHỆ TP. HCM CỘNG HÕA XÃ HỘI CHỦ NGHĨA VIỆT NAM PHÒNG QLKH – ĐTSĐH Độc lập – Tự do – Hạnh phúc TP. HCM, ngày 14 tháng 03 năm 2015 NHIỆM VỤ LUẬN VĂN THẠC SĨ Họ tên học viên: Hoàng Trung Thông Giới tính: Nam Ngày, tháng, năm sinh: 06 / 09 /1975 Nơi sinh: Sơn La Chuyên ngành: Công Nghệ Thông Tin MSHV: 1341860025 I- Tên đề tài: PHƢƠNG PHÁP PHÂN VÙNG PHÂN CẤP TRONG KHAI THÁC TẬP PHỔ BIẾN II- Nhiệm vụ và nội dung: Phân vùng thứ bậc để khai thác tập phổ biến trong những cơ sở dữ liệu lớn: - Khai thác tập phổ biến, các cách tiếp cận - Cơ sở dữ liệu có kích thƣớc lớn - Phƣơng pháp phân vùng, phân cấp dữ liệu trên hệ thống nhiều máy - Áp dụng phƣơng pháp phân vùng phân cấp vào bài toán khai thác tập phổ biến - Xây dựng chƣơng trình demo III- Ngày giao nhiệm vụ: 18/08/2014 IV- Ngày hoàn thành nhiệm vụ: 14/03/2015 V- Cán bộ hƣớng dẫn: PGS.TS. LÊ TRỌNG VĨNH CÁN BỘ HƢỚNG DẪN KHOA QUẢN LÝ CHUYÊN NGÀNH PGS. TS. Lê Trọng Vĩnh
I LỜI CAM ĐOAN Tôi cam đoan đây là công trình nghiên cứu của riêng tôi, với sự hƣớng dẫn của Thầy PGS.TS. LÊ TRỌNG VĨNH và sự đóng góp ý kiến của thầy TS. CAO TÙNG ANH. Các số liệu, kết quả nêu trong luận văn là trung thực và chƣa từng đƣợc ai công bố trong bất kỳ công trình nào khác. Tôi xin cam đoan rằng mọi sự giúp đỡ cho việc thực hiện Luận văn này đã đƣợc cảm ơn và các thông tin trích dẫn trong Luận văn đã đƣợc chỉ rõ nguồn gốc. Học viên thực hiện Luận văn (Ký và ghi rõ họ tên) Hoàng Trung Thông
II LỜI CÁM ƠN Lời đầu tiên tôi xin cám ơn chân thành và sâu sắc nhất đến Thầy PGS.TS. LÊ TRỌNG VĨNH , Thầy đã dành rất nhiều thời gian hƣớng dẫn tôi một cách tận tâm, sâu sát và giúp tôi vƣợt qua những thời điểm khó khăn nhất về luận văn này. Tôi cũng xin gởi lời cảm ơn đến thầy TS. CAO TÙNG ANH đã có những đóng góp ý kiến quý báu cho luận văn này. Tiếp theo tôi xin gởi lời cám ơn chân thành và trân trọng nhất đến quý Thầy Cô Khoa CNTT Trƣờng Đại Học Công Nghệ Tp.HCM đã truyền đạt nhiều kiến thức quý báu cho tôi trong suốt quá trình học tập tại trƣờng. Xin cám ơn gia đình, các bạn học, bạn hữu, đồng nghiệp đã có những góp ý và động viên trong suốt thời gian qua. TP. Hồ Chí Minh, tháng 03/2015
III TÓM TẮT Mặc dù có nhiều phƣơng pháp đã đƣợc đề xuất để nâng cao hiệu quả khai thác dữ liệu nhƣng chỉ có ít nghiên cứu về khả năng mở rộng - đó là vấn đề khai thác tập phổ biến khi kích thƣớc của CSDL là rất lớn. Nghiên cứu [14] đề xuất một phƣơng pháp là phân vùng thứ bậc để khai thác tập phổ biến trong CSDL lớn dựa trên một cấu trúc dữ liệu mới gọi là Danh sách mẫu phổ biến (FPL). Một trong những tính năng chính của FPL là khả năng phân vùng cơ sở dữ liệu để chuyển đổi CSDL thành một tập các CSDL con có kích thƣớc có thể quản lý đƣợc. Kết quả là một cách tiếp cận chia để trị có thể đƣợc phát triển để thực hiện nhiệm vụ khai thác dữ liệu mong muốn. Kết quả cho thấy phân vùng thứ bậc có khả năng khai thác tập phổ biến và tập phổ biến đóng trong CSDL rất lớn.
IV ABSTRACT Although many methods have been proposed to enhance the efﬁciencies of data mining, little research has been devoted to the issue of scalability – that is, the problem of mining frequent itemsets when the size of the database is very large. This study proposes a methodology, hierarchical partitioning, for mining frequent itemsets in large databases, based on a novel data structure called the Frequent Pattern List (FPL). One of the major features of the FPL is its ability to partition the database, and thus transform the database into a set of sub-databases of manageable sizes. As a result, a divide-and-conquer approach can be developed to perform the desired data-mining tasks. Experimental results show that hierarchical partitioning is capable of mining frequent itemsets and frequent closed itemsets in very large databases.
V MỤC LỤC MỞ ĐẦU .......................................................................................................................... 1 1. Đặt vấn đề ............................................................................................................. 1 2. Tính cấp thiết của đề tài. ..................................................................................... 1 3. Mục tiêu của đề tài ............................................................................................... 2 4. Bố cục của luận văn ............................................................................................. 3 CHƢƠNG 1 GIỚI THIỆU VỀ KHAI THÁC DỮ LIỆU, CƠ SỞ DỮ LIỆU KÍCH THƢỚC LỚN................................................................................................................... 4 1.1 Tổng Quan về khai thác dữ liệu .......................................................................... 4 1.1.1 Mục tiêu của khai thác dữ liệu.................................................................................... 4 1.1.2 Các bƣớc chính của quá trình khai thác dữ liệu [12] ................................................. 6 1.1.3 Các dạng dữ liệu có thể khai thác đƣợc [12] ............................................................. 7 1.1.4 Hƣớng tiếp cận và các kỹ thuật trong khai thác dữ liệu [12] .................................... 8 1.1.5 Phân loại các hệ thống khai thác dữ liệu[3]............................................................... 9 1.1.6 Ứng dụng của khai thác dữ liệu[3] ............................................................................ 9 1.2 Cơ Sở Dữ Liệu Kích Thƣớc Lớn. ..................................................................... 10 CHƢƠNG 2 KHAI PHÁ TẬP PHỔ BIẾN .................................................................. 13 2.1 Phƣơng pháp tìm tập phổ biến ......................................................................... 13 2.2 Thuật toán Apriori ............................................................................................ 13 2.3 Phƣơng pháp dựa trên c y P-Tree ................................................................ 16 2.3.1 Cấu trúc cây P-Tree [4], [6] .................................................................................. 16 2.3.2 Xây dựng cây P-tree .............................................................................................. 17 2.3.3 Phép chiếu trên cây FP-tree ..................................................................................... 23 2.3.4 Tìm các tập phổ biến với thuật toán FP-growth ...................................................... 24 CHƢƠNG 3 PHƢƠNG PHÁP PHÂN VÙNG, PHÂN CẤP TRONG KHAI PHÁ TẬP PHỔ BIẾN ..................................................................................................................... 33 3.1 Giới thiệu ............................................................................................................. 33 3.2 Danh sách mẫu phổ biến ( PL) dùng để khai thác tập phổ biến .................. 34 3.3 Phân vùng thứ bậc với danh sách mẫu phố biến ............................................ 38
VI 3.3.1 Một ví dụ về phân vùng thứ bậc .............................................................................. 39 3.3.2 Các thuật toán để phân vùng thứ bậc CSDL và khai thác tập phổ biến .................. 44 3.4 Kết quả thực nghiệm phân vùng phân cấp ..................................................... 47 CHƢƠNG 4 KẾT LUẬN VÀ HƢỚNG NGHIÊN CỨU TRONG TƢƠNG LAI ........ 52
VII DANH MỤC CÁC TỪ VIẾT TẮT DB : Cơ sở dữ liệu giao dịch Conf : Độ tin cậy CSDL : Cơ sở dữ liệu Item : Mục Itemset : Tập mục FPL : Frequent Pattern List FI : Frequent Itemset KDD : Knowledge Discovery and Data Mining LSB : Least Significant Bit MSB : Most Significant Bit Minsup : min support minconf : Ngƣỡng tin cậy tối thiểu (minimum confidence) Supp : Support Sub-DB : Cơ sở dữ liệu con (phụ) TID : Transaction Identification
VIII DANH MỤC CÁC BẢNG Bảng 2.1: Cơ sở dữ liệu mẫu .......................................................................................... 14 Bảng 2.2: Mảng thứ tự danh mục đơn phổ biến f-list .................................................... 19 Bảng 2.3: CSDL sau khi sắp xếp theo thứ tự trong f-list ............................................... 19 Bảng 2.4: Nội dung CSDL{T} ....................................................................................... 26 Bảng 2.5: Nội dung CSDL{TD} .................................................................................... 27 Bảng 2.6: Nội dung CSDL{TA} .................................................................................... 28 Bảng 2.7: Nội dung CSDL{TW}.................................................................................... 29 Bảng 2.8: Nội dung CSDL{D} ...................................................................................... 30 Bảng 2.9: Nội dung CSDL{A} ....................................................................................... 31 Bảng 2.10: Nội dung CSDL{W} .................................................................................... 32 Bảng 3.1: ví dụ CSDL giao tác DB ............................................................................... 35 Bảng 3.2: CSDL con cấp đầu tiên đã đƣợc rút gọn Sub-DB’p ...................................... 40 Bảng 3.3: CSDL con Sub-DB’pb ................................................................................... 42
IX DANH MỤC CÁC HÌNH ẢNH Hình 1.1: Quá trình khai thác tri thức .............................................................................. 6 Hình 2.1: Minh hoạ thuật toán Apriori tìm tập mục phổ biến ....................................... 15 Hình 2.2: Cây FP-tree mới khởi tạo ............................................................................... 20 Hình 2.3: Cây FP- tree sau khi đọc giao dịch CWAT.................................................... 20 Hình 2.4: Cây FP-tree sau khi đọc giao dịch CWD ....................................................... 21 Hình 2.5: Cây FP-tree sau khi đọc giao dịch CWAT..................................................... 21 Hình 2.6: Cây FP-tree sau khi đọc giao dịch CWAD .................................................... 22 Hình 2.7: Cây FP-tree sau khi đọc giao dịch CWADT .................................................. 22 Hình 2.8: Cây FP-tree toàn cục ...................................................................................... 23 Hình 2.10: Tree{T} cục bộ tƣơng ứng với CSDL{T} ................................................... 27 Hình 2.11: Tree{TD} cục bộ tƣơng ứng với CSDL{TD} ............................................. 28 Hình 2.12: Tree{TA} cục bộ tƣơng ứng CSDL{TA}.................................................... 28 Hình 2.13: Tree{TW} cục bộ tƣơng ứng với CSDL{TW} ........................................... 29 Hình 2.14: Tree{D} cục bộ tƣơng ứng với CSDL{D} .................................................. 30 Hình 2.15: Tree{A} cục bộ tƣơng ứng với CSDL{A} .................................................. 31 Hình 2.16: Tree{W} cục bộ tƣơng ứng với CSDL{W} ................................................ 32 Hình 3.1: Các PL đƣợc xây dựng từ DB trong Bảng 3.1. ............................................ 36 Hình 3.2: Các CSDL con cấp đầu tiên từ DB của Bảng 3.1. ......................................... 39 Hình 3.3: FileHeader sau khi phân vùng cấp đầu tiên từ DB của Bảng 3.1. ................. 39 Hình. 3.4: Phân vùng cấp thứ hai cho CSDL con Sub-DB'p trong Bảng 2. .................. 41 Hình 3.5: FileHeader sau khi phân vùng cấp thứ hai cho CSDL con Sub-DB'p ........... 41 Hình 3.6: FPL của CSDL con Sub-DB'pb trong Bảng 3.3. ........................................... 42 Hình 3.7: ileHeader sau khi PL đƣợc xây dựng cho Sub-DB'pb ............................... 43 Hình 3.8: CSDL con cấp thứ 2 sau khi cắt và di chuyển trên Sub-DBpb trong hình.3.4 ........................................................................................................................................ 44 Hình 3.9: File Header sau khi cắt và di chuyển trên Sub-DBpb trong hình.3.4. ........... 44 Hình 3.10: Thuật toán FPL_HPDB. ............................................................................... 45 Hình 3.11: Thuật toán FPL_HP-Mining. ....................................................................... 46
X Hình 3.12: tập tin CSDL đã đƣợc mã hóa ...................................................................... 47 Hình 3.13: tạo dƣờng dẫn để lấy dữ liệu ........................................................................ 48 Hình 3.14: duyệt và sắp xếp danh sách .......................................................................... 48 Hình 3.15: phân vùng thành tập các CSDL con cấp đầu tiên (các node) ...................... 49 Hình 3.16: hiển thị các node sau khi phân vùng CSDL ................................................. 49 Hình 3.17: CSDL con cấp đầu tiên ................................................................................ 50 Hình 3.18: duyệt và sắp xếp danh sách CSDL cấp thứ nhất .......................................... 50 Hình 3.19: phân vùng thành tập các CSDL con cấp thứ 2 (các node) ........................... 51 Hình 3.20: danh sách CSDL cấp thứ 2 ........................................................................... 51
1 MỞ ĐẦU 1. Đặt vấn đề Trong thời đại ngày nay, với sự phát triển vƣợt bậc của công nghệ thông tin và sự phổ biến của Internet. Lƣợng dữ liệu tại các hệ thống thông tin này ngày càng trở nên phong phú, đa dạng và thực sự khổng lồ. Trong tình hình đó, việc chắt lọc những thông tin quý giá từ những dữ liệu khổng lồ này càng có ý nghĩa hơn bao giờ hết, nó đóng vai trò chìa khóa thành công cho sự phát triển của các tổ chức, cá nhân. Các thông tin tìm đƣợc có thể đƣợc vận dụng để cải thiện hiệu quả hoạt động của hệ thống thông tin ban đầu, cải thiện thời gian tìm kiếm, hay đƣa ra những dự đoán giúp cải thiện những quyết định trong tƣơng lai… Các kỹ thuật khai thác dữ liệu (data mining) ngày càng đƣợc quan tâm và ứng dụng rộng rãi trong nhiều lĩnh vực của cuộc sống nhƣ kinh tế, giáo dục, y tế, trong siêu thị,… 2. Tính cấp thiết của đề tài. Vì sự “bùng nổ” của thông tin nhƣ vậy nên ta phải có phƣơng pháp hiệu quả nhất để khai thác thông tin đó và chúng ta phải cân nhắc những yếu tố gì, tiêu chí nào để lựa chọn khai thác thông tin một cách hiệu quả nhất và nhanh nhất?. Một trong những công nghệ hiệu quả nhất là khai thác dữ liệu, đó là công nghệ dùng khai thác các mẫu hữu ích hay những kiến thức có ích từ cơ sở dữ liệu lớn [7]. Nhiệm vụ cơ bản và quan trọng nhất của khai thác dữ liệu là khai thác tập phổ biến, đó là tập các mặt hàng đƣợc thƣờng xuyên mua cùng với nhau trong một giao dịch, những công cụ trong khai thác tập phổ biến điển hình nhƣ phân tích so sánh, phân tích mẫu, phân loại, gom cụm và lƣu trữ dữ liệu [7].
2 Để nâng cao hiệu quả trong khai thác tập phổ biến, một số phƣơng pháp mới và cấu trúc dữ liệu linh hoạt đã đƣợc phát triển, chẳng hạn nhƣ P-tree, FP-Growth [6], Danh sách mẫu phổ biến và danh sách mẫu giao dịch [9], [10], [11], hay Khai thác mẫu khổng lồ một cách hiệu quả trong bộ dữ liệu lớn [8]. Tuy nhiên, khi cơ sở dữ liệu (viết tắt là CSDL) ngày càng phình to ra, thậm chí cấu trúc dữ liệu linh hoạt sẽ phát triển ra khỏi dung lƣợng bộ nhớ thì khả năng mở rộng các phƣơng pháp khai thác dữ liệu là một vấn đề phải đƣợc giải quyết. Các phƣơng pháp thông thƣờng sử dụng một lƣợc đồ phân vùng phẳng để phân vùng CSDL ban đầu thành một tập các CSDL con nhỏ hơn ở cùng cấp độ và sau đó tìm các tập phổ biến cục bộ trong các CSDL con này. Xử lý cuối cùng là quét lại CSDL ban đầu để kiểm tra xem các tập phổ biến cục bộ có phải là phổ biến toàn cục hay không. Điều này, tất nhiên phải mất thêm thời gian và tình hình sẽ xấu đi khi khai thác tập phổ biến đóng bởi vì không chỉ tần số của tập phổ biến đƣợc tính toán mà việc kiểm tra tập hợp con cũng phải đƣợc thực hiện. Đặc biệt những dữ liệu lớn vƣợt khỏi tầm kiểm soát của bộ nhớ máy tính, vậy ta phải sắp xếp, phân vùng phân cấp sao cho nhỏ hơn hoặc bằng bộ nhớ máy tính yêu cầu và tốc độ máy tính cũng sẽ nhanh gấp nhiều lần. Trong nghiên cứu này, tác giả luận văn sẽ tìm hiểu phƣơng pháp phân vùng phân cấp để khai thác tập phổ biến trong những CSDL lớn 3. Mục tiêu của đề tài Mục tiêu của đề tài tìm hiểu việc khai thác các tập phổ biến (frequent item sets) trong cơ sở dữ liệu lớn, dựa trên cấu trúc dữ liệu mới hay gọi là danh sách mẫu phổ biến PL ( requent Pattern List). Phƣơng pháp này phân vùng không gian tìm kiếm và chia cơ sở dữ liệu thành một tập các cơ sở dữ liệu con có kích thƣớc có thể quản lý đƣợc. Kết quả thu đƣợc là, tiếp cận phƣơng pháp chia để trị để khai thác dữ liệu mong muốn mà không cần phải quét lại dữ liệu ban đầu. Phƣơng pháp này đƣợc gọi là “Phƣơng pháp phân cấp trong khai thác tập phổ biến”, nó có thể cải thiện tốc độ và hiệu suất đáng kể trong khai thác tập phổ biến từ cơ sở dữ liệu lớn.
3 4. Bố cục của luận văn Luận văn đƣợc chia làm 5 phần: - Mở đầu - Chƣơng 1: Giới thiệu về khai thác dữ liệu, cơ sở dữ liệu kích thƣớc lớn. - Chƣơng 2: Khai phá tập phổ biến. - Chƣơng 3: Phƣơng pháp phân vùng, phân cấp trong khai phá tập phổ biến - Chƣơng 4: Kết luận và hƣớng phát triển trong tƣơng lai
4 CHƢƠNG 1 GIỚI THIỆU VỀ KHAI THÁC DỮ LIỆU, CƠ SỞ DỮ LIỆU KÍCH THƢỚC LỚN 1.1 Tổng Quan về khai thác dữ liệu 1.1.1 Mục tiêu của khai thác dữ liệu Với sự phát triển của phần mềm và phần cứng máy tính và số lƣợng khổng lồ và tăng tốc của dữ liệu. Từ khối dữ liệu rất lớn nhƣ vậy, cần phải có những công cụ tự động rút trích các thông tin và tri thức có ích, đó là khai thác dữ liệu (Data mining). Khai thác dữ liệu là quá trình tìm kiếm các mẫu mới, những thông tin tiềm ẩn trong các khối dữ liệu khổng lồ, khai thác có thể dự đoán những xu hƣớng trong tƣơng lai, hay giúp cho các công ty kinh doanh ra các quyết định kịp thời, hay dựa trên những sự kiện trong quá khứ của các hệ hỗ trợ ra quyết định (decision support systems - DSSs). Với các ƣu điểm trên, khai thác dữ liệu đƣợc ứng dụng rộng rãi trong các lĩnh vực nhƣ thƣơng mại, tài chính, y học, giáo dục và các lĩnh vực khác. Khai thác dữ liệu đƣợc định nghĩa, hay cách gọi khác của một thuật ngữ rất thông dụng là khám phá tri thức trong cơ sở dữ liệu (Knowledge Discovery in databases - KDD): là việc trích ra các tri thức chƣa đƣợc nhận ra, tiềm ẩn trong các tập dữ liệu lớn một cách tự động [1]  Một ví dụ tiêu biểu cho việc khai thác tập phổ biến [7] là phân tích giỏ hàng. Tiến trình này phân tích thói quen mua sắm của khách hàng bằng cách tìm ra sự kết hợp giữa các danh mục khác nhau từ trong giỏ hàng của họ. Việc khám phá ra những sự kết hợp này giúp ích cho các nhà bán lẻ mở rộng phân phối sản phẩm bởi họ thấu hiểu đƣợc những lợi nhuận có đƣợc từ những danh mục đƣợc khách hàng mua thƣờng xuyên. Cho một ví dụ thực tiễn hơn, nếu khách hàng
5 mua sữa, khả năng họ mua bánh mì trên cùng một lần đi siêu thị là nhƣ thế nào? Những thông tin này sẽ giúp cho các nhà bán lẻ tăng doanh thu và giúp họ  Lựa chọn kế hoạch tiếp thị và trƣng bày sản phẩm.  Kết quả phân tích giỏ hàng có thể giúp bạn lên kế hoạch tiếp thị, chiến lƣợc quảng cáo, trƣng bày sản phẩm hay lập danh mục bán hàng giảm giá …Ví dụ, kết quả phân tích cho thấy nếu khách hàng mua một máy vi tính thì có thể mua kèm phần mềm diệt vi rút. Từ đó, bạn sẽ có kế hoạch trƣng bày sản phẩm hợp lý hơn (Thông tin về máy tính đƣợc hiển thị kèm theo phần mềm diệt vi rút đƣợc khuyến khích mua).  Từ phân tích giỏ hàng bạn cũng có thể tìm ra một số quy tắc hay luật kết hợp có ích. Ví dụ, thông tin khách hàng mua máy vi tính và cũng mua phần mềm diệt vi rút đã đƣa ra luật kết hợp nhƣ sau: Computer  antivirus_software [support = 2%, confidence = 60%]  Độ hỗ trợ (support) và độ tin cậy (confidence) của luật là hai độ đo đƣợc quan tâm nhất. Luật có support = 2%, nghĩa là số lần giao dịch mà máy vi tính và phần mềm diệt vi rút đƣợc mua cùng nhau chiếm 2% trong tổng số các giao dịch; confidence=60%, nghĩa là có 60% khách hàng mua máy vi tính thì cũng sẽ mua phân mềm diệt vi rút.  Luật kết hợp đƣợc quan tâm nếu nó thỏa mãn cả hai ngƣỡng độ hỗ trợ nhỏ nhất (minimum support threshold) và độ tin cậy nhỏ nhất (minimum confidence threshold).
6 1.1.2 Các bƣớc chính của quá trình khai thác dữ liệu [12] Hình 1.1: Quá trình khai thác tri thức - Gom dữ liệu (Gathering): Tập hợp dữ liệu là bƣớc đầu tiên trong quá trình khai phá dữ liệu. Đây là bƣớc đƣợc khai thác trong một cơ sở dữ liệu, một kho dữ liệu và thậm chí các dữ liệu từ các nguồn ứng dụng Web. - Trích chọn dữ liệu (data selection): Ở giai đoạn này dữ liệu đƣợc lựa chọn hoặc phân chia theo một số tiêu chuẩn nào đó, ví dụ chọn tất cả những ngƣời có tuổi đời từ 25 – 35 và có trình độ đại học. - Tiền xử lý dữ liệu (data preprocessing): Giai đoạn thứ ba này là giai đoạn hay bị sao lãng, nhƣng thực tế nó là một bƣớc rất quan trọng trong quá trình khai phá dữ liệu. Một số lỗi thƣờng mắc phải trong khi gom dữ liệu là tính không đủ chặt chẽ, logic. Vì vậy, dữ liệu thƣờng chứa các giá trị vô nghĩa và không có khả năng kết nối dữ liệu. Giai đoạn này sẽ tiến hành xử lý những dạng dữ liệu không chặt chẽ nói trên. Những dữ liệu dạng này đƣợc xem nhƣ thông tin dƣ thừa, không có giá trị. Bởi vậy, đây là một