Nghiên cứu một số phương pháp phân cụm mờ và ứng dụng

bởi Trung tâm Học liệu – Đại học Thái Nguyên Điểm jx đƣợc gọi là nằm trong lân cận của xi nếu jx nằm trong hình hộp p chiều bán kính r của xi .  Tính độ đậm đặc của các điểm dữ liệu. Độ đậm đặc của t t i xx C , ký hiệu là ( ) t t i iD x , là số điểm dữ liệu nằm trong lân cận của t ix .   1 ( ) b t t t t i i j i j D x u r x x     , với 1, 0 ( ) 0, 0 z u z z     . (14) Khi đó, thuật toán 1 đƣợc triển khai theo các bƣớc sau: THUẬT TOÁN 1 Bƣớc 1: Tính 1 1 n z x i jin j    và độ lệch tiêu chuẩn   21 1 n s x z i ji in j    , i=1,2,..p. Tính bán kính 1 min i i p r s    . Bƣớc 2: Tính độ đậm đặc của các điểm dữ liệu Di là số điểm dữ liệu nằm trong hình hộp p chiều bán kính r của ix X : 1 ( ) n j i j u r x x    . Bƣớc 3: Tìm điểm ix X sao cho nó có độ đặc lớn nhất. Bƣớc 4: Tính CC = {xj: xj nằm trong hình hộp p chiều bán kính r của xi} và \X X CC . (* ở đây CC là tập tất cả các điểm dữ liệu nằm trong hình hộp p chiều bán kính r của điểm dữ liệu xi *) Bƣớc 5: Nếu X  thì dừng. Ngƣợc lại, thì quay lên bƣớc 2. 51 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Trong trƣờng hợp mẫu dữ liệu lớn thì chúng ta chia tập dữ liệu ra thành các tập dữ liệu nhỏ hơn. Sau đó mới áp dụng thuật toán 1 cho từng mẫu dữ liệu mới thu đƣợc sau khi đã phân chia. Sau khi chạy xong thuật toán 1, thì ta sẽ có đƣợc một tập các điểm dữ liệu làm ứng viên cho việc chọn các trung tâm của các cụm. Nếu tập này lớn thì chúng ta lại áp dụng lại thuật toán 1 một lần nữa. Điều này đƣợc thể hiện thông qua thuật toán 2. 3.2.3.2. Thuật toán 2: Thuật toán lƣợc bớt các ứng viên Sau khi chạy xong thuật toán 1. Thì từ tập dữ liệu X ban đầu, chúng ta đã chọn ra đƣợc nc các điểm dữ liệu làm ứng viên. Giả sử xC = {xj: xj là điểm dữ liệu ứng viên, 1.. ci n }. Khi nc mà lớn thì ta sử dụng thuật toán 1 cho tập dữ liệu mới là Cx. Kết quả ta thu đƣợc tập dữ liệu mới là  , 1,2,..,px j pC x j n  . Sau khi đã chạy xong thuật toán 2, ta có đƣợc tập dữ liệu mới. Khi đó, ta chuyển sang thuật toán 3 để tìm các điểm dữ liệu làm trung tâm của các cụm, đây là những điểm dữ liệu mà làm min hàm mục tiêu. 3.2.3.3. Thuật toán 3: Thuật toán chọn các ứng viên làm cực tiểu HMT Sau khi kết thúc thuật toán 1 và thuật toán 2 thì ta thu đƣợc tập các điểm dữ liệu làm ứng viên cho trung tâm các cụm là  1 2, ,..., p p c nC cc cc cc . Trong thuật toán FCM, ta dùng hàm mục tiêu ( , )J u v 2 1 1 ( , ) pnn m ji i j i j J u v x cc     (15) Ta thay thế hàm mục tiêu này bằng hàm mục tiêu mới * FCMJ đƣợc xác định nhƣ sau: 2 * 1 1 . qn m c FCM ji i j cc i j J Jx cc       (16) 52 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên với 2 1 1 q q c cc i j i j i J cc cc       (17) và   2 1 1 2 1 1 ji c q i j m ck i k x cc x cc        (18) Thông thƣờng ta hay chọn m = 2. Do các cụm có thể rất gần nhau nên ta dùng JCC có thêm trọng số 1  để có thể phân biệt đƣợc các cụm này trong trƣờng hợp chúng khá gần nhau. Khi đó, thuật toán 3 đƣợc triển khai theo các bƣớc sau: THUẬT TOÁN 3 Bƣớc 1: q = 1, gán ** FCMJ   , 1  . Bƣớc 2: gán c qcc cc , p ccc C  . Bƣớc 3: Tính độ thuộc   2 1 1 2 1 1 ji c q i j m c k i k x cc x cc        ,  1ji , i=1, 2, .., n và j = 1, 2, .., q. Tính * FCMJ theo công thức (17) Bƣớc 4: Nếu * ** FCM FCMJ J thì gán ** * :FCM FCMJ J và q:=q+1; Bƣớc 5: Nếu 1pn   thì dừng với q:=q-1. Ngƣợc lại thì quay lên bƣớc 2 với : 1   . 3.2.3.4. Thuật toán 4:Gán các trung tâm có liên kết “gần gũi” vào 1 cụm Sau khi kết thúc thuật toán 3, ta có một số hữu hạn các điểm dữ liệu đƣợc chọn làm trung tâm của các cụm. Đó là:  1 2, ,..., ,c c ch pcc cc cc h n . 53 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Bây giờ ta kiểm tra xem các cụm có thể kết nối lại đƣợc với nhau hay không. Điều này đƣợc thực hiện nhờ thuật toán 4. Thuật toán này đƣợc triển khai nhƣ sau: Việc 1: Tìm đƣờng dây có thể nối c icc và c jcc (đường dây này phụ thuộc vào trường hợp cụ thể để ta chọn, chẳng hạn nếu là lông mày, ta sẽ tìm một đường cong parabol, con mắt ta có thể dùng hình elip…) Giả sử có những điểm nằm trên đƣờng dây nối c icc và c jcc là: 1 2, ,.., kv v v sao cho: 1 2 1 1... c c i k k j kv cc v v v v cc v        1 c c i jcc cc k    Sau đó, ta tiến hành tính độ đậm đặc của các điểm này: 1 ( ) i n c cc l i l D u r x cc     (19) 1 ( ) j n c cc l j l D u r x cc     (20) 1 ( ), 1,..., a n v l i l D u r x v a k      (21) Nếu các điểm dữ liệu này thỏa mãn với mọi l = 1, 2, …, k đối với tất cả max( , ) 4 i j l cc cc v D D D  thì ta xác định hai cụm này có thể kết nối đƣợc. Việc 2: Ta nối 2 trung tâm và dùng luật bắc cầu để nối tiếp chúng vào một cụm. Chẳng hạn, nếu ( c icc và c jcc là kết nối đƣợc) và ( c jcc và c kcc là kết nối đƣợc) thì c icc , c jcc và c kcc là kết nối đƣợc và các trung tâm này đƣợc gán vào cùng một cụm. Khi đó, thuật toán 4 đƣợc thể hiện chi tiết qua các bƣớc sau: 54 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên THUẬT TOÁN 4 Việc thứ nhất: Bƣớc 1: gán  , 1,...,cl lCluster cc l h  . Bƣớc 2: Ta tạo ra index1 và index2 đều là mảng một chiều cỡ h. Khởi tạo tất cả các phần tử của mảng này với giá trị 0. Bƣớc 3: Đặt i:=1; j:=i+1; Bƣớc 4: Tìm các điểm nằm trên đƣờng dây nối c icc và c jcc (thường đường dây này dựa vào đặc điểm của đường cong cần nhận dạng, chẳng hạn lông mày thì ta dùng một đường cong parabol) là 1 2, ,.., kv v v sao cho: 1 2 1 1... c c i k k j kv cc v v v v cc v        1 c c i jcc cc k    Bƣớc 5: Tính độ đậm đặc của các điểm dữ liệu ở bƣớc 4: 1 ( ) i n c cc l i l D u r x cc     1 ( ) j n c cc l j l D u r x cc     1 ( ), 1,..., a n v l a l D u r x v a k      Bƣớc 6: IF 1 k a  ( max( , ) 4 i j a cc cc v D D D  )THEN If (index1[i]=0) and (index2[j]=0) then Begin cluster cluster cluster j j i   ; Index1[i]:=j; Index2[j]:=i; 55 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên End Else if (     1 0) 2 0index i and index j  then Begin  max( , 1 )j index icluster =  max( , 1 )j index icluster   max( , 2 )i index jcluster ;    1 max( , 1 )index i j index i ;  2index j i ; End Else if ((     2 0) 1 0index j and index i  then Begin  1 2index index j cluster    =  1 2index index j cluster     ;icluster  1index i   1 2index index j   ; End Else if (    ( 1 0) ( 2 0)index i and index j  then Begin temp:=  1 2index index j   ;  max( 1 , )index i tempcluster   max( 1 , )index i tempcluster    min( 1 , )index i tempcluster ;    1 : max( 1 , );index i index i temp End Else (* của IF đầu tiên *) begin  ci icluster cc và  cj jcluster cc End; Bƣớc 7: IF ( ) ( )i h and j h  THEN j:=j+1 và quay trở lại bƣớc 4 ELSE if ( )i h then quay trở lại bƣớc 4 ELSE i:=i+1,j:=j+1 và quay trở lại bƣớc 4 56 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Việc thứ hai: Bƣớc 1: i:=1;FC:=  ; Bƣớc 2: IF  1 0index i  then Begin h:=h-1; xóa icluster ; FC:=FC i ; End; Bƣớc 3: i:=i+1; Bƣớc 4: IF i h THEN quay lại bƣớc 2 ELSE dừng lại . 3.2.3.5. Tổng kết thuật toán FCM-Cải tiến Từ chi tiết của 4 thuật toán nhỏ trên, ta có thể tổng hợp thuật toán FCM-Cải tiến một cách tổng quát thông qua các bƣớc cụ thể nhƣ sau: THUẬT TOÁN FCM-CẢI TIẾN Cho tập dữ liệu  1 2, ,.., nX x x x , ,..1, niRx pi  và *, Npn  Thuật toán FCM-Cải tiến đƣợc thực hiện thông qua các bƣớc sau: Bƣớc 1: Nếu n là lớn thì chạy thuật toán 1 để có đƣợc tất cả các điểm có khả năng làm trung tâm cụm, ngƣợc lại thì chạy bƣớc 3. Bƣớc 2: Nếu sau khi chạy thuật toán 1 mà số điểm làm ứng viên lớn thì ta chạy thuật toán 2 để rút gọn bớt số các điểm ứng viên làm các trung tâm của các cụm. Bƣớc 3: Chạy thuật toán 3 để tìm các điểm làm trung tâm cụm. Bƣớc 4: Chạy thuật toán 4 để nối các trung tâm cụm có liên hệ “gần gũi” vào một cụm. 57 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Sau khi bƣớc 4 kết thúc, ta sẽ có tập các trung tâm của các cụm. Bƣớc 5: (có thể nhảy tới bƣớc 6) Chạy thuật toán FCM với tập các trung tâm của các cụm, sau đó dừng lại. Bƣớc 6: Tính các độ thuộc của các điểm dữ liệu còn lại: Gọi ij là độ thuộc của xi vào c jcc . Ta có: ij       n k m c ki c ji ccx ccx 1 1 1 2 2 )( 1 Tóm lại, phân cụm mờ là một sự mở rộng của PCDL bằng cách thêm vào yếu tố quan hệ giữa các phần tử và các cụm dữ liệu thông qua các trọng số trong ma trận U. Bằng cách này, có thể khám phá ra các cụm dữ liệu phức tạp theo cách mềm dẻo từ một tập dữ liệu đã cho. Thuật toán phân cụm mờ là một cách thức mở rộng cho các thuật toán phân cụm rõ nhằm khám phá ra các cụm dữ liệu chồng lên nhau trên các tập dữ liệu có kích thƣớc lớn, nhiều chiều và nhiều nhiễu... 58 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên CHƢƠNG 4 MÔ HÌNH MẠNG NƠRON ĐA KHỚP DÙNG CHO PHÂN CỤM MỜ 4.1. Tổng quan về mạng Nơron .................................................................................... 4.2. Cấu trúc mạng Nơron ............................................................................................. 4.2.1. Hàm kích hoạt ................................................................................................. 4.2.2. Liên kết mạng .................................................................................................. 4.2.3. Bài toán huấn luyện mạng ............................................................................... 4.3. Mạng HOPFIELD .................................................................................................. 4.3.1. Huấn luyện mạng ............................................................................................ 4.3.2. Sử dụng mạng .................................................................................................. 4.4. Mạng Nơron đa khớp dùng cho phân cụm ............................................................. 4.4.1. Xây dựng lớp mạng Layer1 cho tối ƣu các trung tâm cụm ............................. 4.4.2. Xây dựng lớp mạng Layer2 cho tối ƣu các độ thuộc ...................................... 4.5. Sự hội tụ của FBACN ............................................................................................ 4.5.1. Chứng minh sự hội tụ của FBACN ................................................................. 4.5.2. Sự hội tụ FBACN liên tục của Layer1 ............................................................ 4.5.3. Giải thuật của FBACN và FBACN với việc học ............................................ 58 61 61 61 61 62 62 63 63 65 68 72 72 74 75 Thuật toán FCM-Cải tiến đã khắc phục đƣợc một số hạn chế của thuật toán FCM và εFCM. Tuy nhiên nó lại có nhƣợc điểm là mỗi khi có yêu cầu phân cụm thì thuật toán sẽ chạy từ đầu, các kết quả của các mẫu trƣớc là không sử dụng đƣợc cho lần sau nên thời gian chạy khá lớn nếu nhƣ kích thƣớc mẫu lớn. Vì vậy, trong chƣơng này, chúng ta nghiên cứu một mô hình mạng Nơron đa khớp dùng cho bài toán phân cụm mờ (a fuzzy bi-directional associative clustering network –FBACN). Mạng Nơron này chủ yếu dựa vào tài liệu của hai tác giả Chih-Hsiu Wei, Chin - Shyurng Fahn. 4.1. Tổng quan về mạng Nơron Trƣớc hết chúng ta ai cũng biết rằng tri thức của loài ngƣời cho đến nay hết sức phong phú, sâu rộng và đa dạng. Nó bao gồm những hiểu biết của chúng ta từ thế giới vi mô nhƣ nguyên tử, điện tử, hạt nhân, các hạt cơ bản, ... 59 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên đến những hiểu biết vĩ mô về trái đất, về hệ mặt trời, hệ thiên hà, ... . hiểu biết về thế giới tự nhiên và xã hội, về các nghành khoa học, kỹ thuật khác nhau nhƣ: toán, lý, hóa, công nghệ thông tin và cả những hiểu biết về bản thân con ngƣời. Thế nhƣng có một điều mà có vẻ nhƣ là một nghịch lý đó là chúng ta biết "rất ít" về chính bộ não của chúng ta. Hơn nữa do nhu cầu ngày càng cao trong việc giải quyết các vấn đề phức tạp và do bản chất của con ngƣời là không muốn bằng lòng với hiện tại mà luôn muốn vƣơn tới những gì cao hơn, hoàn thiện hơn. Có lẽ chính vì những điều trên mà thuật ngữ "mạng Nơron" hoặc "mạng Nơron nhân tạo" đã ra đời. Các thuật ngữ đó nói đến một nghành kỹ thuật mới mà nó đòi hỏi kiến thức từ nhiều nghành khoa học khác nhau nhƣ toán học, vật lý học, hóa học, sinh vật học, tâm lý học, thần kinh học, ... và tất cả chỉ nhằm làm sao tạo ra những chiếc máy tính hoạt động giống nhƣ " bộ não " của chính chúng ta. Mạng Nơron nhân tạo hay thƣờng đƣợc gọi ngắn gọn là mạng Nơron là một mô hình toán học hay mô hình tính toán đƣợc xây dựng dựa trên các mạng Nơron sinh học. Nó gồm có một nhóm các Nơron nhân tạo(nút) nối với nhau, và xử lý thông tin bằng cách truyền theo các kết nối và tính giá trị mới tại các nút. Trong nhiều trƣờng hợp, mạng Nơron nhân tạo là một hệ thống thích ứng, tự thay đổi cấu trúc của mình dựa trên các thông tin bên ngoài hay bên trong chảy qua mạng trong quá trình học. Trong thực tế sử dụng, nhiều mạng Nơron là các công cụ mô hình hóa dữ liệu thống kê phi tuyến. Chúng có thể đƣợc dùng để mô hình hóa các mối quan hệ phức tạp giữa dữ liệu vào và kết quả hoặc để tìm kiếm các dạng mẫu trong dữ liệu. 60 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Hình 4.1: Mô hình mạng Nơron Mạng Nơron nhân tạo (Artificial Neural Network) là một mô hình toán học bao gồm các nút xử lý thông tin cơ sở (gọi là đơn vị xử lý hoặc Nơron) có mối liên hệ tƣơng hỗ cao, tiến hành xử lý thông tin song song và phân tán có năng lực tính toán mạnh (ví dụ hiện nay nó có thể học, nhớ và suy diễn từ mẫu dữ liệu...). Mỗi liên kết giữa hai Nơron kèm theo một trọng số nào đó, đặc trƣng cho đặc tính kích hoạt/ức chế giữa các Nơron. Có thể xem trọng số là phƣơng tiện để lƣu giữ thông tin dài hạn trong mạng Nơron và nhiệm vụ của quá trình huấn luyện (hay còn gọi là quá trình học) mạng là cập nhật các trọng số khi có thêm thông tin về các mẫu học, hay nói cách khác, các trọng số đƣợc điều chỉnh sao cho dáng điệu vào ra của nó mô phỏng hoàn toàn phù hợp với môi trƣờng đang xem xét. Vì vậy, cấu trúc của mạng Nơron chủ yếu đƣợc đặc trƣng bởi loại của các Nơron và mối liên hệ xử lý thông tin giữa chúng và do đó, mạng Nơron có rất nhiều ứng dụng trong nhiều lĩnh vực nhƣ nhận dạng, phân lớp ảnh, phân tích - nén dữ liệu, các bài toán tối ƣu, dự báo, chuẩn đoán,… Và xu thế hiện đại đó là sự kết hợp mạng Nơron với logic mờ. 61 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 4.2. Cấu trúc mạng Nơron 4.2.1. Hàm kích hoạt Hàm kích hoạt của từng Nơron trong mạng Nơron đóng vai trò quan trọng trong sự liên kết giữa các Nơron. Hàm này đặc trƣng cho mức độ liên kết giữa các Nơron. Trong lý thuyết mạng Nơron, phép tổng hợp các tín hiệu đầu vào thƣờng đƣợc kí hiệu dƣới dạng: 1 n j i ji i net x    với 1..,j j nx  là các tín hiệu vào. 1( ,..., )ji j jn   là trọng số, n là số tín hiệu đầu vào. Đầu ra của Nơron j thƣờng đƣợc kí hiệu là outj hoặc fj, đƣợc gọi là hàm kích hoạt. 1 ( ( ) ) n j j i i i out f f x t      , với  là ngƣỡng kích hoạt Nơron, t là thời gian, f là hàm kích hoạt. 4.2.2. Liên kết mạng Sự liên kết trong mạng Nơron tuỳ thuộc vào nguyên lý tƣơng tác giữa đầu ra của từng Nơron riêng biệt với các Nơron khác và tạo ra cấu trúc mạng Nơron. Về nguyên tắc sẽ có rất nhiều kiểu liên kết giữa các Nơron nhƣng trong thực tế ta thƣờng gặp các dạng nhƣ: Mạng truyền thẳng và mạng hồi quy.... 4.2.3. Bài toán huấn luyện mạng Bài toán huấn luyện mạng là quá trình giải bài toán tối ƣu hóa tham số của mạng, chủ yếu là các trọng số liên kết mạng và cấu trúc các dạng liên kết của các Nơron, giữa các lớp dựa trên thông tin có trong hệ thống. Thƣờng thì quá trình huấn luyện mạng nơtron(hay còn gọi là thuật học) đƣợc thực hiện qua phép so sánh đầu ra của mạng với tín hiệu chỉ đạo. Mô hình học có giám sát đƣợc mô phỏng nhƣ Hình 4.2 dƣới đây: 62 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Hình 4.2: Mô hình học có giám sát Sai số e = y-d là cơ sở để huấn luyện mạng. Tiếp theo chúng ta tìm hiểu một mô hình mạng Nơron đƣợc áp dụng rất nhiều là mạng Hopfield. 4.3. Mạng HOPFIELD Năm 1982 nhà vật lý ngƣời Mỹ J.J Hopfield đã đề xuất ra mô hình mạng Nơron (Neural Network - NN) cho phép tạo ánh xạ dữ liệu từ tín hiệu vào sang tín hiệu ra theo kiểu tự kết hợp, tức là nếu tín hiệu vào là X thuộc miền giá trị D nào đó thì kết quả Y cũng phải thuộc miền D đó. Nhờ vậy, mà một véctơ tín hiệu vào X bị thiếu thông tin hoặc bị biến dạng có thể đƣợc phục hồi về dạng nguyên bản của mình. Trong ứng dụng, mạng Hopfield đã mô phỏng đƣợc khả năng tự kết hợp của bộ não con ngƣời. Ngoài ra, với một số cải biên mạng Hopfield còn đƣợc dùng để giải quyết các bài toán tối ƣu, bài toán xử lý dữ liệu trong điều khiển tự động... 4.3.1. Huấn luyện mạng Mạng Hopfield học dựa trên nguyên tắc học có giám sát. Giả sử có p mẫu học tƣơng ứng với các véctơ tín hiệu vào Xs, với s = 1, 2, .., p. Mạng Hopfield sẽ xác định ma trận trọng số W sao cho: Xs = Tinh(Xs,W) với mọi s =1, 2, ..p. Với ma trận trọng số W đƣợc xác định nhƣ sau: 63 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 1 0 . , , p sj si sji i j x x if i j          với Xs=(xs1,..,xsm) 4.3.2. Sử dụng mạng Giả sử ta đƣa vào mạng tín hiệu vào là véctơ X. Sử dụng mạng để tính đầu ra tƣơng ứng với tín hiệu vào X là quá trình lặp gồm các bƣớc: 1. Ban đầu, đặt X(0)=X. Gọi Y(1) là véctơ tín hiệu ra tƣơng ứng với một lần cho X(0) lan truyền trong mạng. Y (1) = out (1)= Tính (HF, X(0)). 2. Nếu (0) (0) Y X thì tiếp tục lặp với bƣớc t = t+1 và X(t+1)=Y(1). Ngƣợc lại thì dừng. Tiếp theo chúng ta nghiên cứu một mô hình mạng Nơron dùng cho phân cụm mờ, đó là mạng Nơron đa khớp. 4.4. Mạng Nơron đa khớp dùng cho phân cụm Một vài năm trƣớc, các hệ thống Nơron động(đôi khi gọi là mạng Nơron hồi quy) đƣợc sử dụng nhiều trong các quá trình xử lý thông tin. 64 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Hình 4.3: Mô hình FBACN Cấu trúc của mạng Nơron đa khớp-FBACN đƣợc đƣa ra nhƣ hình 4.3. Lớp hồi quy Layer1 đƣợc thực hiện bởi một mạng Hopfield để tối ƣu hoá các trung tâm cụm. Trong khi đó lớp hồi quy Layer2 đƣợc thực hiện bởi một mạng Nơron đa khớp nối để tối ƣu các độ thuộc. Kết hợp Layer1 và Layer2 tạo thành lớp hồi quy 3, lớp này làm nên cấu trúc động của mạng. Hoạt động của FBACN đƣợc mô tả nhƣ sau: Thứ 1 là khởi tạo ngẫu nhiên các trung tâm cụm và độ thuộc thành viên của Layer1 và Layer2 tƣơng ứng. Thứ 2, khởi tạo các độ thuộc thành viên trong Layer2 sẽ đƣợc truyền sang Layer1. Thứ 3, dựa trên việc nhận đƣợc các độ thuộc thành viên, Layer1 thực hiện quá trình hồi quy để thu đƣợc các trung tâm cụm tối ƣu mới. Thứ 4, các trung tâm cụm mới của Layer1 truyền sang Layer2. Thứ 5, dựa trên việc nhận đƣợc các trung tâm cụm mới, thực hiện quá trình hồi quy để thu đƣợc độ thuộc thành viên tối ƣu mới. Việc hoàn tất quá trình trên từ bƣớc 2 đến bƣớc 5 đƣợc gọi là quá trình lặp. Quá trình lặp diễn ra cho tới khi nào đạt tới một tiêu chuẩn tới hạn. 65 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 4.4.1. Xây dựng lớp mạng Layer1 cho tối ƣu các trung tâm cụm Lớp Layer1 của FBACN có thể sử dụng mạng Hopfield hoặc mạng Nơron đa khớp tuỳ thuộc vào các ràng buộc của FC-partition (FC- fuzzy c). Nếu ràng buộc làm cho hàm mục tiêu có dạng bậc cao, hoặc dạng logarithm, hoặc dạng sin, v.v.. thì ta sử dụng mạng Nơron đa khớp thay vì dùng mạng Hopfield đơn giản. Hình 4.4: Mô hình Lớp Layer1 của FBACN Gọi  ji là trọng số kết nối hoạt động của Nơron j với Nơron vào i. Tất cả các đầu vào đến Nơron thứ j đƣợc kí hiệu là ij. Khi đó, tổng hợp các tín hiệu đầu vào đối với Nơron j là: 1     n j i ji j i net v i (1). Với vi là đầu ra của Nơron i, f là hàm đơn điệu tăng và liên tục. Ta có hàm kích hoạt 2 ( ) 1 1 exp( . ) j j f net r net     (2). ở đây, ngƣỡng r > 0 làm tăng tính thích nghi và khả năng tính toán của mạng Nơron. Giả sử g là chỉ số đệ quy và khi đó 66 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ( 1) ( ) ( ) 1 ( ) ( . ) s g g g j j ji i j i v f net f v i     (3) Khi đó, ta có thể diễn tả mạng Nơron thông qua ma trận NET sau: NET = WV + I (4) với 1 2 s net net NET net               , 11 1 21 2 1 s s s ss W                        , 1 2 s v v V v               và 1 2 s i i I i               Để đánh giá tính ổn định của hệ thống trong hình 4.4, chúng ta dùng hàm tính toán năng lƣợng CEF(computational energy function-CEF). Ta có CEF(E) là: 1 . . . 2 T TE V W V I V   (5) Hay cụ thể hơn là: 1 1 12 1 . . s s ji i j j j j i j s E v v i v        (6) Trong công thức (6) thì E là dạng toàn phƣơng. Vì vậy, trong mạng Nơron động này ta có thể dùng hàm mục tiêu dạng toàn phƣơng để tối ƣu hóa các tham số. Tiếp theo, ta sẽ lý giải sự phù hợp giữa hàm mục tiêu của FC-partion và hàm tính toán năng lƣợng của FBACN. Ta có hàm mục tiêu của FC-partion là: , 1 1 ( ; ) 2 ( ) n c T T T m m k k i k i i i k k i z U v x x v x v v u          (7) Trong Layer1 của FBACN, các tham số tối ƣu là các trung tâm cụm vi. Các độ thuộc mới ui,k đƣợc thực hiện từ lớp 2 tới Layer1 sẽ kích hoạt hồi quy trong Layer1 để tối ƣu vi. Ngoài ra, ui,k tạm thời coi là các hằng số trong khi hồi quy trong Layer1. Từ định nghĩa của hàm mục tiêu, các véctơ trung tâm của các cụm p ipiii Rvvvv  ),..,,( 21 là véctơ p chiều. Vì vậy, ta phải khai triển 67 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên (7) để khử biểu thức véctơ trƣớc khi nó đƣợc đem so sánh với hàm tính toán năng lƣợng thăng giá trị. Thăng giá trị đƣợc khai triển trong công thức (7) với lần khử đầu tiên là: 2 , , , , 1 1 1 ( ; ) 2 . ( ) pn c m m i l k l i l i k k i l z U v v x v u          (8) Quan sát (6) và (8) ta thấy sự khác nhau chính giữa hai công thức này là cách ký hiệu khác nhau. Trong mạng Nơron, thì các hoạt động ra của các Nơron đƣợc ký hiệu một cách duy nhất bằng một ký hiệu dƣới dòng. Chẳng hạn, hoạt động ra vi với si ...1 . Tuy nhiên, sau khi khai triển hàm mục tiêu của FC-pariton, có 2 từ viết dƣới dòng trong tham số vi,l, với 1..1, 1..l i c  . Để thống nhất trong cách thể hiện, ta ký hiệu lại nhƣ sau: , ( 1).i l i p lv v   (9) Khi đó, ta viết lại biểu thức (8) nhƣ sau: , ( 1) , 1 1 1 ( ; ) [ 2( ) . . pn c m m i k i p l k l k i l z U v u v x       2 , ( 1)( ) . ] m j k i p lu v   (10) Số Nơron s trong Layer1 ở (6) là c p . Ta có 1 2 c p i i I i                ,với ( 1) , , 1 2 . n m i p l i k k l k i u x     , 1.. 1..i c và l p  (11) và các phần tử của ma trận W đƣợc xác định bởi: / , 1 2 , 0, n m i p k kji u i j i j             , , 1..i j c n  (12) với ký hiệu | x | là cách lấy số nguyên cao hơn và gần nhất so với x. 68 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Quá trính tối ƣu của Layer1: Mục tiêu của mạng hồi quy là làm cho hàm mục tiêu xấp xỉ tới giá trị nhỏ nhất. Do W là ma trận đối xứng nên WT=W, ta lấy gradient của véctơ năng lƣợng trong (5) ta đƣợc: 1 ( ). . 2 T E W W V I W V I NET          (13) và ( ) . ( )T TE E V NET V       1 . s j j j net v     (14) Tiếp theo, chúng ta xây dựng hàm kích hoạt (liên tục hoặc rời rạc) f đƣợc sử dụng ở trong Layer1 của FBACN theo công thức sau: ( ) ( ) ( 1) ( ) ( ) , 0 ( ) , 0 g g j j jg g j g g j j j v if net v f net v if net            (15) với j là giá trị dƣơng nhỏ nhất để điều chỉnh vj. Ta thấy khi ( ) 0gjnet  thì ( 1) ( )g g j j j jv v v     >0, 1 . 0 s j j j E net v       . Trong kiểu kiến trúc này, thì sự cập nhật hệ số j với giá trị không hạn chế. Theo phƣơng pháp mà ta đã thiết kế thì cách lựa chọn giá trị của nó là phù hợp với tiến triển của Layer1. 4.4.2. Xây dựng lớp mạng Layer2 cho tối ƣu các độ thuộc Lớp mạng Layer2 của FBACN có chức năng là tối ƣu hóa lớp các độ thuộc. Ta có thể coi các vi là các hằng số tạm thời trong khi lớp Layer2 hồi quy. Ta có tập 2 ,k i i kx v d  . Khi đó, công thức:   2 , 1 1 ( ; ) c n m m i k k i i k z U v u x v     đƣợc viết lại là , , 1 1 ( ) c n m i k i k i k u d    . Khi đó, bài toán tối ƣu trong lớp Layer2 của FBACN là: làm min , , 1 1 ( ) . c n m i k i k i k u d    với ràng buộc , 1 1, 1.. c i k i u k n     . 69 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Theo công thức Lagrange thì ta có thể phát biểu lại bài toán nhƣ sau: 2 , , , 1 1 1 ( ) 1 n c c m i k i k i k k i i u d u                  (16) với  là tham số Lagrange (thƣờng 10000 100000  ). Ta ký hiệu lại , ( 1).i k k c iu u   và , ( 1).i k k c id d   (17) Khi đó, ta có thể biểu diễn lại hàm mục tiêu là: 2 ( 1). ( 1). ( 1). 1 1 1 ( ) . ( 1) n c c m k c i k c i k c i k i i u d u                 (18) Trong công thức (18) thì số hạng có bậc cao nhất là ( 1).( ) m k c iu   (thông thường ta chọn m=2) với k=1, 2, ..,n và i = 1, 2, ..., c. Nhƣng mạng Hopfield chỉ phù hợp với bài toán tối ƣu bậc hai. Vì vậy, ta phát triển mạng Nơron đa khớp cho các bài toán tối ƣu chung. Tức mạng Nơron đa khớp có thể giải quyết đƣợc với bất kỳ hàm mục tiêu bậc cao có ràng buộc nào. Mô hình mạng Nơron đa khớp đơn giản đƣợc sử dụng cho Layer2 nhƣ sau: Hình 4.5: Mô hình Lớp Layer2 của FBACN Tính động của mạng Nơron đa khớp trong hình 4.5 là: 70 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ( 1) ( ) ( ) ( ) 1 ( ) ( ( . . ) ) S g g g g j j ji i ji i j i u f net f u z u i      , với j=1, 2, ..., s. (19) Ta có ma trận đầu vào mạng: . .NET WU ZU I   (20) Với 11 12 1 21 22 2 1 2 s s s s ss z z z z z z Z z z z                   và 1 2 S u u U u                                   1 1 2 1 1 )1( m nxc m m m u u u U  , m > 1 và U(1) = U (21) Ta ký hiệu chuyển vị của U(m-1) là: ( 1) T mU  . Khi đó, hàm tính toán năng lƣợng của mạng Nơron sẽ đƣợc tính bởi công thức: IUUZUU m E TTTm ... 2 1 -W.U. 1 )1(               (22) Với số lƣợng Nơron s trong lớp Layer2 là n c . Ta có thể tính toán các phần tử của ma trận W, Z và I nhƣ sau: 1 2 0 0 0 0 0 0 c n d d W m d                       tức là các phần tử của W đƣợc tính theo công thức sau: , 0 , md i j i ji i j          , , 1,2,..i j c n  (23) Z là ma trận cỡ ( ) ( )c n c n   và đƣợc xác định nhƣ sau: 2 ( 1). . 0 , , ji i i c j c c c if z                    với i,j = 1, 2, ..., c n . (24) Và ma trận I là ma trận một chiều cỡ c n và đƣợc xác định nhƣ sau: otherwise 71 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2 2 2 I                 Do ma trận trọng số W là đối xứng (W được gọi là đối xứng nếu A. W.B = B.W.A), vì vậy hàm tính toán năng lƣợng ở (22) đƣợc biểu diễn là: IUUZUU m E TTT ... 2 1 W.U. 1 1)-(m              (25) U có thể điều chỉnh hai ma trận trọng số W và Z. Khi đó, ma trận NET của mạng Nơron đa khớp đƣợc xác định nhƣ sau: 1. .mNET WU ZU I     Gọi h là hàm số xác định bởi: 1)(  mjj uuh (26). Khi đó, h đƣợc gọi là hàm để tính 1m ju  Và tính động của lớp Layer2 đƣợc thể hiện ở công thức: ( 1) ( ) ( ) g g u f net j j   ( ) 1 ( ) 1 ( ( ( ) ) ) s g m g ji j ji j j i f u z u i      (27) Với net j là tổng đầu vào của Nơron thứ j và đƣợc tính bởi công thức: jiji m iji s i j iuzunet     )..( 1 1  (28) Theo công thức (25), ta có gradient năng lƣợng E : sjiuzu u E s i jiji m iji j ..1),)..(( 1 1       với s = n c (29) Từ (28) và (29) ta có , 1.. E net j s ju j      (30) Quá trình tối ƣu của Layer2 Khi hàm mục tiêu (18) đƣợc cân bằng với hàm tính toán năng lƣợng (25) và gradient tính toán năng lƣợng đƣợc liên kết với giá trị net vào, kết quả tối ƣu dần đạt đƣợc khi mạng tiến triển. Từ khái niệm năng lƣợng, hàm 72 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên rời rạc f là hàm kích hoạt của mạng Nơron đa khớp đƣợc xây dựng giống nhƣ của lớp thứ nhất: Vectơ năng lƣợng gradient đƣợc tính toán liên quan đến uj: j j net u    Hàm kích hoạt rời rạc đƣợc đƣa ra : ( ) ( ) ( 1) ( ) ( ) 0, ( ) , g g j j jg g j j g j j if net otherwise u u f net u            (31) Với vectơ năng lƣợng gradient luôn âm và công thức (31), đảm bảo mạng Layer2 sẽ tối ƣu trong quá trình tiến hoá. 4.5. Sự hội tụ của FBACN 4.5.1. Chứng minh sự hội tụ của FBACN Một yếu tố quan trọng cho mạng hồi quy đó là khả năng ổn định của mạng. Trƣớc khi đƣa ra tính ổn định của mạng FBACN, chúng ta sẽ bắt đầu với một vài định nghĩa về không gian Metric và định lý đƣa ra bởi Steck và sau đó là một định lý hội tụ phổ quát. Định nghĩa 1: Trong không gian Metric cho tập X và hàm d: X X R  thỏa mãn các điều kiện: 1) ( , ) 0, ,d x y x y X   2) ( , ) 0d x y x y   3) ( , ) ( , ), ,d x y d y x x y X   4) ( , ) ( , ) ( , )d x z d x y d y z , ,x y z X  Định nghĩa 2: Cho X là không gian Metric với khoảng cách d và : X X  . Điểm x đƣợc gọi là điểm cố định của  nếu ( )x x  . Định nghĩa 3: Ánh xạ  là co nếu tồn tại c*, với *0 1c  sao cho:   ),(.)(),( * yxdcyxd  , Xyx , (32) 73 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nếu  thỏa mãn (32) thì  chỉ có 1 điểm cố định. Thật vậy, giả sử có 2 điểm cố định x và y. Khi đó theo (32) ta có: *( , ) . ( , )d x y c d x y . Vì vậy, d(x,y)=0, nên x = y. Vậy ta có thể khái quát điều trên thông qua định lý sau: Định lý về ánh xạ co(ánh xạ thu gọn-AXC): Ánh xạ co của không gian Metric đầy đủ có duy nhất một điểm cố định. Định lý 1: Cho mạng Nơron nhân tạo hồi quy kết nối đầy đủ gồm các Nơron s với kích hoạt động     s i j g iji g j inetfnet 1 )()1( )(. (33), với f là một hàm có giới hạn, liên tục và có giá trị thực, hàm có đạo hàm có giới hạn và nếu thỏa mãn: s cf ji 1** max '  , sji ..1&  (34) thì mạng hội tụ đến một điểm cố định duy nhất đối với bất kỳ một giá trị khởi tạo nào của mạng. Bổ đề: với mỗi hàm f thỏa mãn điều kiện giả thuyết, thì với bất kỳ ,x y R ta có '( ) ( ) maxf x f y f x y   (35) Dựa vào các định nghĩa, định lý và bổ đề ở trên, một định lý hội tụ phổ biến cho mạng Nơron đa khớp nối đƣợc đƣa ra nhƣ sau: Định lý 2(đối với mạng Nơron đa khớp nối): Ứng với mỗi mạng Nơron đa khớp nối gồm s Nơron có hai trọng số ji và jiz với tính động kích hoạt sau: ( 1) ( ) 1 ( ) 1 ( ( )) ( ) S g g m g j ji j ji j j i net f net z f net i      (36) ở đây f là hàm có giới hạn, liên tục và có giá trị thực. Nếu f thỏa mãn điều kiện: 1 ' ** max 1 ( )m ji jif z c s    , (với i, j = 1, 2, ..., s) (37) thì mạng hội tụ đến một giá trị cố định duy nhất đối với với mọi giá trị khởi đầu của mạng. Chứng minh: Theo định lý về ánh xạ co, để chứng minh FBACN là hội tụ đến một điểm duy nhất thì chúng ta phải chỉ ra tồn tại một hằng số 74 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên c* (0,1) sao cho với mọi giá trị 1 2( , ,..., ) S Snetx netx netx netx  và 1 2( , ,..., ) S Snety nety nety nety  thì   ),(.)(),( * netynetxdcnetynetxd  (38) Ta định nghĩa hàm số:             s j s i jiji m ijis inetfznetfnetnetnetnet 1 1 1 21 ))(.))(((),...,,()(  (39) Với không gian s là đầy đủ với Metric đã lựa chọn, thì ta có: ( , ) 1 s d netx nety netx nety netx nety i ii      , , snetx nety (40) Ta có : ( ( ), ( )) ( ) ( )    d netx nety netx nety = 1 1 1 1 ( ( )) ( ( )) ( ) ( ) S S m m i i ji i i ji j i f netx f nety f netx f nety z           ' 1 ' ' max max 1 1 ( ) S S m i i ji i i ji j i f netx nety f netx nety z           (41) ** 1 1 S S i i i j netx nety c      = *. ( , )c d netx nety (42) với * ** ** 1 . S j c c s c    . Theo (37) thì ** (0,1)c  (43) Theo (42) và (43) thì ánh xạ là ánh xạ co. Do đó, theo điều kiện của (37) thì mạng Nơron đang xét là hội tụ về một điểm duy nhất. 4.5.2. Sự hội tụ FBACN liên tục của Layer1 Hàm kích hoạt của Layer1 đƣợc xây dựng nhƣ sau: 2 ( ) ( ) 1 exp( . ) j f net v j j jr net j j       (44) Với j và r j là các số thực dƣơng. Ta cần tìm giá trị max của đạo hàm cấp 1 của (44). Ta biết rằng đạo hàm cấp 1 của hàm f là cực đại tại x nếu đạo 75 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên hàm cấp 2 của hàm f tại x là bằng 0. Giả sử ''( ) 0f net j  thì ta có netj=0. Vì vậy, giá trị max của ' f là đạt cực đại địa phƣơng tại netj = 0 và giá trị đó là . ' '( )max 2 r j j f f net j    (45) Mặt khác 2 0n ji    nên ta có ' '0 2 . 2 . .max maxf n f n rji j j     (46) Ta có 1 1 . . . . n r r j j js s n j      (47) với s là số lƣợng Nơron có trong mạng và s c p  trong lớp Layer1. Vì thế ta chọn 1 . . r j n s j   , và vì vậy ta có thể tìm đƣợc một hằng số ** (0,1)c  sao cho 1' ** maxf cji s    (48) Điều này thỏa mãn điều kiện của định lý 1 nên ta có mạng là hội tụ đến một điểm. Kết luận: Quá trình tính toán và chứng minh, ta có đƣợc kết quả sau:  Với Layer1, mạng thoả mãn giả thuyết của định lý 1, nên mạng hội tụ  Với Layer2, mạng thoả mãn giả thuyết của định lý 2, nên mạng hội tụ 4.6. Giải thuật của FBACN và FBACN với việc học Giải thuật của FBACN đƣợc thực hiện qua các bƣớc sau: GIẢI THUẬT CỦA FBACN 1) Thiết lập các giá trị c, m, λ, ε và các hệ số iδv, iδu trong lớp Layer1 và Layer2 tƣơng ứng. 2) Đặt hệ số ổn định v và u cho Layer1 và Layer2 tƣơng ứng. 3) Khởi tạo ngẫu nhiên các trung tâm cụm ( 1). ,i p lv   i=1, 2, ..., c và l = 1, 2.., n trong Layer1 và lớp thành viên ,i k fcu M   với k=1, 2, 76 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ...,n và i = 1, 2, ...,c trong Layer2. 4) Cập nhật các hệ số iv v j   và iu u j   và giá trị mạng ban đầu (0) 0net j  với j =1, 2, ..., s (s=c.p trong Layer1 và s=n.c trong Layer2). 5) Thiết lập chỉ số hồi quy g =1 cho Layer1. 6) Trong Layer1, tính ma trận trọng số W theo công thức (12), ma trận tín hiệu vào bên ngoài I theo công thức (11), và giá trị mạng NET theo công thức (4). 7) For j = 1 to s do if ( ) ( 1). 0g gj jnet net   then : / 2 j j v v  ; 8) For j = 1 to s do if ( ) 0gjnet  then :j j j v v v  else :j j j v v v  9) if (( )&( )&...&( ) 1 2 v v v v v vs         then goto 10) else {g:= g+1; goto 6)}. 10) Đặt chỉ số hồi quy g=1 cho Layer2. 11) Trong Layer2, tính ma trận trọng số W theo công thức (23), ma trận trọng số Z theo công thức (24) và  TI  2,...,2,2 và ma trận IUZNET m   .W.U 1 . 12) For j = 1 to s do if ( ) ( 1) . 0 g g net net j j   then : / 2u u j j   ; 13) For j = 1 to s do if ( ) 0 g net j  then :u u uj j j   77 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên else u : u uj j j   14) if (( )&( )&...&( ) 1 2 u u u u u us         then goto 15) else {g:= g+1; goto 11)}. 15) if ( ) ( 1)g g U U   then Stop else goto 4 Đối với FBACN với việc học thì thuật toán tƣơng tự nhƣ của FBACN, nhƣng từ bƣớc 10 đến bƣớc thứ 14 thì đƣợc thay bằng 10’ đến 17’. Trƣớc hết ta định nghĩa một số tham số: p0 là hằng số tỉ lệ xác suất nằm trong [0,1], sử dụng để tính xác suất. EquiCycle là chu kỳ thăng bằng ấm(có nghĩa là khi vòng lặp đang xử lý cần giữ thăng bằng ấm tại nhiệt độ T). Tstart là nhiệt độ xung quanh, Tstop là nhiệt độ dừng(tức dừng việc học) và Tstep là tổng nhiệt độ thấp hơn trong mỗi vòng lặp. Giải thuật của FBACN với việc học đƣợc thực hiện nhƣ sau: GIẢI THUẬT CỦA FBACN VỚI VIỆC HỌC 1’ -> 9’ = 1 -> 9 của FBACN 10’) Đặt T = Tstart. 11’) Đặt chỉ số hồi quy g = 1 cho Layer2. 12’) Trong Layer2, tính giá trị của ma trận trọng số W theo công thức (23), ma trận trọng số Z theo công thức (24) và ma trận tín hiệu vào từ bên ngoài I và ma trận giá trị mạng NET. 13’) if g EquiCycle then { For j =1 to s do { Tính xác xuất ( ) 0 /1 . g j j j T p p e net u     ; 78 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên  ( ) ( 0,1 )gja Rand }} esle { For j =1 to s do { ( ) ( ) 0; 1 g g p a j j  }}; 14’) for j = 1 to s do if ( ) ( 1) ( 1) ( 1) (( . ) 0)&( . 0)) g g g g net net a p j j j j      then : / 2u u j j   15’) for j =1 to s do { if ( ) ( )g g a p j j  then { if Rand([0,1]) 0.5 then :u u uj j j   else :u u uj j j   } else { if ( ) 0 g net j  then :u u uj j j   else :u u uj j j   }} 16’) if 1 2(( )&( )&...&( )su u u u u u        then goto 17’) else {g:= g+1; goto 12’)}. 17’) if T>Tstop then {T:=T-Tstep; goto 11’)} else goto 18’). 18’) if ( ) ( 1)g g U U   then Stop else goto 4) 79 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên CHƢƠNG 5 CÀI ĐẶT THỬ NGHIỆM VÀ ỨNG DỤNG 5.1. Cài đặt thử nghiệm thuật toán FCM ........................................................................ 5.2. Ứng dụng thuật toán FCM-Cải tiến vào nhận dạng ảnh .......................................... 79 82 Chƣơng này trình bày kết quả xây dựng chƣơng trình thử nghiệm của thuật toán FCM và ứng dụng thuật toán FCM-Cải tiến vào quá trình nhận dạng ảnh. 5.1. Cài đặt thử nghiệm thuật toán FCM FCM là một thuật toán đƣợc áp dụng khá nhiều trong phân cụm dữ liệu vì hiệu năng và tính hiện thực của nó khá tốt. Thuật toán FCM đƣợc bắt đầu bằng cách chọn C cụm và chọn ngẫu nhiên c điểm làm trung tâm cụm hoặc chọn phân hoạch ngẫu nhiên C cụm và tính trọng tâm của từng cụm này. Nếu số lƣợng dữ liệu nhỏ hơn số cụm thì ta gán mỗi dữ liệu là một trọng tâm của cụm, mỗi trọng tâm sẽ có 1 số cụm. Nếu số lƣợng dữ liệu lớn hơn số cụm, với mỗi dữ liệu, ta tính toán độ tƣơng tự có trọng số giữa điểm đó và trọng tâm cụm và lấy khoảng cách tối thiểu. Dữ liệu này thuộc về cụm có khoảng cách tối thiểu tới dữ liệu đó. Khi chúng ta không chắc chắn về vị trí của trọng tâm, ta cần điều chỉnh vị trí trọng tâm dựa vào dữ liệu đã cập nhật hiện tại. Sau đó, ta gán tất cả dữ liệu tới trọng tâm mới này. Quá trình này đƣợc lặp lại cho tới khi không còn dữ liệu di chuyển sang cụm khác. Về mặt toán học, vòng lặp này có thể chứng minh là hội tụ cực tiểu cục bộ. Quá trình cài đặt của thuật toán đƣợc mô phỏng thông qua giao diện của chƣơng trình nhƣ Hình 5.1 và Hình 5.2 dƣới đây:  Ngôn ngữ sử dụng là Visual C++ 6.0  Tham số ban đầu: Số cụm = 3, tham số mũ m = 2  Dữ liệu đầu vào là các điểm màu khác nhau 80 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Hình 5.1: Giao diện của chƣơng trình khi khởi động Khi ngƣời sử dụng nhập số cụm vào khung “Nhập số cụm”, kích chuột vào khung chƣơng trình để tạo ra các điểm của cụm, vị trí của các điểm đƣợc thể hiện ở khung “Toạ độ xy”. Chƣơng trình sẽ tự động tạo ra các cụm dữ liệu bằng cách tối giản tổng bình phƣơng các khoảng cách giữa dữ liệu và trọng tâm cụm tƣơng ứng khi ta kích chuột vào khung chƣơng trình để tạo ra mỗi điểm. Mỗi điểm và tọa độ của nó biểu thị cho một đối tƣợng với mô tả hai thuộc tính của đối tƣợng đó là màu sắc của điểm và số nhãn biểu thị cho cụm. 81 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Dƣới đây là hình ảnh thu đƣợc khi chạy chƣơng trình với số cụm nhập vào là 8 cụm.. Hình 5.2: Giao diện của chƣơng trình khi làm việc Chƣơng trình tự động phân thành 8 cụm thông qua số màu hiện trong từng cụm và tâm của mỗi cụm. 82 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 5.2. Ứng dụng thuật toán FCM-Cải tiến vào nhận dạng ảnh Bài toán nhận dạng chính là quá trình phân loại các đối tƣợng đƣợc biểu diễn theo một mô hình nào đó và gán cho chúng vào một lớp dựa theo các quy luật và các mẫu chuẩn. Nhận dạng có rất nhiều ứng dụng, đƣợc áp dụng vào rất nhiều lĩnh vực, chẳng hạn nhƣ nhận dạng vân tay, nhận dạng chữ viết, nhận dạng ảnh… Và phân cụm màu là một bƣớc rất quan trọng trong quá trình nhận dạng ảnh. Do số lƣợng điểm ảnh là rất lớn, thƣờng trên 80.000 điểm ảnh và số lƣợng màu của mẫu dữ liệu ảnh là phụ thuộc vào độ sắc nét của ảnh. Nếu ảnh có chất lƣợng càng tốt thì số lƣợng màu càng lớn, nhƣng dù ảnh có chất lƣợng nhƣ thế nào đi nữa thì số lƣợng màu vẫn lớn. Mặt khác, trong nhận dạng ảnh, chúng ta chỉ quan tâm tới một số yếu tố nhất định, chẳng hạn nhƣ mắt, lông mày, miệng và da,... nên số lƣợng màu mà ta quan tâm cũng không lớn lắm, vì vậy áp dụng thuật toán FCM-Cải tiến vào việc phân cụm màu trong nhận dạng ảnh là một ứng dụng rất cần thiết trong bài toán này. Quá trình ứng dụng của thuật toán FCM-Cải tiến đƣợc mô phỏng thông qua giao diện của chƣơng trình với Hình 5.3, Hình 5.4 và Hình 5.5 dƣới đây:  Ngôn ngữ sử dụng là Visual C++ 6.0  Tham số ban đầu: Khai báo mảng lƣu trữ số lƣợng màu của ảnh, mảng lƣu trữ số trung tâm của cụm, số lƣợng cụm, tham số mũ.  Dữ liệu đầu vào là một File ảnh màu(Bitmap)  Dữ liệu đầu ra là một ảnh màu đã đƣợc nhận dạng với số cụm màu đã đƣợc thuật toán FCM-Cải tiến thực hiện phân cụm. 83 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Hình 5.3: Giao diện của chƣơng trình khi khởi động Khi chƣơng trình khởi động xong, ta chọn một ảnh nguồn để thực hiện bằng cách ấn vào nút “Mở File Ảnh” và chọn một ảnh cần thực hiện nhƣ Hình 5.4 dƣới đây: 84 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Hình 5.4: Giao diện của chƣơng trình khi chọn ảnh để phân cụm Sau khi chọn xong, ta ấn vào nút “Thực hiện phân cụm”. Chƣơng trình sẽ thực hiện quá trình nhận dạng và phân cụm màu theo thuật toán FCM-Cải tiến và hiển thị kết quả ở khung “Ảnh Đích” nhƣ Hình 5.5 dƣới đây. 85 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Hình 5.5: Giao diện của chƣơng trình khi thực hiện phân cụm 86 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên KẾT LUẬN Trong quá trình tìm hiểu và hoàn thành luận văn tốt nghiệp với đề tài “Nghiên cứu một số phương pháp phân cụm mờ và ứng dụng”, dù đã đạt đƣợc những kiến thức nhất định, nhƣng em nhận thấy phân cụm dữ liệu trong KPDL nói chung và phân cụm dữ liệu mờ nói riêng là một lĩnh vực nghiên cứu rộng lớn, nhiều triển vọng. Đề tài đã cố gắng tập trung tìm hiểu, nghiên cứu và trình bày đƣợc một số kỹ thuật và thuật toán phân cụm dữ liệu phổ biến, một số kỹ thuật phân cụm mờ và mô hình mạng nơron đa khớp dùng cho phân cụm mờ trong KPDL hiện nay, trình bày một số cải tiến của thuật toán phân cụm mờ(FCM-Cải tiến) dựa trên các phƣơng pháp đã có, cài đặt thử nghiệm thuật toán phân cụm mờ(FCM) với ứng dụng phân cụm các điểm màu và thực hiện cài đặt ứng dụng của thuật toán FCM-Cải tiến đối với việc phân cụm màu trong bài toán nhận dạng ảnh màu. Tuy nhiên, do những hạn chế về tài liệu và thời gian nên em mới chỉ tìm hiểu đƣợc một số kỹ thuật điển hình trong phân cụm và đặc biệt là phân cụm mờ, cài đặt và thử nghiệm một số thuật toán ứng dụng .... nhƣng còn một số kỹ thuật khác vẫn chƣa đƣợc tìm hiểu và khai thác, cài đặt thử nghiệm chƣa áp dụng đƣợc cho bài toán phân cụm tổng quát.... Trong thời gian tới em sẽ tiếp tục nghiện cứu thêm một số kỹ thuật phân cụm và đặc biệt là các thuật toán phân cụm mờ kết hợp song song ứng dụng vào một số bài toán thực tế ở Việt Nam hiện nay và hy vọng sẽ dần đƣa những kiến thức đã có từ đề tài này sớm trở thành thực tế, phục vụ cho cuộc sống con ngƣời chúng ta. Học viên thực hiện An Hồng Sơn 87 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên TÀI LIỆU THAM KHẢO Tài liệu Tiếng Việt: 1. Phan Đình Diệu (1999), “Lô Gích trong Các Hệ Tri Thức”, NXB Đại học Quốc gia Hà Nội, Hà Nội. 2. Nguyễn Trọng Thuần, “Điều khiển Logic và ứng dụng”, Nhà xuất bản Khoa học và Kỹ thuật, 2004. 3. Bùi Công Cƣờng và Nguyễn Doãn Phƣớc, “Hệ mờ, mạng nơron và ứng dụng ”, NXB Khoa học và kỹ thuật, 2006. 4. Vũ Thanh Nguyên, “Ứng dụng logic mờ, mạng nơron mờ, hệ các luật mờ phân tích dự báo các mặt hàng chiến lược”, Hội thảo khoa học Hệ mờ, mạng nơron và ứng dụng, lần 1, Hà nội 8-9/11/2006. 5. Ngô Quốc Tạo, “Giáo trình Xử Lý Ảnh”, Lớp CHCLC-ĐH Công Nghệ-ĐHQG Hà Nội 2001-2002. 6. Ngô Quốc Tạo, “Bài giảng môn Data Mining”, Lớp CHK5-ĐH Thái Nguyên 2006-2008. 7. Ngô Quốc Tạo, “Bài giảng môn Xử Lý Ảnh”, Lớp CHK5-ĐH Thái Nguyên 2006-2008. Tài liệu Tiếng Anh: 8. Daniel T. Larose, “Discovering Knowledge in Data: An Introduction toData Mining”, ISBN 0-471-66657-2 CopyrightC 2005 John Wiley & Sons, Inc. 9. A. Arning, R. Agrawal, and P. Raghavan. Alinear method for deviation detection in larger databases, “In Proc. 1996 Int. Conf. Data Mining and Knowledge Discovery (KDD-96)”, Portland, Oregon, August 1996. 88 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 10. P.S. Bradley, U. Fayyad, C. Reina, Scaling Clustering Algorithms to Large Databases, “In Proc of 4th International conference on Knowledge Discovery and Dala Mining (Kdd-98)”, New York. 1998. 11. D. Fisher, “Knowledge acquisition via incremental conceptual clustering, In Machine Learning”, 2 pp. 139-/72, 1987. 12. D. Gibson, J. Kleinberg, P. Raghavan, “Clustering Categorical Data: An Approach Based on Dynamical Systems”, VLDB Journal 8 (3-4) pp. 222-236, 2000. 13. J. Han, M. Kamber, “Data Mining Concepts and Techniques”, Morgan Kaufmann Publishers, 2001. 14. A.K. Jain, R.C. Dubes, “Algorithms for clustering data”, Ptentice Hall, Englewood Cliffs, NJ, 1988. 15. R.A. Jarvis, E.A. Patrick, “Clustering using a similarity measure based on shared near neighbors”, IEEE Transactions on Computers C22, pp. 1025-1034, 1973. 16. M. Manago, Y. Kodratoff, “Inđuction of Decision Trees from Complex Structuted Data, In Knowledge Discovery in Databases”, AAAI/Th MIT press, pp. 289-306, 1991. 17. J.C.Bezdek, “Pattern Recognition with fuzzy Objective Function Algorithms”, New York, Plenum, 1981. 18. W.Pedrycz, “Algorithms of fuzzy clustering with partial supervision”, Pattern Recognition, vol. 23, pp.121-146, 1990. 19. M.P.Windham, “Cluster validity for fuzzy clustering algorithms”, “Fuzzy Sets and System”, vol. 3, pp. 177-183, 1981. 20. W.Pedrycz, “Algorithms of fuzzy clustering with partial supervision”, Pattern Recognition, vol. 23, pp.121-146, 1990. 89 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 21. G.Bueno, R.Gonzalez, J.Gonzalez, and M.Garcia-Rojo, “Fuzzy colour C-means clustering for pattern segmentation in histological images”, The 3rd European Medical and Biological Engineering Conference, 2005. 22. Chih-Hsiu Wei, Chin - Shyurng Fahn, “The multisynapse neural network and its application to fuzzy clustering”. 23. J.H.Wang and C.Y.Peng, “Optimal clustering using neural network”, in Proc. IEEE Int. Conf. Syst., Man, Cybern., vol.2, 1998, pp.1625-1630. 24. Y.Guo, X.Yin, and W.Gong, “ART2 neural network clustering for hierarchical simulation”, in Proc. SPIE Int. Soc.Opt.Eng., vol. 2.1998, pp.35-48. 25. M.F.Augusteijn and U.J.Steck, “Supervised adaptive clustering: A hybrid neural network clustering algorithm”, neural Comput.Applicat., vol.7,no. 1, pp.78-89, 1998. 26. E. C. Tsao, J. C. Bezdek, and N. R. Pal, “Fuzzy Kohonen clustering network”, Patterm recognition, vol.27, no.5, pp.757-764, 1994. 27. J. Lin, K. Cheng, and C.Mao, “A fuzzy Hopfield neural network for medical image segmentation”, IEEE Trans. Nuclear Sci., vol.43, 1996. 28. Hathaway R.J and Bezdek J.CNTT (2000), “Generalized fuzzy c-means clustering Strategies using LP Norm Distances”, IEEE Trans.Fuzzy Syst, No 5, pp.576-582. 29. J.E.Steck and S.N.Balakrishnan, “Use of Hopfield newral networks in optimal guidance”, IEEE Trans. Aerosp.Electron. Syst., vol.30, no.1, pp 287-293, Jan.1994.