ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
TIỂU LUẬN MÔN KHAI THÁC DỮ LIỆU
MỘT SỐ THUẬT TOÁN CƠ BẢN
TRONG KHAI THÁC DỮ LIỆU
Giảng viên hướng dẫn : PGS.TS Đỗ Phúc
Học viên thực hiện : Lương Chấn Viễn
MSHV : CH1101155
Lớp : Cao học khóa 6
Tp Hồ Chí Minh, tháng 11 năm 2012
MỤC LỤC
Chương 1: KHAI PHÁ LUẬT KẾT HỢP
Trong phần này ta xem xét các vấn đề phát hiện ra các luật kết hợp giữa các mặt hàng
trong một cơ sở dữ liệu lớn các giao dịch bán hàng và trình bày thuật toán Apiori để giải
quyết vấn đề này. Đánh giá thực nghiệm cho thấy thuật toán Apiori tuyến tính với số
lượng (kích thước) giao dịch và số lượng của các món hàng trong cơ sở dữ liệu.
1.1 Bài toán thực tế
Khi công nghệ mã vạch phát triển cho phép các tổ chức bán lẻ có thể một cách dễ
dàng thu thập và lưu trữ số lượng lớn các dữ liệu bán hàng (basket data). Trong đó
mỗi một mẫu tin (record) trong dữ liệu như vậy thường bao gồm ngày giao dịch và
các mặt hàng đã mua trong giao dịch. Các tổ chức này xem cơ sở dữ liệu như phần
quan trọng của cơ sở tiếp thị. Họ quan tâm đến khả năng tiếp thị định hướng trên
thông tin trong cơ sở dữ liệu, cho phép các nhà tiếp thị của họ có thế phát triển và
thực hiện các chương trình tiếp thị cũng như tùy chỉnh và chiến lược tiếp thị.
Một ví dụ về luật kết hợp là 98 trong tổng số khách hàng mua lốp xe và phụ tùng ô tô
cũng mua các dịch vụ liên quan. Tìm tất cả các luật như vậy để làm cơ sở cho tiếp thị
chéo giữa các mặt hàng. Các ứng dụng khác có thể kể đến như thiết kế catalog, buôn
bán phụ tùng, cách bố trí cửa hàng cũng như phân khúc khách hàng trên thói quen
mua hàng. Các cơ sở dữ liệu có liên quan đến các ứng dụng này thường là rất lớn. Do
đó, các thuật toán liên quan cần phải nhanh (độ phức tạp nhỏ) để có thể sử dụng được.
1.2 Mô hình bài toán

nhỏ; đầu tiên là tập phổ biến có 1 phần tử. Từ các tập phổ biến nhỏ đó, ta suy ra
các tập lớn hơn gọi là tập ứng cử viên. Và duyệt cơ sở dữ liệu để tìm tập phổ
biến dựa trên tập ứng cử viên đó.
1.4.2 Ký hiệu
Giả sử ta có một thứ tự sắp xếp các mặt hang ký hiệu là .
Khi ta nói một itemset (, tập các mặt hànx+_g hay một giac dịch), ta xem như itemset
đã được sắp xếp, tức mặt hàng thứ bé hơn mặt hàng thứ . Nếu ta ký hiệu mặt hàng
thứ trong là thì
5
Một -itemset là một itemset có phần tử như sau
Bảng 1-1. Bảng ký hiệu
1.4.3 Thuật toán tìm tập phổ biến
Thuật toán tìm tập phổ biến dựa trên tính chất của tập phổ biến như sau
Algorithm Apriori
for while do
generate from
end
1.4.4 Thuật toán sinh ứng cử viên Apriori-gen
Như vậy, bài toán cần giải quyết là sinh tập các -itemset làm ứng cử viên để tìm tập
các -itemset phổ biến từ tập các -itemset.
Điều kiện của tập ứng cử viên :
• Tối tiểu: tức dựa trên thông tin của ta có thể loại các itemset chắc chắn không phổ
biến. Nghĩa là:
thì
Trong đó ký hiệu cho quan hệ tập con có phần tử.
• Đầy đủ: .
6
Algorithm Apriori-gen
Input:
Output:

itemset có thuộc bằng cách tìm kiếm trên cây. Nếu xem thời gian di chuyển từ
node cha đến node con là hằng số thì cần tốn thời gian (do duyệt đến chiều sâu
thứ của cây). Vậy mỗi ứng cử trong bước lược được kiểm tra với chi phí .
- Ví dụ về quá trình tìm phần tử thông qua duyệt cây.
Sau khi kết thúc quá trình xây dựng cây, các node trên cây tương ứng là các tập
phổ biến. Các node lá của cây là các tập phổ biến tối đại.
9
1.6 Chương trình demo
10
Bố cục giao diện chương trình gồm 2 phần, phần bên trái cho phép nhập đề bài, phần
bên phải hiển thị quá trình tìm tập phổ biến cũng như luật kết hợp.
Quá trình tìm kiếm luật kết hợp được chia làm 2 phân tương ứng với 2 bước của thuật
toán tìm luật tổng quát:
Bước 1: Tìm tất cả các tập phổ biến bằng thuật toán Apiori
11
Kết luận về tập phổ biến và tập phổ biến tối đại
Bước 2: Sinh luật từ tập phổ biến tìm được ở bước 1
12
13
Chương 2: PHÂN LỚP – CLASSIFICATION
2.1. Classifier
Định nghĩa: một classifier (hàm phân lớp) là một hàm ánh xạ một vector đầu vào
(input feature vector) đến một lớp . Trong đó là không gian đặc tính (feature space).
là tập các lớp cần phân loại. Ở đây ta giả sử các mỗi vector đầu vào chỉ thuộc một lớp
duy nhất, tức các lớp này loại trừ lẫn nhau (mutually exclusive).
Mục tiêu của ta là cần huấn luyện hay tìm một hàm từ một tập huấn luyện ban đầu.
Mỗi tập huấn luyện là một cặp , quá trình huấn luyện như vậy được gọi là học có
giám sát (supervised learning).
Trong nội dung hiện tại, ta chỉ quan tâm đến các hàm phân lớp xác suất, là các hàm
gán nhãn dựa trên việc tính toán .

