MỤC LỤC
LỜI NÓI ĐẦU ....................................................................................................3
CHƯƠNG 1. GIỚI THIỆU VỀ KHAI PHÁ DỮ LIỆU........................................5
1.1. Khái niệm khai phá dữ liệu .......................................................................5
1.2. Kiến trúc của một hệ thống khai phá dữ liệu .............................................6
1.3. Các giai đoạn của quá trình khai phá .........................................................7
1.4. Các phương pháp khai phá dữ liệu ............................................................9
1.5. Các cơ sở dữ liệu phục vụ cho khai phá dữ liệu.......................................10
1.6. Các ứng dụng của khai phá dữ liệu..........................................................11
1.7. Các thách thức và khó khăn trong khai phá dữ liệu..................................12
CHƯƠNG 2. TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU..................................13
2.1. Khái niệm và mục tiêu của phân cụm dữ liệu ..........................................13
2.1.1. Khái niệm về phân cụm dữ liệu ........................................................13
2.1.1.1. Mục tiêu của phân cụm dữ liệu...................................................13
2.1.1.2. Các yêu cầu đối với kỹ thuật phân cụm dữ liệu ..........................14
2.1.1.3. Các kiểu dữ liệu và các thuộc tính trong phân cụm.....................14
2.1.2. Các kỹ thuật tiếp cận trong phân cụm dữ liệu ...................................16
2.1.2.1. Phương pháp phân cụm phân hoạch ..........................................16
2.1.2.3. Phương pháp phân cụm phân cấp ...............................................16
2.1.2.3. Phương pháp phân cụm dựa trên mật độ.....................................17
2.1.2.4. Phân cụm dựa trên lưới ..............................................................18
2.1.2.5. Phân cụm dựa trên mô hình........................................................19
2.1.2.6. Phân cụm có dữ liệu ràng buộc...................................................19
2.1.3.Một số phương pháp trong phân cụm dữ liệu .....................................21
2.1.3.1. Các thuật toán trong phân cụm phân hoạch ................................21
2.1.3.2. Các thuật toán trong phân cụm phân cấp ....................................27
2.1.3.3.Các thuật toán phân cụm dựa trên mật độ ....................................28
2.1.3.4.Phân cụm dựa trên lưới ...............................................................29
2.1.3.5.Phân cụm dựa trên mô hình.........................................................30
2.2. Phân cụm cụm mờ...................................................................................31
2.2.1. Tổng quan về phân cụm mờ..............................................................31

nhiều hiệu quả và thành công lớn đối với khoa học cũng như các hoạt động thực
tế khác, trong đó có lĩnh vực khai phá dữ liệu là một lĩnh vực mang lại hiệu quả
thiết thực cho con người. Khai phá dữ liệu đã giúp chúng ta thu được những tri
thức hữu ích từ cơ sở dữ liệu hay từ các kho dữ liệu khổng lồ khác. Cơ sở dữ liệu
được sử dụng trong các đơn vị, tổ chức kinh doanh, quản lý khoa học chứa đựng
nhiều thông tin tiềm ẩn, phong phú và đa dạng đòi hỏi phải có những phương
pháp nhanh, phù hợp, chính xác, hiệu quả để lấy được những thông tin có ích để
làm tư liệu đối với từng trường hợp cụ thể của con người. Những tri thức thu
được từ cơ sở dữ liệu trên sẽ là nguồn thông tin hỗ trợ cho chúng ta trong từng
công việc chi tiết, cụ thể. Việc tiến hành công việc như vậy chính là thực hiện
quá trình phát hiện tri thức trong cơ sở tri thức ( Knowledge Discovery in
Database) mà trong đó là kỹ thuật khai phá dữ liệu (Data Mining) cho phép phát
hiện những tri thức tiềm ẩn. Ngay từ ngày đầu khi xuất hiện, Data mining đã trở
thành một trong những xu hướng nghiên cứu phổ biến trong lĩnh vực công nghệ
tri thức như nhiều thành tựu nghiên cứu của Data mining đã được áp dụng trong
thực tế. Data mining có nhiều hướng nghiên cứu quan trọng và một trong các
hướng cơ bản trong khai phá dữ liệu là quá trình phân cụm dữ liệu (Data
Clustering). Phân cụm dữ liệu có thể hiểu là quá trình tìm kiếm tri thức, phân
tách (hay chuẩn hóa dữ liệu) thành các cụm hay các tập dữ liệu từ một tập cơ sở
dữ liệu lớn để thu được nguồn thông tin có ích phục vụ cho từng nhu cầu thực tế
của mỗi người, mỗi tổ chức.
Qua thực tế cho thấy, việc thu thập những thông tin quan trọng còn tiềm ẩn
trong cơ sở dữ liệu lớn là rất cần thiết. Vì vậy, việc phân cụm dữ liệu, trích lọc
những thông tin quan trọng phục vụ cho từng nhu cầu của mỗi người đã mang lại
nhiều lợi ích quan trọng góp phần giảm bớt lượng dữ liệu dư thừa hoặc không
cần thiết trong từng ứng dụng thực tế.

