Patent ID: 8805841

Claim:
A method for clustering a plurality of data items stored in a computer, the method comprising: calculating, with the computer, a plurality of components comprising kernels based on a distribution that gives similarity between the data items, wherein a non-negative mixture weight is assigned to each of the kernels; preparing a set of active components that are composed of subscripts of the mixture weights; applying the following operations to the set of active components: selecting one kernel, i, from the plurality of kernels; selecting another kernel, i′, that has a positive weight and has a distribution close to the distribution represented by kernel, i; calculating a sum of weights of kernel i and kernel i′; evaluating a first derivative of a negative likelihood function for the mixture weight; if the first derivative is positive at a point where the kernel i has a weight of zero, updating the weight of kernel i′ using the sum of the weights of kernel i and kernel i′, setting the weight of the kernel i to zero, and pruning away component i from the set of the active components; if the first derivative is negative at a point where the kernel i′ has a weight of zero, updating the weight of kernel i using the sum of weights of kernel i and kernel i′, setting the weight of the kernel i′ to zero, and pruning away component i′ from the set of the active components; if the likelihood function is not monotonic, executing uni-dimensional optimization on the mixture weight for the kernel i; and determining whether the mixture weight has converged, and if not converged yet, reapplying the operations to the set of components, and if the mixture weight has converged, clustering the data items based on the mixture weight.