检索结果-内蒙古大学图书馆

Second-order cone programming models for the unitary weighted Weber problem and for the minimum sum of the squares clustering problem

引用

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH 2025年第2期32卷 961-972页

作者： Linhares, Marcella Braga de Assis Pinto, Renan Vicente Maculan, Nelson Negreiros, Marcos Univ Fed Rio De Janeiro PESC COPPE Rio de Janeiro Brazil Fed Rural Univ Rio Janeiro Dept Math Rio De Janeiro Brazil Univ Estadual Ceara Sci Comp Lab Fortaleza CE Brazil

In this work, new mixed integer nonlinear optimization models are proposed for two clustering problems: the unitary weighted Weber problem and the minimum sum of squares clustering. The proposed formulations are convex quadratic models with linear and second-order cone constraints that can be efficiently solved by interior point algorithms. Their continuous relaxation is convex and differentiable. The numerical experiments show the proposed models are more efficient than some classical models for these problems known in the literature.

关键词： combinatorial optimization nonlinear programming clustering problem second-order cone programming

来源：评论

学校读者我要写书评

暂无评论

clustering problem with 0-1 Quadratic Programming

Clustering Problem with 0-1 Quadratic Programming

引用

Mediterranean Conference on Information and Communication Technologies (MedCT)

作者： Haddouch, Khalid El Allaoui, Ahmad Messaoudi, Abdelhafid El Moutaouakil, Karim Dadi, El Wardani Univ Mohammed First Natl Sch Appl Sci Al Hoceima Oujda Morocco

ISBN: (纸本)9783319302980;9783319302966

The most unsupervised methods of classification suffer from several performance problems, especially the class number, the initialization start points and the solution quality. In this work, we propose a new approach to estimate the class number and to select a set of centers that represent, fiddly, a set of given data. Our key idea consists to express the clustering problem as a bivalent quadratic optimization problem with linear constraints. The proposed model is based on three criterions: the number of centers, the density data and the dispersion of the chosen centers. To validate our proposed approach, we use a genetic algorithm to solve the mathematical model. Experimental results applied on IRIS Data, show that the proposed solution selects an adequate centers and leads to a reasonable class number.

关键词： Bivalent quadratic optimization problem clustering problem Data IRIS Genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

Kernel intuitionistic fuzzy c-means and state transition algorithm for clustering problem

引用

SOFT COMPUTING 2020年第20期24卷 15507-15518页

作者： Zhou, Xiaojun Zhang, Rundong Wang, Xiangyue Huang, Tingwen Yang, Chunhua Cent South Univ Sch Automat Changsha 410083 Peoples R China Peng Cheng Lab Changsha 51800 Peoples R China Texas A&M Univ Qatar POB 23874 Doha Qatar

clustering problems widely exist in machine learning, pattern recognition, image analysis and information sciences, etc. Although many clustering algorithms have been proposed, it is unpractical to find a clustering algorithm suitable for all types of datasets. Fuzzy c-means (FCM) is one of the most frequently-used fuzzy clustering algorithm for the reason that it is efficient, straightforward, and easy to implement. However, the traditional FCM taking Euclidean distance as similarity measurement can not distinguish the intersection between two clusters. Therefore, kernel function has been taken as similarity measurement to solve this issue. As a comprehensive partition criterion, intuitionistic fuzzy set which consider both membership degree and non-membership degree has been used to replace traditional fuzzy set to describe the natural attributes of objective phenomena more delicately. Thus, Kernel intuitionistic fuzzy c-means (KIFCM) has been proposed in this paper to settle clustering problem. Considering FCM is easily getting trapped in local optima due to its high sensitivity to initial centroid. State Transition Algorithm (STA) has been adopted in this study to obtain the initial centroid to enhance its stability. The proposed STA-KIFCM compared with some other clustering algorithms are implemented using five benchmark datasets. Experimental results not only show that the proposed method is efficient and can reveal encouraging results, but also indicate that the proposed method can achieve high accuracy.

关键词： clustering problem State transition algorithm Kernel function Intuitionistic fuzzy set Fuzzy c-means

来源：评论

学校读者我要写书评

暂无评论

Annealed chaotic neural network with nonlinear self-feedback and its application to clustering problem

引用

PATTERN RECOGNITION 2001年第5期34卷 1093-1104页

作者： Lin, JS Natl Chin Yi Inst Technol Dept Elect Engn Taichung Taiwan