3



Khai phá dữ liệu là một bước trong quá trình khám phá tri thức, gồm các
thuật toán khai thác dữ liệu chuyên dụng dưới một số quy định về hiệu quả tính
toán chấp nhận được để tìm ra các mẫu hoặc các mô hình trong dữ liệu.

Hình 1: Quá trình khai phá dữ liệu

5


Vậy ta có thể khái quát hóa khái niệm Khai phá dữ liệu là một quá trình tìm
kiếm, phát hiện các tri thức mới, hữu ích, tiềm ẩn trong CSDL lớn. Cụ thể hơn đó
là tiến trình lọc, sản sinh những tri thức hoặc các mẫu tiềm ẩn, chưa biết thông tin
hữu ích từ các cơ sở dữ liệu lớn.
1.2. Kiến trúc của một hệ thống khai phá dữ liệu
Khai phá dữ liệu là quá trình rút trích thông tin bổ ích từ những kho dữ liệu
lớn. Khai phá dữ liệu là quá trình chính trong khai phá tri thức từ cơ sở dữ liệu.
Kiến trúc của một hệ thống khai phá dữ liệu có các thành phần như sau:

Hình 2: Kiến trúc một hệ thống khai phá dữ liệu
 CSDL, kho dữ liệu hoặc lưu trữ thông tin khác: đây là một hay các tập
CSDL, các kiểu dữ liệu hay các dạng khác nhau của thông tin được lưu
trữ. 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.
 Máy chủ CSDL (Database or Warehouse server): máy chủ có trách nhiệm
lấy dữ liệu thích hợp dựa trên những yêu cầu khám phá của người dùng.
 Cơ sở tri thức (Knowledge-base): đây là miền tri thức dùng để tìm kiếm
hay đánh giá độ quan trọng của các mẫu kết quả thu được. Tri thức này có

6



7


Quá trình khai phá dữ liệu được thể hiện như hình sau:

Hình 3: Quá trình khai phá dữ liệu
Trong đó :
 Xác định nhiệm vụ: xác định chính xác cá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 và tiền xử lý dữ liệu: Thu thập dữ liệu liên quan và tiền xử lý
chúng sao cho thuật toán khai phá dữ liệu có thể hiểu được. Đây là quá
trình khó khăn, có thể gặp phải rất nhiều vướng mắc như: dữ liệu phải
được sao ra nhiều bản, quản lí tập các dữ liệu, phải lặp đi lặp lại nhiều lần
toàn bộ quá trình…
Quá trình khai phá dữ liệu trải qua ba bước:
Bước 1: Lọc dữ liệu được thực hiện trong quá trình tiền xử lý. Đầu tiên là
tích hợp và chỉnh sửa. Dữ liệu được thu thập từ nhiều nguồn khác nhau nên có
thể có những sai sót, dư thừa và trùng lặp. Lọc dữ liệu là cắt bỏ dư thừa để dữ
liệu được định dạng thống nhất. Dữ liệu sau khi lọc và chỉnh sửa sẽ nhỏ hơn, xử
lý nhanh hơn.
Bước 2: Khai phá dữ liệu là công việc chính, sử dụng các thuật toán khác
nhau để khai phá các kiến thức tiềm ẩn trong dữ liệu.
Bước 3: quá trình ước lượng kết quả khai phá theo yêu cầu của người dùng.
Các kết quả được ước lượng bởi những quy tắc nào đó, nếu kết quả cuối cùng
không thỏa mãn yêu cầu thì phải làm lại với kỹ thuật khác cho đến khi có kết quả
mong muốn.

