Improvements to the relational fuzzy c-means clustering algorithm

• Improved relational fuzzy c-means for clustering relational data D is proposed.
• The matrix D   is transformed to Euclidean matrix D˜ using different transformations.
• Quality of D˜ is judged by the ability of RFCM to discover the apparent clusters.
• The subdominant ultrametric transformation produces much better partitions of D˜.
• β-spread minimizes the distortion between D   and D˜, but produces worst clusterings.

Relational fuzzy c-means (RFCM) is an algorithm for clustering objects represented in a pairwise dissimilarity values in a dissimilarity data matrix D. RFCM is dual to the fuzzy c-means (FCM) object data algorithm when D is a Euclidean matrix. When D is not Euclidean, RFCM can fail to execute if it encounters negative relational distances. To overcome this problem we can Euclideanize the relation D prior to clustering. There are different ways to Euclideanize D such as the β-spread transformation. In this article we compare five methods for Euclideanizing D   to D˜. The quality of D˜ for our purpose is judged by the ability of RFCM to discover the apparent cluster structure of the objects underlying the data matrix D  . The subdominant ultrametric transformation is a clear winner, producing much better partitions of D˜ than the other four methods. This leads to a new algorithm which we call the improved RFCM (iRFCM).