Giới thiệu kỹ thuật Self Organizing Map (SOM)

Nguyễn Văn Chức – chuc1803@gmail.com

1.      Sơ lược về Self Organizing Map (SOM)

Self Organizing Map (SOM) hay Self-Organizing Feature Map (SOFM) là một mạng Neuron nhân tạo (Artificial Neural Networks – ANN), được huấn luyện (trained) sử dụng kỹ thuật Unsupervised learning để biểu diễn dữ liệu với số chiều (dimension) thấp hơn nhiều (thường là 2 chiều) so với dữ liệu đầu vào nhiều chiều (thường số chiều lớn). Kết quả của SOM gọi là bản đồ (Map). SOM là một ANN, tuy nhiên SOM khác với các ANN là không sử dụng các lớp ẩn (hidden layers) chỉ sử dụng input và output layer. SOM sử dụng khái niệm láng giềng (neighborhood) để giữ lại đặc trưng của các dữ liệu đầu vào trên bản đồ (có nghĩa là các training sample tương tự nhau thì được đặt gần nhau trên bản đồ). Ưu điểm chính của SOM là biểu diễn trực quan dữ liệu nhiều chiều vào không gian ít chiều hơn (thường là 2 chiều) và đặc trưng của dữ liệu đầu vào được giữ lại trên bản đồ.

Ý tưởng về SOM lần đầu tiên được giới thiệu bởi C. von der Malsburg năm 1973 và được phát triển bởi T. Kohonen (Finland ) năm 1982 nên còn được gọi là Kohonen Network

Kiến trúc của SOM

SOM gồm các thành phần sau:

Output Layer: Gồm các node (neurons) được bố trí trên một lưới (bản đồ) kích thước X xY. Mỗi neuron có vị trí xác định trên lưới, tại mỗi neuron lưu giữ một vector trọng số (weight vector) có số chiều bằng với số chiều của input vector.

Input vector:  Là các training sample có kích thước n

Ma trận trọng số (weight matrix) w_ij kết nối giữa input vector và các neurons

Sau đây là kiến trúc đơn giản của SOM gồm 2 neurons ở lớp output layer. Input vector gồm 4 chiều và weight matrix w_ij (i=1..4 và j=1..2) như sau (hình 1):

 2. Thuật toán SOM

Qui trình training SOM được thực hiện qua các bước như mô tả sau. Trong đó, các tham số có ý nghĩa như sau:

R: Bán kính, dùng để xác định số láng giềng của winning neuron sẽ được cập nhật trọng số.

α (Learning rate): Tốc độ huấn luyện model. Tham số này được cập nhật trong suốt quá trình huấn luyện model, và được điều chỉnh (thường điều chỉnh giảm dần) sau mỗi lần lặp. Điều kiện để kết thúc quá trình training thường là giá trị của learning rate là đủ nhỏ hoặc ma trận trọng số hội tụ

x: input vector

D(j): khoảng cách giữa neuron j đến input vector x

 

 

Để dễ hiểu hơn, ví dụ đơn giản sau đây minh họa cho quá trình Training một SOM đơn giản với 2 neurons và input vector gồm 4 chiều với kiến trúc như hình 1 trên

 

Khởi tạo ngẫu nhiên weight matrix như sau

Để đơn giản ta giả sử bán kính R=0 (số láng giềng của winning neuron =0. Có nghĩa là chỉ cập nhật trọng số của winning neuron chứ không cập nhật trọng số của bất kỳ neuron nào khác)

Learning rate α tại thời điểm ban đầu (t=0) bằng 0.6. tức là α(t=0)=0.6

Learning rate tại thời điển t+1 được điều chỉnh như sau:

Giả sử Training data gồm 4 samples như sau:

Quá trình training SOM được thực hiện bằng cách lần lượt đưa các input vector vào SOM và cập nhật vector trọng số của winning neuron như sau (chú ý trong ví dụ này để thuận tiện ta sử dụng bình phương khoảng cách Euclidean chứ không tính căn bậc hai)

Xét Input vector x=(1 1 0 0)

Khoảng cách từ 2 neurons đến input vector như sau:

Ta thấy rằng khoảng cách từ neuron Y₂ đến input vector nhỏ hơn khoảng cách từ neuron Y₁ đến input vector nên winning neuron là Y₂. Vì R=0 nên ta chỉ cập nhật trong số của neuron Y₂ như sau:

Ma trận trọng số mới sau khi cập nhật là

Tương tự, xét các input vector còn lại trong training data và cập nhật weight matrix như trên và Sau lần lặp thứ nhất (sau khi tất cả các input vector trong training data được đưa vào để huấn luyện, tức là hoàn thành 1 epochs), ta được:

Cập nhật learning rate

Quá trình này lặp lại cho đến khi learning rate đủ nhỏ hoặc weight matrix hội tụ thì kết thúc.

Trong ví dụ này, sau khi lặp lại 100 lần (epochs=100) thì ma trận trọng số hội tụ như sau:

Sau khi huấn luyện, ta có thể kiểm tra mô hình bằng cách xem mỗi neuron như một cluster . Trong ví dụ này, có 2 neurons nên ta có 2 cluster tương ứng là cluster1 và cluster 2. Khi đó một input vector được ánh xạ (mapping) vào vị trí neuron nào thì tương ứng với cluster đó.

Xét input vector x=(1 1 0 0)

Tính khoảng cách từ input vector đến 2 nueron (chú ý bây giờ sử dụng weight matrix cuối cùng đã hội tụ). Ta có:

 Vì Neuron Y₂ là winner nên input vector x=(1 1 0 0) thuộc cluster2. Tương tự xét 3 các input vector còn ta có kết quả như sau:

 

 3. Ứng dụng SOM trong phân cụm dữ liệu

Ứng dụng sau đây minh họa sử dụng SOM trong phân cụm dữ liệu. Dataset là dữ liệu về hoa iris (iris.arff) gồm 150 samples và 4 thuộc tính (4 chiều) là petal length, petal width, sepal length, sepal width. (xem thêm về iris dataset tại đây: http://bis.net.vn/forums/t/369.aspx)

Chương trình sử dụng là SOM Toolbox 2.0 (Download tại đây: http://www.cis.hut.fi/projects/somtoolbox/download)

Kết quả thực hiện SOM với SOM Toolbox 2.0 trên dataset iris như sau:

Bạn cho tôi hỏi. việc tính khoảng cách euclid giữa vector input và vetor trọng số nhằm mục đích gì vậy. bản chất thật sự của nó là gì? vì vector trọng số thể hiện mức độ kết nối các giữa các input so với output chứ nó đâu phải là một điểm nào đó trong không gian nhiều chiều?. Một vấn đề nữa là lý do vì sao bạn lại dựa trên tiêu chí khoảng cách giữa 2 điểm nếu nhỏ (nếu D(1)>D(2) thì cập nhật trọng số trọng số neural y2. Mong bạn giải đáp dùm tôi. Cảm ơn bạn.