Dimension reduction for tree-structured data

Ağaç yapılı verilerin istatistiksel analizi, genişleyen uygulama alanlarıyla ilgi çekici araştırma alanlarından biridir. Klasik veri analizinde, veri nesneleri Öklid uzayındaki noktalarken, ağaç yapılı veri analizinde ağaçlardır. Öklid uzayındaki noktaların ağaçlarla değiştirilmesi, veri analizinde ek karmaşıklık getirir ve boyut indirgeme tekniklerinin kullanılmasını gerektirir. Bu çalışmada, her ağacın köklü ve etiketli olduğu ağaç yapılı veriler için boyut indirgeme teknikleri geliştirmeyi hedefliyoruz. İki klasik boyut küçültme tekniğini ele alıyoruz; temel bileşen analizi (PCA) ve çok boyutlu ölçekleme (MDS), ve bunları ağaç yapılı verilere uyarlıyoruz. Ağaç yapılı veriler için PCA üzerine yapılan önceki bir çalışmanın aksine, bu tezde önerilen PCA teknikleri bir varyans ölçüsünü maksimize ediyor. Rastgele oluşturulmuş veriler ve gerçek hayat verileri üzerinde yapılan hesaplama deneyleri, önerilen PCA tekniklerinin mevcut olana göre üstünlüğünü göstermektedir. Literatürde ağaç yapılı veriler üzerinde MDS gerçekleştirip ağaç uzayına yansıtan bir çalışma bulunmamaktadır. Bu doğrultuda, ağaçların kenarlarının boyut olarak kabul edildiği ağaç yapılı veriler için ilk MDS yöntemini öneriyoruz. Önerilen MDS yönteminde amaç, ağaç çiftleri arasındaki Hamming uzaklıklarını orantısal olarak benzer tutmaktır. Bu amaçla, tutulacak kenarları optimal bir şekilde bulan bir karma tamsayılı doğrusal programlama modeli ve kenarların açgözlülükle tek tek seçildiği sezgisel yöntemler önermekteyiz. Hesaplamalı deneyler, önerilen MDS yöntemlerinin, kenarların yalnızca bir kısmı ile yüksek kümeleme doğruluğu elde edildiğinden yararlı bilgileri tutmada başarılı olduğunu göstermektedir. Hesaplamalı deneyleri sistematik bir şekilde yapabilmek için bir rastgele ağaç üreteci algoritması geliştirilmiştir. Bu algoritma, farklı eğiklik ve yoğunluk parametrelerine sahip ağaç kümeleri oluşturabilmektedir. Bu parametreleri sistematik olarak değiştirerek önerilen yöntemlerin güçlü ve zayıf yönlerini anlayabiliriz.