T.C. SELÇUK ÜNİVERSİTESİ FEN BİLİMLERİ ENSTİTÜSÜ ÖRÜNTÜ TANIMA UYGULAMALARINDA YAPAY ZEKÂ VE ÖZNİTELİK DÖNÜŞÜM METOTLARI KULLANILARAK GELİŞTİRİLEN ÖZNİTELİK SEÇME ALGORİTMALARI Mustafa Serter UZER DOKTORA TEZİ Elektrik-Elektronik Mühendisliği Anabilim Dalı Temmuz-2014 KONYA Her Hakkı Saklıdır TEZ BİLDİRİMİ Bu tezdeki bütün bilgilerin etik davranış ve akademik kurallar çerçevesinde elde edildiğini ve tez yazım kurallarına uygun olarak hazırlanan bu çalışmada bana ait olmayan her türlü ifade ve bilginin kaynağına eksiksiz atıf yapıldığını bildiririm. DECLARATION PAGE I hereby declare that all information in this document has been obtained and presented in accordance with academic rules and ethical conduct. I also declare that, as required by these rules and conduct, I have fully cited and referenced all material and results that are not original to this work. Mustafa Serter UZER Tarih:21.07.2014 ÖZET DOKTORA TEZİ ÖRÜNTÜ TANIMA UYGULAMALARINDA YAPAY ZEKÂ VE ÖZNİTELİK DÖNÜŞÜM METOTLARI KULLANILARAK GELİŞTİRİLEN ÖZNİTELİK SEÇME ALGORİTMALARI Mustafa Serter UZER Selçuk Üniversitesi Fen Bilimleri Enstitüsü Elektrik-Elektronik Mühendisliği Anabilim Dalı Danışman: Doç.Dr. Nihat YILMAZ 2014, 103 Sayfa Jüri Doç.Dr. Nihat YILMAZ Doç.Dr. Yüksel ÖZBAY Doç.Dr. Seral ÖZŞEN Yrd.Doç.Dr. Ömer Kaan BAYKAN Yrd.Doç.Dr. Ali Osman ÖZKAN Bu tez çalışmasında, örüntü tanımanın temel öğelerinden biri olan öznitelik seçimi üzerinde durulmuştur. Özellikle veri madenciliği ve örüntü tanıma uygulamalarında kullanılan öznitelik seçimi, veri boyutunun azaltılmasını ve en iyi öznitelik kümesinin seçimini sağlar. Böylelikle kullanılan sınıflandırıcıların başarısı artar ve eğitim ile test süreleri azalır. Gereksiz öznitelikler tespit edildiği için özniteliklerin elde edilmesinde kullanılacak olan donanım azalır. Bu amaçla, bu tez kapsamında üç yeni öznitelik seçim yöntemi ve bu yöntemlerin kullanımıyla geliştirilen sistemler önerilmiştir. Bu öznitelik seçim yöntemlerinden birincisi, bal arısı sürüsünün akıllı yiyecek arama davranışını taklit eden Yapay Arı Kolonisi (YAK) optimizasyon algoritmasının, kümeleme tabanlı öznitelik seçiminde kullanılmasıyla geliştirilen ve YAKÖS olarak isimlendirilen yeni bir öznitelik seçme yöntemidir. İkincisi ve üçüncüsü, Karesel Diskriminant Analizi (KDA) sınıflandırma algoritmasını kriter alarak geliştirilen Ardışık İleri Yönde Seçim (AİYS) ve Ardışık Geri Yönde Seçim (AGYS) ile Temel Bileşen Analizinin (TBA) birleştirilmesiyle oluşturulmuş ve sırasıyla AİYSP ve AGYSP olarak isimlendirilen iki tane hibrit öznitelik seçme yöntemidir. Geliştirilen yeni YAKÖS yönteminin başarısı, hem Yapay Sinir Ağları (YSA) sınıflandırıcısında hem de Destek Vektör Makinaları (DVM) sınıflandırıcısında test edilirken diğer yöntemler ise YSA sınıflandırıcısında test edilmiştir. En iyi doğru sınıflandırma oranları, Statlog kalp hastalığı veri kümesi için % 88.89, SPECT görüntüleri veri kümesi için % 88.04 ve meme kanseri veri kümesi için % 98.71 olarak YAKÖS+TBA+YSA sisteminde bulunurken Hepatit veri kümesi için % 94.92, karaciğer hastalığı veri kümesi için % 74.81, Diyabet veri kümesi için % 79.29 olarak YAKÖS+DVM sisteminde bulunmuştur. Bunlara ilave olarak, kadınlarda en sık görülen kanser türü olan meme kanserinin teşhisi için AİYSP+YSA ve AGYSP+YSA sistemleri geliştirilmiştir. Kullanılan meme kanseri veri kümesi için AİYSP+YSA sisteminin doğru sınıflandırma oranı % 97.57 ve AGYSP+YSA sisteminin doğru sınıflandırma oranı % 98.57 elde edilmiştir. Sınıflandırmanın güvenilirliğini artırmak için bütün sistemlerde çapraz doğrulama yöntemi kullanılmıştır. Geliştirilen bu yöntemler, literatürdeki aynı veri kümelerini kullanan yöntemlere göre çoğunlukla daha yüksek sınıflandırma başarılarına ulaşmaktadır. Anahtar Kelimeler: Örüntü Tanıma, Temel Bileşen Analizi, Öznitelik seçimi, Yapay Arı Kolonisi, Yapay Sinir Ağı. iv ABSTRACT Ph.D THESIS FEATURE SELECTION ALGORITHMS DEVELOPED BY USING ARTIFICIAL INTELLIGENCE AND FEATURE TRANSFORM METHODS IN PATTERN RECOGNITION APPLICATIONS Mustafa Serter UZER THE GRADUATE SCHOOL OF NATURAL AND APPLIED SCIENCE OF SELÇUK UNIVERSITY THE DEGREE OF DOCTOR OF PHILOSOPHY IN ELECTRICAL AND ELECTRONICS ENGINEERING Advisor: Assoc.Prof.Dr. Nihat YILMAZ 2014, 103 Pages Jury Assoc.Prof.Dr. Nihat YILMAZ Assoc.Prof.Dr. Yüksel ÖZBAY Assoc.Prof.Dr. Seral ÖZŞEN Asst.Prof.Dr. Ömer Kaan BAYKAN Asst.Prof.Dr. Ali Osman ÖZKAN In this thesis study, feature selection which is one of the fundamental topic of pattern recognition, is studied. Feature selection, especially used in data mining and pattern recognition applications, reduce the size of data and enable the selection of the best set of features. Thus, for used classification success increase, and training ve test time reduce. Since redundant features are determined, hardware costs of data acquisition for these features are reduced. For this purpose, three new feature selection methods and systems that improved with these methods are proposed in this thesis. First new feature selection method developed in this study is clustering-based feature selection via the Artificial Bee Colony named as ABCFS. Artificial Bee Colony (ABC) optimization algorithm simulates the intelligent foraging behavior of honey bee swarm. The second and third methods are hybrid features selection methods named as SFSP and SBSP which are composed by combining the Sequential Forward Selection (SFS) and the Sequential Backward Selection (SBS) together with the Principal Component Analysis (PCA) developed by utilizing Quadratic Discriminant Analysis (QDA) classification algorithm criteria. While the success of the ABCFS method is tested with Artificial Neural Networks (ANN) classifier and Support Vector Machines (SVM) classifier, other methods have been tested in the ANN classifier only. The highest classification accuracies for Statlog (Heart) disease, SPECT images, breast cancer dataset were obtained by ABCFS+PCA+ANN as 88.89 %, 88.04 % and 98.71 % respectively. On the other hand, the highest classification accuracies for Hepatitis, Liver Disorders, Diabetes dataset were obtained by ABCFS+SVM as 94.92%, 74.81% and 79.29% respectively. In addition, for detection of breast cancer, which is the most common cancer type seen in women, SFSP+NN and SBSP+NN have been devoloped. For used breast cancer dataset, correct classification rate of SFSP+NN system is 97.57% and correct classification rate of SBSP+NN system is 98.57%. To improve the reliability of classification, cross-validation method was used in all systems. Obtained results show that the performance of proposed methods are generally highly successful compared to other results attained. Keywords: Pattern Recognition, Principal Component Analysis, Feature selection, Artificial Bee Colony, Artificial Neural Network. v ÖNSÖZ Doktora çalışmamı yapabilmem için her zaman bilgi birikimlerini benimle paylaşarak bana yol gösterici olan saygı değer hocam Doç.Dr. Nihat YILMAZ’a teşekkür ederim. Tüm bu çalışmalar süresince bana yardımcı olan varlıkları ile destek ve moral veren aileme ve özellikle eşim Dilek’e ve çocuklarım Fatma Tülay’a ve Atalay Miraç’a teşekkürlerimi sunuyorum. Mustafa Serter UZER KONYA-2014 vi İÇİNDEKİLER ÖZET ......................................................................................................................... iv ABSTRACT .................................................................................................................v ÖNSÖZ ...................................................................................................................... vi İÇİNDEKİLER ........................................................................................................ vii SİMGELER VE KISALTMALAR ........................................................................... iv ŞEKİLLER VE ÇİZELGELER ............................................................................... vi 1. GİRİŞ ......................................................................................................................1 2. KAYNAK ARAŞTIRMASI ....................................................................................5 3. MATERYAL VE METOT ................................................................................... 12 3.1. Materyal .......................................................................................................... 12 3.1.1. Statlog kalp veri kümesi ............................................................................ 12 3.1.2. SPECT kalp veri kümesi ........................................................................... 13 3.1.3. Meme kanseri veri kümesi ......................................................................... 14 3.1.4. Hepatit veri kümesi ................................................................................... 15 3.1.5. Karaciğer hastalığı veri kümesi ................................................................. 16 3.1.6. Diyabet veri kümesi .................................................................................. 17 3.2. Metot ............................................................................................................... 18 3.2.1. Öznitelik seçimi ........................................................................................ 18 3.2.1.1. Alt küme üretimi ............................................................................. 19 3.2.1.2. Alt küme değerlendirmesi ............................................................... 21 3.2.1.3. Durdurma kriteri ............................................................................. 22 3.2.1.4. Sonuç doğrulaması .......................................................................... 22 3.2.2. Öznitelik seçim metotlarının gruplandırılması ........................................... 23 3.2.2.1. Filtre algoritması ............................................................................. 23 3.2.2.2. Sarmalama algoritması .................................................................... 24 3.2.2.3. Hibrit algoritması ............................................................................ 25 3.2.3. Temel alınan öznitelik seçim ve boyut azaltımı yöntemleri ........................ 26 3.2.3.1. Ardışık İleri Yönde Seçim ............................................................... 26 3.2.3.2. Ardışık Geri Yönde Seçim .............................................................. 27 3.2.3.3. Temel Bileşen Analizi ..................................................................... 28 3.2.4. Sıkça kullanılan öznitelik seçim metotları ................................................. 29 3.2.4.1. TBA ve Birliktelik Kurallarına Dayanan Hibrit Öznitelik Seçim Yöntemi ....................................................................................................... 29 3.2.4.2. Bilgi kazancına dayanan öznitelik seçme algoritması ...................... 30 3.2.4.3. Kernel F-skor öznitelik seçme yöntemi ........................................... 31 3.2.4.4. Alt uzay temelli öznitelik seçim yöntemleri ..................................... 32 3.2.4.5. Tam kapsamlı arama ....................................................................... 33 3.2.4.6. Dal ve sınır...................................................................................... 34 3.2.4.7. Bireysel en iyi öznitelik seçimi ........................................................ 34 vii 3.2.4.8. Artı l – çıkar r seçim ....................................................................... 34 3.2.4.9. Ardışık ileri yönde kayan seçim ...................................................... 35 3.2.4.10. Ardışık geri yönde kayan seçim ......................................................... 35 3.2.4.11. Genetik seçim ................................................................................. 35 3.2.5. Optimizasyon ile kümeleme ...................................................................... 36 3.2.6. Yapay Arı Kolonisi algoritması ................................................................. 37 3.2.7. Sınıflandırma ............................................................................................ 40 3.2.7.1. Yapay Sinir Ağları .......................................................................... 40 3.2.7.2. Eğitim algoritması ........................................................................... 42 3.2.7.3. Destek Vektör Makineleri ............................................................... 44 3.2.7.4. Sıralı Minimal Optimizasyon .......................................................... 46 3.2.7.5. Karesel Diskriminant Analizi .......................................................... 48 3.2.8. Performans değerlendirme ......................................................................... 49 3.2.8.1. Sınıflandırma doğruluğu.................................................................. 49 3.2.8.2. Karşıtlık matrisi .............................................................................. 50 3.2.8.3. Duyarlılık ve Belirlilik analizi ......................................................... 50 3.2.8.4. K-katlı çapraz doğrulama ................................................................ 51 4. GELİŞTİRİLEN ÖZNİTELİK SEÇİM METOTLARI ...................................... 52 4.1. Yapay Arı Kolonisi Algoritmasına Dayanan Yeni Öznitelik Seçme Yöntemiyle Geliştirilen Sistemler ............................................................................................... 52 4.1.1. Yapay Arı Kolonisi algoritmasına dayanan yeni öznitelik seçimi (YAKÖS) . .................................................................................................................. 54 4.1.2. YAKÖS yöntemiyle elde edilen verilerin sınıflandırılması ........................ 59 4.2. AGYSP ve AİYSP Öznitelik Seçimi ve YSA Sınıflandıcısıyla Hibrit Meme Kanseri Algılama Sistemi ........................................................................................ 61 4.2.1. AİYSP ve AGYSP ile öznitelik seçimi ................................................ 62 4.2.2. AİYSP ve AGYSP öznitelik seçim yöntemleriyle geliştirilen sistemlerin YSA ile sınıflandırılması .................................................................. 62 5. ARAŞTIRMA SONUÇLARI VE TARTIŞMA ................................................... 64 5.1. YAKÖS ile Geliştirilen Sistemlerin Araştırma Sonuçları ve Tartışma .............. 64 5.1.1. YAKÖS yöntemiyle seçilen özniteliklerin sonuçları ve tartışma ................ 64 5.1.2. YAKÖS yöntemini kullanan sistemlerin sınıflandırma sonuçları ve tartışma .................................................................................................................. 65 5.2. AGYSP ve AİYSP Öznitelik Seçimi ve YSA Sınıflandıcısıyla Hibrit Meme Kanseri Algılama Sisteminin Araştırma Sonuçları ve Tartışma ................................ 80 6. SONUÇLAR VE ÖNERİLER .............................................................................. 85 6.1. Sonuçlar ........................................................................................................... 85 6.2. Öneriler ........................................................................................................... 88 KAYNAKLAR .......................................................................................................... 90 ÖZGEÇMİŞ............................................................................................................. 101 viii SİMGELER VE KISALTMALAR Simgeler C : Kovaryans matris c : Gerçek değer maliyet parametresi c : En önemli S değeri 0 0 D : N özellikli veri kümesinin eğitimi D : Eğitim örneklerinin sayısı Train E : YSA çıkışı için, herbir j nöronunun hatası, j E : Bütün nöronların çıkış hatası f : YSA’da bir aktivasyon fonksiyonu f : Kümeleme probleminin maliyet fonksiyonu i fit : Verilen çözümün uygunluğu i F : n. tane öznitelik n FN : Yanlış negatif FP : Yanlış pozitif F(i) : i. özelliğin f-skor değeri J : Amaç fonksiyonu K : Kümelerin sayısı L : Örneklerin sayısı MCN : Maksimum çevrim sayısı N : j’inci kümedeki örneklerin sayısı j n : Pozitif örneklerin sayısı + n Negatif örneklerin sayısı – : net : Geriye yayılma algoritması için, nöronlar arasındaki bağlantıların ağırlığı j N : Örneklerin sayısı p : Olasılık değeri i SN : Yiyecek kaynağı sayısı S : Aramanın başlatıldığı alt küme 0 S : En uygun alt küme best s : Skala değeri k TP : Doğru pozitif TN : Doğru negatif U : Birim matrisi v : U’nun k. en büyük öz değeri k v : Her bir adayın kaynak pozisyonu ij w : j kümesi ile x örneğinin ilişki ağırlığı ij i w : YSA’da katmanlar arası ağırlıklık matrisi ji x : i’inci örneğin yeri i x : Örneklerin ortalaması, () x : Negatif veri kümelerinin i. özelliğinin ortalaması i () x : Pozitif veri kümelerinin i. özelliğinin ortalaması i x() : k. negatif örneğinin i. özelliği k,i x() : k. pozitif örneğinin i. özelliği k,i Y : Seçilen öznitelikler kümesi k y : j çıkış nöronunun istenen çıkış değeri dj y : Nöronun gerçek çıkışı j z : j’inci kümenin merkezi j zj : Kâşif arının yeni bir kaynak üretmesi i δ : Durdurma kriteri γ : M bağımsız ölçüt vasıtasıyla yapılan değerlendirme sonucu γ : En iyi M bağımsız ölçüt vasıtasıyla yapılan değerlendirme sonucu best θ : A madencilik algoritmasıyla yapılan değerlendirme sonucu θ : En iyi A madencilik algoritmasıyla yapılan değerlendirme sonucu best iv  : Karşılaştırma parametresi k  : Adım boyutunun değeri k  : Skala parametresi k α : Lagrange çarpanı i Kısaltmalar AİYS : Ardışık İleri Yönde Seçim (Sequential Forward Selection-SFS) AGYS : Ardışık Geri Yönde Seçim (Sequential Backward Selection-SBS) AİYSP : Ardışık İleri Yönde Seçim ile TBA’nın birleştirilmesiyle oluşan hibrit öznitelik seçim algoritması AGYSP : Ardışık Geri Yönde Seçim ile TBA’nın birleştirilmesiyle oluşan hibrit öznitelik seçim algoritması APKD : Alan Programlamalı Kapı Dizileri (Field Programmable Gate Array-FPGA) ÇKPSA : Çok Katmanlı Perseptron Sinir Ağı ÇD : Çapraz Doğrulama (Cross validation-CV) DVM : Destek Vektör Makineleri (Support Vector Machines-SVM) FS : Fisher alt uzayı (Fisher Subspace) KDA : Karesel Diskriminant Analizi (Quadratic Discriminant Analysis-QDA) KEDA : Kernel Diskriminant Analizi (Kernel Discriminant Analysis) ÖEGGYA : Ölçeklendirilmiş Eşlenik Gradyan Geriye yayılım Algoritması (Scaled Conjugate Gradient Backpropagation) SMO : Sıralı Minimal Optimizasyon (Sequential Minimal Optimization-SMO) Sİİ : Sayısal İşaret İşleyicileri (Digital Signal Processor-DSP) TBA : Temel Bileşen Analizi (Principal Component Analysis-PCA) YAK : Yapay Arı Kolonisi (Artificial Bee Colony-ABC) YAKÖS : Yapay Arı Kolonisine dayanan öznitelik seçimi (Feature Selection based Artificial Bee Colony-ABCFS) YSA : Yapay Sinir Ağları (Artificial Neural Network-ANN) v