Searching for the optimal ordering of classes in rule induction
Kural çıkarımda optimal sınıf sıralamasını arama
- Tez No: 320750
- Danışmanlar: DOÇ. DR. OLCAY TANER YILDIZ
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2012
- Dil: İngilizce
- Üniversite: Işık Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 62
Özet
Bu tezde, CN2 ve Ripper kural çıkarım algoritmaları üzerinde çalıştık. Bu algoritmaların ortak özelliği K > 2 sınıflı veri kümelerini sınıflandırırken, K-1 adet 2sınıflı probleme çevirerek sınıflandırmalarıdır. Bulgusal yaklaşıma göre, bu algoritmalarsınıfları, artan önsel olasılıklarına göre ögrenirler. Biz de çalışmamızda,kural çıkarım algoritmalarının sınıf sıralamalarına bağlı olarak performanslarınınnasıl değişeceğini araştırırız. Bu amaçla, iki algoritma sunarız.Sunulan ilk algoritma, FOS (ileriye doğru-sıralama arama algoritması), ilk olarakbulgusal yaklaşımın sıralamasıyla başlar. Yan yana sınıfların yer değişimleri ileoluşturulmuş sıralamaları, daha iyi performans elde edildiği sürece, iteratif şekildekarşılaştırır. Bu arama En Dik Tırmanış Algoritması' na bir örnek olduğu içintüm arama uzayında ancak yerel bir başarı noktası bulacak şekilde gerçekleşir.Tüm arama uzayı, K > 8 sınıflı veri kümeler için 8!' den büyük bir uzaydır.Bu nedenle, performansı arttırmak için Rasgele-Başlangıç Dik Tırmanış Algoritması' nda olduğu gibi, rasgele 10 farklı başlangıç sıralamasıyla FOS algoritmasınıçalıştırırız. Bu sonuçların en iyisi, Rasgele-Başlangıç FOS' un sonucunu belirler.Sunduğumuz ikinci algoritma olan İkili Hata Yaklaşıklaması Algoritması, sıralamaarama problemimizi, sıralamaların sınıf ikililerini kullanarak, optimizasyon problemineçevirir. Problemin çözümünü optimal sıralamayı bulmak için kullanırız.Optimizasyon probleminin parametreleri olarak rasgele sıralamalar üretiriz veçeşitli sayıda rasgele sıralamalarla, sıralama sayısının performansa etkisini gözlemleriz.Algoritmalarımızın sonuçlarını Ripper kural çıkarım algoritmasıyla 13 veri kümesiüzerinde karşılaştırırız. Elde ettiğimiz sonuçlar genel olarak, bulduğumuz sıralamalarınperformans ve karmaşıklıkları açısıdan daha iyi kural kümeleri oluşturduğunugösterir. Ayrıca Rasgele-Başlangıç FOS algoritmasının performansının FOS' taniyi olmasına rağmen, algoritmanın karmaşıklığınn FOS' tan kat kat fazla olduğunugözlemleriz. Son olarak, PEA algoritması için hesapladığımız ortalama kestirimhatası sonuçları, algoritmayı oluşturmamıza neden olan varsayımımızın tutarlılığınıdestekler ve dogru sonuçlarla rasgele sıralama sayısı arasındaki ilişkiyi gösterir.
Özet (Çeviri)
In this thesis, we work on rule induction algorithms, basically Ripper. These algorithms solve a $K>2$ class problem by transforming it into a sequence of $K-1$ two class problems. As a heuristic, these algorithms learn classes in the order of increasing prior probabilities.Although the heuristic works well in practice, there is much room for improvement. We propose two algorithms for that purpose.The first algorithm, namely Forward Ordering Search (FOS) starts with the ordering heuristic provided and searches for better orderings by swapping consecutive classes. For a dataset with $K$ classes, the ordering space will be as large as $K$!. Since FOS is an example of Steepest Ascent Hill Climbing (Gradient Search), starting with the heuristic ordering will only give local maximum in the search space.In order to improve the performance, we use 10 random initial orderings as in Random-Restart (Steepest Ascent) Hill-Climbing. The best performance between 10 random initial orderings is the result of Random-Restart FOS.The second algorithm, namely Pairwise Error Approximation (PEA),transforms the ordering search problem into an optimization problem and uses the solution of the optimization algorithm to extract the optimal ordering.In this algorithm, the number of random orderings to construct the optimization problem is a parameter and we try several values of this parameter to see the effect on the performance.We compare our algorithms with the original Ripper on 13 datasets from UCI repository \cite{asuncion07}. Experimental results show that,our algorithms produce rule sets that are significantly better than those produced by Ripper proper in general and the number of rules and conditions of the produced rule setsare comparable with Ripper proper. Even though the accuracy of Random-Restart FOS is better than FOS,the time complexity of the algorithm is far worse than FOS. The average error estimation results of PEA promote the consistency of our pairwise assumption and show the relationship between the accuracyand the number of random orderings to extract the optimal ordering.
Benzer Tezler
- Yüksek binalarda asansörlerin tasarımı ve değerlendirilmesi için bir uzman sistem
An Expert system for the design and evaluation of the elevators in high buildings
NURAY ÇANKAYA
- Gezgin satıcı problemi
Traveling salesman problem
VOLKAN M. ÖZALP
Yüksek Lisans
Türkçe
1995
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiDOÇ.DR. FÜSUN ÜLENGİN
- Geliştirilmiş SPEA2 ile envanter probleminin çözümü
Inventory optimization with a novel SPEA2 algorithm
ALİ BAYRAKDAR
Yüksek Lisans
Türkçe
2020
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Aydın ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. ILHAM HUSEYINOV
- Hücresel imalat sistemlerinde maliyet ve sinir ağları tabanlı iki evreli bir kümelendirme yaklaşımı
Artificial neurat network x operation costs based twostage GT clusterning procedure
AFFAN NOMAK
Yüksek Lisans
Türkçe
1995
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiDOÇ.DR. BÜLENT DURMUŞOĞLU
- Intelligent search and algorithms for optimal assignment of air force resources in operations
Operasyonlarda hava kuvvetleri kaynaklarının en iyi atanması için akıllı arama ve algoritmalar
EMRE RIZVANOĞLU
Yüksek Lisans
İngilizce
2008
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiElektrik ve Elektronik Mühendisliği Bölümü
PROF. DR. M. KEMAL LEBLEBİCİOĞLU