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

Lê Anh Tú và Đtg<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> 116 (02): 79 - 84<br /> <br /> MỘT SỐ GIẢI PHÁP CẢI TIẾN<br /> NHẰM TĂNG TỐC ĐỘ THUẬT TOÁN MẠNG NƠRON SOM<br /> Lê Anh Tú1*, Lê Sơn Thái1, Nguyễn Quang Hoan2<br /> <br /> 1<br /> <br /> Trường Đại học Công nghệ thông tin và Truyền thông – ĐH Thái Nguyên,<br /> 2<br /> Học viện Công nghệ Bưu chính Viễn thông<br /> <br /> TÓM TẮT<br /> 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ữ<br /> 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<br /> 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<br /> 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<br /> quả cài đặt thử nghiệm và đánh giá hiệu quả của mỗi giải pháp.<br /> Từ khóa: SOM, Kohonen, BMU, phân tầng, phân cụm dữ liệu<br /> <br /> GIỚI THIỆU*<br /> Mạng nơron SOM đƣợc Teuvo Kohonen phát<br /> triển vào những năm 80 [1]. Đây là một công<br /> cụ thích hợp để giải bài toán phân cụm dữ<br /> liệu, một bƣớc tiền xử lý quan trọng trong<br /> khai phá dữ liệu [2]. Khi áp dụng mạng nơron<br /> SOM để phân cụm dữ liệu, cần thực hiện theo<br /> 3 giai đoạn:<br /> Giai đoạn 1: Huấn luyện mạng bằng tập dữ<br /> liệu mẫu. Trong trƣờng hợp tập dữ liệu huấn<br /> luyện chƣa đủ lớn thì quá trình huấn luyện có<br /> thể đƣợc lặp lại nhiều lần với cùng một tập<br /> mẫu cho tới khi mạng đạt trạng thái cân bằng.<br /> Giai đoạn 2: Phân cụm nơron (thƣờng sử<br /> dụng thuật toán tích tụ [10]) hoặc trực quan<br /> mạng để quan sát [11].<br /> Giai đoạn 3: Áp dụng mạng đã huấn luyện để<br /> phân cụm (với mỗi phần tử trong tập dữ liệu<br /> cần phân cụm, tìm trên ma trận Kohonen<br /> nơron có đặc trƣng khớp nhất và gán nhãn<br /> phần tử vào nơron này).<br /> Tuy nhiên, thuật toán SOM đòi hỏi thời gian<br /> tính toán lớn (cả thời gian huấn luyện và áp<br /> dụng mạng đã huấn luyện) vì một số lý do sau:<br /> Thứ nhất, tập dữ liệu huấn luyện hoặc số lần<br /> huấn luyện phải đủ lớn để mạng đạt đƣợc<br /> trạng thái cân bằng.<br /> Thứ hai, dữ liệu đƣợc đƣa vào mạng một cách<br /> tuần tự, sau đó với mỗi phần tử dữ liệu đƣợc<br /> *<br /> <br /> Tel: 0989 199088, Email: latu@ictu.edu.vn<br /> <br /> đƣa vào lại phải tìm kiếm tuần tự trên toàn bộ<br /> ma trận Kohonen để xác định nơron chiến<br /> thắng (BMU-Best Matching Unit).<br /> Thứ ba, trong các bài toán khai phá dữ liệu<br /> tập dữ liệu cần đánh giá thƣờng rất lớn. Do<br /> vậy kích thƣớc ma trận Kohonen phải đủ lớn<br /> để mô tả đƣợc hết đặc trƣng của dữ liệu,<br /> thƣờng là hàng nghìn nơron.<br /> Hiện tại, đã có nhiều nghiên cứu về vấn đề<br /> này, chẳng hạn: thuật toán Batch SOM [3]<br /> tăng tốc độ huấn luyện bằng cách chỉ cập nhật<br /> trọng số của các nơron vào cuối quá trình<br /> huấn luyện (sau khi duyệt hết các mẫu huấn<br /> luyện); Tree-Structured SOM (TS-SOM) [5]<br /> là một cấu trúc huấn luyện và tìm kiếm BMU<br /> dạng cây, trong đó mỗi nút trên cây là một<br /> nơron. Số lƣợng nút con của mỗi nút bằng<br /> nhau và tăng theo hàm mũ. Các nút cùng cấp<br /> tạo thành một lớp (layer), lớp trên đƣợc dùng<br /> để huấn luyện lớp dƣới. Ví dụ, lớp đầu tiên có<br /> 4 nút (nơron), mỗi nút có 4 nút con, vậy lớp<br /> thứ hai có 16 nút, lớp thứ 3 có 64 nút,... nhƣ<br /> vậy thời gian huấn luyện nhanh hơn do việc<br /> tìm BMU tại mỗi bƣớc huấn luyện đƣợc thực<br /> hiện theo các nhánh của cây. Tuy nhiên cấu<br /> trúc này vẫn còn nhiều hạn chế do dữ liệu vẫn<br /> đƣợc đƣa vào và xử lý trong mạng một cách<br /> tuần tự. Mô hình mạng nơron SOM phân tầng<br /> (Hierarchical SOMs - HSOM) [4] với tƣ<br /> tƣởng kết hợp chia dữ liệu (chia tập dữ liệu<br /> thành nhiều tập con) và chia mạng (chia ma<br /> trận Kohonen thành nhiều nhóm nhỏ các<br /> 79<br /> <br /> Lê Anh Tú và Đtg<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> nơron, mỗi nhóm nhỏ này đƣợc coi nhƣ một<br /> mạng con) nhằm giảm thời gian tìm kiếm<br /> BMU và xử lý dữ liệu một cách đồng thời.<br /> HSOM có hai dạng chính: dạng thứ nhất,<br /> ngay từ đầu dữ liệu đƣợc chia thành nhiều tập<br /> con để huấn luyện trên nhiều mạng sau đó<br /> tổng hợp các kết quả huấn luyện vào một bản<br /> đồ đặc trƣng chung; dạng thứ hai, tập dữ liệu<br /> sẽ đƣợc phân nhánh dần trong quá trình huấn<br /> luyện do đó hình thành một cấu trúc hình cây,<br /> với mỗi nút có thể là một nơron hoặc là một<br /> mạng Kohonen và đặc trƣng của dữ liệu sẽ<br /> đƣợc biểu diễn trên các nút lá. HSOM là một<br /> cấu trúc phức tạp do có rất nhiều cách khác<br /> nhau để thực hiện chia dữ liệu và chia mạng.<br /> Costa đƣa ra một cấu trúc cây phân tầng biểu<br /> diễn các cụm dữ liệu, trong đó mỗi nút của<br /> cây là một bản đồ Kohonen [6]. Tại mỗi nút,<br /> mạng vẫn đƣợc huấn luyện đầy đủ nhƣ SOM<br /> gốc, sau đó xây dựng ma trận trực quan UMatrix [10] và sử dụng thông tin này để hình<br /> thành các nút con. Mặc dù giải pháp này đƣợc<br /> cho là không hiệu quả vì thực chất tại nút gốc<br /> của cây đã thực hiện xong việc huấn luyện và<br /> U-Matrix của nút gốc hoàn toàn trực quan<br /> đƣợc toàn bộ dữ liệu. Nhƣng phân tích dữ<br /> liệu (chia dữ liệu) theo cấu trúc cây là một ý<br /> tƣởng phù hợp để cài đặt chƣơng trình xử lý<br /> song song.<br /> Sau khi nghiên cứu mô hình SOM gốc và một<br /> số mô hình cải tiến khác của SOM, chúng tôi<br /> nhận thấy có hai vấn đề cần cân nhắc để cải<br /> thiện tốc độ tính toán của mạng. Một là giảm<br /> thời gian tìm kiếm BMU bằng cách thu hẹp<br /> phạm vi tìm kiếm hoặc giảm kích thƣớc ma<br /> trận Kohonen. Hai là kết hợp chia dữ liệu<br /> (data-partition) và chia mạng (networkpartition) để xử lý song song.<br /> Bài báo này trình bày ý tƣởng của hai giải<br /> pháp: thu hẹp phạm vi tìm kiếm BMU [7]<br /> đƣợc đề xuất bởi Teuvo Kohonen và kiến trúc<br /> mạng phân tầng HSOM phân chia theo nhóm<br /> nơron dựa trên ngƣỡng phân ly [8] do chính<br /> nhóm tác giả đề xuất. Đồng thời trình bày các<br /> kết quả cài đặt thực nghiệm của hai giải pháp<br /> trên. Các phần còn lại của bài báo gồm: phần<br /> 80<br /> <br /> 116 (02): 79 - 84<br /> <br /> 2 trình bày thuật toán huấn luyện SOM gốc,<br /> phần 3 trình bày giải pháp thu hẹp phạm vi<br /> tìm kiếm BMU, phần 4 mô tả kiến trúc mạng<br /> phân tầng và cuối cùng đƣa ra một số kết luận<br /> về các nội dung đã trình bày.<br /> THUẬT TOÁN HỌC CỦA SOM [1]<br /> Mạng nơron SOM gồm lớp tín hiệu vào và<br /> lớp ra Kohonen. Lớp Kohonen thƣờng đƣợc<br /> tổ chức dƣới dạng một ma trận 2 chiều các<br /> nơron. Mỗi đơn vị i (nơron) trong lớp<br /> Kohonen đƣợc gắn một vector trọng số wi=<br /> [wi1, wi2, …,win], với n là kích thƣớc vector<br /> đầu vào; wij là trọng số của nơron i ứng với<br /> đầu vào j). Quá trình huấn luyện mạng đƣợc<br /> lặp nhiều lần cho tới khi thỏa mãn điều kiện<br /> dừng (có thể căn cứ trên số lần lặp, số mẫu<br /> học, hay độ cân bằng của mạng). Tại lần lặp<br /> thứ t thực hiện 3 bƣớc:<br /> Bƣớc 1- tìm BMU: chọn ngẫu nhiên một đầu<br /> vào v từ tập dữ liệu, duyệt ma trận Kohonen<br /> tìm nơron b có hàm khoảng cách dist nhỏ nhất<br /> (thƣờng dùng hàm Euclidian). Nơron b đƣợc<br /> gọi là BMU.<br /> dist || v  w b || min || v  w i ||<br /> <br /> (1)<br /> <br /> i<br /> <br /> Bƣớc 2- xác định bán kính lân cận của BMU:<br />  t<br />  t   0 exp   là hàm nội suy bán kính<br />   <br /> (giảm dần theo số lần lặp t), với<br /> kính khởi tạo; hằng số thời gian  <br /> <br /> 0<br /> <br /> là bán<br /> <br /> K<br /> ,<br /> log 0 <br /> <br /> với K là tổng số lần lặp.<br /> Bƣớc 3- cập nhật lại trọng số của các nơron<br /> trong bán kính lân cận của BMU theo hƣớng<br /> gần hơn với vector đầu vào v:<br /> wi t 1  wi t    t  hbi t  v  wi t <br /> <br /> (2)<br /> <br />  t<br />   <br /> <br /> Trong đó:  t   0 exp   là hàm nội suy<br /> tốc độ học, với 0 là giá trị khởi tạo của tốc<br /> độ học; hbi(t) là hàm nội suy theo thời gian<br /> học, thể hiện sự tác động của khoảng cách đối<br /> với quá trình học, đƣợc tính theo công thức<br />  || r  r ||2 <br /> hbi t   exp  b 2 i  trong đó rb và ri là vị<br /> 2 t  <br /> <br /> <br /> Lê Anh Tú và Đtg<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> trí của nơron b và nơron i trong ma trận<br /> Kohonen.<br /> Trong bƣớc 1 của thuật toán, với mỗi mẫu<br /> đầu vào phải tìm kiếm trên toàn bộ ma trận<br /> Kohonen để xác định BMU. Điều này không<br /> thực sự phù hợp trong trƣờng hợp tập mẫu<br /> nhỏ, phải sử dụng lại nhiều lần để huấn luyện.<br /> Giải pháp thu hẹp phạm vi tìm kiếm BMU<br /> trong trƣờng hợp này đƣợc trình bày ở phần<br /> tiếp theo.<br /> THU HẸP PHẠM VI TÌM KIẾM BMU [7]<br /> Khi một tập mẫu đƣợc sử dụng lại nhiều lần<br /> để huấn luyện mạng thì phạm vi tìm BMU ở<br /> những lần huấn luyện sau có thể thu hẹp. Một<br /> cách tìm kiếm thông minh là chỉ tìm quanh vị<br /> trí của BMU tƣơng ứng với vector mẫu ở lần<br /> huấn luyện trƣớc đó.<br /> <br /> Hình 1. Minh họa giải pháp thu hẹp phạm vi tìm<br /> kiếm BMU<br /> <br /> Với mỗi vector mẫu đầu vào, sau khi xác định<br /> đƣợc BMU tiến hành lƣu thông tin vị trí<br /> BMU của mẫu đó. Thông tin này sẽ đƣợc sử<br /> dụng để xác định khu vực tìm kiếm BMU cho<br /> chính mẫu đó trong lần huấn luyện tiếp theo.<br /> Hình 1 minh họa việc bổ sung thêm một<br /> trƣờng Pointer để lƣu vị trí BMU. Ở lần huấn<br /> luyện sau của vector mẫu vị trí đã lƣu trữ sẽ<br /> đƣợc kiểm tra trƣớc, sau đó mới kiểm tra các<br /> vị trí xung quanh.<br /> Chúng tôi đã tiến hành cài đặt, thử nghiệm<br /> giải pháp thu hẹp phạm vi tìm kiếm BMU để<br /> so sánh kết quả với thuật toán SOM gốc. Với<br /> dữ liệu vào ảnh số, mạng đƣợc thiết kế có 3<br /> đầu vào tƣơng ứng với 3 màu R, G, B của<br /> mỗi điểm ảnh, ma trận Kohonen vuông<br /> 30x30, giá trị phạm vi tìm kiếm đƣợc thiết lập<br /> bằng giá trị bán kính lân cận. Hình 2 trình bày<br /> kết quả thử nghiệm với cùng một ảnh mẫu<br /> kích thƣớc 141x140, thực hiện huấn luyện<br /> <br /> 116 (02): 79 - 84<br /> <br /> mạng với số lần lặp lại tập mẫu khác nhau.<br /> Nếu sử dụng tập mẫu 1 lần thì giải pháp cải<br /> tiến lâu hơn thuật toán gốc do phải tổ chức dữ<br /> liệu để lƣu trƣờng Pointer (giá trị khác biệt<br /> tƣơng đối nhỏ). Nhƣng khi số lần sử dụng tập<br /> mẫu càng tăng thì thời gian huấn luyện mạng<br /> càng giảm do vị trí tìm kiếm BMU đƣợc xác<br /> định theo trƣờng Pointer và chỉ trong phạm vi<br /> bằng bán kính lân cận tại thời điểm đó. Chúng<br /> tôi đã thử nghiệm trên nhiều ảnh khác nhau<br /> đều cho kết quả tƣơng tự.<br /> MÔ HÌNH HSOM SỬ DỤNG NGƢỠNG<br /> PHÂN LY<br /> Chúng tôi đề xuất một mô hình mạng HSOM<br /> phân tầng theo nhóm nơron. Mô hình mạng<br /> này xuất phát từ ý tƣởng ban đầu phân chia<br /> dữ liệu thành các cụm lớn, từ mỗi cụm lớn<br /> tiếp tục chia thành các cụm nhỏ, và từ các<br /> cụm nhỏ lại tiếp tục chia thành các cụm nhỏ<br /> hơn nữa. Trong đó, mỗi nút của cây đƣợc<br /> thiết kế là một mạng nơron SOM, cho phép<br /> phân cụm dữ liệu chi tiết dần từ nút gốc tới<br /> nút lá. Một nút cha sau khi đƣợc huấn luyện<br /> sẽ phân tập dữ liệu dùng để huấn luyện nó<br /> thành các tập con. Mỗi tập dữ liệu con lại tiếp<br /> tục đƣợc dùng để huấn luyện nút con tƣơng<br /> ứng đƣợc sinh ra. Chúng tôi đã áp dụng kỹ<br /> thuật phân nhóm nhanh các nơron ngay trong<br /> quá trình huấn luyện mạng dựa vào ngƣỡng<br /> phân ly T [9], do vậy quy trình áp dụng SOM<br /> cho bài toán phân cụm không cần thực hiện<br /> giai đoạn 2 đã nêu ở trên. Cơ sở của việc phân<br /> chia này dựa vào ngƣỡng phân ly T, với<br /> <br />   T  max || vi  v j || , trong đó<br /> i, j<br /> <br /> là giá trị<br /> <br /> giới hạn về độ phi tƣơng tự của các phần tử<br /> trong cùng một cụm, max || vi  v j || là giá trị<br /> i, j<br /> <br /> khác biệt lớn nhất giữa hai phần tử bất kỳ trên<br /> toàn tập dữ liệu.<br /> Cây sẽ tự phát triển và đƣợc huấn luyện theo<br /> từng tầng. Mỗi tầng, huấn luyện tất cả các nút<br /> lá với cùng một ngƣỡng T, tầng kế tiếp T<br /> giảm đi một giá trị , cho tới khi T= . Hình 3<br /> minh họa kiến trúc huấn luyện gồm m tầng,<br /> tầng đầu tiên đƣợc huấn luyện với ngƣỡng<br /> T  T1  max || vi  v j || , ở mỗi tầng T giảm đi<br /> i, j<br /> <br /> một giá trị<br /> <br /> cho tới khi đạt ngƣỡng .<br /> 81<br /> <br /> Lê Anh Tú và Đtg<br /> <br /> Ảnh gốc<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> Số lần sử<br /> dụng tập<br /> mẫu<br /> 1<br /> 2<br /> 5<br /> 10<br /> <br /> Thuật toán SOM gốc<br /> Huấn<br /> luyện(ms)<br /> 2683.23<br /> 4965.21<br /> 10416.75<br /> 21038.49<br /> <br /> Ảnh kết quả<br /> <br /> 116 (02): 79 - 84<br /> <br /> Giải pháp thu hẹp phạm vi<br /> tìm kiếm BMU<br /> Huấn<br /> luyện(ms)<br /> <br /> Ảnh kết quả<br /> <br /> 2934.77<br /> 4394.72<br /> 9053.87<br /> 18383.06<br /> <br /> Hình 2. Thực nghiệm giải pháp thu hẹp phạm vi tìm kiếm BMU<br /> <br /> Tầng đầu tiên, tập dữ liệu ban đầu I đƣợc<br /> huấn luyện bởi Kohonen K1 có kích thƣớc<br /> (n n) và ngƣỡng phân ly là T1. Kết quả thu<br /> đƣợc k tập con của I={I1, I2,…, Ik}. Tầng thứ<br /> hai, mỗi tập con I1, I2,…, Ik đƣợc huấn luyện<br /> bởi các Kohonen con tƣơng ứng KI1, KI2,…,<br /> KIk với ngƣỡng phân ly giảm T2=T1- . Nhƣ<br /> vậy mỗi tập Ii (với i=1..k) đƣợc huấn luyện<br /> bởi KIi lại đƣợc phân thành các tập con Ii1,<br /> Ii2,… Ở các tầng tiếp theo, lặp lại việc giảm T<br /> và huấn luyện mỗi nút con bằng tập con<br /> tƣơng ứng của nó, cho tới khi T= .<br /> Kích thƣớc của các nút con sẽ giảm dần phụ<br /> thuộc vào kích thƣớc nút cha và tỉ số giữa số<br /> phần tử trong tập con dùng để huấn luyện nó<br /> với số phần tử dùng để huấn luyện nút cha.<br /> Gọi nchild là kích thƣớc nút con, ta có:<br /> nchild<br /> <br /> |I<br /> <br /> <br /> child | <br /> <br />  <br />  n parent , trong đó: |.| thể hiện<br />  | I parent | <br /> <br /> số phần tử trong một tập hợp, điều chỉnh<br /> kích thƣớc nút con không giảm quá nhiều so<br /> với nút cha (chúng tôi thử nghiệm với =0.3).<br /> Do nút gốc và các nút trung gian chỉ có vai<br /> trò định hƣớng việc phân chia dữ liệu. Nên<br /> kích thƣớc nút gốc (ma trận Kohonen K1)<br /> không cần đủ lớn để mô tả đƣợc hết đặc trƣng<br /> của tập dữ liệu. Điều này làm giảm đáng kể<br /> thời gian huấn luyện tại mỗi nút. Ngoài ra, dữ<br /> liệu đƣợc phân mảnh theo cấu trúc cây để<br /> huấn luyện song song trên các mạng Kohonen<br /> riêng biệt nên thời gian huấn luyện và áp<br /> dụng mạng sau huấn luyện nhanh hơn mô<br /> hình SOM gốc.<br /> Bảng dƣới đây trình bày kết quả thử nghiệm.<br /> Mạng SOM gốc đƣợc thiết kế tƣơng tự phần<br /> 82<br /> <br /> 3, mô hình cây phân tầng kích thƣớc Kohonen<br /> là 11x11 và T=30 (với 30