Chaos is a revolutionary concept, which brings a novel strategy of science for researchers. In this paper, a chaotic neural network is proposed and the simulated annealing strategy also embedded to construct an annealed chaotic neural network (ACNN) and apply to the clustering problem. In addition to retain the characteristics of the conventional neural units, the ACNN displays a rich range of behavior reminiscent of that observed in neurons. Unlike the conventional neural network, the ACNN has rich range and flexible dynamics, so that it can be expected to have higher ability of searching for globally optimal or near-optimum results, However, the chaotic neural network does not stay in the global solution due to the chaotic dynamical mechanism being nut clear. A chaotic mechanism with annealing strategy is introduced into the Hopfield network to construct a ACNN for expecting a better opportunity of converging to the optimal solution in this paper. In experimental results unlike the fuzzy clustering methods getting local minima solutions, the ACNN method can always obtain the near-global optimal results. From the classification of real multispectral images, the ACNN can obtain suitable results. (C) 2001 Pattern Recognition Society. Published by Elsevier Science Ltd. All rights reserved.

关键词： chaotic neural network Hopfield network self-feedback clustering problem annealing

来源：评论

学校读者我要写书评

暂无评论

Computational experience on four algorithms for the hard clustering problem

引用

PATTERN RECOGNITION LETTERS 1996年第3期17卷 295-308页

作者： AlSultan, KS Khan, MM KING FAHD UNIV PETR & MINERALS DATA PROC CTR DHAHRAN 31261 SAUDI ARABIA

In this paper, we consider the problem of clustering m objects in c clusters. The objects are represented by points in n-dimensional Euclidean space, and the objective is to classify these m points into c clusters such that the distance between points within a cluster and its center is minimized. The problem is a difficult optimization problem due to the fact that: it posseses many local minima. Several algorithms have been developed to solve this problem which include the k-means algorithm, the simulated annealing algorithm, the tabu search algorithm, and the genetic algorithm. Zn this paper, we study the four algorithms and compare their computational performance for the clustering problem. We test these algorithms on several clustering problems from the literature as well as several random problems and we report on our computational experience.

关键词： clustering problem k-means algorithm simulated annealing tabu search genetic algorithm computational comparison

来源：评论

学校读者我要写书评

暂无评论

A global optimization RLT-based approach for solving the fuzzy clustering problem

引用

JOURNAL OF GLOBAL OPTIMIZATION 2005年第4期33卷 597-615页

作者： Sherali, HD Desai, J Virginia Polytech Inst & State Univ Grado Dept Ind & Syst Engn 0118 Blacksburg VA 24061 USA

The field of cluster analysis is primarily concerned with the partitioning of data points into different clusters so as to optimize a certain criterion. Rapid advances in technology have made it possible to address clustering problems via optimization theory. In this paper, we present a global optimization algorithm to solve the fuzzy clustering problem, where each data point is to be assigned to (possibly) several clusters, with a membership grade assigned to each data point that reflects the likelihood of the data point belonging to that cluster. The fuzzy clustering problem is formulated as a nonlinear program, for which a tight linear programming relaxation is constructed via the Reformulation-Linearization Technique (RLT) in concert with additional valid inequalities. This construct is embedded within a specialized branch-and-bound (B&B) algorithm to solve the problem to global optimality. Computational experience is reported using several standard data sets from the literature as well as using synthetically generated larger problem instances. The results validate the robustness of the proposed algorithmic procedure and exhibit its dominance over the popular fuzzy c-means algorithmic technique and the commercial global optimizer BARON.

关键词： clustering problem fuzzy clustering fuzzy c-means algorithm global optimization Reformulation-Linearization Technique

来源：评论

学校读者我要写书评

暂无评论

A global optimization RLT-based approach for solving the hard clustering problem

引用

JOURNAL OF GLOBAL OPTIMIZATION 2005年第2期32卷 281-306页

作者： Sherali, HD Desai, J Virginia Polytech Inst & State Univ Grado Dept Ind & Syst Engn 0118 Blacksburg VA 24061 USA

The field of cluster analysis is primarily concerned with the sorting of data points into different clusters so as to optimize a certain criterion. Rapid advances in technology have made it possible to address clustering problems via optimization theory. In this paper, we present a global optimization algorithm to solve the hard clustering problem, where each data point is to be assigned to exactly one cluster. The hard clustering problem is formulated as a nonlinear program, for which a tight linear programming relaxation is constructed via the Reformulation-Linearization Technique (RLT) in concert with additional valid inequalities that serve to defeat the inherent symmetry in the problem. This construct is embedded within a specialized branch-and-bound algorithm to solve the problem to global optimality. Pertinent implementation issues that can enhance the efficiency of the branch-and-bound algorithm are also discussed. Computational experience is reported using several standard data sets found in the literature as well as using synthetically generated larger problem instances. The results validate the robustness of the proposed algorithmic procedure and exhibit its dominance over the popular k-means clustering technique. Finally, a heuristic procedure to obtain a good quality solution at a relative ease of computational effort is also described.

关键词： clustering problem global optimization hard clustering k-means algorithm Reformulation-Linearization Technique

来源：评论

学校读者我要写书评

暂无评论

An Improved Approximation Algorithm for the Capacitated Correlation clustering problem

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2024年第6期35卷 757-774页

作者： Ji, Sai Cheng, Yukun Tan, Jingjing Zhao, Zhongrui Hebei Univ Technol Inst Math Tianjin 300401 Peoples R China Suzhou Univ Sci & Technol Sch Business Suzhou 215009 Peoples R China Weifang Univ Sch Math & Informat Sci Weifang 261061 Peoples R China Beijing Univ Technol Dept Operat Res & Informat Engn Beijing 100124 Peoples R China

Correlation clustering problem (CorCP) is a classical clustering problem, which clusters data based on the similarity of data set, and has many applications in interaction networks, cross-lingual link detection, and communication networks, etc. In this paper, we study a practical generalization of the CorCP, called the capacitated correlation clustering problem (the capacitated CorCP), by constructing a labeled complete graph. On this labeled complete graph, each vertex represents a piece of data. If two pieces of data are similar, then the edge between the corresponding vertices is marked by a positive label +. Otherwise, this edge is marked by a negative label -. The objective of the capacitated CorCP is to group some similar data sets into one cluster as far as possible, while satisfying the cluster capacity constraint. To achieve this objective, we shall partition the vertex set of the labeled complete graph into several clusters, each cluster's size subjecting to an upper bound, so as to minimize the number of disagreements. Here the number of disagreements is defined as the total number of the edges with positive labels between clusters and the edges with negative labels within clusters. Different with the previous algorithm in [18], which subjects to the constraint on the cluster size by a penalty measure, we design an algorithm for the capacitated CorCP to directly output a feasible solution by iteratively constructing clusters based on a preset threshold. Through carefully setting the threshold and sophisticatedly analyzing, our algorithm is proved to have an improved approximation ratio of 5.37. In addition, we also conduct a series of numerical experiments to demonstrate the effectiveness of our algorithm.

关键词： clustering problem capacitated correlation clustering approximation algorithms LP-rounding

来源：评论

学校读者我要写书评

暂无评论

A TABU SEARCH APPROACH TO THE clustering problem

引用

PATTERN RECOGNITION 1995年第9期28卷 1443-1451页

作者： ALSULTAN, KS Department of Systems Engineering King Fahd University of Petroleum and Minerals Dhahran 31261 Saudi Arabia

In this paper we consider the problem of clustering m objects into c clusters. The objects are represented by points in an n-dimensional Euclidean space, and the objective is to classify these m points into c clusters such that the distance between points within a cluster and its center (which is to be found) is minimized. The problem is a nonconvex program that has many local minima. It has been studied by many researchers and the most well-known algorithm for solving it is the k-means algorithm. In this paper, we develop a new algorithm for solving this problem based on a tabu search technique. Preliminary computational experience on the developed algorithm are encouraging and compare favorably with both the k-means and the simulated annealing algorithms.

关键词： clustering problem TABU SEARCH K-MEANS ALGORITHM SIMULATED ANNEALING NONCONVEX PROGRAMMING GLOBAL OPTIMUM

来源：评论

学校读者我要写书评

暂无评论

Qualitative properties of the minimum sum-of-squares clustering problem

引用

OPTIMIZATION 2020年第9期69卷 2131-2154页

作者： Cuong Tran Hung Yao, Jen-Chih Yen Nguyen Dong Hanoi Univ Ind Fac Informat Technol Dept Comp Sci Hanoi Vietnam China Med Univ Ctr Gen Educ Taichung Taiwan Vietnam Acad Sci & Technol Inst Math Hanoi Vietnam

Fundamental qualitative properties of the minimum sum-of-squares clustering problem are established in this paper. We prove that the problem always has a global solution and, under a mild condition, the global solution set is finite. Moreover, the components of each global solution can be computed by an explicit formula. Based on a new concept of non-trivial local solution, we get necessary conditions for a system of centroids to be such a local solution. Interestingly, these necessary conditions are also sufficient ones. Finally, it is proved that the optimal value function is locally Lipschitz, the global solution map is locally upper Lipschitz, and the local solution map has the Aubin property, provided that the original data points are distinct. The obtained complete characterizations of the non-trivial local solutions allow one to understand better the performance of not only thek-means algorithm, but also of other solution methods for the problem in question.

关键词： clustering problem local and global solutions attraction sets solution existence stability properties

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：