Bi-clustering Using Non-parametric Bayesian Methods
Summary:
Multiway clustering is a popular analysis method due to its several potential applications. Various techniques have been developed to cluster different entities of a data matrix simultaneously by taking relational entries into account. Many of those techniques assume that the number of clusters to be discovered is known prior to the clustering operation. However, in real-world problems we have limited knowledge about the number of clusters before discovering them. Nonparametric methods, on the other hand, perform biclustering and learn the number of clusters concurrently. In this thesis, we introduce two nonparametric Bayesian biclustering methods that are applicable on two-way data. In the first method we model the rows and columns of the two-way data using Dirichlet Process Mixture Models and cluster them simultaneously, whereas in the second one we cluster the entities separately after applying spectral matrix decomposition on the data. We apply the biclustering algorithms on four different datasets; a simulated dataset created by a generative Gaussian model, a dataset of animals and their attributes, a cross-national trade and diplomacy dataset with five different relational networks, and a biological dataset from a microarray study of lung cancer. Since there are few real world data annotated with ground truth biclusters, we generally utilize link prediction in order to evaluate biclustering performances. We randomly remove data entries and predict them based on the fact that the entries in the same bicluster are similar to each other. First biclustering method results in higher accuracy since it makes use of all relational information in the data while the spectral method reduces dimensionality of the data prior to the clustering operation. On the other hand, computational complexity of spectral method is far less due to the reduction in the data entries to process.
Özet:
Çok indis üzerinden veri öbekleme, olası birçok uygulaması dolayısıyla popüler bir araştırma alanıdır. Bir data matrisinin farklı indislerini aynı anda öbekleyebilmek için farklı yöntemler geliştirilmiştir. Bu yöntemlerin çoğu, ortaya çıkarılacak öbek sayısının öbekleme işleminden önce bilindiğini varsaymaktadır. Ancak gerçek hayat problemlerinde, öbekler ortaya çıkarılmadan önce öbek sayısı hakkında eldeki bilgi sınırlıdır. Buna karşılık parametrik olmayan yöntemler ise iki indis üzerinden öbekleme işlemi ile eş zamanlı olarak öbek sayısını öğrenmektedir. Bu tezde, iki adet parametrik olmayan iki indis üzerinden Bayesci öbekleme yöntemi tanıtılmaktadır. İlk yöntemde iki indisli verinin satır ve sütunları Dirichlet Süreci Karışım Modelleri ile modellenip eş zamanlı olarak öbeklenirken, ikinci yöntemde ise satır ve sütunlar veri üzerinde İzgesel Matris Ayrıştırması uygulandıktan sonra ayrı ayrı öbeklenmektedir. İki indis üzerinden öbekleme yöntemleri farklı veri grupları üzerinde test edilmektedir. Bu veri grupları, üretici bir Gauss modeli ile oluşturulmuş simule bir veri grubu, çeşitli hayvanlar ve özelliklerini içeren bir veri grubu, ülkeler arası ticaret ve diplomasi ilişkilerini gösteren ve beş farklı ağdan oluşan bir veri grubu, ve akciğer kanseri üzerinde bir mikro cihaz çalışmasına ait biyolojik veri grubu olmak üzere dört tanedir. İki indisli verilerde gerçek öbekler genelde tanımsız olduğundan, algoritmaların öbekleme performanslarını değerlendirmek için bağlantı tahmini kullanılmaktadır. Veri noktalarının bir kısmı rastsal olarak seçilip kaldırılmakta, ve bu noktalar aynı öbekteki noktaların benzer olması gerektiği bilgisine dayanılarak tahmin edilmektedir. Tanıttığımız yöntemlerin ilkinde bilgi kaybı olmaksızın verinin tümü kullanıldığından ilk yöntem daha hassas sonuç vermektedir. Buna karşılık ikinci yöntemde veri noktası sayısı önsel olarak oldukça azaltıldığından ikinci yöntemin zaman ve bellek karmaşıklığı çok daha düşüktür.