8



9


Từ những lớp dữ liệu hoặc những khái niệm được xác định trước, dự đoán
giá trị của những đối tượng quan tâm.
Một kỹ thuật phân lớp dữ liệu được Han và Kamber đưa ra là cây quyết
định. Mỗi nút của cây đại diện một quyết định dựa vào giá trị thuộc tính tương
ứng.
Phân nhóm dữ liệu: Phân nhóm là kỹ thuật khai phá dữ liệu tương tự như
phân lớp dữ liệu. tuy nhiên, sự phân nhóm là quá trình học không giám sát, là quá
trình nhóm những đối tượng vào trong những lớp tương đương, những đối tượng
trong cùng nhóm phải tương đương nhau và khác với những đối tượng khác trong
các nhóm khác. Trong phân nhóm đối tượng, những đối tượng được nhóm lại
cùng nhau dựa vào sự giống nhau của chúng. Sự giống nhau giữa những đối
tượng được xác định bởi những chức năng giống nhau. Thông thường sự giống
nhau về định lượng như khoảng cách hoặc độ đo khác được xác định bởi những
chuyên gia trong lĩnh vực.
1.5. Các cơ sở dữ liệu phục vụ cho khai phá dữ liệu
Dựa vào những kiểu dữ liệu mà kỹ thuật khai phá áp dụng, có thể chia dữ
liệu thành các loại khác nhau:
Cơ sở dữ liệu quan hệ: Đến nay hầu như dữ liệu được lưu trữ dưới dạng cơ
sở dữ liệu quan hệ. Cơ sở dữ liệu quan hệ có cấu trúc cao, dữ liệu được
mô tả bởi một tập các thuộc tính và lưu trong bảng. Khai phá dữ liệu trên
cơ sở dữ liệu quan hệ chủ yếu tập trung khai phá mẫu.
Cơ sở dữ liệu giao tác: là tập hợp những bản ghi giao dịch , trong đa số các
trường hợp chúng là những bản ghi các dữ liệu hoạt động của doanh
nghiệp, tổ chức. Khai phá dữ liệu trên cơ sở dữ liệu giao tác tập trung vào
khai phá luật kết hợp tìm mối tương quan giữa những mục dữ liệu của bản
ghi giao dịch.

 Chuẩn đoán triệu chứng, phương pháp trong điều trị y học.
 Tìm kiếm, đối sánh các hệ Gene và thông tin di truyền trong sinh học.
 Phân tích tình hình tài chính, thị trường, dự báo giá cổ phiếu trong tài
chính, thị trường và chứng khoán.
 Phân tích dữ liệu marketing, khách hang.
 Điều khiển và lập lịch trình.
 Bảo hiểm, Giáo dục, Y tế……

11


1.7. Các thách thức và khó khăn trong khai phá dữ liệu
Khai phá dữ liệu liên quan đến nhiều ngành, nhiều lĩnh vực trong thực tế, vì
vậy các thách thức và khó khăn ngày càng nhiều, càng lớn hơn. Dưới đây là một
số khó khăn cần được quan tâm và giải quyết:
 Các cơ sở dữ liệu lớn, các tập dữ liệu cần xử lý có kích thước lớn. Thực tế,
