Bài giảng Khai phá dữ liệu: SOM (self organizing maps)

KHAI THÁC DỮ LIỆU

SOM (SELF ORGANIZING MAPS) Kohonen

24/05/2016

GIỚI THIỆU

 Mạng nơron nhân tạo này lần đầu tiên được giới thiệu bởi Kohonen vào năm 1982, nó được biết đến như là ánh xạ đặc trưng tự tổ chức (SOM).

 Mạng nơron Kohonen (hay nơron tự tổ chức) mô hình hóa cách hoạt động bộ não của con người, mặc dù nó khá đơn giản. Chúng ta có thể nhận được một số ý tưởng cách bộ não lưu trữ hình ảnh và cách nó nhận dạng các hình ảnh.

 Kỹ thuật SOM đã được áp dụng thành công trong một số lĩnh vực như nhận dạng, phân cụm dữ liệu, dự đoán chuỗi và khai phá dữ liệu,... Mẫu được nhận dạng có thể là ảnh, âm thanh hoặc văn bản,...

24/05/2016

ĐỊNH NGHĨA

 Mạng noron SOM là mạng có khả năng sử dụng những kinh nghiệm của quá khứ để thích ứng với những biến đổi của môi trường (không dự báo trước). Loại mạng này thuộc nhóm hệ học, thích nghi không cần có tín hiệu chỉ đạo từ bên ngoài.

24/05/2016

CẤU TRÚC SOM

24/05/2016

THUẬT TOÁN SOM TỔNG QUÁT

 Training: số k cụm k, và CSDL có n đối tượng

1. Xác định cấu trúc tầng ra. 2. Huấn luyện trọng số kết nối giữa intput và output 3. Xác định công thức cập nhật trọng số. 4. Khoảng cách trong kiến trúc mạng được thay đổi và

cập nhật trong các lần lặp.

5. Tốc độ học biến đổi trong quá trình huấn luyện. Kiểm thử: 1. Giá trị kiểm thử sử dụng bộ trọng số của huấn luyện

24/05/2016

MÃ GIẢ THUẬT TOÁN SOM

 Xác định số đầu ra của mạng.  Khởi tạo trọng số kết nối thường [-1,1]  LL=1;  While (LL == true)

1. Chọn lần lượt vecto đầu vào il 2. Dùng công thức tính khoảng cách Euclide đến từng vecto

trọng số của từng node ra.

3. Chọn vecto trọng số wj có giá trị nhỏ nhất ở bước 2. 4. Cập nhật vecto trọng số wj theo công thức:

Wj(t+1) = Wj(t) + (t)(Xi – Wj(t))

5. Tăng LL End While

24/05/2016

Ví dụ

Huấn luyện mạng SOM dựa trên khoảng cách Euclide bình phương để phân thành 02 cụm với dữ liệu huấn luyện như sau:

X1 = (1, 1, 0, 0) X2 = (0, 0, 0, 1) X3 = (1, 0, 0, 0) X4 = (0, 0, 1, 1) Vector trọng số kết nối W1 = (0.2, 0.6, 0.5, 0.9); W2 = (0.8, 0.4, 0.7, 0.3) Hệ số học (t) = 0.6 Công thức cập nhật trọng số Wj(t+1) = Wj(t) + (t)(Xi – Wj(t))

24/05/2016

Ví dụ

Lần 01: Chọn vetor huấn luyện là X1 = (1, 1, 0, 0) Khoảng cách đến cụm 1: d2 = (0.2 – 1) 2 + (0.6 – 1)2 + (0.5 – 0)2 + (0.9 – 0)2 = 1.86 Khoảng cách đến cụm 2: d2 = (0.8 - 1)2 + (0.4 - 1)2 + (0.7 - 0)2 + (0.3 - 0)2 = 0.98 Cụm 2 là cụm chiến thắng. Cập nhật vector trọng số kết nối đến cụm 2: W2(2) = (0.8, 0.4, 0.7, 0.3) + 0.6((1, 1, 0, 0) - (0.8, 0.4, 0.7, 0.3)) = (0.92, 0.76, 0.28, 0.12)

24/05/2016

Ví dụ

Lần 02: W1(3) = (0.08, 0.24, 0.20, 0.96) Lần 03: W2(4) = (0.97, 0.3, 0.11, 0.05) Lần 04: W1(5) = (0.03, 0.10, 0.68, 0.98)

24/05/2016

Ví dụ

Kết luận: Sau khi huấn luyện có trọng số kết nối là: W1 = (0.03, 0.10, 0.68, 0.98) W2 = (0.97, 0.3, 0.11, 0.05)

24/05/2016

Ví dụ

I1 = (1.1, 1.7, 1.8) I2 = (0, 0, 0) I3 = (0, 0.5, 1.5) I4 = (1, 0, 0) I5 = (0.5, 0.5, 0.5) I6 = (1, 1, 1)

Bài giảng Khai phá dữ liệu: SOM (self organizing maps) - Văn Thế Thành