Co-clustering signed 3-partite graphs

Abstract

Gerçek veri, karmaşık ve kendi içirisinde çok ilişkilidir. Bu yüzden, türdeş kü- meleme metotları bu verileri incelemek için yeterli desteği sağlamaz. Bu tarz kümeleme, farklı tür veri nesneleri arasındaki bağlantıları göz ardı eder. Buna dayanarak, gerçek verinin aynı türden olmayan nesneleri aynı kümeye koyabi- lecek yöntemler ile analiz edilmesi gerekir. Bu noktada, ihtiyaca cevap veren yöntem, k-kutuplu kümelemedir. Bu yöntem, farklı türden nesneler arasındaki bağlantıları değerlendirerek karışık kümeleme yapma yeteneğine sahiptir. Bulu- nan kümeler, hem aynı türdeki hem de farklı türdeki nesnelerin aralarındaki iliş- kileri göstermek açısından etkilidir. Örneklemek gerekirse, <kişi,konu,kelime> üçlülerinden oluşan büyük ve karmaşık bir veriden, aynı konu hakkında benzer kelimeleri kullanarak olumlu ifadelerini belirten kişiler bulunabilir. Bu tezde, farklı cinsten nesneler içeren kümeler bularak bu tarz analizler yapılmasını sağ- layacak STriCluster algoritmasını anlatacağım. Bu algoritma 3 farklı tür ve aralarındaki üçlü ilişkilerden oluşan veri üzerinden koşar. Her bir ilişki, her bir türden olmak üzere tam olarak 3 nesne arasındadır ve olumlu ya da olumsuz bir ifade taşır. Bu algoritma, olumlu ifadelerin yoğunlukta olduğu 3-kutuplu kümeler bulur. Bir nesne birden fazla küme tarafından içerilebilir ya da hiçbir kümeye ait olmayabilir. Bu kümeleri bulurken bir takım sezgisel yöntemler kul- lanır. Ek olarak, algoritmamız olumsuz ifade taşıyan ilişkileri ve boşlukları etkili şekilde kontrol altında tutar. Algoritmanın 3-kutuplu kümeleme işlemini tutarlı ve etkili bir şekilde gerçekleştirdiğini, yapay ve gerçek veri üzerinde koşulan test- lerle göstereceğim. Bu testlerden elde edilen ölçümler ve grafikler, algoritmanın etkinliğini destekleyecektir.

Real world data is complex and multi-related among itself. Considering a social media, multiple users can interact with same item such as commenting, liking etc. Data composed of these actions contains many nodes from different types (user, item, sentiment). Therefore, clustering nodes with same type will not be sufficient to analyze it. It will ignore relations between nodes from different types. Such data should be dealt with heterogeneous multi-partite clustering methods. Thus, clustering does not ignore relations among different types. At the end, heterogeneous clusters are found, which are effective to represent inter- partition relations as well as intra-partition ones. To exemplify, from a complex big relations of <user,keyword,issue>, clusters may be extracted such that they contains users who uses similar sentiments to address same issues. I present a new algorithm, called STriCluster, which evaluates heterogeneous data which contains relations of three different types. Each relation is called an hyperedge where each links three nodes from distinct types. Moreover, hyperedges carry a sentiment, which is either positive or negative. The algorithm finds tripartite clusters which express high positivity. Overlap of hyperedges among clusters are not allowed while a node can be part of many clusters. Furthermore, our algorithm handles negative property and sparseness of hyperedges while discov- ering tripartite clusters of hyperedges with positive properties. I will show its effectiveness via experiments and results. Experiments are performed on both synthetic and real-world data.