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.