IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v10y2022i1p144-d717366.html
   My bibliography  Save this article

Stochastic Approximate Algorithms for Uncertain Constrained K -Means Problem

Author

Listed:
  • Jianguang Lu

    (State Key Laboratory of Public Big Data, Guizhou University, Guiyang 550025, China
    Chongqing Innovation Center of Industrial Big-Data Co., Ltd., Chongqing 400707, China)

  • Juan Tang

    (School of Computer Science and Cyber Engineering, Guangzhou University, Guangzhou 510006, China
    Institute of Computing Science and Technology, Guangzhou University, Guangzhou 510006, China)

  • Bin Xing

    (Chongqing Innovation Center of Industrial Big-Data Co., Ltd., Chongqing 400707, China
    National Engineering Laboratory for Industrial Big-Data Application Technology, Chongqing 400707, China)

  • Xianghong Tang

    (State Key Laboratory of Public Big Data, Guizhou University, Guiyang 550025, China)

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.

Suggested Citation

  • Jianguang Lu & Juan Tang & Bin Xing & Xianghong Tang, 2022. "Stochastic Approximate Algorithms for Uncertain Constrained K -Means Problem," Mathematics, MDPI, vol. 10(1), pages 1-14, January.
    • Handle: RePEc:gam:jmathe:v:10:y:2022:i:1:p:144-:d:717366
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/10/1/144/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/10/1/144/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Valls, Aida & Batet, Montserrat & López, Eva M., 2009. "Using expert's rules as background knowledge in the ClusDM methodology," European Journal of Operational Research, Elsevier, vol. 195(3), pages 864-875, June.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Meyer, Patrick & Olteanu, Alexandru-Liviu, 2013. "Formalizing and solving the problem of clustering in MCDA," European Journal of Operational Research, Elsevier, vol. 227(3), pages 494-502.
    2. Galo, Nadya Regina & Calache, Lucas Daniel Del Rosso & Carpinetti, Luiz Cesar Ribeiro, 2018. "A group decision approach for supplier categorization based on hesitant fuzzy and ELECTRE TRI," International Journal of Production Economics, Elsevier, vol. 202(C), pages 182-196.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:10:y:2022:i:1:p:144-:d:717366. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.