2.4. Chương trình Demo
Phần nhập đề bài
Phần nhập lời giải tương ứng
16
17
Chương 3: GOM CỤM – CLUSTERING
Bài toán gom cụm: khi cho trước một tập dữ liệu huấn luyện thì mục tiêu của bài toán là
gom nhóm các các dữ liệu tương tự nhau vào một tập cụm. Mỗi một cụm đại diện cho các
phần tử trong cụm đó.
3.1Thuận toán gọm cụm -means
-mean clustering algorithm
Đầu vào:
• Tập dữ liệu huấn luyện .
• Số lượng các cụm: .
1. Khởi tạo các trọng tâm của các cụm .
2. Lặp cho đến khi hội tụ:
Tính cụm của :
Tính lại tọa độ của cụm :
Bảng 1-2Thuận toán gọm cụm k-mean
Việc khởi tạo các trọng tâm của các cụm một cách ngẫu nhiên bằng cách chọn ngọn
nhiên example trong tập dữ liệu (tuy nhiên không nhất thiết phải như vậy).
Mỗi lần lặp của thuật toán, ta gán lại nhãn cụm cho bằng cách chọn cụm có trọng
tâm gần nhất. Sau đó, ta di chuyển trọng tâm của cụm đến trọng tâm của các điểm
thuộc cụm. Thuật toán hội tụ có thể kiểm tra bằng cách (1) nếu trong tâm mới của
cụm không thay đổi hoặc thay đổi rất nhỏ thì ta nói thuật toán hội tụ. Cách (2) là
kiểm tra các nhãn có thay đổi qua mỗi bước lặp hay không.
18
Hình trên thể hiện quá trình chạy của thuật toán. Các dữ liệu huấn luyện được thể hiện
qua các chấm trên đồ thị (hình 1). Các trọng tâm của cum thể hiện qua các dấu x trên
đồ thị (hình 2). Trong trường hợp của ví dụ và trong tậm của 2 cụm được khởi tạo

Có thể thấy quan hệ là một quan hệ tương đương vì nó thỏa các tính chất phản xạ, đối
xứng và bắc cầu. Do đó quan hệ có thể phân hoạch tập vũ trụ thành các lớp tương
23
đương . Ta ký hiệu lớp tương của đối tượng là là tập các đối tượng bất khả phân biệt
với dựa vào thuộc tính .
4.3Xấp xỉ tập hợp
Ta thường quan tâm việc phân hoạch tập vũ trụ thành các lớp, khái niệm. Tuy nhiên,
một số khái niệm không thể được định nghĩa rõ ràng nếu dựa vào các thuộc tính của
đối tượng.
Xấp xỉ tập hợp cho ta định nghĩa những khái niệm như thế một cách xấp xỉ, bằng 2
tập rõ.
Cho trước một hệ thống thông tin và một tập con . Ta xấp xỉ tập bằng tập thuộc tính
bởi 2 tập rõ (crisp set) như sau
Khi đó nếu một đối tượng thì ta nói chắc chắn thuộc . Nếu thì ta nói có thể thuộc ,
ngược lại nếu thì chắc chắn không thuộc .
Các tính chất của , :
4.4Các rút gọn - reducts
Ta có thể loại bỏ một số thuộc tính mà không làm xấu đi việc phân lớp. Ta nói là một
rút gọn của nếu khả năng phân biệt của bằng . Khi đó ta nói bảo toàn quan hệ bất
khả phân biệt của cũng như là bảo toàn xấp xỉ tập hợp. Nếu một tập bảo toàn quan
24
hệ bất khả phân biệt thì mọi tập thuộc tính cũng bảo toàn quan hệ bất khả phân biệt.
Do đó, ta chỉ xét những tập tối tiểu ( sao cho bảo toàn quan hệ bất khả phân biệt)
được gọi là reduct của .
Định nghĩa miền -dương của thuộc tính :
Cho một hệ thống thông tin , thuộc tính quyết định và tập thuộc tính .
Ta nói thuộc tính là phân biệt được nếu , ngược lại, là bất khả phân biệt.
Định nghĩa: Reduct
Ta nói là một reduct của nếu mọi thuộc tính là bất khả phân biệt và .
Ta gọi tập tất cả reduct của là . Khi đó, tập tất cả các thuộc tính điều kiện không thể