TIỂU LUẬN MÔN KHAI THÁC DỮ LIỆU
LỜI CẢM ƠN
«
Ngày nay, gom cụm dữ liệu là một nhiệm vụ chính trong môn học khai thác dữ liệu.Việc
gom cụm dữ liệu có rất nhiều ý nghĩa trong khoa học máy tính và trong đời sống con
người. Do vậy việc hiểu sâu sắc thuật toán gom cụm là điều vô cùng cần thiết cho những
ai học ngành công nghệ sáng tạo này. Để tạo ra nhiều ứng dụng về khai thác dữ liệu có ý
nghĩa cho ngành khoa học máy tính nói riêng và cho con người nói chung thì việc học kỹ
lưỡng và hiểu cặn kẻ về môn khai thác dữ liệu là điều vô cùng cần thiết, và dĩ nhiên
không thể thiếu kiến thức về gom cụm dữ liệu.
Do vậy:
Em xin chân thành cảm ơn nhà trường đã tạo mọi điều kiện thuận lợi cho chúng em được
đến trường và được học tập.
Em xin chân thành cảm ơn PGS.TS. Đỗ Phúc – Giảng viên môn học khai thác dữ liêu đã
truyền đạt những kiến thức vô cùng quý báu, xin chân thành cám ơn ban cố vấn học tập
và ban quản trị chương trình đào tạo thạc sĩ Công nghệ thông tin qua mạng của Đại Học
Quốc Gia TPHCM đã tạo điều kiện về tài liệu tham khảo để em có thể hoàn thành môn
học này.
Em xin chân thành cảm ơn
Nguyễn Thành Đệ
HVTH: Nguyễn Thành Đệ Trang: 1
TIỂU LUẬN MÔN KHAI THÁC DỮ LIỆU
1. Giới thiệu về kỹ thuật gom cụm trong Khai phá dữ liệu (Clustering
Techniques in Data Mining)
Gom cụm dữ liệu, quá trình nhóm những đối tượng tương tự, là một vấn đề nghiên
cứu và nổi tiếng. Một vài ứng dụng ban đầu là về thông kê. Trong những năm gần đây,
gom cụm dữ liệu là một kỹ thuật chính trong chuyên ngành khái thác dữ liệu. Hoạt động
cơ bản này có thể được áp dụng trong nhiều nhiều vụ như phân đoạn, phân lớp, mổ xẻ
không giám sát…
Phân cụm là kỹ thuật rất quan trọng trong khai phá dữ liệu, nó thuộc lớp các
phương pháp Unsupervised Learning trong Machine Learning. Có rất nhiều định nghĩa

Thuật toán K-Means được mô tả như sau
HVTH: Nguyễn Thành Đệ Trang: 3
TIỂU LUẬN MÔN KHAI THÁC DỮ LIỆU
Hình 2: Mô tả thuật toán k-means
Thuật toán K-Means thực hiện qua các bước chính sau:
1. Chọn ngẫu nhiên K tâm (centroid) cho K cụm (cluster). Mỗi cụm được đại diện
bằng các tâm của cụm.
2. Tính khoảng cách giữa các đối tượng (objects) đến K tâm (thường dùng khoảng
cách Euclidean)
3. Nhóm các đối tượng vào nhóm gần nhất
4. Xác định lại tâm mới cho các nhóm
5. Thực hiện lại bước 2 cho đến khi không có sự thay đổi nhóm nào của các đối
tượng
Ví dụ minh họa thuật toán K-Mean:
HVTH: Nguyễn Thành Đệ Trang: 4
TIỂU LUẬN MÔN KHAI THÁC DỮ LIỆU
Giả sử ta có 4 loại thuốc A,B,C,D, mỗi loại thuộc được biểu diễn bởi 2 đặc trưng X và Y
như sau. Mục đích của ta là nhóm các thuốc đã cho vào 2 nhóm (K=2) dựa vào các đặc
trưng của chúng.
Bước 1. Khởi tạo tâm (centroid) cho 2 nhóm. Giả sử ta chọn A là tâm của nhóm thứ nhất
(tọa độ tâm nhóm thứ nhất c1(1,1)) và B là tâm của nhóm thứ 2 (tạo độ tâm nhóm thứ hai
c2 (2,1)).
Hình 3. Vòng lặp 0
Bước 2. Tính khoảng cách từ các đối tượng đến tâm của các nhóm (Khoảng cách
Euclidean)
HVTH: Nguyễn Thành Đệ Trang: 5
TIỂU LUẬN MÔN KHAI THÁC DỮ LIỆU
Mỗi cột trong ma trận khoảng cách (D) là một đối tượng (cột thứ nhất tương ứng
với đối tượng A, cột thứ 2 tương ứng với đối tượng B,…). Hàng thứ nhất trong ma trận
khoảng cách biểu diễn khoảng cách giữa các đối tượng đến tâm của nhóm thứ nhất (c1)

