Stochastic Approximate Algorithms for Uncertain Constrained K -Means Problem

Jianguang Lu, Juan Tang, Bin Xing and Xianghong Tang
Additional contact information
Jianguang Lu: State Key Laboratory of Public Big Data, Guizhou University, Guiyang 550025, China
Juan Tang: School of Computer Science and Cyber Engineering, Guangzhou University, Guangzhou 510006, China
Bin Xing: Chongqing Innovation Center of Industrial Big-Data Co., Ltd., Chongqing 400707, China
Xianghong Tang: State Key Laboratory of Public Big Data, Guizhou University, Guiyang 550025, China

Mathematics, 2022, vol. 10, issue 1, 1-14

Abstract: The k -means problem has been paid much attention for many applications. In this paper, we define the uncertain constrained k -means problem and propose a ( 1 + ϵ ) -approximate algorithm for the problem. First, a general mathematical model of the uncertain constrained k -means problem is proposed. Second, the random sampling properties of the uncertain constrained k -means problem are studied. This paper mainly studies the gap between the center of random sampling and the real center, which should be controlled within a given range with a large probability, so as to obtain the important sampling properties to solve this kind of problem. Finally, using mathematical induction, we assume that the first j − 1 cluster centers are obtained, so we only need to solve the j -th center. The algorithm has the elapsed time O ( ( 1891 e k ϵ 2 ) 8 k / ϵ n d ) , and outputs a collection of size O ( ( 1891 e k ϵ 2 ) 8 k / ϵ n ) of candidate sets including approximation centers.

Keywords: stochastic approximate algorithms; uncertain constrained k-means; approximation centers (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/1/144/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/1/144/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:1:p:144-:d:717366

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().