Variable neighborhood search for clustering and data mining

数据挖掘在运筹学和计算机科学中是一个相对较新的领域。聚类是最流行的数据挖掘技术之一。它的目的是解决以下非常普遍的问题：给定一个描述某些对象的数据集，找出它是否具有某种结构，如果是，则确定其中的组。更准确地说，聚类分析的目标是找到给定数据集的子集，称为簇，这些子集既是同质的，又是分开的。同质性意味着同一簇中的对象应该彼此相似；分离意味着不同簇中的对象应该彼此不同。由于同质性和分离性可以在许多方面实现精确，因此有许多具体的聚类问题，甚至有更精确或启发式的方法来解决它们。许多标准要么强调同质性，要么强调分离。如果簇间平方和等于最小化簇之间的平方和，则平方和准则不是最小化和的情况。因此，最小平方和聚类是聚类分析的核心。在这个方案中，我们计划开发启发式方法来解决大规模的最小平方和聚类问题。此外，由于我们开发的方法同时提供了目标函数的上下界解，因此我们的方法将具有保证的性能。这种方法基于原始-对偶可变邻域搜索(PD-VNS)元启发式(或构建启发式的框架)。我们首先用VNS解决原始问题，得到高质量的解，然后找出相应的(不可行的)对偶解。然后在度量不可行性的对偶空间中对非线性函数进行约化。这个问题也是由VNS解决的。如果问题不是很大，我们尝试用分枝定界法来弥合积分间隙，以得到精确的解。

Data mining is relatively new area in Operations research and Computer sciences. Clustering is one of the most popular data mining techniques. It aims at solving the following very general problem: given a data set describing some objects, find if it has some structure, and if so, determine groups within it. More precisely, cluster analysis aims at finding subsets of the given data sets, called clusters, which are both homogenous and well separated. Homogeneity means that objects in the same cluster should resemble one another; separation means that objects indifferent clusters should differ one from the other. As homogeneity and separation can be made precise in many ways, there are many specific clustering problems, and even more exact or heuristic methods to solve them. Many criteria stress either homogeneity or separation. This is not the case for the sum-of-squares criterion as minimizing the sum if inter-cluster sum-of-squares is tantamount to minimizing the between clusters sum-of-squares. Therefore minimum sum-of-squares clustering is central to cluster analysis.Within this proposal we are planning to develop heuristic method for solving large-scale minimum sum-of-squares clustering problem. In addition, our method will have guaranteed performance since we develop method that in the same time provide solutions with both upper and lower bounds on the objective function. Such an approach is based on Primal-dual variable neighborhood search (PD VNS)metaheuristic (or framework for building heuristics). We first solve primal problem to get solution of good quality by using VNS and then we find corresponding (unfeasible) dual solution. Then we reduce nonlinear function in the dual space that measures unfeasibility. This problem is also solved by VNS. If the problem is not very large, we try to close the integrality gap by using branch-and-bound method in order to get exact solution.