kích thước của các tập dữ liệu thường ở mức tera- byte .
 Mức độ nhiễu cao hoặc dữ liệu bị thiếu.
 Số chiều các thuộc tính lớn.
 Thay đổi dữ liệu và tri thức có thể làm cho các mẫu đã phát hiện không
còn phù hợp.
 Quan hệ giữa các trường phức tạp.
 Việc giao tiếp với người sử dụng và kết hợp các tri thức.
 Tích hợp với các hệ thống khác.
Cơ sở dữ liệu có thể lớn về số lượng các bản ghi, về số lượng các thuộc tính
trong CSDL . Để giải quyết vấn đề này, người ta đưa ra một ngưỡng nào đó cho
CSDL bằng các cách như chiết xuất mẫu, xấp xỉ hoặc xử lý song song.
Để khắc phục việc dữ liệu thay đổi phụ thuộc theo thời gian ta cần phải
chuẩn hóa,cải tiến, nâng cấp các mẫu, các mô hình và có thể xem các thay đổi
này là mục đích của khai phá và tìm kiếm các mẫu bị thay đổi.

2.1.1.1. Mục tiêu của phân cụm dữ liệu
Mục tiêu của phân cụm dữ liệu là xác định được bản chất nhóm trong tập
dữ liệu chưa có nhãn. Nó có thể là không có tiêu chuẩn tuyệt đối “tốt” mà có thể
không phụ thuộc vào kết quả phân cụm. Vì vậy, nó đòi hỏi người sử dụng phải
cung cấp tiêu chuẩn phân cụm một cách rõ ràng theo cách mà kết quả phân cụm
sẽ đáp ứng yêu cầu.
Hiện nay chưa có một phương pháp phân cụm tổng quát nào có thể giải
quyết chọn vẹn cho tất cả các dạng cấu trúc dữ liệu. Hơn nữa, các phương pháp
phân cụm cần có một cách thức biểu diễn cấu trúc của dữ liệu, và với mỗi cách
thức biểu khác nhau sẽ có tương ứng một thuật toán phân cụm phù hợp.

13


2.1.1.2. Các yêu cầu đối với kỹ thuật phân cụm dữ liệu
 Việc phân cụm dữ liệu đều nhằm thỏa mãn các yêu cầu cơ bản sau:
 Có khả năng mở rộng
 Thích nghi với các kiểu dữ liệu khác nhau.
 Khám phá ra các cụm với hình thù bất kỳ.
 Tối thiểu lượng tri thức cần cho xác định các tham số đầu vào.
 Ít nhạy cảm với thứ tự của dữ liệu vào.
 Thích nghi với dữ liệu nhiễu cao.
 Ít nhạy cảm với các tham số đầu vào.
 Thích nghi với dữ liệu đa chiều.
 Dễ hiểu, dễ cài đặt và khả thi.
2.1.1.3. Các kiểu dữ liệu và các thuộc tính trong phân cụm
Bao gồm 2 kiểu dữ liệu:
Dữ liệu dựa trên kích thước miền:
Thuộc tính liên tục (Continuous Attribute) : nếu miền giá trị của nó là vô
hạn không đếm được

i

, trong đó q là số tự

i 1

nhiên dương.
Khoảng cách Euclide : d ( x , y ) 

n
2
 ( x i  y i ) , đây là trường hợp đặc biệt
i 1

của khoảng cách Minskowski trong trường hợp q=2.
n
Khoảng cách Manhattan : d ( x, y )   | xi  yi | , đây là trường hợp đặc biệt
i 1
của khoảng cách Minskowski trong trường hợp q=1.
Khoảng cách cực đại : d ( x, y )  Max n | xi  yi | , đây là trường hợp của
i 1
khoảng cách Minskowski trong trường hợp q-> .
 Thuộc tính tỉ lệ (Ratio Scale) : là thuộc tính khoảng nhưng được xác định
