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

An Approximation algorithm Based on seeding algorithm for Fuzzy k-Means Problem with Penalties

Journal of the Operations Research Society of China 2024年第2期12卷 387-409页

作者： Wen-Zhao Liu Min Li School of Mathematics and Statistics Shandong Normal UniversityJinan 250014ShandongChina

As a classic NP-hard problem in machine learning and computational geometry,the k-means problem aims to partition the given dataset into k clusters according to the minimal squared Euclidean *** from k-means problem and most of its variants,fuzzy k-means problem belongs to the soft clustering problem,where each given data point has relationship to every center *** to fuzzy k-means problem,fuzzy k-means problem with penalties allows that some data points need not be clustered instead of being paid *** this paper,we propose an O(αk In k)-approximation algorithm based on seeding algorithm for fuzzy k-means problem with penalties,whereαinvolves the ratio of the maximal penalty value to the minimal ***,we implement numerical experiments to show the effectiveness of our algorithm.

关键词： Approximation algorithm seeding algorithm Fuzzy k-means problem with penalties

来源：评论

学校读者我要写书评

暂无评论

The seeding algorithm for k-means problem with penalties

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2020年第1期39卷 15-32页

作者： Li, Min Xu, Dachuan Yue, Jun Zhang, Dongmei Zhang, Peng Shandong Normal Univ Sch Math & Stat Jinan 250014 Peoples R China Beijing Univ Technol Coll Appl Sci Dept Operat Res & Sci Comp Beijing 100124 Peoples R China Shandong Jianzhu Univ Sch Comp Sci & Technol Jinan 250101 Peoples R China Shandong Univ Sch Software Jinan 250101 Peoples R China

The k-means problem is a classic NP-hard problem in machine learning and computational geometry. And its goal is to separate the given set into k clusters according to the minimal squared distance. The k-means problem with penalties, as one generalization of k-means problem, allows that some point need not be clustered instead of being paid some penalty. In this paper, we study the k-means problem with penalties by using the seeding algorithm. We propose that the accuracy only involves the ratio of the maximal penalty value to the minimal one. When the penalty is uniform, the approximation factor reduces to the same one for the k-means problem. Moreover, our result generalizes the k-means++ for k-means problem to the penalty version. Numerical experiments show that our seeding algorithm is more effective than the one without using seeding.

关键词： Approximation algorithm k-means Penalty seeding algorithm

来源：评论

学校读者我要写书评

暂无评论

The Parallel seeding algorithm for k-Means Problem with Penalties

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2020年第4期37卷

作者： Li, Min Xu, Dachuan Yue, Jun Zhang, Dongmei Shandong Normal Univ Sch Math & Stat Jinan 250014 Peoples R China Beijing Univ Technol Dept Operat Res & Sci Comp Beijing 100124 Peoples R China Shandong Jianzhu Univ Sch Comp Sci & Technol Jinan 250101 Peoples R China

As a classic NP-hard problem in machine learning and computational geometry, the k-means problem aims to partition a data point set into k clusters such that the sum of the squared distance from each point to its nearest center is minimized. The k-means problem with penalties, denoted by k-MPWP, generalizing the k-means problem, allows that some points can be paid some penalties instead of being clustered. In this paper, we study the seeding algorithm of k-MPWP and propose a parallel seeding algorithm for k-MPWP along with the corresponding theoretical analysis.

关键词： Approximation algorithm k-means penalty seeding algorithm parallel

来源：评论

学校读者我要写书评

暂无评论

THE APPROXIMATION algorithm BASED ON seeding METHOD FOR FUNCTIONAL k-MEANS PROBLEM

引用

JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION 2022年第1期18卷 411-426页

作者： Li, Min Wang, Yishui Xu, Dachuan Zhang, Dongmei Shandong Normal Univ Sch Math & Stat Jinan 250014 Peoples R China Chinese Acad Sci Shenzhen Inst Adv Technol 1068 Xueyuan Ave Shenzhen 518055 Peoples R China Beijing Univ Technol Dept Operat Res & Informat Engn Beijing 100124 Peoples R China Shandong Jianzhu Univ Sch Comp Sci & Technol Jinan 250101 Peoples R China

