Topological data analysis and clustering algorithms in machine learning
Topolojik veri analizi ve makine öğreniminde kümeleme algoritmaları
- Tez No: 835078
- Danışmanlar: PROF. DR. ATABEY KAYGUN
- Tez Türü: Doktora
- Konular: Matematik, İstatistik, Mathematics, Statistics
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2023
- Dil: İngilizce
- Üniversite: İstanbul Teknik Üniversitesi
- Enstitü: Lisansüstü Eğitim Enstitüsü
- Ana Bilim Dalı: Matematik Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Matematik Mühendisliği Bilim Dalı
- Sayfa Sayısı: 107
Özet
Bu tez bir istatistiksel veri bilimi ve makine öğrenmesi tezidir. Tez, özel olarak, istatistiksel veri biliminin yeni bir alt disiplini olan topolojik veri bilimi (TVB) alanındadır. TVB istatistik, veri bilimi, genel ve cebirsel topoloji gibi birbirinden farklı ve uzak alanları sağlam bir teorik matematik tabanında birleştirip büyük hacimli ve yüksek boyutlu veriler konusunda yeni bakış açıları geliştiren yeni bir veri bilimi disiplini olup son yıllarda geniş kullanım alanı bulmuştur. Bu tezde, sadece verilen sonlu örneklemler üzerinde tanımlanan komplekslerden gelen homolojik bilgi kullanılarak tüm derecelerdeki kalıcı homoloji sınıfları üzerinde kofenetik metrik olarak adlandırılan yeni bir Arşimedyen olmayan metrik (diğer bir deyişle ultra-metrik) tanımlıyoruz. Ardından, farklı veri kümeleri üzerinde yapılan sayısal deneylere dayanarak, kofenetik metriğimiz ile sıfırıncı kalıcı homolojiden gelen topolojik bilginin, farklı metrikler kullanan farklı hiyerarşik kümeleme algoritmaları tarafından sağlanan bilgi ile tutarlı olduğunu istatistiksel olarak doğruluyoruz. Ayrıca, kofenetik metrikle elde ettiğimiz kümelerin, diğer metriklerle elde edilen kümelere kıyasla rekabetçi silüet skorları ve Rand endeksleri verdiğini gözlemliyoruz. Manifoldlar gibi sürekli geometrik nesnelerin simpleksel kompleksler gibi sonlu ve ayrık nesneler üzerinden incelenmesi topoloji tarihi kadar eskidir. Özellikle bir manifoldun homotopi tipi o manifold için verilmiş açık toplarla verilmiş bir örtüsünden okunabilir. Biz bu tezde, bu fikri bir manifolddan alınmış sonlu bir örneklem üzerinde tanımlanacak açık toplarla tanımlanmış reel sayılar üzerinde filtrelenmiş simpleksel komplekslere uygulayacağız. Pozitif reel sayılar kümesi üzerinde filtrelenmiş bir simpleksel kompleks hakkındaki homolojik bilgi genellikle ilişkili Betti sayılarının gelişimini gösteren bir barkodla sunulur. Bununla birlikte, filtrelenmiş bir simpleksel kompleksin homoloji sınıflarıyla ilişkili harika bir karmaşık kombinatorik vardır ve bunları indeks poseti üzerinde saymaktan daha fazlası yapılabilir. Bu tezde, bu kombinatoryal bilginin filtrelenmiş bir matroid veya daha da iyisi köklü ağaçlar tarafından kodlanabileceğini gösteriyoruz. Ayrıca bu köklü ağaçların kobordizmalar (cobordisms) olarak gerçekleştirilebileceğini de gösteriyoruz. Bu tezin konusu Bölüm 1'de sunulmuş olup, ve bu bölümde ayrıca topolojik veri analizine (TVA) de kısa bir giriş yapılmaktadır. Bölüm 2'de, sonraki bölümlerde ihtiyaç duyacağımız veri analizinin temel kavramları olan topolojik ve metrik uzayları özetlenmektedir. Bölüm 3'te, kümeleme tekniklerinin matematiksel temellerine daha derinlemesine gireceğiz. Kümeleme algoritmaları, özellikle hiyerarşik kümeleme algoritmaları bu tezde kilit bir rol oynamaktadır. Çeşitli kümeleme stratejilerinin karşılaştırmaları da bu tezde önemli roller üstlenmektedir. Bu nedenle, kümeleme algoritmalarında kullanılan sayısal ölçütleri de araştırıyoruz. Bu tür kümeleme stratejilerini ve karşılaştırmalarını da aynı bölümde değerlendireceğiz. Ayrıca, tamamlayıcı bir örnek olarak, Türkiye'deki şehirlerin aralarındaki mesafeleri ele alarak ortaya çıkan kümeleri karşılaştırdık. Bu tezde yaptığımız TVA hesaplamalarında ağırlıklı olarak simpleksel ve zincir kompleksleri, ve bunların homolojileri kullanılmaktadır. Tüm örneklerde, kalıcı homolojisini hesaplamak için önce filtrelenmiş bir simpleksel kompleksin homolojisini hesaplıyoruz. Birincil hesaplama prosedürü, bir nokta bulutunu filtrelenmiş bir simpleksel kompleks haline getirerek başlar ve ardından ortaya çıkan filtrelenmiş diferansiyel dereceli kompleksin homolojisini hesaplamaktır. Bölüm 4 ve 5, simpleksel kompleksler, diferansiyel dereceli kompleksler ve homolojiler hakkında gerekli tüm arka plan bilgilerini sağlamaktadır. Ayrıca, soyut simpleksel komplekslerin bir koleksiyonu için homoloji sınıflarının hesaplanmasına ilişkin eksiksiz çalışılmış örnekler sunuyoruz. Nokta bulutunun topolojik özelliklerini tam olarak yakalamak için temel zorluk, simpleksler teknolojisi için en uygun yakınlık parametresini bulmaktır.Kalıcı homoloji (Persistent homology) tam olarak bu sorunla başa çıkmak için geliştirilmiştir. Yakınlık parametresi değiştikçe, sağlanan verilerin her bir topolojik özelliğinin ne kadar süre dayandığını takip eder. Bu, barkodlar olarak temsil edilen aralıkların çoklu kümelerini üretir. Bu kavramları Bölüm 6'da ele alıyoruz. Bölüm 7, filtrelenmiş simpleksel ve zincir kompleksler için titiz bir teorik temel geliştirmeye adanmıştır. Filtrelenmiş kompleksler için böyle bir temel geliştirmenin yanı sıra, özellikle bir matroid'deki devreler (circuits) tarafından etiketlenen dendrogramları kullanarak, filtrelenmiş komplekslerin homolojileri için filtrelenmiş matroidler şeklinde heyecan verici bir kombinatoryal temsil keşfettik. Bölüm 8'de, bu tezin literatüre ana katkısı olan homoloji sınıfları üzerinde homolojik kofenetik uzaklık adı verilen yeni bir Arşimedyen olmayan metrik tanımladık. Bölüm 9'de, kendileri de yüksek boyutlu küreler olan delinmiş kürelerin kobordizmalarını kullanarak filtrelenmiş bir kompleksten gelen homolojik bilginin başka bir sunumunu geliştirmekle ilgileniyoruz. Bölüm 10'da, sayısal deneylerimizde kofenetik mesafeyi nasıl kullandığımıza dair ayrıntılı bir açıklama sunuyoruz. İlk deneyde, $\mathbb{R}^2$ içine gömülü küçük bir sentetik veri kümesi üzerinde standart sıfırıncı kalıcı homoloji gösterimlerini (barkodlar), kofenetik uzaklıktan türettiğimiz dendrogramı ve hiyerarşik kümeleme algoritmasından gelen dendrogramı Öklid metriği ile karşılaştırdık. İkinci deneyde, küçük bir Türkiye şehri örneğinin coğrafi koordinatlarını inceledik. İlk deneyde olduğu gibi aynı istatistiksel karşılaştırma metodolojisini izleyerek, çalışmamızın geçerliliğini değerlendirmek için sıfırıncı homoloji üzerinde kofenetik metrikler tarafından üretilen dendrogramları ve çeşitli mesafe ölçümleri kullanan hiyerarşik kümeleme algoritmaları tarafından üretilen dendrogramları karşılaştırdık. Üçüncü ve son deneyde, hiyerarşik kümeleme algoritmalarını çeşitli veri kümelerine (Türkiye şehirleri, Iris, Kanser Coimbra ve iki farklı sentetik veri kümeleri) kofenetik metriğimiz de dahil olmak üzere farklı metriklerle uyguladık ve kümeleme sonuçlarını istatistiksel olarak analiz ettik. Son olarak, Bölüm 11'de, elde ettiğimiz sonuçları, yaklaşımımızın yüksek hesaplama gücü ve yüksek bellek gereksinimi gibi kısıtlamalarını özetliyor ve analiz ediyoruz. Ayrıca bu bölümde, bu tezi genişletmek için, gerçek dünya veri kümeleriyle uygun uygulamalar tasarlamak, kobordizmaları görselleştirmek veya kategorik veri kümesi üzerinde filtrelenmiş kombinatoryal simpleksel kompleksler geliştirmek gibi izlenebilecek potansiyel gelecek araştırma yönlerini tartışıyoruz.
Özet (Çeviri)
In this dissertation, we define a new non-Archimedean metric (a.k.a. an ultra-metric) called cophenetic metric on persistent homology classes of all degrees using only homological information. Then, based on numerical experiments on different datasets, we statistically verify that the topological information coming from the zeroth persistent homology with our cophenetic metric is consistent with the information provided by different hierarchical clustering algorithms using different metrics. We also observe that the clusters we obtained via the cophenetic metric do yield competitive silhouette scores and the Rand indices in comparison with clusters obtained from other metrics. The homological information about a filtered simplicial complex over the poset of positive real numbers is often presented by a barcode which depicts the evolution of the associated Betti numbers. However, there is wonderfully complex combinatorics associated with the homology classes of a filtered complex, and one can do more than just count them over the index poset. In this thesis, we show that this combinatorial information can be encoded by a filtered matroid, or even better, by rooted forests. We also show that these rooted forests can be realized as cobordisms. The subject of this thesis is presented in Chapter 1, in which we also provide a survey of the literature and a brief introduction to topological data analysis (TDA). In Chapter 2, we summarize the fundamental concepts from topological and metric spaces that we will need in subsequent chapters. In Chapter 3, we will go more deeply into the mathematical foundations of clustering techniques. Clustering algorithms, especially hierarchical clustering algorithms, play a key role in this dissertation. Comparisons of various clustering strategies also play important roles in this thesis. For this reason, we also survey numerical metrics to assess such clustering strategies in the same chapter. We also work out a complete example on a collection of Turkish cities and the distances between them, and compare the resulting clusters. The TDA calculations we make in this thesis heavily use simplicial and chain complexes, and their homologies. In all examples, we first calculate the homology of a filtered simplicial complexes in order to calculate its persistent homology. The primary computation procedure begins by distilling a point cloud into a filtered simplicial complex, followed by calculating the homology of the resulting filtered differential graded complex. Chapters 4 and 5 provide all the necessary background information on simplicial complexes, differential graded complexes, and homologies. We also present complete worked-out examples of calculating homology classes for a collection of simple simplicial complexes. To capture the exact topological features of the point cloud, the main challenge is to find an optimal proximity parameter for the simplicial technology. Persistent homology is developed precisely to deal with this issue. It keeps track of how long each topological feature of the supplied data endures as the proximity parameter varies. It produces multisets of intervals represented as barcodes. We cover these concepts in Chapter 6. Chapter 7 is devoted to developing a rigorous theoretical foundation for filtered simplicial and chain complexes. Along with developing such a foundation for filtered complexes, we also discovered an exciting combinatorial representation for homologies of filtered complexes in the form of filtered matroids, especially by employing dendrograms labeled by circuits in a matroid. In Chapter 8, we defined a new non-archimedean metric called homological cophenetic distance on homology classes which is the main contribution of this thesis to literature. In Chapter 9 we are concerned with developing another presentation of the homological information coming from a filtered complex using cobordisms of punctured spheres, which are themselves punctured higher dimensional spheres. In Chapter 10, we give a detailed account of how we used the cophenetic distance in our numerical experiments. In the first experiment, we compared the standard zeroth persistent homology representations (barcodes), the dendrogram we derived from the cophenetic distance, and the dendrogram coming from the hierarchical clustering algorithm with the Euclidean metric on a small synthetic dataset embedded in $\mathbb{R}^2$. In the second experiment, we studied the geographic coordinates of a small sample of Turkish cities. By following the same statistical comparison methodology as in the first experiment, we compare the dendrograms produced by cophenetic metrics on the zeroth homology and the dendrograms produced by hierarchical clustering algorithms using a variety of distance measurements in order to assess the validity of our study. In the third and last experiment, we applied the hierarchical clustering algorithms to various datasets (the dataset of Turkish cities, the Iris dataset, the Cancer Coimbra dataset, and two synthetic datasets) with different metrics including our cophenetic metric, and we statistically analyzed the clustering results. Finally, in Chapter11, we summarize and analyze the results we obtain, and the constraints of our approach such as need for high computational power and high memory requirements. We also discuss potential future research directions one can follow to extend this thesis such as designing suitable applications with real-world datasets, visualizing cobordisms, or developing filtered combinatorial simplicial complexes on a categorical dataset.
Benzer Tezler
- Hierarchical structures in data science
Veri bilimi'nde hiyerarşik yapılar
HALİME BEYZA KÜÇÜKDAĞ
Yüksek Lisans
İngilizce
2019
MatematikGalatasaray ÜniversitesiMatematik Ana Bilim Dalı
DR. ÖĞR. ÜYESİ AYŞEGÜL ULUS
- Etkin sorgu önerileri için kullanıcı sorgularının görev tabanlı yönetilmesi
Task based management of user queries for effective query suggestions
NURULLAH ATEŞ
Doktora
Türkçe
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. YUSUF YASLAN
- Sosyal ağların çizge entropi kullanılarak analiz edilmesi ve uygulamaları
Analysis and applications of social networks with graph entropy
İHSAN TUĞAL
Doktora
Türkçe
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİnönü ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. ALİ KARCI
- Identification of drug targets towards prostate cancer
Prostat kanserine yönelik ilaç hedeflerinin tanımlanması
ELİF ESVAP
Yüksek Lisans
İngilizce
2018
BiyoteknolojiBoğaziçi ÜniversitesiKimya Mühendisliği Ana Bilim Dalı
PROF. DR. ŞEFİKA KUTLU ÜLGEN
DOÇ. DR. ELİF ÖZKIRIMLI ÖLMEZ