Mô hình cây quyết định và ứng dụng trong “mũi nhân tạo” để nhận dạng đối tượng từ mùi vị - Trần Hoài Linh

Trần Hoài Linh và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 99(11): 127 - 131 127 MÔ HÌNH CÂY QUYẾT ĐỊNH VÀ ỨNG DỤNG TRONG “MŨI NHÂN TẠO” ĐỂ NHẬN DẠNG ĐỐI TƯỢNG TỪ MÙI VỊ Trần Hoài Linh1*, Trương Tuấn Anh2 1Trường Đại học Bách Khoa Hà Nội; 2Trường Đại học Kỹ thuật Công nghiệp - ĐH Thái Nguyên TÓM TẮT Bài báo để cập tới mô hình nhận dạng ứng dụng trong thiết bị “mũi nhân tạo” để xác định thành phần của các “mùi” thoát ra từ đối tượng, từ đó đưa ra được kết quả nhận dạng về đối tượng. Mô hình cây quyết định sẽ được đề xuất sử dụng. Các thông số của cây sẽ được xác định bởi thuật toán ID3. Đối tượng để nhận dạng là các loại bia khác nhau. Khí mùi thoát ra từ dung dịch bia sẽ được thu thập bởi một hệ thống đo với 7 cảm biến khí khác nhau để khắc phục hiện tượng trùng phổ của các cảm biến điện trở này. Các kết quả tính toán và mô phỏng sẽ minh chứng được sự đơn giản, hiệu quả và tính khả thi để triển khai giải pháp trên các mạch vi xử lý của thiết bị đo. Từ khóa: mũi nhân tạo, cây quyết định, thuật toán ID3, cảm biến khí, nhận dạng bia GIỚI THIỆU CHUNG* Bài toán phân tích và nhận dạng các khí thành phần trong một hỗn hợp khí có nhu cầu sử dụng cao trong thực tế [2,3]. Có thể kể tới các ứng dụng quan trọng như nhiệm vụ phát hiện rò rỉ khí cháy nổ, khí độc trong nhà máy, trong dân dụng, phân tích đánh giá chất lượng thực phẩm, đánh giá các điều kiện môi trường,... Trong các thiết bị đo và phân tích nồng độ khí, các cảm biến đóng vai trò rất quan trọng. Các thiết bị đo sử dụng phân tích phổ có độ chính xác rất cao nhưng lại cồng kềnh, phức tạp, thường chỉ phù hợp cho việc sử dụng trong phòng thí nghiệm. Để có được các thiết bị gọn nhẹ, đơn giản cho các ứng dụng ngoài hiện trường hoặc xách tay ta thường sử dụng một trong ba loại cảm biến sau: - Cảm biến sợi đốt: có phủ một lớp ô-xít kim loại, được một sợi đốt nhỏ nung lên nhiệt độ cần thiết (thường là lớn hơn 250oC) để tạo điều kiện phản ứng, khi cho hỗn hợp khí chạy qua thì các phần tử khí nhất định sẽ tác động với lớp ô-xít kim loại để tạo ra tín hiệu điện trở, điện áp hoặc dòng điện để đưa tới đầu ra của cảm biến. - Cảm biến polymer: có phủ một lớp màng polymer có khả năng hấp thụ một lượng phân tử khí, khi đó điện trở bề mặt của polymer sẽ * Tel: 0912 316629, Email: thlinh2000@yahoo.com thay đổi. Đo điện trở này ta sẽ ước lượng được nồng độ của thành phần khí vừa đo. - Cảm biến tinh thể: Có chứa một tinh thể đã được lựa chọn sẵn cho mỗi loại khí có thể đo. Khi hỗn hợp khí được đưa qua cảm biến, một số phân tử khí được hấp thụ bởi tinh thể này khiến cho tần số dao động riêng của tinh thể thay đổi. Đo tần số dao động của tinh thể ta có thể ước lượng được nồng độ của thành phần khí trong hỗn hợp. Các loại cảm biến vừa nêu có ưu điểm là gọn nhẹ, dễ thao tác, tuy nhiên nhược điểm chung lớn nhất của chúng là có đặc tính phi tuyến, đồng thời tính chọn lọc của cảm biến thấp, có nghĩa là cảm biến tác động với nhiều loại khí khác nhau, do đó nếu trong hỗn hợp xuất hiện đồng thời các khí đó thì ta không thể xác định được nồng độ của từng thành phần. Một ví dụ dạng đặc tính của các cảm biến này được cho trên hình 1. Trong đó trục hoành là nồng độ của thành phần khí (Tính theo %LEL - Lower Level of Explosion), trục tung là điện áp đầu ra của cảm biến. Để khắc phục được nhược điểm này ta có thể xây dựng một thiết bị đo sử dụng một ma trận cảm biến. Khi sử dụng số chỉ của nhiều cảm biến đồng thời ta có thể ước lượng được chính xác hơn các thành phần của hỗn hợp khí. Tuy nhiên có hai vấn đề lớn cần phải khắc phục khi đó là: 1. Sử dụng bao nhiêu cảm biến là đủ? 2. Thuật toán xử lý tín hiệu từ các cảm Trần Hoài Linh và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 99(11): 127 - 131 128 biến như thế nào để loại trừ hiệu ứng trùng phổ (tính không chọn lọc) của cảm biến? Hình 1: Một đặc tính ví dụ của cảm biến khí cháy nổ của Figaro Trong bài báo này, một phương pháp phân tích tín hiệu sử dụng mô hình Cây quyết định (Decision Tree - DT) sẽ được ứng dụng để giải quyết hai vấn đề trên [1,5,6,7]. Cây quyết định được xây dựng trên cơ sở một tập mẫu bằng thuật toán ID3 [6,7]. Các đặc tính được sử dụng trong các nút điều kiện của cây sẽ quyết định lựa chọn các cảm biến. Tín hiệu nhận dạng đầu ra của thiết bị sẽ là kết quả nhận dạng từ cây quyết định. Giải pháp này sẽ được minh họa qua ví dụ nhận dạng loại bia thông qua mùi của sản phẩm đo về từ 7 cảm biến khác nhau. Kết quả hoạt động sẽ cho thấy tính hiệu quả của giải pháp. CÂY QUYẾT ĐỊNH VÀ THUẬT TOÁN ID3 Cây quyết định là một mô hình nhận dạng kinh điển đã được sử dụng rất rộng rãi trong nhiều ứng dụng thực tế. Cấu trúc và nguyên lý hoạt động của cây cũng khá đơn giản [1,4]. Mỗi cây là một đồ thị không có chu trình trong đó, cây có 1 nút quy ước được gọi là gốc. Mỗi nút của cây có thể có một số nhánh đi tới các nút cấp thấp hơn được gọi là nút con. Nút không có phân nhánh và nút con được gọi là lá. Cây quyết định được thiết kế với mỗi nút sẽ có một điều kiện phân nhánh. Tại các nút lá sẽ có 1 giá trị tương ứng với kết quả nhận dạng. Trên hình 2 là mô hình của một cây quyết định đơn giản. Trong các phương pháp xây dựng cây quyết định ta thường sử dụng cây nhị phân (bậc 2) để đơn giản hóa việc mô tả các thuật toán. Giả thiết này không làm giảm tính tổng quát của cây do một cây bậc bất kỳ đều có thể chuyển về một cây nhị phân tương đương. Hình 3 minh họa phương pháp chuyển một nút bậc 3 về thành 2 nút bậc 2 trong một cây. Đồng thời các điều kiện phân nhánh tại mỗi nút ta sẽ sử dụng các điều kiện đơn (ở dạng x op A với op là toán tử so sánh cơ bản , , , , , .= ≠ > ≥ < ≤ ). Hình 2: Mô hình cây quyết định Hình 3: Phương pháp chuyển một nút bậc cao thành một nút bậc 2 Trần Hoài Linh và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 99(11): 127 - 131 129 Để xây dựng một cây quyết định cho một bộ mẫu số liệu cho trước, ta có thể sử dụng nhiều phương pháp khác nhau, trong đó phương pháp phổ biến nhất là phương pháp ID3. Nội dung cơ bản của phương pháp này dựa trên công thức lượng thay đổi entropy của một nút cây. Theo đó, với một bộ số liệu cho trước, nếu như tại một nút V ta có N số liệu 1x , 2 ,...,x Nx thuộc M nhóm 1 2, , MC C C thì entropy của nút này sẽ là: 2 1 ( ) log ( ) M i i i E V p p = = −∑ với { }:j j i i x x C p N ∈ = là xác suất số liệu jx của nút thuộc về nhóm iC . Với định nghĩa trên ta sẽ tiếp tục định nghĩa độ giảm entropy của nút khi sử dụng một điều kiện phân nhánh S này đó. Với một nút V, khi sử dụng điều kiện phân nhánh S thì các số liệu được phân chia về các nút con iSV với số lượng là iN ( ii N N=∑ ). Sử dụng công thức entropy cho từng nút, ta có độ giảm entropy của V khi sử dụng điều kiện S là: ( , ) ( ) ( )i i i NGain V S E V E SV N = −∑ Đối với nút tất cả các điều kiện phân nhánh có thể sẽ được xem xét và kiểm tra (với một biến x có K giá trị khác nhau ta có thể tạo được K+1 điều kiện phân chia khác nhau). Điều kiện phân nhánh được lựa chọn sẽ là điều kiện phân nhánh ứng với độ giảm entropy lớn nhất. Quá trình phân nhánh sẽ được dừng lại khi tại mỗi nút lá tất cả các mẫu số liệu đều thuộc về cùng một nhóm. MÔ HÌNH MŨI NHÂN TẠO VÀ ỨNG DỤNG TRONG BÀI TOÁN XÁC ĐỊNH THÀNH PHẦN HỖN HỢP KHÍ Bài toán thiết bị đo cần xây dựng trong nghiên cứu này là thiết bị “mũi nhân tạo” để xác định và phân loại các mẫu bia đóng chai thông qua việc đo và phân tích nồng độ các thành phần khí thoát ra từ mẫu. “Mũi nhân tạo” là tên dùng chung cho các thiết bị đo sử dụng cảm biến phản ứng với khí thoát ra từ đối tượng đang xem xét. Các loại bia đang xét gồm 4 mẫu bia từ châu Âu là Krol Zloty, Lech, Warka và Zywiec. Các thành phần khí thoát ra từ các mẫu bia này được thu thập đồng thời thông qua hệ 7 cảm biến là TGS815, TGS821, TGS822, TGS825 và TGS 842 của hãng Figaro, NAP-11AS và NAP- 11AE của Nemoto [2,3]. Các cảm biến này đều phản ứng với các thành phần khí thoát ra từ các loại bia đã nêu trên nhưng với các mức độ và đặc tính khác nhau. Mô hình tổng thể của mũi nhân tạo đo với một hệ cảm biến được trình bày trên hình 4. Hình 4: Mô hình “mũi nhân tạo” phân tích tín hiệu từ hệ cảm biến Các tín hiệu đo về từ hộp đo với hệ cảm biến sẽ được thu thập, phân tích và xử lý bằng phần mềm trên PC. Trong bài báo này ta sẽ sử dụng mô hình cây quyết định và thuật toán ID3 để làm mô hình nhận dạng các thành phần khí trong hỗn hợp đầu vào của mẫu khí. Cây quyết định cũng sẽ hỗ trợ ta trong việc lựa chọn các cảm biến hiệu quả cho bài toán, cụ thể là chỉ những cảm biến mà tín hiệu được sử dụng trong cây quyết định mới được lựa chọn để tiếp tục sử dụng trong thực tế. Do mô hình cây quyết định cũng tương đối đơn giản, nhất là khi sử dụng các điều kiện so sánh đơn, nên có thể dễ dàng lập trình triển khai trên các hệ vi xử lý để từ đó có được các thiết bị đo độc lập, hoạt động không cần tới PC. CÁC KẾT QUẢ THỬ NGHIỆM Để thử nghiệm các ý tưởng giải pháp đã đề xuất ở trên, các thiết bị đo đã được triển khai trong thực tế. 576 mẫu đo cho 4 loại bia (chia đều 144 mẫu cho mỗi loại) đã được thu thập. Bộ số liệu mẫu này được chia thành 2 tập con: 288 mẫu được dùng để xây dựng mô hình, 288 mẫu được dùng để kiểm tra chất lượng của mô hình. Phần mềm xây dựng cây quyết định theo thuật toán ID3 được xây dựng trong môi trường Matlab. Trần Hoài Linh và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 99(11): 127 - 131 130 Với 288 mẫu số liệu học, ta tiến hành xây dựng cây quyết định và thu được kết quả như trên hình 5 (điều kiện của nút được thỏa mãn thì rẽ trái, không thỏa mãn thì rẽ phải). Hình 5: Cây quyết định xây dựng từ bộ mẫu số liệu học (mã 1 = ‘Krol Zloty’, 2 = ‘Lech’, 3 = ‘Warka’ và 4 = ‘Zywiec’) Từ hình 5 ta thấy chỉ các tín hiệu từ các cảm biến số 2 (TGS821), số 3 (TGS822) và số 5 (TGS842) là được sử dụng để tiến hành nhận dạng. Do đó đây cũng sẽ là định hướng để thiết bị đo cuối cùng sẽ chỉ sử dụng ba cảm biến này. Với cấu trúc đơn giản như trên hình 5, ta có thể xây dựng các luật nhận dạng như sau để dễ dàng sử dụng trong lập trình thiết bị độc lập. Ứng với mỗi nút lá ta có thể tổng hợp các điều kiện để đi từ gốc đến nút đó. Với 8 lá của cây trên hình 5 ta có thể xây dựng 8 luật tương ứng. Ví dụ một số luật như sau: Lá số 1 (tính từ trái sang phải): if 2 0,0245x < then class = ‘4’ (Bia Zywiec) Lá số 2 (tính từ trái sang phải): if 20,05385 0,0245x> > and 5 0,1179x < then class = ‘2’ (Bia Lech) Lá số 8 (ngoài cùng bên phải): if 2 0,0751x > and 3 0,0627x > then class = ‘3’ (Bia Warka). Tiến hành thử nghiệm với 288 mẫu còn lại từ bộ số liệu kiểm tra ta có kết quả chỉ có duy nhất 1 mẫu được nhận dạng không chính xác, 287 mẫu được nhận dạng đúng. Mẫu nhận dạng không chính xác có các tín hiệu đầu vào là: ]1701,0;1538,0;1179,0;0205,0;0485,0 ;075,0;0221,0[],,,,,,[ 7654321 −=xxxxxxx Khi đưa vào cây quyết định sẽ có được kết quả là 3 (nút gốc → nút gốc → rẽ trái → rẽ phải → rẽ phải) trong khi số liệu gốc là mẫu của loại bia số 1. Toàn bộ 287 mẫu còn lại được phân loại và nhận dạng đúng, tương ứng với độ chính xác 99,65%, sai số 0,35%. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN Bài báo đã trình bày về mô hình cây quyết định và phương pháp xây dựng cây theo thuật toán ID3 cho phép tạo ra các cây có chiều cao nhỏ, thuận tiện cho việc sử dụng trong thực tế. Việc sử dụng cây quyết định còn cho phép xác định các thông số đặc trưng cần thiết cho quá trình nhận dạng, từ đó cho phép loại bỏ các thông số không cần thiết để làm đơn giản hóa hệ thu thập, giảm thời gian thu thập và xử lý tín hiệu. Các ý tưởng giải pháp đã được thử nghiệm trên bài toán thực tế là phân loại bia dựa trên phân tích các thành phần khí thoát ra từ dung dịch bia. Kết quả cho thấy chỉ cần sử dụng 3 cảm biến TGS821, TGS822 và TGS842 là đủ để xây dựng thiết bị đo nhận dạng loại bia với độ chính xác rất cao là 99,65%. Với thuật toán hoạt động đơn giản của Cây quyết định thì mô hình được đề xuất trong bài báo này hoàn toàn có thể được triển khai trên các thiết bị thực tế mà chỉ cần sử dụng các vi xử lý thông dụng. TÀI LIỆU THAM KHẢO [1]. Andrew Colin, Building Decision Trees with the ID3 Algorithm, Dr. Dobbs Journal, 1996. [2]. K. Brudzewski, Smart chemical sensing system for analysis of multi-component mixtures of gases, MST NEWS Poland 2, pp. 1 - 11, 1996. [3]. K. Brudzewski, S. Osowski, Gas analysis system composed of a solid state sensor array and hybrid neural network structure, Sensors and Actuators-B55 (Chemical), pp. 38-46, 1999. [4]. Tom Mitchell , Machine Learning, McGraw- Hill, pp. 52-81, 1997. [5]. Lynn Monson, Algorithm Alley Column: C4.5, Dr. Dobbs Journal, Jan 1997. [6]. J. Ross Quinlan, C4.5 Programs for Machine Learning, Morgan Kaufmann, 1993. [7]. Paul E. Utgoff, Incremental Induction of Decision Trees, Kluwer Academic Publishers, 1989. Trần Hoài Linh và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 99(11): 127 - 131 131 SUMMARY DECISION TREE AND ITS APPLICATION IN OBJECTS RECOGNITION BASED ON THEIR FLAVORS Trần Hoài Linh1*, Trương Tuấn Anh2 1Hanoi University of Science and Technology; 2College of Technology - TNU This paper presents the idea of creating an “artificial nose” to detect the components of gas mixtures in order to recognize the given object. The decision tree model is used as the pattern recognizer. The paramters of the tree are determined by using the ID3 algorithm. The objects to be recognized are different beer samples. The gases generated by the beer samples are exposed to a matrix of 7 gas sensors due to the nonideality of the sensors. The numerical experiments and simulations will show the effectivity, reliability of the solution and its posibility to be implemented on measuring devices. Keywords: artificial nose, decision tree, ID3 algorithm, gas sensor, beer recognition. Ngày nhận bài:03/7/2012, ngày phản biện:20/7/2012, ngày duyệt đăng:10/12/2012 * Tel: 0912 316629, Email: thlinh2000@yahoo.com