Tümevaran kavram keşif sistemleri için TF-IDF tabanlı sezgisel bir yöntem
A TF-IDF based heuristic for bottom-up concept discovery systems
Yazar: CEMRE ONUR BAŞ
Danışman: DR. ÖĞR. ÜYESİ ALEV MUTLU
Kocaeli Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2020
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Özet:
Kavram keşif sistemleri, hedef ilişki olarak adlandırılan bir ilişkiyi bu ilişki ile doğrudan veya dolaylı olarak ilişkili arkaplan verisi olarak adlandırlan ilişkiler aracılığıyla tanımlayan modelleri arar. Tümevaran tabanlı kavram keşif sistemlerinde, sadece bir doğru hedef örneği açıklayan doymuş bir alt kuraldan başlanılarak ve yinelemeli olarak bu kuralı genelleştirilerek olabildiğince çok doğru hedef örneği ve olabildiğince az yanlış hedef örneğini açıklayan modeller oluşturulur. Fazla sayıda doğru hedef örneği olan veri kümelerinde, doymuş alt kural oluşturulacak hedef örneği seçmek, elde edilecek hipotezin kapsayıcılığını belirleyeceği için, önem arz etmektedir.

Bu çalışmada, tümevaran kavram keşif sistemlerinde doymuş alt kuralı oluşturmak için tf-idf tabanlı sezgisel bir yöntem önerilmektedir. Önerilen yöntemde veriler, hedef ilişki ve arkaplan verisi örneklerinin düğümleri, kenarların ise hedef ilişki örnekleri ile ilgili arkaplan örneklerini bağladığı bir çizge şeklinde temsil edilmektedir. Her hedef ilişki için biri doğru hedef örnekleri diğeri de yanlış hedef örnekleri modelleyen iki çizge şeklinde temsil edilmiştir. Her çizge örneklerin olası tüm genelleştirmeleri ile zenginleştirilmiştir. Her düğüm için tf-idf hesaplanmıştır. En yüksek tf-idf değerli düğümler birleştirilerek doymuş alt kural
oluşturulmuştur. Elde edilen doymuş alt kural olabildiğince çok doğru hedef örneği ve olabildiğince az yanlış hedef örneği açıklayacak şekilde genelleştirilmiştir.
Önerilen yöntemin başarısı 10-katlı çapraz doğrulama ile mutagenesis isimli biyokimyasal veri kümesi kullanılarak değerlendirilmiştir. Her katta, verilerin %90 eğitim %10'u da test için
kullanılmıştır. Tablo 4.9 ve Tablo 4.12'de sonuçlara ait karmaşıklık matrisi verilmiştir.

Deney sonuçları 0,94 doğruluk, 0,96 hassasiyet ve 0,88 yanlış tahminleme oranına sahiptir. Elde edilen kavram tanımlarına incelendiğinde çok genel kuralların çözüm kümesine eklenmesini engelleyeci tedbirlerin alınmasını gerekliliği görülmüştür.

Abstract:
Concept discovery systems look for patterns that explain a relation called target relation by means of its directly or indirectly related relations, called background knowledge. Bottom-up concept discovery systems start with building a saturated bottom clause and iteratively generalize it to cover as many positive target instances and as few negative instances as possible. In case of large population of positive target instances, choosing a target instance to build a bottom clause for becomes crucial as the bottom clause affects the overall coverage.

In this study, we propose a tf-idf based heuristic for building a bottom clause for bottom-up concept discovery systems. In the proposed method, data is represented as a graph where nodes represent facts and target instances and edges connect facts to target instances. For each target relation, two graphs, one representing the positive target instances and the other representing the negative target instances are built. Each graph is enhanced with all possible generalizations of the facts. For each node, tf-idf weight is calculated. To build a bottom clause, nodes with highest tf-idf weights are conjoined, i.e. logically anded, and the resulting bottom clause is generalized to cover as many positive target instances as possible and as few negative target instances as possible.

To evaluate performance of the proposed method a 10-fold experiment is conducted on a biochemical data set called mutagenesis. At each fold, 90% of the target instances are used to build the model and the remaining 10% of the instances are used to validate the model. In Table 4.9 and Table 4.12, we represent the confusion matrix. At each fold, a number of concept descriptors are obtained describing positive and negative target instances, and in validation step majority voting principle is employed.

The experimental results indicate 0.94 accuracy, 0.96 sensitivity, and 0.88 negative prediction rate. Analysis on the induced concept descriptors suggests to implement mechanism to prevent the inclusion of overly general concept descriptors in the solution set.