Chương 1 đã nêu lên được nội dung bài toán cần giải quyết và các công việc thực hiện của đồ án kèm theo giải pháp đề xuất. Trong chương tiếp theo, đồ án sẽ trình bay chỉ tiết hơn về các kỹ thuật sử dụng NGUYEN THỊ NGOC ANH - D17HTTTI 8 DO ÁN TOT NGHIỆP CHƯƠNG 2 CHUONG 2: KY THUẬT PHAN CUM DỰA TREN K-MEAN TRONG KHAI PHA NHAT KY TRUY VAN 2. Kỹ thuật phân cum trong khai pha dữ liệu 2. Tổng quan về kỹ thuật phân cum Phân cụm dữ liệu là một kỹ thuật trong khai phá dữ liệu, nhằm tìm kiếm, phát hiện các cụm, các mau dir 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 ra quyết định.
Mục tiêu của phân cụm là tìm cách nhóm các đối tượng đã cho vào các cụm (clusters), sao cho các đối tượng trong cùng 1 cụm tương tự (similar) nhau và các đối tượng khác cụm thì không tương tự (dissimilar) nhau, nhờ đó phát hiện ra cấu trúc an của đữ liệu. Đề phân cụm dữ liệu cần thực hiện các bước cơ bản sau [2]: Chọn đặc trưng: Các đặc trưng lựa chọn phải hợp lý dé có thé mã hoá nhiều nhất các thông tin liên quan đến công việc quan tâm. Chọn độ đo gần nhất: Một độ đo chỉ ra mức độ tương tự hay không tương tự giữa hai vectơ đặc trưng. Tiêu chuẩn phân cụm: Tiêu chuẩn phân cụm có thé được biểu diễn bởi hàm chi phí hoặc một vài quy tắc khác.
Công nhận kết quả: Sau khi có kết quả phân cụm, cần kiểm tra tính đúng đắn của Giải thích kết quả: Bằng kết quả thực nghiệm cần phân tích để đưa ra kết luận đúng đắn. Một số ứng dụng của phân cụm Phân cụm được áp dụng rộng rãi trong nhiều lĩnh vực từ kinh tế, y tế đến sinh học, công nghệ. và có các ứng dụng chính như: - Hỗ trợ giai đoạn tiền xử lý dữ liệu(data preprocessing) - Mô tả sự phân bố đữ liệu/ đối tượng(data distribution) - Nhận dạng mẫu(pattern recognition) - Phan tích dữ liệu không gian(Spatial data analysis) - _ Xử lý anh(image processing) - Phân mảnh thi trường(market segmentation) - Gom cum tài ligu((www) document clustering) 2. Các kiểu dữ liệu và độ đo tương tự Việc định nghĩa thế nào là giống nhau, không giống nhau là 1 phần rất quan trọng trong việc phân nhóm (clustering), bởi vì nó sẽ ảnh hưởng đến toàn bộ cấu trúc của các nhóm ấy.
Tùy theo từng kiểu dit liệu sẽ có các độ đo tương tự khác nhau được áp dung, NGUYEN THỊ NGOC ANH - D17HTTTI 9 DO ÁN TOT NGHIỆP CHƯƠNG 2 nhưng về cơ bản có 2 nhóm dit liệu chính là thuộc tính hạng muc(Categories) và thuộc tính số(Numeric). Thuộc tính hạng mục bao gồm các loại: thuộc tính định danh(nominal Scale), thuộc tính có thứ tự (Ordinal Scale). Thuộc tính số bao gồm thuộc tính khoảng (Interval Scale), thuộc tính tỉ lệ (Ratio Scale). 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 : e_ Thuộc tính khoảng (Interval Scale): Nhằm dé đo các giá trị theo xấp xi tuyến tính.
Với thuộc tính khoảng, chúng ta có thê xác định một đối tượng là đứng trước hoặc đứng sau một đối tượng khác với một khoảng là bao nhiêu. Các đơn vị đo có thể ảnh hưởng đến phân tích cụm. Vì vậy để tránh sự phụ thuộc vào đơn vị đo, cần chuẩn hóa dữ liệu. Các bước chuẩn hóa dữ liệu: Tính giá trị trung bình và sai số tuyệt đối trung bình my =~ (Xap + Xap + + Xny) (2.1) Sp = = ([xap — mự| + |xa¢ — mự| + + |xịy — mự|) (22) Tính độ đo chuẩn Xif-—m Zij = s i (2.3) Sau khi chuan hoa, d6 do phi tuong tu cua hai đối tượng dữ liệu x, y được xác định bang các metric khoảng cách như sau: Khoảng cách Minskowski: 1/4 d(x,y) = Xï-¡|¡ — vil! (2.4) q: là số tự nhiên nguyên đương Khoảng cách Euclide: d(x,y) = | peli — Vil? (2.5) Day là trường hợp đặc biệt cua khoảng cách Minskowski trong trường hợp q=2 Khoảng cách Manhattan: d(x,y) = Dix: — vil (2.6) Day là trường hop đặc biệt cua khoảng cach Minskowski trong trường hợp q=1 e Thuộc tính tỉ lệ (Ratio Scale): là thuộc tính khoảng nhưng được xác định một điểm mốc tương đối, 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ệ. 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ụ q; = log(x;), NGUYEN THỊ NGOC ANH - D17HTTTI 10 DO ÁN TOT NGHIỆP CHƯƠNG 2 lúc này q; đó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ũ. Các phương pháp tính độ tương tự: - _ Xử lý chúng như các biến thang đo khoảng.
- Ap dụng các biến đối logarithmic. - _ Xử lý chúng như đữ liệu thứ tự liên tục. - _ Xử lý chúng theo hạng như thang đo khoảng. e Thuộc tính có thw 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.
Phép đo độ phi tương tự giữa các đối tượng dir 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ó M; giá trị (M; là kích thước miền giá tri) Các trạng thái M; được sắp thứ tự như sau: [1.M;], 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 ?;_, voi; €{1.M,} 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 .7) Sử dung công thức tinh độ phi tương tự của thuộc tính khoảng đối với các giá tri Z trên đây thu được độ phi tương tự của thuộc tính có thứ tự e Thuộc tính nhị phân: Thuộc tính định danh chỉ có 2 giá tri Gia sử tat cả thuộc tính về đối tượng đều là nhị phân biéu thị băng 0 và 1. y=ll|y=0 x=l a b a+b x=0 c d c+d a+clb+dla+b+c+d Hình 2. Độ tương tu biến nhị phân Trong đó: a là tổng số các thuộc tính có giá trị là 1 trong cả hai đối tượng x, y. b là tong số các giá trị thuộc tính có giá trị là 1 trong x và 0 trong y.
c là tổng số các giá trị thuộc tính có giá trị là 0 trong x và 1 trong y. d là tổng số các giá trị thuộc tính có giá trị là 0 trong cả x và y. Ta có tông số các thuộc tính về đối tượng p=a+b+c+d NGUYEN THỊ NGOC ANH - D17HTTTI 11 DO ÁN TOT NGHIỆP CHƯƠNG 2 Các phép đo độ tương tự giữa hai đối tượng trong trường hợp dữ liệu thuộc tính nhị phân được định nghĩa như sau: Hệ sô đôi sánh đơn giản: b d(x,y) =“— (2.8) Hệ số Jacard: d(x,V) = ng (2.9) e Thuộc tính định danh(nominal scale): day 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á tri là rời rac không phân biệt thứ tự và có nhiêu hơn hai phân tử. Có hai phương pháp dé tính toán sự tương tự giữa hai đối tượng: Phương pháp 1: Đối sánh don giản Độ đo phi tương tự giữa hai đối tượng x và y được định nghĩa như sau: d(x,y) = — (2.10) Trong đó m là số thuộc tinh đối sánh tương ứng trùng nhau giữa 2 đối tượng.
Phương pháp 2: Dùng một số lượng lon các biến nhị phân: - Tao biến nhị phân mới cho từng trạng thái định danh. - _ Các biên thứ tự có thê là liên tục hay rời rac - Thr tự của các tri là quan trong. Vi dụ: hang. - C6 thê xử lý như tỉ lệ khoảng như sau: - Thay thé z; ; bởi hang cua chúng.
- Ảnh xạ phạm vi của từng biên vào đoạn [0,1] băng cách thay thê đôi tượng i trong biến thứ f boi, .M,} Tính sự khác nhau dùng các phương pháp cho biến tỉ lệ theo khoảng. Tịr—1 Zit = tr (2.11) 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 tinh dtr 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 tinh 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, ví dụ với mỗi thuộc tính dữ liệu đã được gán trọng số tương ứng wi (1<i<k), độ tương đồng dữ liệu được xác định như sau: d(x,y) = _|3‡—¡w¡|x¡ — vil? (2.12) NGUYEN THỊ NGOC ANH - D17HTTTI 12 DO ÁN TOT NGHIỆP CHƯƠNG 2 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, ví 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.
Tóm lại, tuỳ từng trường hợp dữ liệu cụ thé ma người ta sử dụng các cách tính độ tương tự khác nhau. Một số phương pháp phân cụm [1] Một số phương pháp phân cụm điền hình: Phân cụm phân hoạch, phân cụm phân cấp, phân cụm dựa trên mật độ, phân cụm dựa trên lưới, phân cụm dựa trên mô hình, phân cụm có ràng buộc. Phân cụm phân hoạch Cho một cơ sở dữ liệu D chứa n đối tượng, tạo phân hoạch thành tập có k cụm Sao cho: - Moi cụm chứa ít nhất một đối tượng ; - Mỗi đôi tượng thuộc về một cum duy nhât - k cụm tìm được thỏa mãn tiêu chuân tối ưu đã định. Phương pháp heuristic điên hình được biết đên là k-means và k-medoids.
Phân cụm phân cấp Phân cụm phân cấp 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 bằng phương pháp trên xuống (Top down) hoặc phương pháp dưới lên (Bottum up). Phương pháp “dưới lên” (Bottom up): Phương pháp này bắt đầu bằng cách khởi tạo mỗi đối tượng riêng biệt là một cụm, 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 nhóm), quá trình này được thực hiện cho đến khi tất cả các nhóm được kết nhập thành một nhó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 tham lam trong quá trình phân cụm.