Method for estimating similarity function coefficients from object classification data

摘要

Given a set of objects {A, B, C, ...}, each described by a set of attribute values, and given a classification of these objects into categories, a similarity function accounts well for this classification only a small number of objects are not correctly classified. This is obtained when coefficients are found for the similarity function which result in an error rate that is considered to be an acceptable level. A method for estimating a coefficient for a similarity function comprises the steps of: (a) selecting an initial value w = wo as the initial coefficient of a similarity function SIMw(a,b); (b) selecting an initial value k = ko defining the number of most-similar objects to use when testing the classification of an object; (c) computing similarity measures by using the current estimate of SIMw for an object S to neighboring objects Gi in the given category and for the object S to neighboring objects Bj outside the given category, and forming a training set of respective data 〈S, SIMw(S,Gi), SIMw(S,Bj)〉 for members in the category and those outside the category; (d) reducing the training set by eliminating all data except for the k-nearest (most similar) objects of Gi and Bj; (e) estimating new coefficients for the similarity function by adjusting w to minimize an error rate measured in terms of the extent to which neighboring objects Bj outside the category have higher similarity measures than neighboring objects Gi within the category; and (f) repeating steps (c), (d), and (e) until the error rate is reduced below a predetermined low level.