Hierarchical and Non-Hierarchical Medoid Clustering Using Asymmetric Similarity Measures

Medoid clustering frequently gives better interpretation than the K-means clustering, since a unique object is the representative element of a cluster. Moreover the method of medoids can be applied to non-metric cases such as weighted graphs that arise in analyzing SNS (Social Networking Service) networks. A fundamental problem in clustering is that asymmetric similarity measures are difficult to handle, while relations are asymmetric in SNS user groups. In this paper we consider K-medoids clustering for asymmetric graphs in which a cluster has two different centers with outgoing directions and incoming directions. Moreover two-stage agglomerative hierarchical clustering is studied in which the first stage is a one-pass K-medoids and the second stage uses an agglomerative algorithm. These methods are applied to artificial and real data sets.