Metin madenciliği için iyileştirilmiş bir kümeleme yapısının tasarımı ve uygulaması
Design and application of an improved clustering algorithm for text mining
Yazar: VOLKAN TUNALI
Danışman: PROF. DR. A. YILMAZ ÇAMURCU ; YRD. DOÇ. DR. T. TUGAY BİLGİN
Marmara Üniversitesi / Fen Bilimleri Enstitüsü / Elektronik-Bilgisayar Eğitimi Ana Bilim Dalı
Derece: Doktora, 2011
Konu: Bilgi ve Belge Yönetimi = Information and Records Management ; Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control
Dizin: Kümeleme = Clustering ; Kümeleme analizi = Cluster analysis ; Veri madenciliği = Data mining ; Veri tabanı = Database ; Veri tabanı yönetim sistemi = Database management system

Özet:
Veritabanlarında Bilgi Keşfi olarak da adlandırılan Veri Madenciliği, veritabanları ve veri ambarları gibi çeşitli veri depolarında saklanmakta olan büyük miktardaki verinin işlenerek içindeki geçerli, daha önceden bilinmeyen, potansiyel olarak kullanışlı, yararlı ve değerli olabilecek bilginin çıkartılması sürecidir. Veri madenciliğinin önemli tekniklerinden biri olan veri kümeleme, benzer veri nesnelerinin farklı gruplara sınıflandırılması işlemidir. Bir veri kümesi belirli bir uzaklık ölçütüne göre alt kümelere ayrılırken hedef her bir altkümedeki nesnelerin ortak bir karaktere sahip olmasıdır. Metin Kümeleme ise doküman koleksiyonlarının doküman benzerliklerine bağlı olarak kümelere ayrıştırılmasıdır. Sonuç olarak, bir küme içerisindeki dokümanların genellikle benzer bir konuda olmaları beklenir.Bu tez çalışmasında, metin veri setlerinin kümelenmesi için geliştirilmiş algoritma ve yaklaşımlar ayrıntılı olarak incelenmiş, çok boyutlu ve çok büyük metin veri setlerini kümelenmesinde karşılaşılan sorunlar ve zorluklar irdelenerek bunlar için çözüm yöntemleri getirilmiştir.Tez çalışması dört bölümden oluşmaktadır. İlk bölümde öncelikle veri madenciliği, metin madenciliği ve metin kümeleme kavramları tanımlanarak metin kümelemedeki güncel problemlerden bahsedilmiştir. Daha sonra, tez kapsamında çözüm getirilen problemin tanımı yapılarak tezin amacı ve organizasyonu verilmiştir.Problemin tanımının ardından ikinci bölümde metin madenciliği sistemlerinin genel yapısı, metin kümeleme, metin kümelemede karşılaşılan sorunlar, önişleme teknikleri, doküman temsil yöntemleri, boyut indirgeme teknikleri incelenmiştir. Ayrıca metin kümeleme sürecinin kalitesini ve başarımını doğrudan etkileyen uzaklık ve benzerlik ölçüm yöntemleri ile kümeleme kalitesi ölçüm yöntemleri ele alınmıştır. Bu bölümde son olarak metin kümeleme alanında yapılmış önemli çalışmaların, önerdikleri yaklaşım ve çözüm yöntemleriyle kapsamlı olarak incelendiği geniş bir literatür taramasına yer verilmiştir.Tez kapsamında, çok boyutlu doküman koleksiyonlarının yüksek başarımla ve verimli bir şekilde kümelenebilmesi amacıyla, keskin kümeleme yapan Küresel K-Means algoritmasında değişiklik yapılarak esnek kümeleme yaklaşımlarındaki örtüşen kümeler oluşabilmesi fikri Küresel K-Means algoritmasına uygulanmış, K-Means döngüsü içerisinde dokümanların kümelere benzerliklerine göre belli ölçüde birden çok kümeye dahil olmasına izin verildiği özgün bir algoritma olan Çoklu-Küme Küresel K-Means algoritması geliştirilmiştir. Üçüncü bölümde, geliştirilen bu yeni kümeleme algoritmasının yapısı ayrıntılı olarak açıklanmış ve analiz edilmiştir. Çeşitli metin veri setleri üzerinde gerçekleştirilen deneylerle Çoklu-Küme Küresel K-Means algoritmasının işlemci zamanı kullanımında hissedilir bir fark oluşturmadan kümeleme kalitesinde büyük bir artış sağladığı, temel alınan Küresel K-Means algoritmasının ölçeklenebilirliğini koruyarak büyük doküman koleksiyonları üzerinde uygulanabilir olduğu gösterilmiştir.Dördüncü bölümde, tez çalışması ile geliştirilen algoritmanın genel değerlendirmesi yapılarak sağlanan bilimsel katkılar özetlenmiş, konu ile ilgili çalışacak araştırmacılar için öneriler verilmiştir.

Abstract:
Data Mining, also known as Knowledge Discovery in Databases, is the process of extracting previously unknown, potentially useful, and valuable knowledge from huge amounts of data stored in databases and data warehouses. One of the most important techniques of Data Mining is clustering which assigns a set of objects into groups (called clusters) so that the objects in the same cluster are more similar to each other than to those in other clusters. Text Clustering is the task of grouping documents in a collection into clusters according to similarities among them. It is naturally exptected that documents in a cluster are of the same or similar topic.In this dissertation, algorithms and approaches developed for clustering textual data sets are studied in detail, problems and difficulties encountered in clustering very high dimensional and very large textual datasets are examined, and solutions to those problems are developed.The dissertation consists of four chapters. In the first chapter, data mining, text mining and text clustering concepts are defined and current challenges in text clustering are discussed. In addition, problem description, objectives and organization of the dissertation are presented.After the problem definition, general structure of text mining systems, text clustering, problems of text clustering, preprocessing techniques, document representation models, and dimension reduction methods are further investigated in the second chapter. Moreover, methods that directly affect the performance of text clustering process such as distance and similarity measurements, and clustering quality evaluation techniques are discussed. Finally in this chapter, there is an intensive literature review that presents important work in the field of text clustering with their approaches and solutions to the problem.In this dissertation, the Spherical K-Means algorithm which performs hard clustering is modified so as to apply the idea of generating overlapping clusters of soft clustering approaches for clustering high dimensional document datasets efficiently and with high performance. A new and original algorithm called Multi-Cluster Spherical K-Means which allows documents to be assigned to more than one clusters according to similarities to the clusters in the main K-Means loop is developed. In the third chapter, structure of this new clustering algorithm is explained in detail and thoroughly analyzed. Experimental results on several textual benchmark data sets prove that Multi-Cluster Spherical K-Means algorithm provides significant increase in clustering quality without causing considerable difference in CPU time usage when compared to Spherical K-Means algorithm. It is also shown that Multi-Cluster Spherical K-Means algorithm is feasible for large document collections, still preserving the scalability of Spherical K-Means.The fourth chapter concludes the dissertation with a general review of the algorithm developed and a summary of the scientific contributions. Additionally, some future directions of research and some recommendations for the researchers are presented.