Một số giải pháp cải tiến nhằm tăng tốc độ thuật toán mạng nơron som

Mạng nơron SOM được ứng dụng chủ yếu trong các bài toán phân cụm dữ liệu. Tuy nhiên, tập dữ liệu vào cho những bài toán này thường rất lớn ảnh hứớng tới thời gian tính toán. Bài báo này trình bày hai giải pháp để cải thiện thời gian tính toán của mạng gồm: thu hẹp phạm vi tìm kiếm nơron chiến thắng và xử lý dữ liệu song song dựa trên kiến trúc mạng phân tầng. Đồng thời trình bày kết quả cài đặt thử nghiệm và đánh giá hiệu quả của mỗi giải pháp.
Nội dung trích xuất từ tài liệu:
Một số giải pháp cải tiến nhằm tăng tốc độ thuật toán mạng nơron somLê Anh Tú và ĐtgTạp chí KHOA HỌC & CÔNG NGHỆ116 (02): 79 - 84MỘT SỐ GIẢI PHÁP CẢI TIẾNNHẰM TĂNG TỐC ĐỘ THUẬT TOÁN MẠNG NƠRON SOMLê Anh Tú1*, Lê Sơn Thái1, Nguyễn Quang Hoan21Trường Đại học Công nghệ thông tin và Truyền thông – ĐH Thái Nguyên,2Học viện Công nghệ Bưu chính Viễn thôngTÓM TẮTMạng nơron SOM được ứng dụng chủ yếu trong các bài toán phân cụm dữ liệu. Tuy nhiên, tập dữliệu vào cho những bài toán này thường rất lớn ảnh hướng tới thời gian tính toán. Bài báo này trìnhbày hai giải pháp để cải thiện thời gian tính toán của mạng gồm: thu hẹp phạm vi tìm kiếm nơronchiến thắng và xử lý dữ liệu song song dựa trên kiến trúc mạng phân tầng. Đồng thời trình bày kếtquả cài đặt thử nghiệm và đánh giá hiệu quả của mỗi giải pháp.Từ khóa: SOM, Kohonen, BMU, phân tầng, phân cụm dữ liệuGIỚI THIỆU*Mạng nơron SOM được Teuvo Kohonen pháttriển vào những năm 80 [1]. Đây là một côngcụ thích hợp để giải bài toán phân cụm dữliệu, một bước tiền xử lý quan trọng trongkhai phá dữ liệu [2]. Khi áp dụng mạng nơronSOM để phân cụm dữ liệu, cần thực hiện theo3 giai đoạn:Giai đoạn 1: Huấn luyện mạng bằng tập dữliệu mẫu. Trong trường hợp tập dữ liệu huấnluyện chưa đủ lớn thì quá trình huấn luyện cóthể được lặp lại nhiều lần với cùng một tậpmẫu cho tới khi mạng đạt trạng thái cân bằng.Giai đoạn 2: Phân cụm nơron (thường sửdụng thuật toán tích tụ [10]) hoặc trực quanmạng để quan sát [11].Giai đoạn 3: Áp dụng mạng đã huấn luyện đểphân cụm (với mỗi phần tử trong tập dữ liệucần phân cụm, tìm trên ma trận Kohonennơron có đặc trưng khớp nhất và gán nhãnphần tử vào nơron này).Tuy nhiên, thuật toán SOM đòi hỏi thời giantính toán lớn (cả thời gian huấn luyện và ápdụng mạng đã huấn luyện) vì một số lý do sau:Thứ nhất, tập dữ liệu huấn luyện hoặc số lầnhuấn luyện phải đủ lớn để mạng đạt đượctrạng thái cân bằng.Thứ hai, dữ liệu được đưa vào mạng một cáchtuần tự, sau đó với mỗi phần tử dữ liệu được*Tel: 0989 199088, Email: latu@ictu.edu.vnđưa vào lại phải tìm kiếm tuần tự trên toàn bộma trận Kohonen để xác định nơron chiếnthắng (BMU-Best Matching Unit).Thứ ba, trong các bài toán khai phá dữ liệutập dữ liệu cần đánh giá thường rất lớn. Dovậy kích thước ma trận Kohonen phải đủ lớnđể mô tả được hết đặc trưng của dữ liệu,thường là hàng nghìn nơron.Hiện tại, đã có nhiều nghiên cứu về vấn đềnày, chẳng hạn: thuật toán Batch SOM [3]tăng tốc độ huấn luyện bằng cách chỉ cập nhậttrọng số của các nơron vào cuối quá trìnhhuấn luyện (sau khi duyệt hết các mẫu huấnluyện); Tree-Structured SOM (TS-SOM) [5]là một cấu trúc huấn luyện và tìm kiếm BMUdạng cây, trong đó mỗi nút trên cây là mộtnơron. Số lượng nút con của mỗi nút bằngnhau và tăng theo hàm mũ. Các nút cùng cấptạo thành một lớp (layer), lớp trên được dùngđể huấn luyện lớp dưới. Ví dụ, lớp đầu tiên có4 nút (nơron), mỗi nút có 4 nút con, vậy lớpthứ hai có 16 nút, lớp thứ 3 có 64 nút,... nhưvậy thời gian huấn luyện nhanh hơn do việctìm BMU tại mỗi bước huấn luyện được thựchiện theo các nhánh của cây. Tuy nhiên cấutrúc này vẫn còn nhiều hạn chế do dữ liệu vẫnđược đưa vào và xử lý trong mạng một cáchtuần tự. Mô hình mạng nơron SOM phân tầng(Hierarchical SOMs - HSOM) [4] với tưtưởng kết hợp chia dữ liệu (chia tập dữ liệuthành nhiều tập con) và chia mạng (chia matrận Kohonen thành nhiều nhóm nhỏ các79Lê Anh Tú và ĐtgTạp chí KHOA HỌC & CÔNG NGHỆnơron, mỗi nhóm nhỏ này được coi như mộtmạng con) nhằm giảm thời gian tìm kiếmBMU và xử lý dữ liệu một cách đồng thời.HSOM có hai dạng chính: dạng thứ nhất,ngay từ đầu dữ liệu được chia thành nhiều tậpcon để huấn luyện trên nhiều mạng sau đótổng hợp các kết quả huấn luyện vào một bảnđồ đặc trưng chung; dạng thứ hai, tập dữ liệusẽ được phân nhánh dần trong quá trình huấnluyện do đó hình thành một cấu trúc hình cây,với mỗi nút có thể là một nơron hoặc là mộtmạng Kohonen và đặc trưng của dữ liệu sẽđược biểu diễn trên các nút lá. HSOM là mộtcấu trúc phức tạp do có rất nhiều cách khácnhau để thực hiện chia dữ liệu và chia mạng.Costa đưa ra một cấu trúc cây phân tầng biểudiễn các cụm dữ liệu, trong đó mỗi nút củacây là một bản đồ Kohonen [6]. Tại mỗi nút,mạng vẫn được huấn luyện đầy đủ như SOMgốc, sau đó xây dựng ma trận trực quan UMatrix [10] và sử dụng thông tin này để hìnhthành các nút con. Mặc dù giải pháp này đượccho là không hiệu quả vì thực chất tại nút gốccủa cây đã thực hiện xong việc huấn luyện vàU-Matrix của nút gốc hoàn toàn trực quanđược toàn bộ dữ liệu. Nhưng phân tích dữliệu (chia dữ liệu) theo cấu trúc cây là một ýtưởng phù hợp để cài đặt chương trình xử lýsong song.Sau khi nghiên cứu mô hình SOM gốc và mộtsố mô hình cải tiến khác của SOM, chúng tôinhận thấy có hai vấn đề cần cân nhắc để cảithiện tốc độ tính toán của mạng. Một là giảmthời gian tìm kiếm BMU bằng cách thu hẹpphạm vi tìm kiếm hoặc giảm kích thước matrận Kohonen. Hai ...