một cách tương đối so với điểm mốc, thí dụ như thuộc tính chiều cao hoặc
cân nặng lấy điểm 0 làm mốc. Có nhiều cách khác nhau để tính độ tương
tự giữa các thuộc tính tỷ lệ. Có thể sử dụng công thức tính logarit cho mỗi
thuộc tính xi.
Trong các thuộc tính dữ liệu trình bày ở trên, thuộc tính định danh và thuộc
tính có thứ tự gọi chung là thuộc tính hạng mục (Categorical), thuộc tính khoảng
và thuộc tính tỉ lệ được gọi là thuộc tính số (Numeric).

cấu trúc có dạng hình cây, cây phân cấp này được xây dựng theo kỹ thuật đệ quy.
Có 2 cách phổ biến đó là:
 Bottom –up (hòa nhập nhóm)
 Top- down (phân chia nhóm)

16


Hình 4: Các chiến lược phân cụm phân cấp
Có nhiều trường hợp kết hợp cả hai phương pháp phân cụm phân hoạch và
phân cụm phân cấp, nghĩa là kết quả thu được của phương pháp phân cấp có thể
cải tiến thông qua bước phân cụm phân hoạch.
2.1.2.3. Phương pháp phân cụm dựa trên mật độ
Kỹ thuật này nhóm các đối tượng dữ liệu dựa trên hàm mật độ xác định, mật
độ là số các đối tượng lân cận của một đối tượng dữ liệu theo một nghĩa nào
đó.Với cách tiếp cận này, khi dữ liệu đã được xác định thì nó tiếp tục phát triển
them các đối tượng dữ liệu mới miễn là số các đối tượng lân cận này phải lớn
hơn một ngưỡng đã được xác định trước.
Ưu điểm:
 Phát hiện ra được các cụm dữ liệu với hình thù bất kỳ.
 Khắc phục được phần tử ngoại lai hoặc trị nhiễu tốt.
Nhược điểm:
 Việc xác định các tham số mật độ của thuật toán là khó khăn trong khi các
tham số này lại có tác động rất lớn đến kết quả phân cụm.

17


2.1.2.4. Phân cụm dựa trên lưới
Phương pháp này thích hợp với dữ liệu nhiều chiều, dựa trên cấu trúc dữ

Phương pháp có hai cách tiếp cận chính:
 Mô hình thống kê
 Mạng nơron
Phương pháp này gần giống với phương pháp phân cụm dựa trên mật độ vì
chúng phát triển các cụm riêng biệt nhằm cải tiến các mô hình đã được xác định
trước đó, có khi nó không băt đầu với một số cụm cố định và không sử dụng
cùng một khái niệm mật độ cho các cụm.
2.1.2.6. Phân cụm có dữ liệu ràng buộc
Các thuật toán trên hầu hết cung cấp ít cách thức cho người dung để xác
định các ràng buộc trong thế giới thực cần phải thỏa mãn quá trình phân cụm. Vì
vậy, để phân cụm dữ liệu không gian hiệu quả hơn, các nghiên cứu bổ sung cần
được thực hiện để cung cấp cho người dùng khả năng kết hợp các ràng buộc
trong thuật toán phân cụm.

19


Hình 6: Các cách mà cụm có thể đưa ra
Một số nhánh nghiên cứu được phát triển trên cơ sở của phương pháp này:
Phân cụm thống kê: dựa trên các khái niệm phân tích hệ thống, người ta sử dụng
các độ đo tương tự để phân hoạch các đối tượng nhưng chúng chỉ áp dụng cho
các dữ liệu có thuộc tính số.
 Phân cụm khái niệm: áp dụng cho dữ liệu hạng mục, chúng phân cụm các
đối tượng theo các khái niệm mà chúng xử lý.
 Phân cụm mờ: sử dụng kỹ thuật phân cụm mờ để phân cụm dữ liệu, các
thuật toán này chỉ ra lược đồ phân cụm thích hợp với tất cả các hoạt động
đời sống hàng ngày, chúng xử lý dữ liệu thực không chắc chắn.
 Phân cụm mạng Kohonen: loại phân cụm này dựa trên khái niệm của
mạng nơron. Mạng Kohonen có:
 Tầng nơron vào: Mỗi nơron vào tương ứng với mỗi thuộc tính của

