Phân cụm dữ liệu nửa giám sát và giải thuật di truyền

Đề tàiPHÂN CỤM DỮ LIỆU NỬA GIÁM SÁT VÀ GIẢI THUẬT DI TRUYỀNGiáo viên hướng dẫn: ThS.Nguyễn Thị Xuân HươngSinh viên : Trần Thị Như Quỳnh. Mã số : 080313Lớp : CT802. BÁO CÁO TỐT NGHIỆP1NỘI DUNG12345Giải thuật di truyền (GA)Phân cụm dữ liệuCác phương pháp PCDL phân hoạch và thuật toán PCDL nửa giám sátThuật toán K-tâm phân cụm nửa giám sát cho dữ liệu hỗn hợp và GAChương trình ứng dụng2Khái niệm PHÂN CỤM DỮ LIỆU"PCDL là một kỹ thuật 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 ra quyết định" 3Bài toán phân cụm dữ liệu Input : X={X1,,XN } Output : K phân hoạch {C1,,CK } và các phần tử trong mỗi phân hoạch có độ tương đồng cao nhất.PHÂN CỤM DỮ LIỆU4 Kiểu dữ liệu và độ đo tương tự sử dụng trong bài toán phân cụm dữ liệu 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 +Thuộc tính rời rạc Phân loại các kiểu dữ liệu dựa trên hệ đo +Thuộc tính định danh (nominal Scale): +Thuộc tính có thứ tự (Ordinal Scale) +Thuộc tính khoảng (Interval Scale) +Thuộc tính tỉ lệ (Ratio Scale)PHÂN CỤM DỮ LIỆU5 Tương tự và phi tương tự Thuộc tính khoảng Khoảng cách Minskowski Khoảng cách Euclide : Khoảng cách Manhattan : Khoảng cách cực đại : PHÂN CỤM DỮ LIỆU6Thuộc tính nhị phân x:0x:1y:0y:1++++Bảng tham số Hệ số Jacard Hệ số đối sánhPHÂN CỤM DỮ LIỆU7 Thuộc tính định danh Thuộc tính có thứ tựThuộc tính tỉ lệ PHÂN CỤM DỮ LIỆU8 Thương mại Sinh học Phân tích dữ liệu không gian Lập quy hoạch đô thị Nghiên cứu trái đất Địa lý Web Mining Ứng dụng của phân cụm dữ liệuPHÂN CỤM DỮ LIỆU9GiẢi thuẬt di truyỀn Giới thiệu Theo giải thuật di truyền cổ điển mỗi cá thể luôn phải tự tìm cách thích nghi tốt nhất với môi trường sống rất phức tạp và luôn luôn thay đổi. Cá thể nào có khả năng thích nghi với môi trường cao hơn thì tồn tại, phát triển, ngược lại sẽ có nhiều nguy cơ bị tiêu vong 10 Trong giải thuật di truyền cổ điển, mỗi cá thể (hay nhiễm sắc thể) được mã hóa bởi các chuỗi nhị phân. Ví dụ: một nhiễm sắc thể n. gồm 8 gene như sau: 10010110 Mỗi kiểu gene biểu thị một lời giải tiềm năng của bài toán. GiẢi thuẬt di truyỀn Cấu trúc nhiễm sắc thể và kiểu gene11Cấu trúc của giải thuật di truyền cổ điểnvoid GA{ t = 0; Khởi tạo P(t); Đánh giá (P(t)); While ( not E) { t = t+1; Chọn Q(t) từ P(t-1) //bằng bánh xe sổ số Tái tạo P(t) từ Q(t) //bằng các toán tử di truyền Đánh giá P(t) }}GiẢi thuẬt di truyỀn 12Thủ tục chọn lọc Cá thể 1 có xác xuất chọn lọc là 11%. Mỗi lần quay bánh xe sổ số nó có khả năng được chọn là 0.11. GiẢi thuẬt di truyỀn 364%111%225%13Thủ tục tái tạo (lai ghép và đột biến)Child 11101111000 011110Child 21010100100 110110Parent 11101100100 110110Parent 21010111000 011110Thực hiện lai ghép tại vị trí số 5 sẽ tạo ra hai con:Ví dụ: có hai nhiễm sắc thể bố và mẹPhép lai ghépGiẢi thuẬt di truyỀn 14V11101111000 011110V1’1101011000 011110Phép đột biến Trong giải thuật di truyền cổ điển, mỗi cá thể biểu diễn bởi một chuỗi nhị phân. Phép đột biến tại một chỗ nào đó là việc đảo bít tương ứng tại vị trí đó. Ví dụ: NST V1 được chọn để đột biến tại gen số 5.GiẢi thuẬt di truyỀn 15Điều kiện kết thúc Kết thúc theo kết quảKết thúc dựa vào số thế hệTính theo thời gianTổ hợp nhiều cáchGiẢi thuẬt di truyỀn 16 Giải thuật di truyền tỏ ra rất hiệu quả đối với các bài toán mà hàm mục tiêu phức tạp Đối với các bài toán đã có phương pháp giải tốt bằng phương pháp truyền thống giải thuật di truyền tỏ ra kém hiệu quả hơnGiẢi thuẬt di truyỀn Sự hội tụ của giải thuật di truyền 17 Lai đơn giảnLai số học đơnLai số học toàn cục Các toán tử biến dị Biến dị đềuBiến dị không đều Biểu diễn bằng vectơ số thựcGiẢi thuẬt di truyỀn 18PCDL PHÂN HOẠCH VÀ PCDL NỬA GIÁM SÁTCác phương pháp phân cụm dữ liệu phân hoạch Thuật toán K-means19DOM(Aj) là miền giá trị của thuộc tính Aj (Aj có thể là tập số thực, định danh hay là tập có thứ tự. )Các khoảng cách được xác định trên DOM(Aj)x,y DOM(Aj) ta hàm dj(x,y) xác định bởi :i) Nếu Aj là thuộc tính số thì dj(x,y)= (1) Mêtric trên dữ liệu hỗn hợp ii) Nếu Aj là thuộc tính thứ tự và DOM(Aj) =với ta lấy một hàm fjOM(Aj)→ [0,1]sao cho Khi đó dj(x,y)= │fj(x)-fj(y) │PCDL PHÂN HOẠCH VÀ PCDL NỬA GIÁM SÁT20iii) Nếu Aj là dữ liệu định danh thì dj(x,y)=Khoảng cách trên hai đối tượng dữ liệu hỗn hợp : x = (x1,...,xn) và y = (y1,...,yn) khoảng cách d(x,y) được tính bởi công thức: Các khoảng cách được xác định trên DOM(Aj) (4) trong đó các dj(xj,yj) được tính theo các công thức (1-3) vàlà các trọng số dượng(3)PCDL PHÂN HOẠCH VÀ PCDL NỬA GIÁM SÁT21Proceduce k-tâmBeginChọn các trọng số , các hàm fj ,xác định k. Chọn k phần tử ban đầu của D làm tâm các cụm Xếp mỗi x  D vào cụm Cj mà nó gần tâm nhất;For j=1,...,k do ;RepeatPhân bố lại cụm theo tâm mới// như k-mean;Cập nhật lại tâm cho các cụm // nhờ tính modeUntil các cụm không đổi;Xác định các cụmEndThuËt to¸n k-t©mPCDL PHÂN HOẠCH VÀ PCDL NỬA GIÁM SÁT22Bài toán:Cho một tập dữ liệu X gồm N đối tượng dữ liệuTập giống S gồm K cụm giốngNhiệm vụ: đoán số cụm Kd mong muốn mà vẫn dữ được cấu trúc cụm tốtVí dụ: Bài toán phân loại văn bản WebPCDL PHÂN HOẠCH VÀ PCDL NỬA GIÁM SÁTThuật toán phân cụm dữ liệu nửa giám sát 23Thuật toán được phát biểu như sau:Input: Tập các đối tượng dữ liệu D={X1,X2,.XN} số lượng cụm là k, tập giống Mô tả thuật toán: 1.Khởi tạo ngẫu nhiên quần thể P(0) gồm tập các lời giải với 2. Với mỗi lời giải thuộc quần thể P(0) {thực hiện K-tâm nửa giám sát với trọng số  đã biết}; 3. Đánh giá các P(0) theo hàm thích nghi fitnes; 4. while (t < số thế hệ) do { Chọn lọc Q(t) từ P(t-1); Tái tạo P(t) từ Q(t) ;// nhờ thủ tục tái tạo Với mỗi lời giải thuộc quần thể P(t) {thực hiện K-tâm nửa giám sát với trọng số  đã biết}; Đánh giá P(t) ; } 5.Biểu diễn lời giải . 6.Thực hiện K-tâm;THUẬT TOÁN K-TÂM PCDL NỬA GIÁM SÁT VÀ GA24 Khởi tạo các cụm: với h=1,...K; t0Lặp cho tới khi hội tụ Xếp mỗi x  D vào cụm Cj mà nó gần tâm nhất;Ước lượng tâm: tt+1;Thuật toán K-tâm nửa giám sát với trọng số  :THUẬT TOÁN K-TÂM PCDL NỬA GIÁM SÁT VÀ GA25 Biểu diễn dữ liệu Mỗi lời giải  (trọng số cần tìm) của giải thuật di truyền được biểu diễn bằng một xâu số thực với Hàm mục tiêu Hàm mục tiêu E = tổng số đối tượng trong tập giống bị phân cụm sai. Hàm thích nghi (fittness) , Bài toán cần tìm trọng số  thích hợp để hàm fittness đạt max. THUẬT TOÁN K-TÂM PCDL NỬA GIÁM SÁT VÀ GA26 Input : Có một tập rất lớn các thông tin về khách hàng và loại sách. Output : Các nhóm khách hàng có một số tiêu chí chung.-Sử dụng thuật toán K-tâm theo phương pháp nửa giám sát và giải thuật di truyền cho việc lựa chọn trọng số thích hợp cho các thuộc tính-Các kiểu dữ liệu có thể là giá trị số hay sắp thứ tự hay là thuộc tính định danh1.Phát biểu bài toánCHƯƠNG TRÌNH ỨNG DỤNG27 Các thông tin về mỗi khách hàng như sau :STTTên thuộc tínhTrọng số11050Kiểu dữ liệu1name định danh2birthyear số3city định danhCHƯƠNG TRÌNH ỨNG DỤNG28Thông tin về mỗi quyển sách như sau :CHƯƠNG TRÌNH ỨNG DỤNGSTTTên thuộc tínhTrọng sốKiểu dữ liệu1name định danh2authour định danh3publisher định danh4year số5genre định danh6price số150501001015010292. Các chức năng của phần mềmCHƯƠNG TRÌNH ỨNG DỤNG Giao diện chương trình :30 Chức năng dữ liệu gồm :CHƯƠNG TRÌNH ỨNG DỤNG31 Các thông số : Nhập số nhóm cần phân tách , số bộ tâm khởi tạo ban đầu, số bước thực hiện k-tâm và số bước thực hiện GA. CHƯƠNG TRÌNH ỨNG DỤNG32CHƯƠNG TRÌNH ỨNG DỤNG Chức năng thực hiện gồm : 33CHƯƠNG TRÌNH ỨNG DỤNG Chức năng kết quả gồm : 34CHƯƠNG TRÌNH ỨNG DỤNG 3.Kết quả thực hiện chương trình -Khởi tạo 5 bộ tâm 35CHƯƠNG TRÌNH ỨNG DỤNG  - Phân cụm theo k-tâm với bộ tâm số 2 36CHƯƠNG TRÌNH ỨNG DỤNG-Kết quả phân cụm với thuật toán k-tâm 37CHƯƠNG TRÌNH ỨNG DỤNG -Bộ tâm tốt nhất sau khi thực hiện GA : 38CHƯƠNG TRÌNH ỨNG DỤNG-Kết quả thực hiện thuật toán k-tâm kết hợp GA39CHƯƠNG TRÌNH ỨNG DỤNGNhận Xét Thuật toán k-tâm đơn thuần cho ta kết quả không tốt bằng kết quả sau khi có sự kết hợp của GATrong các bài toán không gian tìm kiếm rộng sự kết hợp với GA cho ta kết quả tốt hơn. Thuật toán k-tâm đơn thuần cho ta kết quả không tốt bằng kết quả sau khi có sự kết hợp của GA40 Em xin chân thành cảm ơn!41...