Thuật toán K-Means có ưu điểm là đơn giản, dễ hiểu và cài đặt. Tuy nhiên, một số
hạn chế của K-Means là hiệu quả của thuật toán phụ thuộc vào việc chọn số nhóm K
(phải xác định trước) và chi phí cho thực hiện vòng lặp tính toán khoảng cách lớn khi số
cụm K và dữ liệu phân cụm lớn.
3. Thuật toán k-means song song
Trong phần trước đã nói về thuật toán k-means. Bây giờ em sẽ trình bày thuật toán
k-means song song. Đầu tiên chúng ta bắt đầu với vòng lặp mainLoop như hình 6. Vòng
lặp đầu tiên lý tưởng cho quá trình song song hóa của một đối tượng dựa trên phân phối
dữ liệu. Tuy nhiên vòng lặp song song hóa là vô cùng khó khăn. Vấn đề nằm trong một
liên kết giữa việc gọi hai hàm là getNearestMean và recalculateMean. Một đối tượng
HVTH: Nguyễn Thành Đệ Trang: 9
TIỂU LUẬN MÔN KHAI THÁC DỮ LIỆU
được chọn để xử lý sẽ gọi tất cả ba hàm bên trong vòng lặp phải hoàn thành trước khi đối
tượng khác được gọi. Do đó, đơn giản quá trình song song hóa trong mainLoop là không
thể. Mỗi bộ vi xử lý có thể, phụ thuộc các bộ vi xử lý khác, tìm cụm gần nhất cho tất cả
các đối tượng cục bộ. Thành viên của cụm cho mỗi đối tượng được định nghĩa, giá trị
chính và giá trị của các thành viên thường phải cập nhật thường xuyên.
Hình 6. Thuật toán K-Means song song
4. Cài đặt thuật toán k-means song song.
N điểm được thực hiện bởi thuật toán gom cụm K-means. Thuật toán này được cài
đặt bằng C# và có sử dụng thư viện xử lý song song(Task Parallel Library (TPL)).
Lớp tĩnh KMeansFactory để cài đặt Kmeans trên một mảng của khoảng cách và trọng
tâm.
public static class KMeansFactory
{
#region Distance & Centroid Function for double[]
public static double EuclideanDistace(double[] d1, double[] d2) //distance function
{
double dist = 0;
for (int i = 0; i < d1.Length; i++)

#endregion
public static BaseKMeans<double[]> CreateParallel()
{
BaseKMeans<double[]> nDimkMeans = new
ParallelKMeans<double[]>(EuclideanDistace, MeanAsCentroid);
return nDimkMeans;
}
public static BaseKMeans<double[]> CreateSequential()
{
BaseKMeans<double[]> nDimkMeans = new
SequentialKMeans<double[]>(EuclideanDistace, MeanAsCentroid);
return nDimkMeans;
}
}
Tạo một thực thể ParallelKMeans<T>(khoảng cách DistanceDelegate<T>, trọng tâm
CentroidDelegate<T>) sau đó gọi public T[] Run( int k, T[] inputs )
HVTH: Nguyễn Thành Đệ Trang: 12
TIỂU LUẬN MÔN KHAI THÁC DỮ LIỆU
Đây là một phiên bản có hỗ trợ đầy đủ, cơ bản nhất và chấp nhận hai đại diện để
tính toán khoảng cách giữa các đối tượng và tính toán trọng tâm. Những thuận lợi là khả
năng thực hiện gom cụm bất cứ một đối tượng nào và dễ dàng chuyển đổi từ thuật toán k-
means thành bất kỳ các thuật toán liên quan như k-median/k-mediod, hoặc sử dụng bất kỳ
khoảng cách như khoảng cách Manhattan.
Thuật toán này chia ra ba bộ phận chính, mỗi bộ phận đều có tiềm năng để chạy song
song, nó được chia ra ở việc khởi tạo khu vực của những điểm gần nhất với các trọng
tâm, và nó tính toán lại trọng tâm. Vòng lặp khởi tạo như bên dưới, để song song hóa
ConcurrentBag<T>[] inputMap = new ConcurrentBag<T>[resInput.K];
Parallel.For( 0, resInput.K, //For each mean
( i ) =>
{

} );
Mỗi vòng lặp sẽ cập nhật lại trọng tâm, chúng phân vùng dựa vào các trọng tâm.
Bằng cách làm này, sẽ giảm số lượng khóa mà chỉ cần một đối tượng duy nhất nắm giữ.
Đối tượng giữ theo dõi toàn bộ thay đổi trong những trọng tâm, vì thế có thể biết được
khi nào thuật toán hội tụ.
HVTH: Nguyễn Thành Đệ Trang: 14
TIỂU LUẬN MÔN KHAI THÁC DỮ LIỆU
Để giảm thêm nữa số lượng truy cập của đối tượng lồng nhau. TPL cung cấp các
biến cục bộ tiến trình và những tiến trình cuối cùng, các biến đó hoạt động trên toàn bộ
các phân vùng, nhưng chỉ có tiến trình được tạo. Tiến trình cuối là một hàm delegate
được gọi khi hoàn thành mỗi tiến trình. Đây là nơi hợp với kết quả của tất cả các tiến
trình với nhau và truy cập những đối tượng với nhau.
int totalEpsilon = 0;
Parallel.For<int>( 0, resInput.K, () => 0, // For each mean
( i, _loopState, epsilonSubtotal ) =>
{
ConcurrentBag<T> myInputList = inputMap[i];
T newCentroid = Centroid( myInputList );
T lastCentroid = resInput.Result[i];
double epsilon = Distance( newCentroid, lastCentroid );
if( epsilon > 0 )
epsilonSubtotal++;
resInput.Result[i] = newCentroid;
return epsilonSubtotal;
},
( epsilonSubtotal ) =>
{
Interlocked.Add( ref totalEpsilon, epsilonSubtotal );
HVTH: Nguyễn Thành Đệ Trang: 15
TIỂU LUẬN MÔN KHAI THÁC DỮ LIỆU

for (int i = 0; i < vectorSize; i++)
{
newCentroid[i] /= count;
}
return newCentroid;
}
#endregion
Factory tạo 2 đối tượng sử dụng thuật toán k-means song và thuật toán k-mean tuần tự:
HVTH: Nguyễn Thành Đệ Trang: 16
TIỂU LUẬN MÔN KHAI THÁC DỮ LIỆU
seqKMeans = PointKMeansFactory.Create(false);
parKMeans = PointKMeansFactory.Create(true);
public static BaseKMeans<double[]> CreateParallel()
{
BaseKMeans<double[]> nDimkMeans = new
ParallelKMeans<double[]>(EuclideanDistace, MeanAsCentroid);
return nDimkMeans;
}
public static BaseKMeans<double[]> CreateSequential()
{
BaseKMeans<double[]> nDimkMeans = new
SequentialKMeans<double[]>(EuclideanDistace, MeanAsCentroid);
return nDimkMeans;
}
TPL sử dụng kỹ thuật chia để trị để phân vùng những vòng lặp. Tuy nhiên, TPL
cung cấp cho chúng ta một sự lựa chọn phân vùng vòng lặp trong bất kỳ cách lựa chọn
nào. Chúng ta thử nghiệm với phân vùng vòng lặp bằng số lượng các bộ vi xử lý. Kết quả
cho thấy TPL cho ra một kết quả tốt và những sự kiện đó ít tốn kém về phân vùng và tài
nguyên hơn.
Các Giao diện của chương trình:

Tuy nhiên, thuật toán k-means cũng có những khuyết điểm sau:
- Không đảm bảo đạt được tối ưu toàn cục và kết quả đầu ra phụ thuộc nhiều vào
việc chọn k điểm khởi đầu. Do đó có thể phải chạy lại thuật toán với nhiều bộ khởi
HVTH: Nguyễn Thành Đệ Trang: 23
TIỂU LUẬN MÔN KHAI THÁC DỮ LIỆU
đầu khác nhau để có thể đạt kết quả đủ tốt. Trong thực tế, có thể áp dụng thuật giải
di truyền để phát sinh các bộ khởi đầu.
- Cần phải xác định trước số cụm.
- Khó xác định số cụm thực sự mà không gian dữ liệu có. Do đó có thể phải thử với
các giá trị k khác nhau.
- Khó phát hiện các loại cụm có hình dạng phức tạp và nhất là các dạng cụm không
lồi.
- Không thể xử lý nhiễu và mẫu cá biệt.
- Chỉ có thể áp dụng khi tính được trọng tâm.
6. Tài liệu tham khảo
[1] PGS.TS. Đỗ Phúc. Giáo Trình Khai Thác Dữ Liệu
[1] M.R. Anderberg. Cluster Analysis for Applications . Academic Press, 1973.
[2] John A. Hatigan. Clustering Algorithms . John Wiley and Sons, 1975.
[3] W. Kloesgen and J.M. Zytkow. Knowledge discovery in database terminology.
Advances in Knowledge Discovery and Data Mining, pages 573{592, 1996.
[4] J.B. MacQueen. Some methods for classication and analysis of multivariate ob-
servations. Proceedings of the 5th Berkeley Symposium on Mathematical Statistics
and Probability , 1967.
[5] C.F. Olson. Parallel algorithms for hierarchical clustering. Parallel Computing, 21,
1995.
[6] E.M. Rasmussen and P. Willett. Eciency of hierarchical agglomerative clustering
using the icl distributed array oricessor. Journal of Documentation , 45(1), 1989.
[7] Helmuth Spaeth. Cluster Analysis Algorithms. John Wiley and Sons, 1980.
[8] http://bis.net.vn
[9] http://www.codethinked.com/multi-threaded-k-means-clustering-in-net-40