模糊聚类的一次定位算法

Algorithm of once location for fuzzy clustering

相似矩阵的传递闭包是模糊聚类的重要方法,根据在求相似矩阵的等价矩阵中取大取小运算的特征,得出相似矩阵的上三角形中的任一元素值在其等价矩阵中出现的位置,由计算过程中,当前比它大或等于的元素所在位置决定。在此基础上,将上三角形中的所有非零元素按降序排序,从第二个元素开始,按顺序计算每个元素可传递到的位置,得所求的等价矩阵。这种通过一次计算可得等价阵的最终结果的算法称为一次定位法。该算法的时间复杂度小于等于n平方级,空间复杂度为n平方级。

To study the transitive closure of similarity matrix in fuzzy clustering, the algorithm of once location for solving the transitive closure of similarity matrix is proposed. By analyzing the characteristics of operation max（min） in calculating equivalence matrix, it is obtained that the location of the biggest element in the superior triangle of similarity matrix is invariable in its equivalence matrix, and the location of any element is determined by the element that is bigger. On this basis, the algorithm of once location is given, which reduces the time T（ n ） for calculating the equivalence matrix. For any given n samples, the time complexity T（ n ） of the algorithm satisfies T（ n ） ≤O（ n^2） , and space complexity is O （n^2）. Experimental results show that this algorithm is reasonable and effective.