Sử dụng mạng nơron nhân tạo Fuzzy ART để phân cụm dữ liệu

Nông Thị Hoa và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 106(06): 49 - 53 49 SỬ DỤNG MẠNG NƠRON NHÂN TẠO FUZZY ART ĐỂ PHÂN CỤM DỮ LIỆU Nông Thị Hoa1*, Hoàng Trọng Vĩnh2 1Trường Đại học Công nghệ Thông tin & Truyền thông - ĐH Thái Nguyên 2Công ty FPT software TÓM TẮT Mạng nơron mờ là một mạng nơron nhân tạo mà phối hợp của các khái niệm mờ, các luật suy diễn mờ với kiến trúc và việc học của các mạng nơron. Phân cụm dữ liệu là một công cụ quan trọng của khai thác dữ liệu và tìm ra tri thức trong một số lượng lớn dữ liệu. Fuzzy ART (Fuzzy Adaptive Resonance Theory) là một mạng nơron mờ mà giải quyết bài toán phân cụm dữ liệu tốt hơn các phương pháp phân cụm truyền thống. Trong nghiên cứu này, chúng tôi phân tích các ưu điểm của Fuzzy ART và hướng dẫn chọn các tham số của mô hình Fuzzy ART để giải bài toán phân cụm cho các tập dữ liệu đạt độ chính xác cao nhất. Các thực nghiệm được làm với 5 tập dữ liệu chuẩn trong cơ sở dữ liệu UCI để chứng minh tính hiệu quả của Fuzzy ART. Kết quả thực nghiệm cho thấy Fuzzy ART cho kết quả phân cụm với độ chính xác cao. Từ khóa: Fuzzy ART, ART, Fuzzy Neural Network, Fuzzy Set, Clustering GIỚI THIỆU* Phân cụm dữ liệu là một công cụ quan trọng của khai thác dữ liệu và tìm ra tri thức trong một số lượng lớn dữ liệu. Hơn nữa, phân cụm còn tổng hợp một số lượng lớn dữ liệu trong một số lượng nhỏ các nhóm nên phân cụm có ích cho cho việc hiểu một số lượng lớn dữ liệu. Một số phương pháp phân cụm truyền thống đã được đưa ra như K-mean [2], phân cụm phân cấp [3], và mô hình SOM [6] nhưng độ phức tạp tính toán của các phương pháp này khá lớn. Fuzzy ART [1] là một mạng nơron mờ có các ưu điểm gồm: Học dữ liệu huấn luyện cho đến khi thỏa mãn một điều kiện nhất định, có thể sinh ra nhóm mới mà không phá vỡ các nhóm đang tồn tại, dễ dàng lựa chọn các tham số của mạng. Do đó, Fuzzy ART phân cụm dữ liệu với độ chính xác cao và giảm đáng kể độ phức tạp tính toán. BÀI TOÁN PHÂN CỤM DỮ LIỆU Phát biểu bài toán Cho tập dữ liệu D. Mỗi dữ liệu I trong tập D được biểu diễn bằng một véc tơ có M phần tử. Mỗi thành phần của I nằm trong khoảng [0, 1]. Khi đó ta có: I=(I1, ., IM ). * Tel: 01238 492 484 Tập D có p nhóm. Mỗi nhóm có một véc tơ trọng số W gồm có M phần tử. Khi đó véc tơ trọng số của nhóm k được biểu diễn như sau: Wk=(Wk1, ., IkM ) Mỗi dữ liệu I thuộc về một nhóm h nhất định. Yêu cầu: Dựa vào sự tương đồng giữa mỗi dữ liệu I và véc tơ trọng số W của các nhóm để phân dữ liệu I vào nhóm h. Một số phương pháp giải truyền thống Teuvo Kohonen [6] đưa ra một mô hình của một quá trình tự tổ chức mới mà được gọi là mô hình SOM. SOM là một mạng nơ ron nhân tạo thực hiện học không giám sát để tạo ra một biểu diễn cho không gian dữ liệu vào với số chiều thấp hơn. M.Queen [2] đưa ra thuật toán K-mean mà phân chia tập dữ liệu vào một số cụm nhất định bằng việc cực tiểu hàm lỗi bình phương. Sau đó, trọng số của các cụm được cập nhật bởi giá trị trung bình của các mẫu trong mỗi phân cụm. Johnson [3] đưa ra thuật toán phân cụm phân cấp dựa vào sự nhập lại của hai cụm gần nhất. Tuy nhiên các phương pháp này có độ phức tạp tính toán khá cao do việc luôn tính lại trọng số của mỗi phân lớp khi xét một dữ liệu huấn luyện. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nông Thị Hoa và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 106(06): 49 - 53 50 FUZZY ART Mô hình mạng ART Các mạng nơron ART được phát triển bởi Grossberg [4][5] để giải quyết vấn đề về hiện tượng ổn định-linh hoạt. Mạng ART là một thuật toán học tăng cường nên mạng ART thích nghi được với một dữ liệu mới. Ở một thời điểm, mạng ART không cho phép thay đổi các mẫu đã lưu cho đến khi mẫu vào khớp với các mẫu đã lưu với một mức nhiễu nhất định. Nghĩa là, mạng ART có cả tính linh hoạt và ổn định. Một phân nhóm mới có thể hình thành khi môi trường không khớp với các mẫu đã lưu, nhưng môi trường không thể thay đổi các mẫu đã lưu trừ khi sự tương tự của chúng đạt đến một mức đặt trước. Cấu trúc chung của mạng ART được thể hiện ở Hình 1. Một mạng ART điển hình có hai tầng: tầng dữ liệu vào (F1) và tầng dữ liệu ra (F2). Tầng dữ liệu vào chứa N nút với N là số lượng các mẫu dữ liệu vào. Số lượng nút của tầng dữ liệu ra là động. Mỗi nút của tầng có một véc tơ kiểu tương ứng. Tính động của mạng được điều khiển bởi hai hệ thống con: hệ thống chú ý và hệ thống định hướng. Hệ thống chú ý đưa ra một nơron chiến thắng (hay nhóm) và hệ thống định hướng quyết định nhóm nào chấp nhận hay không chấp nhận dữ liệu vào đó. Mạng này ở trong một trạng thái cộng hưởng khi hệ thống định hướng chấp nhận một nhóm chiến thắng, nghĩa là véc tơ kiểu chiến thắng khớp đủ gần với mẫu dữ liệu vào hiện tại. Thuật toán Fuzzy ART Thuật toán này được Carpenter trình bày ngắn gọn trong [1]. Sau đây là ba tham số thể hiện tính động của mô hình Fuzzy ART: • tham số chọn α> 0; • tham số tốc độ học β∈[0, 1] • tham số ngưỡng ∈[0, 1]; Nội dung của thuật toán được trình bày như sau: Bước 1: Khởi tạo véc tơ trọng số. mỗi phân lớp j tương ứng với một véc tơ Wj= (Wj1,..., WjM) của các trọng số thích nghi hay vết bộ nhớ dài hạn. Số các nhóm tiềm năng N (j = i,..., N) là bất kỳ. Khởi tạo (1) và mỗi nhóm được coi là chưa hình thành. Sau khi một nhóm được chọn để mã hóa, nhóm được hình thành. Như biểu diễn dưới đây, mỗi vết bộ nhớ dài hạn Wji là không tăng dần theo thời gian và vì vậy các Wji hội tụ tới một giới hạn. Bước 2: Lựa chọn một nhóm chiến thắng: Với mỗi dữ liệu vào I và nhóm j, hàm chọn Tj được định nghĩa bởi (2) với phép toán AND, ⋏, trong logic mờ được định nghĩa: (3) và với dạng được định nghĩa: (4) Để đơn giản việc ký hiệu, Tj(I) trong Công thức 2 thường được viết là Tj khi dữ liệu vào I là cố định. Sự chọn nhóm được gắn chỉ số bằng j, với (5) Nếu có nhiều hơn một Tj là cực đại thì nhóm j với chỉ số nhỏ nhất được chọn. Cụ thể hơn, các nút được hình thành theo thứ tự j = 1, 2, 3, . . . . Bước 3: Kiểm tra trạng thái của mạng là cộng hưởng hay thiết lập lại: Cộng hưởng xuất hiện nếu hàm đối chiếu của nhóm được chọn đạt điều kiện về ngưỡng. Điều kiện là: (6) Sau đó việc học sẽ diễn ra. Hình 1: Mô hình đơn giản của mạng ART Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nông Thị Hoa và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 106(06): 49 - 53 51 Thiết lập lại xuất hiện nếu (7) Sau đó, giá trị của hàm chọn Tj được thiết lập -1 cho các biểu diễn dữ liệu vào để ngăn sự lựa chọn lại dữ liệu vào trong quá trình tìm kiếm. Một chỉ số mới j được chọn bởi Công thức 5. Quá trình tìm kiếm tiếp tục cho đến khi j được chọn thỏa mãn Công thức 6. Nếu không có nhóm đang tồn tại nào thỏa mãn điều trong Công thức 6 thì một nhóm mới j được sinh ra và đặt Bước 4: Học dữ liệu huấn luyện: :Véc tơ trọng số Wj được cập nhật theo công thức (8) Phân cụm dữ liệu bằng Fuzzy ART: Chọn ra một tập con (D’) các mẫu bất kỳ từ tập D. Dùng tập D’ để Fuzzy ART huấn luyện. Sau đó dùng tập dữ liệu còn lại để kiểm tra khả năng phân cụm của Fuzzy ART. Để tăng hiệu quả của việc học có thể chọn nhiều tập con khác nhau để huấn luyện và dùng phần dữ liệu còn để kiểm tra khả năng phân cụm. PHÂN TÍCH CÁC ƯU ĐIỂM VÀ HƯỚNG DẪN CHỌN CÁC THAM SỐ CHO FUZZY ART Các ưu điểm của Fuzzy ART để giải bài toán phân cụm dữ liệu Việc dùng mô hình Fuzzy ART vào phân cụm dữ liệu sẽ tận dụng được hết các ưu điểm của Fuzzy ART. Thứ nhất, Fuzzy ART học dữ liệu huấn luyện để hình thành các nhóm chỉ khi mức độ tương đồng giữa dữ liệu huấn luyện và một nhóm đạt đến một ngưỡng nhất định. Điều kiện này được điều chỉnh để chất lượng của mỗi nhóm là cao. Thứ hai, Fuzzy ART sinh ra các nhóm mới khi mức độ tương đồng giữa dữ liệu huấn luyện và mọi nhóm đều không đạt ngưỡng về sự tương đồng. Do nhóm mới được hình thành nên làm giảm được sự chồng chéo các nhóm. Thứ ba, các tham số của Fuzzy ART được lựa chọn dễ dàng do miền giá trị của cả ba tham số đều nằm trong miền [0, 1] và có thể chọn giá trị thích hợp như hướng dẫn ở phần tiếp theo. Theo các phân tích ở trên, chúng ta thấy Fuzzy ART giải quyết tốt bài toán phân cụm bởi hai lý do sau: Fuzzy ART được thiết kế để phân cụm dữ liệu và dễ dàng chọn được các tham số của Fuzzy ART để khả năng phân cụm là cao nhất. Hơn nữa, Fuzzy ART chỉ cập nhật trọng số của một nhóm được chọn và trọng số của nhóm mới cũng không phụ thuộc vào các mẫu đã xét thuộc về nhóm đó nên độ phức tạp tính toán của Fuzzy ART giảm hơn khá nhiều so với các phương pháp phân cụm truyền thống. Nói cách khác, việc áp dụng Fuzzy ART cho bài toán phân cụm dữ liệu là hiệu quả cả về mặt chất lượng và giảm thời gian tính toán. Hướng dẫn chọn giá trị cho các tham số của Fuzzy ART Việc lựa chọn giá trị cho các tham số để Fuzzy ART có khả năng phân cụm cao nhất là khá đơn giản. Theo Công thức (2), nếu α càng lớn thì khả năng dữ liệu huấn luyện được chọn vào một nhóm lại càng giảm và ngược lại. Do đó tùy vào mục đích của bài toán phân cụm là cần phân cụm thô hay độ chính xác cao, chúng ta có thể chọn α là nhỏ hay lớn. Tham số β thể hiện tốc độ học của mô hình. Nói cách khác, β thể hiện mức độ ảnh hưởng của dữ liệu huấn luyện đến trọng số của các nhóm. Theo Công thức (8), nếu β càng lớn thì ảnh hưởng của dữ liệu huấn luyện càng nhiều và ngược lại. Do đó tùy vào tính chất của dữ liệu trong tập mẫu, chúng ta có thể chọn β là lớn nếu các dữ liệu trong tập mẫu là chuẩn và chọn β là nhỏ nếu tập mẫu có chứa các mẫu dị thường. Theo Công thức (6), nếu ρ càng lớn thì sự tương đồng giữa dữ liệu huấn luyện và một nhóm càng cao. Do đó, chúng ta có thể chọn ρ thích hợp ứng với tính chất của tập dữ liệu cần phân cụm. Nói cách khác, nếu dữ liệu phân bố rời rạc và có nhiều dữ liệu dị thường thì nên chọn ρ là nhỏ và ngược lại. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nông Thị Hoa và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 106(06): 49 - 53 52 KẾT QUẢ THỰC NGHIỆM Chúng tôi chọn 5 tập dữ liệu chuẩn từ cơ sở dữ liệu UCI1 và Shape2 bao gồm Iris, Wine, Jain, Flame, và R15. Các tập dữ liệu này là khác nhau từ số thuộc tính, số phân cụm, số mẫu huấn luyện, và sự phân bố các mẫu ở các phân cụm. Bảng 1 thể hiện các thông tin trên của các tập dữ liệu được chọn. Bảng 1: Đặc trưng của các tập dữ liệu Thứ tự Tên tập dữ liệu Số phân cụm Số thuộc tính Số mẫu 1 Iris 3 4 150 2 Glass 7 9 214 3 Wine 3 13 178 4 Jain 2 2 373 5 R15 15 2 600 Dữ liệu của các tập dữ liệu được chuẩn hóa về miền [0,1]. Chúng tôi xác định giá trị của các tham số của mô hình để đạt được kết quả phân cụm cao nhất với α=0.5, β=0.1 và ρ=0.4. Với mỗi tập dữ liệu, chúng tôi làm các thử nghiệm con với số lượng mẫu tăng dần. Tỷ lệ phần trăm các mẫu được phân cụm đúng được thể hiện trong một bảng tương ứng với tập dữ liệu đó. Kiểm tra với tập Iris Sự phân bố số mẫu trong ba nhóm là đồng đếu mỗi nhóm có 50 mẫu. Bảng 2 thể hiện kết quả thực nghiệm với tập mẫu Iris. Các kết quả thể hiện rằng Fuzzy ART có tỉ lệ phân cụm dữ liệu đúng từ 93.3% đến 100%. Kết quả này cho thấy Fuzzy ART phân lớp đạt hiệu quả cao với tập Iris. Bảng 2: Tỷ lệ phần trăm các mẫu được phân cụm đúng trong tập mẫu Iris Số mẫu 30 60 90 120 150 Kết quả 100 98.3 93.3 95 96 Kiểm tra với tập Flame Sự phân bố số mẫu trong hai nhóm là 87 và 153. Các số liệu từ Bảng 3 thể hiện kết quả 1 Dữ liệu ở địa chỉ http:// archive.ics.uci.edu/ml/ datasets 2 Dữ liệu ở địa chỉ thực nghiệm với tập mẫu Flame. Các kết quả thể hiện rằng Fuzzy ART có tỉ lệ phân cụm dữ liệu đúng từ 84.6% đến 100%. Kết quả này cho thấy Fuzzy ART phân lớp đạt hiệu quả khá cao với tập Flame. Bảng 3: Tỷ lệ phần trăm các mẫu được phân cụm đúng trong tập mẫu Flame Số mẫu 50 100 150 200 240 Kết quả 100 98.0 98.7 95 84.6 Kiểm tra với tập R15 Sự phân bố số mẫu trong 15 nhóm là đồng đếu mỗi nhóm có 40 mẫu. Bảng 4 thể hiện kết quả thực nghiệm với tập mẫu R15. Các kết quả thể hiện rằng Fuzzy ART có tỉ lệ phân cụm dữ liệu đúng từ 95.3% đến 97.3%. Kết quả này cho thấy Fuzzy ART phân lớp đạt hiệu quả cao với tập R15. Bảng 4: Tỷ lệ phần trăm các mẫu được phân cụm đúng trong tập mẫu R15 Số mẫu 100 200 300 400 500 600 Kết quả 96 95.5 95.3 96 96.8 97.3 Kiểm tra với tập Wine Sự phân bố số mẫu trong ba nhóm lần lượt là 59, 71, và 48. Bảng 5 thể hiện kết quả thực nghiệm với tập mẫu Wine. Các kết quả thể hiện rằng Fuzzy ART có tỉ lệ phân cụm dữ liệu đúng từ 76.7% đến 100%. Kết quả này cho thấy Fuzzy ART phân lớp đạt hiệu quả khá cao với tập Wine. Bảng 5: Tỷ lệ phần trăm các mẫu được phân cụm đúng trong tập mẫu Wine Số mẫu 30 60 90 120 150 178 Kết quả 100 98.3 83.3 76.7 77.3 77.5 Kiểm tra với tập Jain Sự phân bố số mẫu trong hai nhóm là 276 và 97. Các số liệu từ Bảng 6 thể hiện kết quả thực nghiệm với tập mẫu Jain. Các kết thể hiện rằng Fuzzy ART có tỉ lệ phân cụm dữ liệu đúng từ 94.6% đến 99.6%. Kết quả này Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nông Thị Hoa và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 106(06): 49 - 53 53 cho thấy Fuzzy ART phân lớp đạt hiệu quả cao với tập Jain. Bảng 6: Tỷ lệ phần trăm các mẫu được phân cụm đúng trong tập mẫu Jain Số mẫu 100 200 300 373 Kết quả 99 99.5 96.3 94.6 Việc lựa chọn ba tham số α, β, ρ và kết quả phân cụm đúng của 5 thực nghiệm trên cho thấy Fuzzy ART giải quyết hiệu quả bài toán phân cụm dữ liệu với tỷ lệ % phân cụm đúng cao hơn 95% trong hầu hết các kiểm tra con. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN Chúng tôi đã sử dụng thành công mô hình Fuzzy ART cho nhiệm vụ phân cụm dữ liệu với việc lựa các tham số của mô hình để đạt kết quả phân cụm cao nhất. Kết quả thực nghiệm cũng cho thấy độ chính xác của các nhóm do Fuzzy phân cụm là cao trong hầu hết các trường hợp. Hiện nay, các thử nghiệm đã cho kết quả cao nhưng để khả năng phân cụm của Fuzzy ART chính xác hơn thì cần thiết kế thêm các thuật toán để tìm ra giá trị thích hợp cho các tham số tùy vào từng tập dữ liệu mẫu. TÀI LIỆU THAM KHẢO 1. G. Carpenter, S. Grossberg, and D. B. Rosen (1991), “Fuzzy ART: Fast Stable Learning and Categorization of Analog Patterns by an Adaptive Resonance System,” Neural Networks, vol. 4, pp. 759–771. 2. J.B.MacQueen (1967), “Some methods for classification and analysis of multivariate obser- vations,” Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability, no. 1, pp. 281–297. 3. S. C. Johnson (1967), "Hierarchical Clustering Schemes," Psychometrika, vol. 32, issue 3, pp. 241-254. 4. S. Grossberg (1976), “Adaptive pattern classification and universal recoding, II: Feedback, expectation, olfaction and illusions,” Biological Cybernetics, 23, 187-212. 5. S. Grossberg (1980), “How does a brain build a cognitive code”, Studies of mind and brain: Neural principles of learning, perception, development, cognition, and motor control (Chap. I). Boston, MA: Reidel Press. 6. T. Kohonen (1982), “Self-Organizing Formation of Topologically Correct Feature Maps,” Biological Cybernetics, Springer-Verlag, vol. 69, pp. 59–69. SUMMARY USING FUZZY ART NEURAL NETWORK FOR CLUTERING DATA Nong Thi Hoa1*, Hoang Trong Vinh2 1College of Information Technology & Communication - TNU 2 FPT software company Fuzzy neural network is an artificial neural network that combines fuzzy concepts, fuzzy inference rule with structure and learning ability of neural network. Clustering is an important tool in data mining and knowledge discovery. Fuzzy ART (Fuzzy Adaptive Resonance Theory) is a fuzzy neural network that solves effectively clustering problem. Fuzzy ART clusters better than traditional methods based on three following advantages: Learning data until satisfying a given conddition, creating a new category without affecting to existing categories, and easily choosing parameters of Fuzzy ART. In this papper, we apply Fuzzy ART for clustering 5 brenchmark datasets. After showing results of experiments, we present guide to choose suitable values for parameters of Fuzzy ART that the ability of clustering is the highest. Then, we analysis the advantages of Fuzzy ART when it is applied to clustering data. Results from experiments also show that Fuzzy ART cluster much effectively for clustering problems. Key words: Fuzzy ART, ART, Fuzzy Neural Network, Fuzzy Set, Clustering Ngày nhận bài: 15/5/2013; Ngày phản biện: 20/5/2013; Ngày duyệt đăng:26/7/2013 * Tel: 01238 492 484 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên