Đồ án Tìm hiểu phương pháp phân cụm

kiện của tiền đề, thì bộ dữ liệu đó có lớp chỉ ra trong kết luận”. 1.5.9. Hồi quy. Về mặt khái niệm, nhiệm vụ hồi quy tương tự như phân lớp. Điểm khác nhau là ở chỗ thuộc tính dự báo là liên tục thay vì rời rạc. Việc dự báo các giá trị số thường được thực hiện bởi công cụ thống kê cổ điển, chẳng hạn như hồi quy tuyến tính. Tuy nhiên, các phương pháp mô hình hóa cũng có thế sử dụng, chẳng hạn như cây quyết định, trong đó các nút lá là một mô hình tuyến tính phát sinh tập các lớp giả (pseudo-class) có giá trị thuộc tính đích tương tự nhau, sau đó sử dụng phương pháp quy nạp bằng tổ hợp các giá trị của thuộc tính lớp cho các bộ dữ liệu theo luật. 1.5.10. Tổng hợp. Nhiệm vụ của tổng hợp chính là việc sản sinh ra các mô tả đặc trưng cho một lớp. Các mô tả này là một kiểu tổng hợp, tóm tắt mô tả các đặc tính chung của tất cả ( hoặc hấu hết ) các bộ dữ liệu dạng giỏ mua hàng thuộc một lớp. Các mô tả đặc trưng thể hiện dưới dạng các luật thường có khuôn dạng :”nếu một bộ dữ liệu thuộc về một lớp đã chỉ ra trong tiền đề, thì bộ dữ liệu đó có tất cả cá thuộc tính đã nêu ra trong kết luận ”. Các luật này có những đặc trưng khác biệt so với các luật phân lớp. Luật phát hiện đặc trưng cho một lớp chỉ được sản sinh khi các bộ dữ liệu đã thuộc về lớp đó. 1.5.11. So sánh các nhiệm vụ phát hiện tri thức. Phát hiện tri thức hướng CSDL có độ chính xác cao. Đây là điểm khác biệt quan trọng so với các đòi hỏi của các nhiệm vụ phát hiện tri thức khác. Nhiệm vụ phát hiện sự sai lệch liên quan đến phát hiện tri thức ở mức ý nghĩa do người dùng quy định. Nhiệm vụ xác định liên kết cũng tương tự với ngưỡng tin cậy và ngưỡng hỗ trợ (tần suất tương đối ). Nhiệm vụ tổng hợp liên quan đến phát hiện tri thức có tính phổ biến cao tức là luật được phát hiện phải bao hàm một số dữ liệu. Các nhiệm vụ như phát hiện sự phụ thuộc, nhân quả, phân lớp và hồi quy chủ yếu liên quan đến phát hiện tri thức có độ chính xác cao. CHƯƠNG 2 PHƯƠNG PHÁP PHÂN CỤM VÀ CÁC CÁCH TIẾP CẬN Trong chương này sẽ trình bày về một số phương pháp phân cụm và hướng tiếp cận. Vấn đề về phân cụm dữ liệu Các kiểu dữ liệu và độ đo tương tự Khái niệm về tương tự và phi tương tự Các phương pháp tiếp cận trong phân cụm dữ liệu. 2.1. Vấn đề về phân cụm dữ liệu. Phân cụm dữ liệu là một lĩnh vực đang được phát triển mạnh mẽ như thống kê, học máy, nhận dạng, Data mining, Ở một mức cơ bản nhất, người ta đã đưa ra định nghĩa phân cụm dữ liệu như sau [1][7]: " Phân cụm dữ liệu là một kỹ thuật trong DATA MINING, nhằm tìm kiếm, phát hiện các cụm, các mẫu dữ liệu tự nhiên tiềm ẩn, quan tâm trong tập dữ liệu lớn, từ đó cung cấp thông tin, tri thức hữu ích cho việc ra quyết định" Như vậy , phân cụm dữ liệu là quá trình phân chia một tập dữ liệu ban đầu thành các cụm dữ liệu sao cho các phần tử trong một cụm "tương tự" (Similar) với nhau và các phần tử trong các cụm khác nhau sẽ "phi tương tự" (Dissimilar) với nhau. Số các cụm dữ liệu được phân ở đây có thể được xác định trước theo kinh nghiệm hoặc có thể được tự động xác định của phương pháp phân cụm. Chúng ta có thể minh hoạ vấn đề phân cụm như hình 3 sau đây : Hình 3 : Mô phỏng vấn đề phân cụm dữ liệu Ở hình trên, sau khi phân cụm ta thu được bốn cụm trong đó các đối tượng "gần nhau" hay là "tương tự" thì được xếp vào một cụm, trong khi đó các đối tượng "xa nhau" hay là "phi tương tự" thuộc về các cụm khác nhau. Trong phân cụm dữ liệu khái niệm (Concept Clustering) thì hai hoặc hoặc nhiều đối tượng cùng được xếp vào một cụm nếu chúng có chung một định nghĩa về khái niệm hoặc chúng xấp xỉ với các khái niệm mô tả cho trước. Ở đây phân cụm dữ liệu không sử dụng khái niệm “tương tự” như đã trình bày ở trên. Vấn đề thường gặp trong phân cụm dữ liệu đó là hầu hết các dữ liệu cần cho phân cụm đều có chứa dữ liệu "nhiễu" (noise) do quá trình thu thập thiếu chính xác hoặc thiếu đầy đủ, vì vậy cần xây dựng chiến lược cho bước tiền xử lý dữ liệu nhằm khắc phục hoặc loại bỏ "nhiễu" trước khi bước vào giai đoạn phân tích phân cụm dữ liệu. 2.2. Các kiểu dữ liệu và độ đo tương tự Trong phân cụm dữ liệu, các đối tượng dữ liệu cần phân tích có thể là con người, các thực thể phần mềm, Các đối tượng này thường được diễn tả dưới dạng các đặc tính hay còn gọi là thuộc tính của nó. Các thuộc tính này là các tham số cho giải quyết vấn đề phân cụm dữ liệu và sự lựa chọn chúng có tác động đáng kể đến các kết quả của phân cụm. Phân loại khái niệm các kiểu thuộc tính khác nhau là một vấn đề cần giải quyết đối với hầu hết các tập dữ liệu nhằm cung cấp các phương tiện thuận lợi để nhận dạng sự khác nhau của các phần tử dữ liệu. Dưới đây là cách phân lớp dựa trên hai đặc trưng là: kích thước miền (Domain Size) và hệ đo (Measurement Scale) Cho một CSDL D chứa n đối tượng trong không gian k chiều trong đó x,y,z là các đối tượng thuộc D : x=(x1,x2,..,xk);y=(y1,y2,..,yk);z=(z1,z2,..,zk), trong đó xi, yi, zi với là các đặc trưng hoặc thuộc tính tương ứng của các đối tượng x,y,z. Vì vậy, hai khái niệm “các kiểu dữ liệu” và “các kiểu thuộc tính dữ liệu” được xem là tương đương với nhau, như vậy, chúng ta sẽ có các kiểu dữ liệu sau : 2.2.1. Phân loại các kiể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, nghĩa là giữa hai giá trị tồn tại vô số giá trị khác. Thuộc tính rời rạc (DiscretteAttribute) : Nếu miền giá trị của nó là tập hữu hạn, đếm được. Lớp các thuộc tính nhị phân là trường hợp đặc biệt của thuộc tính rời rạc mà miền giá trị của nó chỉ có 2 phần tử được diễn tả như : Yes / No hoặc False/true, 2.2.2 Phân loại các kiểu dữ liệu dựa trên hệ đo Giả sử rằng chúng ta có hai đối tượng x, y và các thuộc tính xi, yi tương ứng với thuộc tính thứ i của chúng. Chúng ta có các lớp kiểu dữ liệu như sau : Thuộc tính định danh (nominal Scale): đây là dạng thuộc tính khái quát hoá của thuộc tính nhị phân, trong đó miền giá trị là rời rạc không phân biệt thứ tự và có nhiều hơn hai phần tử - nghĩa là nếu x và y là hai đối tượng thuộc tính thì chỉ có thể xác định là x y hoặc x=y. Thuộc tính có thứ tự (Ordinal Scale): là thuộc tính định danh có thêm tính thứ tự, nhưng chúng không được định lượng. Nếu x và y là hai thuộc tính thứ tự thì ta có thể xác định là x y hoặc x=y hoặc x>y hoặc x<y. Thuộc tính khoảng (Interval Scale) : Nhằm để đo các giá trị theo xấp xỉ tuyến tính. Với thuộc tính khoảng, chúng ta có thể xác định một thuộc tính là đứng trước hoặc đứng sau thuộc tính khác với một khoảng là bao nhiêu. Nếu xi>yi thì ta nói x cách y một khoảng xi – yi tương ứng với thuộc tính thứ i. 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 đầy ý nghĩa. 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), trong khi đó thì thuộc tính khoảng và thuộc tính tỉ lệ được gọi là thuộc tính số (Numeric). Người ta còn đặc biệt quan tâm đến dữ liệu không gian (Spatial Data). Đây là loại dữ liệu có các thuộc tính số khái quát trong không gian nhiều chiều, dữ liệu không gian mô tả các thông tin liên quan đến không gian chứa đựng các đối tượng, thí dụ như thông tin về hình học, Dữ liệu không gian có thể là dữ liệu liên tục hoặc rời rạc : Dữ liệu không gian rời rạc : có thể là một điểm trong không gian nhiều chiều và cho phép ta xác định được khoảng cách giữa các đối tượng dữ liệu trong không gian. Dữ liệu không gian liên tục : bao chứa một vùng trong không gian. 2.3. Khái niệm về tương tự và phi tương tự. Khi các đặc tính của dữ liệu được xác định, người ta đi tìm cách thích hợp để xác định "khoảng cách" giữa các đối tượng, hay là phép đo tương tự dữ liệu. Đây là các hàm để đo sự giống nhau giữa các cặp đối tượng dữ liệu, thông thường các hàm này hoặc là để tính độ tương tự (Similar) hoặc là tính độ phi tương tự (Dissimilar) giữa các đối tượng dữ liệu. Giá trị của hàm tính độ đo tương tự càng lớn thì sự giống nhau giữa đối tượng càng lớn và ngược lại, còn hàm tính độ phi tương tự tỉ lệ nghịch với hàm tính độ tương tự. Độ tương tự hoặc độ phi tương tự có nhiều cách để xác định, chúng thường được đo bằng khoảng cách giữa các đối tượng. Tất cả các cách đo độ tương tự đều phụ thuộc vào kiểu thuộc tính mà chúng ta phân tích. Thí dụ, đối với thuộc tính hạng mục (Categorical) người ta không sử dụng độ đo khoảng cách mà sử dụng một hướng hình học của dữ liệu. Tất cả các độ đo dưới đây được xác định trong không đo gian metric. Bất kỳ một metric nào cũng là một độ đo, nhưng điều ngược lại không đúng. Để tránh sự nhầm lẫn, thuật ngữ độ đo ở đây đề cập đến hàm tính độ tương tự hoặc hàm tính độ phi tương tự. Một không gian metric là một tập trong đó có xác định các "khoảng cách" giữa từng cặp phần tử, với những tính chất thông thường của khoảng cách hình học. Nghĩa là, một tập X (các phần tử của nó có thể là những đối tượng bất kỳ ) các đối tượng dữ liệu trong CSDL D như đã đề cập ở trên được gọi là một không gian metric nếu: Với mỗi cặp phần tử x,y thuộc X đều xác định theo một quy tắc nào đó, một số thực δ(x,y), được gọi là khoảng cách giữa x và y. Quy tắc nói trên thoả mãn hệ tính chất sau : (i)δ(x,y)>0 nếu x ≠y (ii)δ(x,y)=0 nếu =y (iii) δ(x,y) = δ(y,x) với mọi x,y (iv) δ(x,y) ≤ δ(x,z)+δ(z,y) Hàm δ(x,y) được gọi là một metric của không gian. Các phần tử của X được gọi là các điểm của không gian này. Sau đây là các phép đo độ tương tự áp dụng đối với các kiểu dữ liệu khác nhau [1][3]: Thuộc tính khoảng : Sau khi chuẩn hoá, độ đo phi tương tự của hai đối tượng dữ liệu x, y được xác định bằng các metric khoảng cách như sau : Khoảng cách Minskowski : , trong đó q là số tự nhiên dương. Khoảng cách Euclide :, đây là trường hợp đặc biệt của khoảng cách Minskowski trong trường hợp q=2. Khoảng cách Manhattan : , đây là trường hợp đặc biệt của khoảng cách Minskowski trong trường hợp q=1. Khoảng cách cực đại : , đây là trường hợp của khoảng cách Minskowski trong trường hợp q-> ¥. Thuộc tính nhị phân : Trước hết chúng ta có xây dựng bảng tham số sau : y:1 y:0 x:1 + x:0 + + + Bảng 1 : Bảng tham số Trong đó : =+++, các đối tượng x, y mà tất cả các thuộc tính tính của nó đều là nhị phân biểu thị bằng 0 và 1. Bảng trên cho ta các thông tin sau : là tổng số các thuộc tính có giá trị là 1 trong cả hai đối tượng x,y. là tổng số các giá trị thuộc tính có giá trị là 1 trong x và 0 trong y là tổng số các giá trị thuộc tính có giá trị là 0 trong x và 1 trong y là tổng số các giá trị thuộc tính có giá trị là 0 trong x và y Các phép đo độ tương đồng đối với dữ liệu thuộc tính nhị phân được định nghĩa như sau : Hệ số đối sánh đơn giản : , ở đây cả hai đối tượng x và y có vai trò như nhau, nghĩa là chúng đối xứng và có cùng trọng số. Hệ số Jacard : , chú ý rằng tham số này bỏ qua số các đối sánh giữa 0-0. Công thức tính này được sử dụng trong trường hợp mà trọng số của các thuộc tính có giá trị 1 của đối tượng dữ liệu có cao hơn nhiều so với các thuộc tính có giá trị 0, như vậy các thuộc tính nhị phân ở đây là không đối xứng. Thuộc tính định danh : Độ đo phi tương tự giữa hai đối tượng x và y được định nghĩa như sau : , trong đó m là số thuộc tính đối sánh tương ứng trùng nhau, và p là tổng số các thuộc tính. Thuộc tính có thứ tự : Phép đo độ phi tương tự giữa các đối tượng dữ liệu với thuộc tính thứ tự được thực hiện như sau, ở đây ta giả sử i là thuộc tính thứ tự có Mi giá trị (Mi kích thước miền giá trị) : Các trạng thái Mi được sắp thứ tự như sau : [1Mi], chúng ta có thể thay thế mỗi giá trị của thuộc tính bằng giá trị cùng loại ri, với ri {1Mi}. Mỗi một thuộc tính có thứ tự có các miền giá trị khác nhau, vì vậy chúng ta chuyển đổi chúng về cùng miền giá trị [0,1] bằng cách thực hiện phép biến đổi sau cho mỗi thuộc tính : Sử dụng công thức tính độ phi tương tự của thuộc tính khoảng đối với các giá trị , đây cũng chính là độ phi tương tự của thuộc tính có thứ tự. Thuộc tính tỉ lệ : Có nhiều cách khác nhau để tính độ tương tự giữa các thuộc tính tỉ lệ. Một trong những số đó là sử dụng công thức tính logarit cho mỗi thuộc tính xi, thí dụ qi = log(xi), lúc này qi đóng vai trò như thuộc tính khoảng (Interval -Scale). Phép biến đổi logarit này thích hợp trong trường hợp các giá trị của thuộc tính là số mũ. Trong thực tế, khi tính độ đo tương tự dữ liệu, người ta chỉ xem xét một phần các thuộc tính đặc trưng đối với các kiểu dữ liệu hoặc là đánh trọng số cho cho tất cả các thuộc tính dữ liệu. Trong một số trường hợp, người ta loại bỏ đơn vị đo của các thuộc tính dữ liệu bằng cách chuẩn hoá chúng, hoặc gán trọng số cho mỗi thuộc tính giá trị trung bình, độ lệch chuẩn. Các trọng số này có thể sử dụng trong các độ đo khoảng cách trên, thí dụ với mỗi thuộc tính dữ liệu đã được gán trọng số tương ứng wi (), độ tương đồng dữ liệu được xác định như sau : . Người ta có thể chuyển đổi giữa các mô hình cho các kiểu dữ liệu trên, thí dụ dữ liệu kiểu hạng mục có thể chuyển đổi thành dữ liệu nhị phân và ngược lại. Thế nhưng, giải pháp này rất tốn kém về chi phí tính toán, do vậy, cần phải cân nhắc khi áp dụng cách thức này. Tóm lại, tuỳ từng trường hợp dữ liệu cụ thể mà người ta sử dụng các mô hình tính độ tương tự khác nhau. Việc xác định độ tương đồng dữ liệu thích hợp, chính xác, đảm bảo khách quan là rất quan trọng, góp phần xây dựng thuật toán phân cụm dữ liệu có hiệu quả cao trong việc đảm bảo chất lượng cũng như chi phí tính toán của thuật toán. 2.4. Các phương pháp tiếp cận trong phân cụm dữ liệu. Phương pháp phân cụm dữ liệu được chia thành các nhóm sau [1]: Phương pháp phân hoạch Phương pháp phân cấp Phương pháp phân cụm dựa trên mật độ Phương pháp phân cụm dựa trên lưới Phương pháp phân cụm dựa trên mô hình Phương pháp phân cụm có ràng buộc 2.4.1. Phương pháp phân hoạch Phương pháp phân hoạch nhằm phân một tập dữ liệu có n phần tử cho trước thành k cụm dữ liệu sao cho: mỗi phần tử dữ liệu chỉ thuộc về một cụm và mỗi cụm có tối thiểu ít nhất một phần tử dữ liệu. Các thuật toán phân hoạch có độ phức tạp rất lớn khi xác định nghiệm tối ưu toàn cục, do nó phải tìm kiếm tất cả các cách phân hoạch có thể được. Trên thực tế người ta thường tìm giải pháp tối ưu cho vấn đề này bằng cách sử dụng một hàm tiêu chuẩn để đánh giá chất lượng của các cụm cũng như để hướng quá trình tìm kiếm phân hoạch dữ liệu. Các thuật toán phân cụm phân hoạch cố gắng cải tiến tiêu chuẩn phân cụm, bằng cách tính các giá trị đo độ tương tự giữa các đối tượng dữ liệu và sắp xếp các giá trị này, sau đó thuật toán lựa chọn một giá trị trong dãy sắp xếp sao cho hàm tiêu chuẩn đạt giá trị tối thiểu. Ý tưởng chính của thuật toán phân cụm phân hoạch tối ưu cục bộ là sử dụng chiến lược ăn tham (Greedy) để tìm kiếm nghiệm. Một số thuật toán phân cụm phân hoạch điển hình như K-means, PAM, CLARA, CLARANS. 2.4.2. Phương pháp phân cấp Phương pháp này sắp xếp một tập dữ liệu đã cho thành một 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ây phân cụm có thể được xây dựng theo hai phương pháp tổng quát sau : Phương pháp “dưới lên” (Bottom up) : Phương pháp này bắt đầu với mỗi đối tượng được khởi tạo tương ứng với các cụm riêng biệt, sau đó tiến hành nhóm các đối tượng theo một độ đo tương tự (như khoảng cách giữa hai trung tâm của hai cụm), quá trình này được thực hiện cho đến khi tất cả các cụm được hòa nhập vào một cụm (mức cao nhất của cây phân cấp) hoặc cho đến khi các điều kiện kết thúc thỏa mãn. Như vậy, cách tiếp cận này sử dụng chiến lược ăn tham trong quá trình phân cụm. Phương pháp “trên xuống” (Top Down) : Bắt đầu với trạng thái là tất cả các đối tượng được xếp trong cùng một cụm. Mỗi vòng lặp thành công, một cụm được tách thành các cụm nhỏ hơn theo giá trị của một phép đo độ tương tự nào đó cho đến khi mỗi đối tượng là một cụm, hoặc cho đến khi điều kiện dừng thỏa mãn. Cách tiếp cận này sử dụng chiến lược chia để trị trong quá trình phân cụm. 2.4.3 Phương pháp phân cụm dữ liệu dựa trên mật độ Phương pháp này nhóm các đối tượng theo hàm mật độ xác định. Mật độ được định nghĩa như là số các đối tượng lân cận của một đối tượng dữ liệu theo một ngưỡng nào đó. Trong cách tiếp cận này, khi một cụm dữ liệu đã xác định thì nó tiếp tục được phát triển thêm các đối tượng dữ liệu mới miễn là số các đối tượng lân cận của các đối tượng này phải lớn hơn một ngưỡng đã được xác định trước. Phương pháp phân cụm dựa vào mật độ của các đối tượng để xác định các cụm dữ liệu có thể phát hiện ra các cụm dữ liệu với hình thù bất kỳ. Tuy vậy, việc xác định các tham số mật độ của thuật toán rất 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 dữ liệu. Hình 4 dưới đây là một minh hoạ về các cụm dữ liệu với các hình thù khác nhau dựa trên mật độ được khám phá từ 3 CSDL khác nhau. CSDL 3 CSDL 1 CSDL 2 Hình 4 : Một số hình dạng cụm khám phá được từ phân cụm dựa trên mật độ Một số thuật toán phân cụm dữ liệu dựa trên mật độ điển hình như DBSCAN, OPTICS, DENCLUE. 2.4.4. Phương pháp phân cụm dựa trên lưới. Kỹ thuật phân cụm dựa trên mật độ không thích hợp với dữ liệu nhiều chiều, để giải quyết vấn đề này, người ta đã dử dụng phương pháp phân cụm dựa trên lưới. Đây là phương pháp dựa trên cấu trúc dữ liệu lưới để phân cụm dữ liệu, phương pháp này chủ yếu tập trung áp dụng cho lớp dữ liệu không gian. Mục tiêu của phương pháp này là lượng hoá tập dữ liệu thành các ô (Cell), các cell này tạo thành cấu trúc dữ liệu lưới, sau đó các thao tác phân cụm dữ liệu làm việc với các đối tượng trong từng Cell này. Cách tiếp cận dựa trên lưới này không di chuyển các đối tượng trong các cell mà xây dựng nhiều mức phân cấp của nhóm các đối tượng trong một cell. Trong ngữ cảnh này, phương pháp này gần giống với phương pháp phân cụm phân cấp nhưng chỉ có điều chúng không trộn các Cell. Do vậy các cụm không dựa trên độ đo khoảng cách (hay còn gọi là độ đo tương tự đối với các dữ liệu không gian) mà nó được quyết định bởi một tham số xác định trước. Ưu điểm của phương pháp phân cụm dữ liệu dựa trên lưới là thời gian xử lý nhanh và độc lập với số đối tượng dữ liệu trong tập dữ liệu ban đầu, thay vào đó là chúng phụ thuộc vào số cell trong mỗi chiều của không gian lưới. Một số thuật toán phân cụm dữ liệu dựa trên cấu trúc lưới điển hình như : STING, WAVECluster, CLIQUE, 2.4.5. Phương pháp phân cụm dựa trên mô hình Phương pháp này cố gắng khám phá các phép xấp xỉ tốt của các tham số mô hình sao cho khớp với dữ liệu một cách tốt nhất. Chúng có thể sử dụng chiến lược phân cụm phân hoạch hoặc chiến lược phân cụm phân cấp, dựa trên cấu trúc hoặc mô hình mà chúng giả định về tập dữ liệu và cách mà chúng tinh chỉnh các mô hình này để nhận dạng ra các phân hoạch. Phương pháp phân cụm dữ liệu dựa trên mô hình cố gắng khớp giữa dữ liệu với mô hình toán học, nó dựa trên giả định rằng dữ liệu được tạo ra bằng hỗn hợp phân phối xác suất cơ bản. Các thuật toán phân cụm dựa trên mô hình có hai tiếp cận chính : Mô hình thống kê và Mạng Nơ ron. 2.4.6. Phân cụm dữ liệu có ràng buộc Để 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. Thực tế, các phương pháp trên đang được phát triển và áp dụng nhiều trong phân cụm dữ liệu. Đến nay, đã có một số nhánh nghiên cứu được phát triển trên cơ sở của các phương pháp tiếp cận trong phân cụm dữ liệu đã trình bày ở trên như sau : Phân cụm thống kê : Dựa trên các khái niệm phân tích thống kê, nhánh nghiên cứu này 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 : Các kỹ thuật phân cụm được phát triển á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 mờ để phân cụm dữ liệu, trong đó một đối tượng dữ liệu có thể thuộc vào nhiều cụm dữ liệu khác nhau. Các thuật toán thuộc loại này chỉ ra lược đồ phân cụm thích hợp với tất cả hoạt động đời sống hàng ngày, chúng chỉ xử lý các dữ liệu thực không chắc chắn. Thuật toán phân cụm mờ quan trọng nhất là thuật toán FCM (Fuzzy c-means) . 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 các mạng nơ ron. Mạng Kohnen có tầng nơ ron vào và các tầng nơ ron ra. Mỗi nơ ron của tầng vào tương ứng với mỗi thuộc tính của bản ghi, mỗi một nơ ron vào kết nối với tất cả các nơ ron của tầng ra. Mỗi liên kết được gắn liền với một trọng số nhằm xác định vị trí của nơ ron ra tương ứng. CHƯƠNG 3 TÌM HIỂU MỘT SỐ THUẬT TOÁN PHÂN CỤM Một số thuật toán phân cụm sẽ được trình bày cụ thể: Thuật toán phân hoạch K-means. Thuật toán DBSCAN Thuật toán OPTICS 3.1. Thuật toán phân hoạch K-means. K-means là một phương pháp được sử dụng rất rộng rãi trên thực tế và nó có thể được biến đổi để thích hợp với nhiều bài toán cụ thể. Phương pháp này được J.B MacQueen đưa ra vào năm 1967. Thuật toán K-means yêu cầu tham số đầu vào là k và thiết lập cho mỗi phần được chia của n đối tượng trong k cụm với mục đích là kết quả tương tự ngoài cụm là lớn nhưng ngược lại những nét tương tự trong cụm là thấp. Những nét tương tự của cụm được đo bằng sự liên quan đến giá trị trung bình của các đối tượng trong cụm. Tư tưởng của thuật toán xử lý như sau: Bước đầu tiên chúng ta chọn bất kỳ k đối tượng được mô tả là trung tâm của các cụm. Trong những trường hợp tổng quát, việc chọn trung tâm là những điểm có khoảng cách không gian giữa chúng lớn có thể đáp ứng được việc chia nhóm tốt hơn. Bước tiếp theo xác định các điểm dữ liệu còn lại vào các cụm sao cho việc chia đó là thích hợp nhất dựa trên khoảng cách giữa đối tượng và trung tâm cụm. Sau khi đã thực hiện đối với tất cả các điểm dữ liệu chúng ta chia được tất cả các điểm này vào k cụm. Sau đó sẽ tính lại trung tâm mới cho mỗi cụm. Khi trung tâm cụm thay đổi, vị trí của mỗi một điểm dữ liệu cũng được tính toán lại. Có thể mô tả thuật toán K- means như sau : Đầu vào : Số cụm k và CSDL chứa n đối tượng. Đầu ra : Thiết lập k cụm: c1,, c2, cn. Phương pháp : Thuật toán K-means được thực hiện như sau : 1) Chọn tùy ý k đối tượng cho việc khởi tạo trung tâm các cụm. 2) Lặp 3) Gán lại mỗi đối tượng vào các cụm để các đối tượng tương tự nhau nhất dựa trên giá trị trung bình của các đối tượng trong cụm 4) Cập nhật giá trị trung bình của các cụm, tính toán giá trị trung bình của các đối tượng cho mỗi cụm. 5) Cho đến khi không thay đổi được nữa a b c Hình 5: Phân cụm dữ liệu dựa trên thuật toán K-means. Độ phức tạp của thuật toán là O(nkt).c Thuật toán K-means không phù hợp cho việc tìm ra các cụm không có hình dạng lồi hoặc các cụm có nhiều kích thước khác nhau. Hơn nữa nó nhạy cảm với nhiễu. Việc chọn k làm trung tâm là k điểm đầu cùng với việc thay đổi lại các cụm nếu chỉ đơn giản thao cách làm vừa trình bày thì hiệu quả của thuật toán K- means không cao đặc biệt là khi áp dụng với những dữ liệu lớn bởi thuật toán luôn yêu cầu phải tính lại toàn bộ khoảng cách từ một điểm dữ liệu đến tất cả các trung tâm của cụm. Chính vì thế người ta đã cải tiến thuật toán K-means thành thuật toán DBSCAN (Density – Based Spatial Clustering of Application With Noise) với việc tìm trung tâm được xác định bởi hai tham số ε và MinPts một cách ngẫu nhiên và thuật toán tìm biên đã làm tăng hiệu quả của việc phân cụm do vậy thuật toán này thường sử dụng khi xử lý dữ liệu lớn. 3.2. Thuật toán DBSCAN (Density–Based Spatial Clustering of Application With Noise). Thuật toán DBSCAN dựa trên ý tưởng những điểm trong một cụm phải có mật độ các điểm lân cận vượt qua một ngưỡng nào đó. Một cụm được xác định bằng một tập tất cả các đối tượng liên thông mật độ với các láng giềng của nó. Một số định nghĩa và bổ đề sử dụng trong DBSCAN Định nghĩa 1: Lân cận với ngưỡng ε của một điểm (ε– Neighborhood of a Point) Lân cận với ngưỡng ε của một điểm P kí hiện là Nε(p) được xác định như sau: Nε(p) = { q ÎD | khoảng cách (p,q) £ ε} Một điểm p muốn nằm trong một cụm C nào đó thì Nε(p) phải có tối thiểu MinPts điểm. Số điểm tối thiểu được chọn là bao nhiêu cũng là một bài toán khó vì: nếu số điểm tối thiểu lớn chỉ những điểm nằm thực sự trong cụm C mới đạt được điểu đó. Ngược lại, nếu số điểm tối thiểu là nhỏ, mọi điểm sẽ chỉ rơi vào một cụm. Như định nghĩa trên thì chỉ những điểm nằm thực sự trong cụm mới thỏa mãn điều kiện là điểm của cụm. Để tránh được điều đó chúng ta có thể đưa ra một tiêu chuẩn khác để định nghĩa một điểm thuộc vào một cụm như sau : nếu một điểm p muốn thuộc một cụm C phải tồn tại một điểm q mà p Nε(p) phải lớn hơn số điểm tối thiểu. Điều đó được định nghĩa như sau: Định nghĩa 2: Đến được trực tiếp theo mật độ ( Directly density – reachable) Một điểm p được gọi là đến được trực tiếp từ điểm q với ngưỡng ε nếu : p ÎN ε(q) || N ε(q)|| ≥ MinPts Ta có thể thấy rằng đến được trực tiếp là một hàm phản xạ, đối xứng đối với hai điểm nhân và bất đối xứng nếu một trong hai điểm đó không phải điểm nhân . Ví dụ : a b Hình 6: Mô phỏng tính chất đến được trực tiếp Hình 6 (a): p là điểm biên, q là điểm nhân Hìn