Mục đích: sinh ra k cụm dữ liệu {C1,C2…, Ck} từ một tập dữ liệu ban đầu
gồm n đối tượng trong không gian d chiều Xi = (xi1,xi2, …, xid) )(i=1..n), sao cho
hàm tiêu chuẩn: E  k  xC D 2 ( x  m i ) đạt giá trị tối thiểu.
i
i 1

Với mi là trọng tâm của cụm Ci, D là khoảng cách giữa hai đối tượng.

Hình 8: Tính toán trọng tâm các cụm mới
Thuật toán phân hoạch K-means do MacQeen đề xuất trong lĩnh vực thống
kê năm 1967, mục đích của thuật toán k-means là sinh ra k cụm dữ liệu {C1, C2,
…,Ck} từ một tập dữ liệu chứa n đối tượng trong không gian d chiều Xi = (xi1, xi2,
…, xid) ( i  1, n ), sao cho hàm tiêu chuẩn : E  k  xC D 2 ( x  m i )
i

(2.1)

i 1

đạt giá trị tối thiểu. Trong đó : mi là trọng tâm của cụm Ci, D là khoảng cách giữa
hai đối tượng ( khoảng cách Euclide). Trọng tâm của một cụm là một véc tơ,
trong đó giá trị của mỗi phần tử của nó là trung bình cộng của các thành phần
tương ứng của các đối tượng vectơ dữ liệu trong cụm đang xét. Tham số đầu vào
của thuật toán là số cụm k, và tham số đầu ra của thuật toán là các trọng tâm của
các cụm dữ liệu. K-means bao gồm các bước cơ bản như sau:
InPut : Số cụm k và các trọng tâm cụm {mj}kj=1 ;


OutPut : Các cụm Ci  i  1, k  và hàm tiêu chuẩn E đạt giá trị tối thiểu


 Số lượng và các tham số là do người dùng nhập, nên nếu đầu vào khác
nhau thì kết quả các cụm sẽ khác nhau

23


Thuật toán K-tâm:
Ý tưởng :Thuật toán K-tâm phân cụm dữ liệu hỗn hợp là mở rộng của thuật
toán K-means cho dữ liệu hỗn hợp trong đó có sử dụng khái niệm Mode của dữ
liệu hỗn hợp, khi đã mở rộng các miền giá trị của thuộc tính có thứ tự và xác định
khoảng cách giữa các đối tượng.
Thuật toán này hội tụ sau một số hữu hạn bước lặp tới điểm cực tiểu địa



phương của hàm P như sau: p  k

j
2
 d x, z
j 1 xC j

Ta xét D là tập N đối tượng x

i



N


ii) Thuộc tính số: Aj thuộc tính số nếu DOM(Aj) là tập số thực.

24


ii) Thuộc tính thứ tự: Nếu DOM(Aj) là tập hữu hạn và có thứ tự hoàn toàn
thì Aj được gọi là thuộc tính có thứ tự (chẳng hạn: DOM(Aj) = { không đau, hơi
đau, đau và rất đau}..
Trên miền giá trị DOM(Aj) của một thuộc tính Aj ta xác định các khoảng
cách như sau.
Định nghĩa 2:  x,y DOM(Aj) hàm dj(x,y) xác định bởi :
Nếu Aj là thuộc tính số thì dj(x,y)= x  y

(2.3)

Nếu Aj là thuộc tính thứ tự và DOM(Aj) = a 1j ,..., a kj  với a 1j  a 2j  ...  a kj , ta
lấy một hàm đơn điệu fj: DOM(Aj)→ [0,1] sao cho f j (a 1j )  0; f j (a kj )  1 (Hàm

i 1
này có thể là : f j ( a ij ) 
). Khi đó dj(x,y)= │fj(x) - fj(y) │
k 1
0 khi : x  y
 1 khi : x  y

Nếu Aj là dữ liệu định danh thì d j(x,y)= 

(2.4)
(2.5)


25

(2.7)