Kaba kümeler teorisi üzerine algoritmalar
Algorithms based on rough set theory
Yazar: FATİH AYBAR
Danışman: YRD. DOÇ. DR. ŞAHİN EMRAH
Ankara Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2011
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control
Dizin: Bilgi sistemleri = Information systems ; Kaba kümeler = Rough sets ; Karar formülasyonları = Decision rules ; Kurala dayalı sistemler = Rule-based systems ; Sınıflandırma = Classification

Özet:
Kaba kümeler teorisi Pawlak (1982) tarafından geliştirildi ve kendisine birçok dalda uygulama alanı buldu. Bu alanlara bir kaç örnek verilecek olursa; tıp, yapay zeka, finans, çelişki çözümlemesi, resim analizi, örüntü algılama, kontrol teorisi, özellik çıkarımı, sınıflandırma, kural indirgeme, makine öğrenmesi ve uzman sistemler sayılabilir. Kaba kümeler teorisinin uygulandığı konulardan biri de sınıflandırma ve kural indirgemedir. Kural indirgeme gerçekleştirmesi (Kİ) üzerine ilk algoritma Pawlak (1991) tarafından tasarlandı ve Kusiak ile Tseng tarafından düzenlendi. Kİ algoritması önemli bir eksiklik içermektedir. Bu algoritma tüm durumları inceler ve bulduğu kuralların tamamını kural indirgeme olarak kabul eder. Jia-Yuarn Guo ve Vira Chankong tarafından 2002'de uygulanan Geliştirilmiş Kural İndirgeme Algoritması (GKİ) ise Kİ algoritmasının bu eksikliğini tamamlamıştır, ancak bunun için bilgi sisteminin her incelemeden önce yeniden düzenlenmesine ihtiyaç vardır. Bu tez kapsamında, en az sayıda kural indirgeme durumlarını bulmak için Budanmış Kural İndirgeme Algoritması (BKİ) geliştirilmiştir. GKİ yönteminden farklı olarak bu algoritma ağaç tipi veri yapısını kullanmaktadır. BKİ algoritması, Wisconsin göğüs kanseri verisinde hastalıkları teşhis etmede uygulanmıştır. 699 hastanın bulunduğu bilgi sisteminde 490 hastaya ait veri, eğitim amacıyla sisteme verilmiştir. Kalan 209 kaydın hastalık değerleri %99.52 doğruluk oranında başarıyla tahmin edilmiştir. GKİ algoritması üzerine yapılan çalışmalar esnasında, algoritmanın yüksek miktarda bellek kaynağına ihtiyaç duyduğu görülmüştür. Bu sebeple algoritmada bazı iyileştirmeler yapılabileceği anlaşılmıştır. Çalışmalar neticesinde daha az bellek kullanan ve daha basit işleyişe sahip bir algoritma elde edilmiştir. Kİ, GKİ, BKİ ve iyileştirilmiş GKİ algoritmalarının, aynı bilgisayar üzerinde Wisconsin göğüs kanseri verisindeki kural indirgemeleri bulmaları sağlanmıştır. Algoritmalar arasında yapılan karşılaştırma sonucunda BKİ algoritmasının 10 saniye ile en iyi performansa sahip olduğu, bunu 12 saniye ile GKİ'nin takip ettiği; iyileştirilmiş GKİ'nin ise 13 saniyede tamamlandığı görülmüştür. Kİ algoritması ise 142 saniye ile en kötü performansa sahiptir.

Abstract:
Rough set theory was developed by Pawlak (1982) and is applied in many domains, such as, medicine, artificial intelligence, finance, conflict resolution, image analysis, pattern recognition, control theory, feature extraction, classification, rule reduction, machine learning and expert systems. One of the topics that rough set theory is applied, is classification and rule reduction. First algorithm for Rule Reduct Generation (RG) was proposed by Pawlak (1991) and modified by Kusiak and Tseng. The RG algorithm has important deficiency. This algorithm finds all the situations which consist of found rule reducts as subset and regard them as they are all rule reduct. The Modified Rule Reduct Generation Algorithm (MRG) which is developed by Jia-Yuarn Guo and Vira Chankong (2002) fills this deficiency, but in that case before using information system, it is needed to be sorted. In this article, the Pruning Rule Reduct Generation Algorithm (PRG) is suggested to find the set of minimum rule reduct. Unlike MRG, PRG Algorithm uses tree structured data type. The PRG algorithm is applied on medical diagnosis. The Wisconsin breast cancer database is used to make a prediction. The information system has 699 patients and 490 of them are given to the system as training data. The rest of the records in the database, that contain 209 patients are tried to be predicted. The PRG algorithm can reach successful solutions in an accuracy of 99.52%. While implementing the MRG, it is understood that the method needs too much memory allocation. So some parts of the method are viewed as needing some reorganization. After some developments, a simple algorithm is produced that needs less memory. The algorithms RG, MRG, PRG and improving on MRG are applied to find out the rule reducts in the Wisconsin breast cancer database on the same computer. The comparison of the algorithms shows that PRG has the best execution time with 10 seconds. The MRG terminates in 12 seconds and the procedure improving on MRG runs along 13 seconds. The RG terminates in 142 seconds and it has the worst performance.