Pairwise partitioning: A nonmetric algorithm for identifying feature-based similarity structures (Q1362283)

An algorithm for finding features is presented. This algorithm is based on the pairwise partitionig of the set of items. The algorithm takes into account only ordering of similarities between items, no metric properties are used. A feature structure \(\left[ A,X,M\right] ,\) is defined to be the set of items, \(A\), the set of features, \(X\), and the feature matrix, \(M=m_{ix}\), where \(m_{i,x}=1\) if item i posses feature \(x\) and \(m_{i,x}=0\) otherwise. Between two items \(i,j\) is defined the similarity \(s_{i,j}\). The algorithm described in this paper creates a feature structure on the basis of the ordering of particular similarities. Features correspond to partitions of the set \(A\) derived by the comparing of similarities. There are presented conditions under which the algorithm correctly identifies features for different type.