Bilgi sistemlerinde fark fonksiyonu tabanlı özellik seçme yönteminin geliştirilmesi
Development of discernibility function based feature selection method in information systems
Yazar: MEHMET HACIBEYOĞLU
Danışman: PROF. DR. AHMET ARSLAN
Selçuk Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Doktora, 2012
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Özet:
Bilgi sistemlerinde özellik seçmenin amacı şart özelliklerinin orijinal kümesi ile aynı sınıflandırma başarısı sağlayan özelliklerin bir veya birkaç tane minimal alt kümesini bulmaktır. Genellikle bir veri kümesi özelliklerin birden fazla minimal alt kümelerine sahip olabilir ve bunların hepsini bulmak bir NP-hard (belirsiz polinomal-zor) problemdir. Bu yüzden bir veri kümesine ait olan özelliklerin bir veya birkaç minimal alt kümesini bulan sezgisel algoritmalar geliştirilmiştir. Fakat bu algoritmaları kullanmak en iyi çözümü kaçırma riskini de beraberinde getirmektedir. Çünkü özelliklerin bulunan alt kümesi bazen en iyi küme olmayabilir. Bu yüzden, özelliklerin en iyi alt kümesini bulmak istendiğinde bu iş için yegâne olan fark fonksiyonu tabanlı özellik seçme yaklaşımı kullanılır. Fakat maalesef bu yaklaşıma dayanan algoritmalar bellek taşmasından dolayı işini bitirmeden sonlanırlar. Bu algoritmalar için bellek taşmasının sebebi fark fonksiyonun disjunktif normal forma çevrilirken üstel olarak artan hafıza karmaşıklığıdır. Bu yüzden, bu çalışmada, disjunktif normal formun orijinal fark fonksiyonundan değil indirgenmiş fark fonksiyonundan elde edilmesi yöntemi geliştirilmiş ve bu yolla karmaşıklık kendi kareköküne kadar azaltılmıştır. Böylece, iki aşamadan oluşan lojik fonksiyon tabanlı bir özellik seçme yöntemi geliştirilmiştir. Birinci aşamada veri kümesinin doğruluk tablo görüntüsü kullanılarak indirgenmiş fark fonksiyonu oluşturulur, ikinci aşamada ise elde edilen indirgenmiş fark fonksiyonu iteratif olarak bölünerek disjunktif normal forma çevrilir ve böylece işlenmekte olan veri kümesine ait özelliklerin minimal alt kümeleri elde edilir. Geliştirilen özellik seçme yöntemi bu özelliği sayesinde diğer özellik seçme yöntemleri ile işlenemeyen veri kümelerini de başarı ile işlenebilmektedir.

Abstract:
The goal of feature selection in information systems is to find the minimal subset of condition feature set that has the same classification power as the original condition feature set. Usually one dataset may have a lot of minimal subset of attributes and finding all of them is known as an NP-hard problem. Therefore, when only one minimal subset of attribute is required, some heuristic for finding only one or a small number of possible minimal subset of attributes is used. But in this case there is a risk that the best minimal subset of attributes would be overlooked. When the best solution of a feature selection task is required, the discernibility function-based approach, generating all minimal subset of attributes, is used. But unfortunately discernibility function-based feature selection programs fail due to overflow the computer?s memory. This is the intractable space complexity of the conversion of a discernibility function to disjunctive normal form. Thus, in this study, we developed a method that obtained disjunctive normal form from minimized discernibility function which the value computational complexity is reduced the square root of the original conversion. Based on these facts, we developed a two-step logic function?based feature selection method. The first stage, developed method derives minimized discernibility function from the truth table image of a dataset. The second stage finds all minimal subset of attributes of a dataset by iteratively partitioning the discernibility function so that the part to be converted to disjunctive normal form. Due to this property, it can process most of datasets that can not be processed by other discernibility function based programs.