Different from the classical k-means problem, the functional k means problem involves a kind of dynamic data, which is generated by continuous processes. In this paper, we mainly design an O(ln k)-approximation algorithm based on the seeding method for functional k-means problem. Moreover, the numerical experiment presented shows that this algorithm is more efficient than the functional k-means clustering algorithm.

关键词： functional k-means k-means seeding algorithm approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

The bi-criteria seeding algorithms for two variants of k-means problem

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第3期44卷 1693-1704页

作者： Li, Min Shandong Normal Univ Sch Math & Stat Jinan 250014 Peoples R China

The k-means problem is very classic and important in computer science and machine learning, so there are many variants presented depending on different backgrounds, such as the k-means problem with penalties, the spherical k-means clustering, and so on. Since the k-means problem is NP-hard, the research of its approximation algorithm is very hot. In this paper, we apply a bi-criteria seeding algorithm to both k-means problem with penalties and spherical k-means problem, and improve (upon) the performance guarantees given by the k-means++ algorithm for these two problems.

关键词： Approximation algorithm k-means problem with penalties Spherical k-means clustering seeding algorithm

来源：评论

学校读者我要写书评

暂无评论

The seeding algorithms for spherical k-means clustering

引用

JOURNAL OF GLOBAL OPTIMIZATION 2020年第4期76卷 695-708页

作者： Li, Min Xu, Dachuan Zhang, Dongmei Zou, Juan Shandong Normal Univ Sch Math & Stat Jinan 250014 Peoples R China Beijing Univ Technol Beijing Inst Sci & Engn Comp Beijing 100124 Peoples R China Shandong Jianzhu Univ Sch Comp Sci & Technol Jinan 250101 Peoples R China Qufu Normal Univ Sch Math Sci Qufu 273165 Shandong Peoples R China

In order to cluster the textual data with high dimension in modern data analysis, the spherical k-means clustering is presented. It aims to partition the given points with unit length into k sets so as to minimize the within-cluster sum of cosine dissimilarity. In this paper, we mainly study seeding algorithms for spherical k-means clustering, for its special case (with separable sets), as well as for its generalized problem (alpha spherical k-means clustering). About the spherical k-means clustering with separable sets, an approximate algorithm with a constant factor is presented. Moreover, it can be generalized to the alpha-spherical separable k-means clustering. By slickly constructing a useful function, we also show that the famous seeding algorithms such as k-means++ and k-means|| for k-means problem can be applied directly to solve the alpha-spherical k-means clustering. Except for theoretical analysis, the numerical experiment is also included.

关键词： Approximation algorithm Spherical k-means clustering k-means problem Separable set seeding algorithm

来源：评论

学校读者我要写书评

暂无评论

Improved local search algorithms for Bregman k-means and its variants

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第4期44卷 2533-2550页

作者： Tian, Xiaoyun Xu, Dachuan Guo, Longkun Wu, Dan Beijing Univ Technol Dept Operat Res & Informat Engn Beijing 100124 Peoples R China Beijing Univ Technol Beijing Inst Sci & Engn Comp Beijing 100124 Peoples R China Qilu Univ Technol Shandong Acad Sci Sch Comp Sci & Technol Jinan 250353 Peoples R China Henan Univ Sci & Technol Sch Math & Stat Luoyang 471023 Peoples R China

In this paper, we consider the Bregman k-means problem (BKM) which is a variant of the classical k-means problem. For an n-point set S and k = 0, and obtain an approximation ratio of O(log(2) k) in expectation.

In this paper, we consider the Bregman k-means problem (BKM) which is a variant of the classical k-means problem. For an n-point set S and k <= n with respect to mu-similar Bregman divergence, the BKM problem aims first to find a center subset C subset of S with vertical bar C vertical bar= k and then separate S into k clusters according to C, such that the sum of mu-similarBregman divergence from each point in S to its nearest center is minimized. We propose a mu-similar BregMeans++ algorithm by employing the local search scheme, and prove that the algorithm deserves a constant approximation guarantee. Moreover, we extend our algorithm to solve a variant of BKM called noisy mu-similar Bregman k-means++ (noisy mu-BKM++) which is BKM in the noisy scenario. For the same instance and purpose as BKM, we consider the case of sampling a point with an imprecise probability by a factor between 1- epsilon(1) and 1+ epsilon(2) for epsilon(1) is an element of epsilon[0, 1) and epsilon(2) >= 0, and obtain an approximation ratio of O(log(2) k) in expectation.

