Tài liệu Phân lớp các mẫu với ứng dụng của mạng nơron nhân tạo

1 .. ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CNTT & TRUYỀN THÔNG ----------------  ---------------- Vũ Thị Hiền PHÂN LỚP CÁC MẪU VỚI ỨNG DỤNG CỦA MẠNG NƠRON NHÂN TẠO LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái Nguyên - 2012 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 2 MỞ ĐẦU Phân lớp các mẫu là một vấn đề thú vị và bổ ích. Đây là vấn đề rất hay gặp trong cuộc sống. Các nhà băng cần phân lớp khách hàng theo các mức rủi do để trong từng hoàn cảnh cụ thể, với những khách hàng cụ thể nhân viên nhà băng quyết định có cho vay hay không hoặc cho vay nhiều hay cho vay ít. Các nhà quản lý cần xếp cán bộ, nhân viên dưới quyền vào các lớp để qui hoạch xây dựng đội ngũ. Mỗi cán bộ, nhân viên với những giá trị của những thông số khác nhau cần phải được đưa vào những lớp khác nhau. Các nhà giáo dục cần phân lớp các em học sinh theo những tiêu chí khác nhau. Khi biết đối tượng dạy học của mình thuộc lớp nào ta sẽ có những phương pháp giáo dục thích hợp. Các trường chuyên nghiệp cần phân lớp các học sinh theo các tham số khác nhau tương ứng với những mức học bổng khác nhau. Với những kho dữ liệu khổng lồ, phân lớp là thao tác giúp ta khai phá dữ liệu, tìm kiếm tri thức được nhanh chóng và hiệu quả hơn. Các đối tượng cần phân lớp thường được biểu diễn bởi một vectơ, trong đó mỗi thuộc tính có thể có những thứ nguyên khác nhau vì thế việc phân lớp rất khó khăn. Ví dụ cần phân lớp cán bộ theo các tiêu chí tài và đức. Thật khó đánh giá xem ai ở lớp trên, ai ở lớp dưới khi giá trị trung bình của hai tiêu chí này của họ là xấp xỉ như nhau. Nếu việc phân lớp không chính xác, cũng giống như đánh giá không chính xác tất yếu sẽ dẫn đến những hậu quả tai hại. Đã có nhiều người quan tâm đến vấn đề phân lớp. Nhưng các phương pháp đã có thường chịu ảnh hưởng nhiều của cảm tính, hoặc chịu ảnh hưởng nhiều của yếu tố tâm lý, của chủ thể phân lớp. Ngay cả với những phương pháp toán học, do ranh giới phân lớp nhiều trường hợp không phải là tuyến tính nên bài toán phân lớp thường có độ phức tạp tính toán lớn và độ chính xác không cao. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 3 Mạng nơron nhân tạo là mô hình tính toán mô phỏng hoạt động của não người. Do có tính mềm dẻo, linh hoạt và khả năng dung thứ lỗi, mạng nơron có thể xấp xỉ mọi hàm với độ chính xác cao nên việc phân lớp bằng mạng nơron sẽ đưa đến kết quả không những khách quan mà còn đảm bảo kết quả tốt. Về mặt lý thuyết, phân lớp nhờ mạng nơron nhân tạo đã được nghiên cứu và khẳng định là một khả năng tiềm tàng của mô hình tính toán này. Những khảo nghiệm sâu về các giải thuật với mạng phân lớp và nghiên cứu thử nghiệm mô hình này còn chưa nhiều. Vì thế, trong khuôn khổ của một luận văn thạc sĩ tôi chọn đề tài: “Phân lớp các mẫu với ứng dụng của mạng nơron nhân tạo” nhằm tìm hiểu thêm về mạng nơron nhân tạo với việc phân lớp các con số. Từ đó rút ra những kết luận cần thiết cho việc xây dựng các ứng dụng cụ thể về sau. Em xin cảm ơn sự giúp đỡ nhiệt tình của các thầy, đặc biệt là TS. Nguyễn Tân Ân. Luận văn không thể tránh khỏi sai xót, em mong nhận được sự đóng góp ý kiến của các thầy và các bạn để luận văn được hoàn thiện hơn. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 4 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 5 Chƣơng 1 Bài toán phân lớp 1.1 Khái niệm phân lớp 1.1.1 Khái niệm phân lớp Phân lớp dữ liệu là kĩ thuật dựa trên tập huấn luyện và những giá trị hay nhãn của lớp trong một thuộc tính phân lớp và sử dụng nó trong việc phân lớp dữ liệu mới. Phân lớp cũng là tiên đoán loại lớp của nhãn. 1.1.2 Bài toán phân lớp • Mục đích: để dự đoán những nhãn phân lớp cho các bộ dữ liệu/mẫu mới • Đầu vào: một tập các mẫu dữ liệu huấn luyện, với một nhãn phân lớp cho mỗi mẫu dữ liệu • Đầu ra: mô hình (bộ phân lớp) dựa trên tập huấn luyện và những nhãn phân lớp 1.2 Một số ứng dụng phân lớp tiêu biểu • Tín dụng • Tiếp thị • Chẩn đoán y khoa • Phân tích hiệu quả điều trị 1.3 Quy trình phân lớp Bao gồm 2 bước: Xây dựng mô hình và sử dụng mô hình. - Bước 1. Xây dựng mô hình: là mô tả một tập những lớp được định nghĩa trước. Trong đó, mỗi bộ hoặc mẫu được gán thuộc về một lớp được định nghĩa trước như là được xác định bởi thuộc tính nhãn lớp, tập hợp của những bộ được sử dụng trong việc sử dụng mô hình được gọi là tập huấn luyện. Mô hình được biểu diễn là những luật phân lớp, cây quyết định và những công thức toán học. - Bước 2. Sử dụng mô hình: Việc sử dụng mô hình phục vụ cho mục đích phân lớp dữ liệu trong tương lai hoặc phân lớp cho những đối tượng chưa biết đến. Trước khi sử dụng mô hình người ta thường phải đánh giá tính chính xác của mô hình, trong đó nhãn được biết của mẫu kiểm tra được so sánh với kết quả Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 6 phân lớp của mô hình, độ chính xác là phần trăm của tập hợp mẫu kiểm tra mà phân loại đúng bởi mô hình, tập kiểm tra là độc lập với tập huấn luyện. 1.4 Các kỹ thuật phân lớp 1.4.1 Phân lớp bằng phƣơng pháp qui nạp cây quyết định 1.4.1.1 Khái niệm cây quyết định Cây quyết định là một flow-chart giống cấu trúc cây, nút bên trong biểu thị một kiểm tra trên một thuộc tính, nhánh biểu diễn đầu ra của kiểm tra, nút lá biểu diễn nhãn lớp hoặc sự phân bố của lớp. Việc tạo cây quyết định bao gồm 2 giai đoạn: Tạo cây và tỉa cây. Để tạo cây ở thời điểm bắt đầu tất cả những ví dụ huấn luyện ở gốc sau đó phân chia ví dụ huấn luyện theo cách đệ qui dựa trên thuộc tính được chọn. Việc tỉa cây là xác định và xóa những nhánh mà có phần tử hỗn loạn hoặc những phần tử nằm ngoài (những phần tử không thể phân vào một lớp nào đó). Việc sử dụng cây quyết định nhƣ sau: Kiểm tra những giá trị thuộc tính của mẫu đối với cây quyết định. 1.4.1.2 Thuật toán qui nạp cây quyết định Giải thuật cơ bản (giải thuật tham lam) được chia thành các bước như sau: 1. Cây được xây dựng đệ qui từ trên xuống dưới (top-down) và theo cách thức chia để trị (divide-conquer). 2. Ở thời điểm bắt đầu, tất cả những ví dụ huấn luyện ở gốc. 3. Thuộc tính được phân loại (nếu là giá trị liên tục chúng được rời rạc hóa) 4. Những ví dụ huấn luyện được phân chia đệ qui dựa trên thuộc tính mà nó chọn lựa. 5. Kiểm tra những thuộc tính được chọn dựa trên nền tảng của heristic hoặc của một định lượng thống kê. Điều kiện để dừng việc phân chia: 1. Tất cả những mẫu huấn luyện đối với một nút cho trước thuộc về cùng một lớp. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 7 2. Không còn thuộc tính còn lại nào để phân chia tiếp. 3. Không còn lại mẫu nào. 1.4.1.3 Nội dung giải thuật học cây quyết định cơ bản ID3 ID3 là một giải thuật học cây quyết định được phát triển bởi Ross Quinlan (1983). Ý tưởng cơ bản của giải thuật ID3 là để xây dựng cây quyết định bằng việc sử dụng một cách tìm kiếm từ trên xuống trên những tập hợp cho trước để kiểm tra mỗi thuộc tính tại mỗi nút của cây. Để chọn ra thuộc tính hữu ích nhất cho sự phân loại trên những tập hợp cho trước, chúng ta sẽ đưa ra một hệ đo độ lợi thông tin. Để tìm ra một cách tối ưu để phân loại một tập hợp thông tin, vấn đề đặt ra là chúng ta cần phải làm tối thiểu hóa (chẳng hạn, tối thiểu chiều cao của cây). Như vậy chúng ta cần một số chức năng có thể đánh giá trường hợp nào cho ra một sự phân chia cân bằng nhất. Hệ đo độ lợi thông tin sẽ là hàm như vậy. 1.4.1.4 Những thiếu sót của giải thuật ID3 Trường hợp thiếu sót thứ nhất: Một thiếu sót quan trọng của ID3 là không gian phân chia hợp lệ tại một nút là cạn kiệt. Một sự phân chia là sự phân hoạch của mỗi trường hợp của không gian mà kết quả đạt được từ việc thử nghiệm tại một nút quyết định ID3 và con cháu của nó cho phép sự kiểm tra tại một thuộc tính đơn và nhánh trong kết quả cho ra từ sự kiểm tra này. Trường hợp thiếu sót thứ hai: ID3 dựa rất nhiều vào số lượng của những tập hợp dữ liệu đưa vào. Quản lý sự tạp nhiễu của tập dữ liệu vào vô cùng quan trọng khi chúng ta ứng dụng giải thuật học cây quyết định vào thế giới thực. Ví dụ, khi có sự lẫn tạp trong tập dữ liệu đưa vào hoặc khi số lượng ví dụ đưa vào quá nhỏ để tạo ra một ví dụ điển hình của hàm mục tiêu đúng. ID3 có thể dẫn đến việc tạo quyết định sai. Có rất nhiều những mở rộng từ giải thuật ID3 cơ bản đã phát triển để áp dụng những luật học cây quyết định vào thế giới thực, như những post-pruning Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 8 tree, quản lý những thuộc tính giá trị thực, liên quan đến việc thiếu những thuộc tính, sử dụng những tiêu chuẩn chọn lựa thuộc tính khác hơn thu thập thông tin. 1.4.1.5 Sự phân lớp cây quyết định trong cơ sở dữ liệu lớn Sự phân lớp là một vấn đề cổ điển được nguyên cứu một cách mở rộng bởi những nhà thống kê và những nhà nguyên cứu máy học. Hướng phát triển hiện nay của việc phân lớp là phân lớp những tập dữ liệu với hàng tỉ những mẫu thử và hàng trăm thuộc tính với tốc độ vừa phải. Qui nạp cây quyết định được đánh giá cao trong khai phá dữ liệu lớn vì:  Tốc độ học tương đối nhanh hơn so với những phương pháp phân loại khác.  Có thể hoán chuyển được thành những luật phân lớp đơn giản và dễ hiểu.  Có thể sử dụng truy vấn SQL để truy xuất cơ sở dữ liệu.  Sự chính xác phân lớp có thể so sánh được với những phương pháp khác. 1.4.2 Phƣơng pháp phân lớp Bayesian (Bayesian classifier) 1.4.2.1 Đặc điểm Lý thuyết Bayesian cung cấp một tiếp cận theo xác xuất để suy diễn. Nó dựa trên giả thuyết rằng số lượng của khuynh hướng bị chi phối bởi phân bố xác suất và quyết định tối ưu có thể được tạo bởi sự suy luận về những xác suất đi liền với dữ liệu được quan sát. Đây là vấn đề quan trọng của máy học bởi vì nó cung cấp một tiếp cận định lượng cho việc xem xét cẩn thận bằng chứng hỗ trợ những giả thuyết thay đổi. Lý thuyết Bayesian cung cấp giải thuật học cơ bản mà vận dụng những xác suất như là một khung làm việc cho sự phân tích sự hoạt động của những giải thuật mà không thể vận dụng rõ ràng. Học theo xác suất: Tính xác suất xuất hiện cho giả thuyết, trong số những tiếp cận thực dụng nhất cho các kiểu chắc chắn của những vấn đề học. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 9 Tính tăng dần: mỗi ví dụ huấn luyện có thể gia tăng việc tăng hoặc giảm mà không gian giả thuyết đúng. Kiến thức trước có thể kết hợp với dữ liệu được quan sát. Tiên đoán xác suất: Tiên đoán nhiều không gian giả thuyết, được đo bởi xác suất của nó. Tiêu chuẩn: Thậm chí khi phương thức Bayesian khó tính toán, chúng cũng cung cấp một tiêu chuẩn tốt nhất cho việc tạo quyết định. 1.4.2.2 Khó khăn của phương pháp phân lớp Bayesian Khó khăn thực tế của phương pháp phân lớp Bayesian ở chỗ: - Đòi hỏi kiến thức khởi tạo của nhiều khả năng có thể xảy ra, và - Chi phí tính toán đáng kể. 1.4.2.3 Sự độc lập của giả thuyết: Những giả thuyết độc lập nhau sẽ giúp cho việc tính toán trở nên dễ dàng. Độ lợi phân lớp tốt nhất đạt được rất ít trong thực tế vì những thuộc tính (biến) thường liên quan với nhau. Để vượt qua những giới hạn này người ta giải quyết bằng 2 cách:  Dùng mạng Bayesian, đây chính là sự kết hợp của lý luận và quan hệ nhân quả giữa những thuộc tính.  Cây quyết định mà suy luận trên một thuộc tính ở thời điểm xem xét những thuộc tính quan trọng đầu tiên . 1.4.2.4 Mạng Bayesian Tin cậy ( Bayesian belief network ) : Bayesian belief network cho phép một tập con của những biến độc lập theo điều kiện. Trong Bayesian belief người ta sử dụng mô hình đồ thị của quan hệ nhân quả. Có nhiều cách học của Bayesian belief networks như sau:  Cho trước cả cấu trúc mạng và những biến: đây là cách dễ dàng.  Cho trước cấu trúc mạng nhưng chỉ có một vài biến chứ không phải là tất cả. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 10  Cấu trúc mạng hoàn toàn không được biết. 1.4.3 Phƣơng pháp phân lớp bằng mạng lan truyền ngƣợc (mạng Nơron) 1.4.3.1 Cấu trúc của một neural như sau: Hình 1 - Cấu trúc của một Nơron Vector x n chiều được ánh xạ vào biến y dựa trên tích vô hướng và một hàm ánh xạ phi tuyến . 1.4.3.2 Mạng huấn luyện: a) Mục tiêu cơ bản của việc huấn luyện Đạt được một tập hợp của những trọng số mà có thể làm cho hầu hết tất cả những bộ trong tập huấn luyện được phân lớp đúng. b) Những bước của quá trình huấn luyện  Khởi tạo trọng số với những giá trị ngẫu nhiên.  Lần lượt đưa mỗi bộ vào trong mạng.  Đối với mỗi đơn vị: - Tính toán mạng input cho mỗi đơn vị như một sự kết hợp tuyến tính của tất cả những input đối với đơn vị. - Tính toán giá trị output sử dụng hàm kích hoạt. - Tính toán lỗi. - Cập nhật trọng số và khuynh hướng. 1.4.3.3 Mạng thu giảm và rút trích luật Mạng thu giảm: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 11  Mạng kết nối hoàn toàn sẽ khó nối khớp với nhau.  Với n node input, n hidden node và m output node dẫn đến h(m+N) trọng số.  Thu giảm ở điểm: loại một số liên kết mà không ảnh hưởng phân lớp chính xác của mạng. 1.4.3.4 Những ích lợi của mạng nơron 1. Ưu điểm:  Tiên đoán chính xác cao.  Hoạt động mạnh làm việc được ngay khi các mẫu chứa lỗi.  Output có thể là giá trị rời rạc, giá trị thực hoặc vector của nhiều thuộc tính rời rạc hoặc giá trị thực .  Đánh giá nhanh hàm mục tiêu được học. 2. Nhược điểm:  Thời gian huấn luyện lâu.  Khó có thể hiểu được hàm học (trọng số).  Khó có thể kết hợp tri thức lĩnh vực. 1.4.4 Phân lớp dựa trên nguyên lý khai phá luật kết hợp Có nhiều phương thức đối với sự phân lớp dựa trên luật kết hợp.  ARCS: Khai phá sự kết hợp số lượng và gom cụm của những luật kết hợp .  Phân loại kết hợp: Khai phá độ hỗ trợ cao và độ tin cậy cao trong công thức “cond_set =>y” trong đó y là một nhãn lớp.  CAEP (Phân lớp bằng cách tập hợp lại những mẫu nổi bật): trong đó những mẫu nổi bật (Emerging patterns): những tập thành phần itemset hỗ trợ gia tăng quan trọng từ một lớp sang lớp khác. Khai phá những mẫu nổi bật dựa trên độ hỗ trợ tối thiểu và tốc độ phát triển. 1.4.5 Các phƣơng pháp phân lớp khác 1.4.5.1 Các phương pháp dựa trên khoảng cách Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 12 Chứa những ví dụ huấn luyện và trì hoãn xử lý cho đến khi một thực thể mới được phân lớp. Những cách tiếp cận thông thường:  Tiếp cận người láng giềng gần nhất k-nearest neighbor.  Hồi qui trọng lượng cục bộ: bằng cách xây dựng những xấp xỉ cục bộ.  Lập luận dựa trên trường hợp: Người ta sử dụng biểu diễn kí hiệu và tri thức dựa trên suy diễn. Giải thuật K-Nearest Neighbor (K-NN): Tất cả những thực thể tương ứng với những điểm trên không gian n-D. Người láng giềng gần nhất được định nghĩa trong biểu thức của khoảng cách Euclidean. Hàm mục tiêu có thể được rời rạc hóa hoặc giá trị thực. Đối với những giá trị rời rạc, k-NN trả về hầu hết giá trị thông thường giữa k ví dụ huấn luyện gần nhất với xq. Biểu đồ Vonoroi: bề mặt quyết định được qui vào bởi 1-NN đối với một tập điển hình của những ví dụ huấn luyện. Giải thuật k-NN đối với giá trị liên tục đối với những hàm mục tiêu giá trị liên tục. Tính toán giá trị trung bình của k láng giềng gần nhất. Giải thuật khoảng cách trọng lượng người láng giềng gần nhất. Trọng lượng đóng góp của mỗi láng giềng theo khoảng cách của chúng đến điểm truy vấn xq , gán trọng lượng lớn hơn cho láng giềng gần hơn w 1 d ( x q  xi ) 2 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 13 Tương tự, đối với những hàm mục tiêu giá trị thực. Mạnh đối với dữ liệu hỗn loạn bởi trung bình k-nearest neighbor. Trở ngại của chiều: Khoảng cách giữa những láng giềng có thể bị chi phối bởi những thuộc tính quan trọng. Để vượt qua điều này, kéo dãn trục hoặc loại trừ những thuộc tính ít quan trọng nhất. 1.4.5.2 Giải thuật Di truyền (Genetic Algorithms) Giải thuật di truyền dựa trên sự tiến bộ sinh học. Mỗi luật được biểu diễn bởi một chuỗi dữ liệu bit. Một mẫu khởi tạo được tạo ra bao hàm những luật được tạo một cách ngẫu nhiên. Dựa trên khái niệm của cái thích hợp nhất tồn tại. Những qui luật phù hợp nhất sẽ được biểu diễn bởi sự phân lớp chính xác của nó trên một tập hợp của những ví dụ huấn luyện. Sự thích hợp của một luật được biểu diễn bởi độ chính xác sự phân lớp của nó trên tập hợp những ví dụ huấn luyện. Kết quả được tạo ra bởi sự giao nhau và sự biến đổi. 1.4.5.3 Tiếp cận tập thô Tập thô được sử dụng để xấp xỉ hoặc định nghĩa “thô” những lớp tương đương. Một tập thô cho một lớp C được xấp xỉ bởi 2 tập hợp: một xấp xỉ dưới (chắc chắn ở trong C) và một xấp xỉ trên. Tìm kiếm tập rút gọn của những thuộc tính (đối với đặc tính rút gọn) là NP khó nhưng ma trận phân biệt được sử dụng để thu giảm cường độ tính toán. 1.4.5.4 Tiếp cận tập mờ Logic mờ sử dụng những giá trị thực giữa 0.0 và 1.0 để biểu diễn độ của quan hệ thành viên (ví dụ sử dụng đồ thị thành viên mờ). Những giá trị thuộc tính được chuyển sang những giá trị mờ. Đối với một ví dụ mới cho trước, nhiều hơn một giá trị mờ có thể được áp dụng. Mỗi luật có thể áp dụng đóng góp một đề cử cho thành viên theo thể loại. Thông thường, những giá trị thực đối với thể loại được tiên đoán được tổng kết. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 14 1.4.5.5 Phân lớp bằng suy luận dựa trên trường hợp (case-based reasoning) Những thực thể được biểu diễn bởi sự mô tả giàu tính tượng trưng (ví dụ hàm đồ thị). Kết hợp nhiều trường hợp nhận được, suy luận dựa trên tri thức và vấn đề giải quyết. 1.5. Kết luận chƣơng 1 Với bài toán phân lớp mẫu tổng quát có nhiều hướng tiếp cận để giải quyết. Hiện nay, các hướng tiếp cận phổ biến cho việc giải quyết bài toán phân lớp mẫu là: sử dụng K-NN và K-Mean với các độ đo khác nhau, Support Vector Machine (SVM) và mạng Nơron nhân tạo (ANN) … Phương pháp phân lớp bằng K-NN và K-Mean rất phổ cập hiện nay thích hợp với lớp bài toán, trong đó không gian biểu diễn mẫu nhỏ. Tuy nhiên, trong trường hợp không gian biểu diễn mẫu có kích thước lớn thì chi phí tính toán của hai phương pháp này cao. Phương pháp SVM áp dụng khá tốt cho các bài toán phân lớp mẫu ngay cả khi không gian biểu diễn mẫu lớn. Với các tiếp cận của phương pháp này, cần thiết phải xác định các siêu phẳng để phân lớp mẫu. Một cách tiếp cận khá phổ biến hiện nay là dùng mạng Nơron nhân tạo cho bài toán phân lớp mẫu. Với cách tiếp cận này, một mạng Nơron nhân tạo sẽ được huấn luyện với tập mẫu để tìm ra bộ trọng số phục vụ cho quá trình phân lớp. Cách tiếp cận này khắc phục được nhược điểm của SVM nhờ sử dụng hệ số ngưỡng trong quá trình phân loại mẫu. Cụ thể, nếu mẫu cần phân loại không thuộc L lớp cho trước, mạng Nơron nhân tạo xác định được và thông báo kết quả đối tượng đó nằm ngoài cơ sở dữ liệu các lớp đã có. Nhờ những ưu điểm trên của mạng Nơron, phương pháp phân lớp nhờ mạng Nơron nhân tạo sẽ ngày càng được phát triển và có nhiều ứng dụng hơn. Chương 2 sẽ trình bày cụ thể phương pháp phân lớp này. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 15 Chƣơng 2 Phân lớp các mẫu với ứng dụng của mạng Nơron nhân tạo 2.1 Mạng Nơron nhân tạo Mạng nơron nhân tạo là một mô hình tính toán được xây dựng dựa trên sự mô phỏng bộ não người. Để tìm hiểu về mạng nơron nhân tạo trước hết ta hãy điểm qua vài nét về mạng nơron sinh học. 2.1.1 Mạng nơron sinh học Kết quả các nghiên cứu về sinh học cho thấy bộ não người là một hệ thống có cấu trúc cực kỳ phức tạp. Nó có thể xử lý phi tuyến, song song và giải quyết cùng một lúc nhiều công việc khác nhau. Não còn có khả năng tự tổ chức hoặc tái tổ chức các bộ phận cấu thành của chính nó như các tế bào thần kinh hay các khớp nối thần kinh nhằm thực hiện hiệu quả nhất các nhiệm vụ đặt ra. Trung tâm của bộ não con người là một mạng lưới các tế bào thần kinh. Mạng lưới này thu nhận thông tin, xử lý thông tin, đưa ra các quyết định và điều khiển việc thực hiện các quyết định đó một cách phù hợp. Ngoài cùng của mạng lưới thần kinh là các bộ tiếp nhận làm nhiệm vụ nhận và chuyển đổi các kích thích từ các cơ quan khác trong cơ thể người hay từ môi trường bên ngoài thành các xung điện. Tiếp đó các xung điện này được lan truyền trong mạng và được biến đổi thành các xung điện điều khiển. Các xung điều khiển sẽ điều khiển con người hành động đáp ứng lại các kích thích mà bộ não nhận được. Cấu trúc của não là giống nhau cho tất cả mọi người, nhưng chỉ có khác ở các mức nơron và các nhóm nơron, những kinh nghiệm của con người có được là do não đã thay đổi các mối nối giữa các nơron của nó. Ba yếu tố chính quyết định khả năng xử lý của bộ não là các tế bào thần kinh (nơron), các khớp nối thần kinh và cấu trúc của các mối nối liên hợp thần kinh. Nơron là đơn vị cơ bản của thần kinh. Mỗi nơron gồm một nhân tế bào nhỏ với những sợi kéo dài gọi là trục của đuôi gai. Điểm cuối của các sợi trục của một nơron gặp điểm cuối của các đuôi gai của nhiều nơron khác. Trong não bộ con người có một mạng lưới các nơron rất phức tạp và luôn thay đổi. Các Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 16 nơron mà các sợi trục của chúng gặp nhau thường xuyên để trao đổi các tín hiệu điện. Người ta ước có khoảng 100 tỷ nơron trong não và khoảng 10 nghìn tỷ mối nối giữa chúng với nhau. Khả năng học tập và ghi nhớ của con người là kết quả của cách mà các nơron kết nối với nhau, và các tín hiệu do nơron phát ra tạo nên cơ sở cho tất cả mọi cảm nhận, ý nghĩ và hành động của chúng ta. Hình 2.1 - Mạng nơron sinh học Các nơron có thể tồn tại ở hai dạng: “đốt cháy” hay “không đốt cháy”. Khi một nơron được “đốt cháy”, nó phát ra khoảng từ 50 đến 100 xung điện mỗi giây, nếu nó không được “đốt cháy”, nó chỉ phát ra vài xung điện. Một nơron trở thành “đốt cháy” khi nó nhận được đủ mức kích thích từ những nơron mà nó kết nối. Có một màng bao quanh mỗi nơron mà bề mặt của màng có một “điện áp” hay điện thế, những thay đổi về điện áp này tạo cơ sở cho các tín hiệu thần kinh. Một nơron phát ra các xung điện đi từ nhân tế bào dọc theo các sợi trục, ở điểm cuối của nhiều nhánh của sợi trục, các xung điện được đuôi gai của nơron khác bắt lấy qua những khe mảnh mà ta gọi là khớp thần kinh. Mỗi xung đưa tới khớp thần kinh làm khớp thần kinh nhả ra những hóa chất gọi là vật truyền thần kinh, vật này đi qua khớp thần kinh và qua màng đuôi gai. Đến lượt nó, vật truyền thần kinh lại tác động tạo ra điện thế của nơron nhận. Nơron sẽ trở thành bị “đốt cháy” nếu điện thế của nó vượt quá một ngưỡng nào đó. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 17 Hình 2.2 Sơ đồ mạng nơron sinh học Một số nơron có đuôi gai tạo nên các giác quan nhận sự kích thích từ thế giới bên ngoài. Đuôi gai ở da nhạy cảm đối với áp suất và nhiệt độ, đuôi gai ở mắt lại nhạy cảm với ánh sáng. Các sản phẩm của não người được các nơron thần kinh vận động mang đi, từ não bộ đến các cơ. Khi một xung điện đi tới một cơ, nó làm cơ này co lại. Như vậy tất cả các cảm nhận của chúng ta về thế giới, từ nghe thấy tiếng chim hót cho tới cảm thấy đau khi kim châm - đều bắt đầu với tư cách là những xung điện ở điểm cuối các nơron cảm giác của chúng ta. Và xung điện ở các nơron dây thần kinh vận động của chúng ta chịu trách nhiệm về tất cả mọi thứ từ đơn giản như cái nháy mắt cho tới những hành động phức tạp khác. Khi chúng ta trải nghiệm và phản ứng với thế giới xung quanh chúng ta thì những nơron mới và những khớp thần kinh mới lại được hình thành, một số cũ biến mất và bản chất của một lớp thần kinh riêng biệt có thể thay đổi. Nhận thức của chúng ta về thế giới có được là nhờ sự đốt cháy các nơron trong não và khả năng học tập của chúng ta là kết quả của sự thay đổi kết nối giữa các nơron. 2.1.2 Mạng nơron nhân tạo 2.1.2.1 Những bộ phận của mạng nơron nhân tạo: Mỗi nơron là một bộ vi xử lý đơn giản. Các nơron được nối với nhau tạo nên mạng. Có thể chia các nơron trong mạng ra làm ba loại: - Các nơron vào: Đó là các nơron nhận tín hiệu vào. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 18 - Các nơron ẩn: Đó là các nơron chỉ truyền nhận tín hiệu trong nội bộ mạng. - Các nơron ra: Đó là các nơron làm nhiệm vụ đưa tín hiệu ra. Các nơron vào chỉ làm nhiệm vụ nhận tín hiệu ngoài mạng đưa vào mạng. Nó chỉ như một bộ cảm ứng mà không xử lý thông tin giống với cách xử lý thông tin của các nơron bên trong. 2.1.2.2 Sự liên hệ giữa các phần tử trong mạng nơron nhân tạo: Các nơron được nối với nhau theo các mối liên hệ giữa chúng. Cấu trúc của các mối liên hệ cho thấy các phần tử của mạng được nối với nhau như thế nào. Có trường hợp mỗi phần tử được nối với các phần tử khác của mạng. Có trường hợp các nơron được tổ chức theo các lớp phân cấp, lớp trước mới có thể truyền tín hiệu cho lớp sau. Và lại có trường hợp cho phép các nơron có thể liên hệ ngược trong đó các nơron lớp sau cũng có thể truyền tín hiệu cho lớp trước hoặc các nơron trong một lớp các nơron cũng có thể gửi tín hiệu cho nhau. Thực tế các kiểu liên hệ với nhau là vô hạn, nhưng thông thường đối với mỗi mô hình mạng người ta chỉ dùng một loại liên hệ. Như sau này ta sẽ thấy, có mạng truyền thẳng, mạng lan truyền ngược … Mỗi mối liên hệ được xác định bởi ba đặc trưng: - Phần tử từ đó mối liên hệ đi ra. - Phần tử mà mối liên hệ hướng vào nó. - Trọng số của mối liên hệ: đây là một số thực. Trọng số âm tương ứng với trường hợp tính tích cực của phần tử bị ép lại (tương ứng với trường hợp tín hiệu vào làm nơron nhận bị ức chế). Trọng số dương tương ứng với trường hợp tính tích cực của phần tử tương ứng được tăng lên (tương ứng với trường hợp tín hiệu vào làm nơron nhận được làm cho hưng phấn). Giá trị tuyệt đối của trọng số đặc trưng cho cường độ của mối liên hệ. 2.1.2.3 Biểu diễn nơron nhân tạo trong mối liên hệ với các nơron khác: Hình dưới đây mô tả một nơron nhân tạo trong mối liên hệ với các nơron khác. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 19 x S  1 y F x 2 x 3 Hình 2.3 : Mô hình nơron nhân tạo Trong đó : -  : Là bộ cộng - F : Là bộ biến đổi (x1 , x2 , …., xn) = XT là véc tơ vào. (w1 , w2 , …., wn) = W là các véc tơ trọng số. Hoạt động của nơron như sau: Khi tín hiệu vào được đưa vào nơron, tùy thuộc vào các trọng số wi mà nơron nhận được nhiều, ít với mức độ và ý nghĩa khác nhau. wi càng lớn thì nơron nhận thành phần thứ i (tức xi) càng nhiều. - wi > 0 thì xi làm nơron hưng phấn. - wi < 0 thì xi làm nơron ức chế . - wi = 0 thì xi không liên hệ với nơron. - Bộ cộng sẽ cộng có trọng số các tín hiệu đó n S   wixi i 1 0.7 Ví dụ với nơron j sau đây: -0.3 0.1 j 3.1 0.3 0.5 Hình 2.4. Tính tổng các tín hiệu đến một phần tử cụ thể n S=  xiwij = (0.7 * -0.3) + (0.1 * 3.1) + (0.3*0.5) = 0.25 i 1 Hoặc biểu diễn dưới dạng nhân ma trận ta có: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 20   0 .3  S = [0.7 0.1 0.3]  3.1 = 0.25  0.5 Thường thì với mỗi nơron có một độ lệch b. Khi đó n  S= xiwij + b i 1 Người ta đưa thành phần này vào trong tổng bằng cách coi như có một tín hiệu vào thứ 0 luôn có độ lớn bằng 1 được đưa vào nơron với cường độ liên hệ là w0j. Tổng trở thành: n S= x i0 i w ij trong đó x0 luôn luôn được coi bằng một hằng số ví dụ bằng 1 như hình dưới đây. 1 x 1 x w0j = b w1j w2j j w3j 1 x 1 Hình 2.5. Độ lệch ban đầu được coi như một nơron Cấu trúc và cường độ của các mối liên hệ thường được biểu diễn dưới dạng ma trận trọng số W, trong đó mỗi phần tử wij là trọng số của mối liên hệ đi từ phần tử i đến phần tử j (chú ý rằng có thể qui ước wij là trọng số của mối liên hệ đi từ phần tử j đến phần tử i). Để biểu diễn cấu trúc và cường độ của các mối liên hệ người ta dùng các ma trận trọng số. Trên hình 2.6 và 2.7 là các ví dụ về cách biểu diễn này. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn