Chương 1 PHÂN TÍCH CHÙM CÁC PHẦN TỬ ROI RAC Phan tích chùm các phần tử rời rac là một phương pháp thống kê da biến, nhằm nhóm các phần tử rời rạc ban đầu thành các chùm, sao cho các phần tử trong một chùm thì tương tự nhau, và các phần tử thuộc các chùm khác nhau thì không tương tự nhau, theo một số tiêu chí được định trước. Nói một cách khác, bài toán CDE là bài toán phân tích chùm, với đối tượng là các phần tử rời rạc. Trong bài toán phân tích chùm, các phần tử rời rạc là đối tượng được quan tâm nghiên cứu nhiều hơn so với các đối tượng khác (hàm mật độ xác suất, khoảng, chuỗi thời gian.), nên thông thường khi đề cập đến phân tích chùm, ta thường hiểu đó là bài toán CDE. Trong chương này, luận án trình bày một số tiêu chuẩn nhằm đánh giá sự tương tự của các phần tử rời rạc, một số thuật toán phân tích chùm được sử dụng phổ biến, một số tiêu chuẩn nhằm đánh giá chất lượng chùm được xây dựng.
Bên cạnh đó, trong chương này, luận án cũng trình bày một số đề xuất mới của nhóm nghiên cứu bao gồm: hệ số tương tự chùm các phan tử rời rac (Similar Coefficient of Cluster for Discrete Elements, SCD) và thuật toán phân tích chim tự động, không thứ bậc dựa trên SCD [Phd].1 Sự tương tự của các phan tử rời rac 1.1 Sự tương tự của hai phần tử rời rac Khoảng cách là đại lượng thường dùng để đánh giá sự tương tự của hai phần tử rời rac. Khoảng cách giữa hai phan tử là một metric, nghĩa là nếu d(x, y) là khoảng cách của hai phần tử x và y (x,y € R”) thi đ(x,y) phải thỏa các điều kiện sau đây: 1. Dau “=” xảy ra khi x = y. Theo 3 điều kiện trên, ta có thé định nghĩa khoảng cách giữa 2 phan tử theo nhiều cách khác nhau.
Cho hai điểm x = (#1,#2,.,n) € JR", khi đó ta có một số khoảng cách phổ biến như sau. e® Khoảng cách Euclide: e® Khoảng cách city-block: da(%,y) = À ` lai — yil- (1.2) m øe Khoảng cách Chebyshev: e Khoảng cách Minkowski bậc m: (1. i=l Ta có một số nhận xét sau: e Khoảng cách Euclide thường được sử dụng phổ biến nhất trong các áp dụng của nhiều vấn đề hiện tại. Nó mô tả độ lớn của đoạn thang nối trực tiếp hai điểm x va y.
e Khoảng cách city-block mô tả tổng độ lớn của n đoạn gấp khúc nối hai điểm x,y€R". Mỗi đoạn trong n đoạn nay song song với | trục tương ứng trong n trục của hệ quy chiếu. e Khoảng cách Chebyshev mô tả đoạn thang có độ dài lớn nhất trong ø đoạn gấp khúc đã được đề cập trong khoảng cách city-block. e Khoảng cách Minkowski bậc m là một khoảng cách mang tính tổng quát.
Với những m khác nhau, khoảng cách Minkowski bậc m sẽ tương ứng với một loại khoảng cách khác nhau. Độ lớn của khoảng cách Minkowski bậc m sẽ càng giảm khi m càng tăng.2 Sự tương tự của một nhóm các phần tử rời rac Thông thường, khi chùm được xây dựng, ta cần đánh giá chất lượng của các chùm được tạo. Để làm được điều này, ta cần có các khoảng cách nhằm đánh giá sự tương tự của một nhóm các phần tử rời rạc. Trong lĩnh vực phân tích chùm, các khoảng cách này được gọi là “khoảng cách nội bộ” (intracluster distance).
Gọi x và y là hai điểm dữ liệu n chiều bất kỳ thuộc nhóm C, x,y € R”, một số khoảng cách phổ biến 6 dùng để đánh giá sự tương tự của một nhóm hữu hạn các phần tử rời rac như sau. e Khoảng cách max (Complete Diameter Distance): dmax(C) = max d(x,y).5) x,yeŒ e Khoảng cách trung bình (Average Diameter Distance ): 8„(C) = cóc D> dx.7) xeŒC Trong các công thức trên, d là khoảng cách giữa hai phần tử rời rac đã được định nghĩa ở phần trước, tùy vào loại khoảng cách d được sử dụng mà ta lại có nhiều kết quả khác nhau; |C| là số phần tử có trong nhóm (chùm) C; v là trọng tâm (điểm trung bình) của nhóm (chùm) Œ được tính bởi v = a » x.3 Sự tương tự giữa hai nhóm các phần tử rời rac Các thang đo đánh giá sự tương tự giữa hai nhóm các phần tử rời rạc thường được quan tâm trong việc đánh giá chất lượng của một kết quả phân tích chùm khi ta muốn biết các chùm được xây dựng có sự tách biệt như thế nào. Bên cạnh đó, chúng thường được sử dụng trong phân tích chùm theo hướng tiếp cận thứ bậc, khi ta xây dựng các chùm mới dựa trên thông tin các chùm được tạo trước đó. Gọi x, và y là hai điểm dữ liệu n chiều bất kỳ lần lượt thuộc hai nhóm hữu hạn C, và C2, một số thang đo dùng để đánh giá sự tương tự giữa hai nhóm các phan tử rời rac Cy và C2 được tóm tắt bởi các công thức bên dưới.
12 e Khoảng cách min: yeG e hoảng cách max: Amax(C1, C2) = max d(x, y).2 Một số thuật toán phân tích chùm cho các phần tử rời rac Tùy vào khía cạnh đang xem xét mà các thuật toán phân tích chùm các phần tử rời rạc có thể được phân chia thành nhiều hướng tiếp cận khác nhau. Hình trình bày tổng quan các hướng tiếp cận của bài toán CDE. Theo đó, bài toán CDE có thể chia thành hai hướng tiếp cận chính là phân tích chùm không mờ và phân tích chùm mờ. Trong hướng tiếp cận không mờ, mỗi phần tử được gán vào một chùm cụ thể và không thuộc vào các chùm khác; ngược lại, trong hướng tiếp cận mờ, mỗi phần tử đồng thời thuộc vào tất cả các chùm với các mức độ phụ thuộc nhất định.
Trong mỗi hướng tiếp cận mờ hoặc không mờ, ta lại có nhiều hướng tiếp cận khác nhau như phân tích chùm dựa vào khoảng cách/trọng tâm (distance/centroids based clustering), phân tích chim dựa vào mô hình (model-based clustering), phân tích chùm dựa vào mật độ (density-based clustering). Ngoài ra, một số hướng tiếp cận khác như phân tích chùm thứ bậc và phân tích chùm tự động cũng có thể được kết hợp với cả phân tích chim mờ hoặc không mờ để cho ra một số hướng tiếp cận khác nhau. Phần này của luận án sẽ tập trung trình bày một số thuật toán phân tích chùm phổ biến theo hướng tiếp cận không thứ bậc-không mờ. Trong hướng tiếp cận không thứ bậc-không mờ này, luận án lựa chọn trình bày ba thuật toán cổ điển đại diện cho ba hướng phân tích chùm: dựa vào trọng tâm, dựa vào mật độ và dựa vào mô hình.
Các thuật toán cụ thể bao gồm: thuật toán k- trung bình (k-means), thuật toán phan tích chùm DBSCAN và thuật toán cực đại hóa kỳ vọng (EM). Do đây là các thuật toán đã phổ biến và được sử dụng như các phương pháp đối chiếu trong luận án, luận án chỉ giới thiệu sơ lược các nguyên lý và các bước thực hiện chính. Các phân tích toán học và chứng minh hội tụ có thể được tham khảo tại [BỊ B71 56]. 13 Distance- based clustering Density- based clustering NON-FUZZY CLUS- TERING Model- CLUSTERING aetsin FOR DISCRETE ELEMENT Others Hình 1.1: Tổng quan các thuật toán CDE 1.1 Thuật toán k-means Cho trước tập dữ liệu cần phân tích chùm X gồm phần tử rời rac n chiều: X = {XI,Xa,.,Xw}, (x; € IR"), và cho trước số chùm k, thuật toán k-means chia tập dữ liệu X thành k chùm sao cho tổng khoảng cách giữa các phần tử đến trọng tâm chùm chứa nó là nhỏ nhất.
Thuật toán k-means được trình bay chi tiết bởi Thuật toán 1.1 và được minh họa bởi Hình |L.2| Step 1 Step 2 Step 3 Step 3 (repeat) Hình 1.2: Minh hoa các bước của thuật toán k-means 14 Thuật toán 1. Khởi tạo k trọng tâm của k chùm {v.v " vi") một cách ngẫu nhiên. Tìm phân vùng tương ứng với k trọng tâm bằng cách gán từng phần tử vào chùm chứa trọng tam gần nó nhất, nghĩa là tìm phan vùng C9) = {ci CỤ), " c9} At VỚI co = {x EX : d(x, vl) = min đ(x, vn] .11) j Bước 3: Cập nhật các trọng tâm bởi công thức: 1 vị) = So x.12) Ic! ? xeo Bước 4: Lặp lại Bước 2 va Bước 3 cho đến khi thuật toán hội tụ, nghĩa là các trọng tam không đổi qua hai vòng lặp liên tiếp, vl) = vi) vị, 1. Thuật toán phan tích chùm DBSCAN Thuật toán k-means ở phần trên xây dựng chùm dựa vào khoảng cách từ các phần tử đến trọng tâm, do đó, các chùm được xây dựng thường mang dạng hình cầu.
Điều này dẫn đến một số điểm không phù hợp khi ứng dụng cho dữ liệu mà các chùm có dạng bất kỳ. Thuật toán DBSCAN được đề xuất bởi là một thuật toán có thể giải quyết được bài toán phân tích chùm với hình dạng bất kỳ. Thuật toán này cũng thực hiện việc tính toán khoảng cách giữa các phần tử, tuy nhiên, các khoảng cách này không được áp dụng một cách trực tiếp để xây dựng chùm mà được sử dụng để xét tính liên thông của các điểm dữ liệu. Chính việc các điểm dữ liệu có liên thông với nhau hay không sẽ quyết định đến việc chúng có thuộc cùng một chùm hay không.
Trong thuật toán DBSCAN, ta cần xác định trước hai tham số gồm: e và minpts. Cho tập dữ liệu X, với x; va x; là hai điểm thuộc X. Nếu d(x;,x;) < e, thi x; được gọi là “liên thông trực tiếp” từ x;, va x; được gọi là điểm lõi. Nếu tồn tại một day X1,X2,.,X sao cho x; liên thông trực tiếp với x;41, Vi = 1,2,.,n — 1, thi x, được gọi là “liên thông” từ xị.
Thuật toán DBSCAN bắt đầu bằng việc chọn ngẫu nhiên một điểm dữ liệu, nếu điểm dữ liệu được chọn là điểm lõi, tất cả những điểm liên thông với điểm này được xét vào cùng một chùm. Quá trình này được lặp đến khi tất các điểm trong bộ dữ liệu đã được xét vào một chùm nhất định. Tính “liên 15 thông” và “liên thông trực tiếp” giữa các điểm được minh họa bởi Hình Thuật toán DBSCAN được minh họa bởi Hình và được trình bày chi tiết trong Thuật toán 1. Lien thong rp tuctiep gg lw 08 Lien thong 0 ® Chưm1 © Chum2 0.3: Minh hoa tính chất liên thong giữa các điểm dữ liệu (b) Vòng lặp 1 T „20x94 T „2220 XNK.
II ee eer Mec ee "1. Mã sa VN SSBO 08 09 1 ° 06 07 (c) Vong lap 2 (d) Két qua phan chim Hình 1.4: Minh hoa thuật toán DBSCAN Thuật toán 1.2 Khởi tao tập dữ liệu tạm thời D = X, thiết lập hai tham số ¢ và minpts.