关键词： seeding algorithm Local search k-means m-similar Bregman divergences

来源：评论

学校读者我要写书评

暂无评论

The spherical k-means plus plus algorithm via local search scheme

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第4期44卷 2375-2394页

作者： Tian, Xiaoyun Xu, Dachuan Du, Donglei Gai, Ling Beijing Univ Technol Dept Operat Res & Informat Engn Beijing 100124 Peoples R China Univ New Brunswick Fac Management Fredericton NB E3B 9Y2 Canada Donghua Univ Glorious Sun Sch Business & Management Shanghai 200051 Peoples R China

The spherical k-means problem (SKMP) is an important variant of the k-means clustering problem (KMP). In this paper, we consider the SKMP, which aims to divide the n points in a given data point set S into k clusters so as to minimize the total sum of the cosine dissimilarity measure from each data point to their respective closest cluster center. Our main contribution is to design an expected constant approximation algorithm for the SKMP by integrating the seeding algorithm for the KMP and the local search technique. By utilizing the structure of the clusters, we further obtain an improved LocalSearch++ algorithm involving epsilon k local search steps.

关键词： Spherical k-means Local search seeding algorithm Approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Approximation algorithms for fuzzy C-means problem based on seeding method

引用

THEORETICAL COMPUTER SCIENCE 2021年 885卷 146-158页

作者： Liu, Qian Liu, Jianxin Li, Min Zhou, Yang Shandong Normal Univ Sch Math & Stat Jinan Peoples R China

As a kind of important soft clustering model, the fuzzy C-means method is widely applied in many fields. In this method, instead of the strict distributive ability in the classical k-means method, all the sample points are endowed with degrees of membership to each center to depict the fuzzy clustering. In this paper, we show that the fuzzy C-means++ algorithm, which introduces the k-means++ algorithm as a seeding strategy, gives a solution for which the approximation guarantee is O(k(2) ln k). A novel seeding algorithm is then designed based on the contribution of the fuzzy potential function, which improves the approximation ratio to O(k lnk). Preliminary numerical experiments are proposed to support the theoretical results of this paper. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Fuzzy C-means problem seeding algorithm Approximation algorithm Approximation ratio

来源：评论

学校读者我要写书评

暂无评论

Reinforcement-Learning-Based Dynamic Opinion Maximization Framework in Signed Social Networks

引用

IEEE TRANSACTIONS ON COGNITIVE AND DEVELOPMENTAL SYSTEMS 2023年第1期15卷 54-64页

作者： He, Qiang Lv, Yingjie Wang, Xingwei Li, Jianhua Huang, Min Ma, Lianbo Cai, Yuliang Northeastern Univ Coll Med & Biol Informat Engn Shenyang 110169 Peoples R China Northeastern Univ Coll Comp Sci & Engn State Key Lab Synthet Automat Proc Ind Shenyang 110169 Peoples R China Northeastern Univ Coll Comp Sci & Engn State Key Lab Synthet Automat Proc Ind Shenyang 110819 Peoples R China Northeastern Univ Coll Software Engn Shenyang 110619 Peoples R China Northeastern Univ Coll Informat Sci & Engn Shenyang 110819 Peoples R China

opinion maximization (DOM) is a significant optimization issue, whose target is to select some nodes in the network and prorogate the opinions of network nodes, and produce the optimum node opinions. Until now, the node opinions of related researches are unchanged and seldom focus on social relationships. In the real scenario, the dynamic process of network nodes over time and user preference have existed. Therefore, this article proposes the Q-learning-based DOM (QDOM) framework in signed social networks to solve the OM problem, which is made up of two phases: 1) the activated dynamic opinion model and 2) the Q-learning-based seeding process. We propose the activated dynamic opinion model based on stateless Q-learning theory to derive the opinion propagation process. Moreover, we design the Q-learning-based seeding algorithm to obtain the seed nodes. The experimental results on the four signed social network data sets demonstrate that the proposed framework outperforms the state-of-the-art approaches on positive opinions, the ratio of positive opinions, and activated nodes.

关键词： Heuristic algorithms Social networking (online) Q-learning Integrated circuit modeling Greedy algorithms Adaptation models Optimization Activated dynamic opinion model seeding algorithm social trust

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：