• Login
    View Item 
    •   BEARdocs Home
    • Graduate School
    • Electronic Theses and Dissertations
    • View Item
    •   BEARdocs Home
    • Graduate School
    • Electronic Theses and Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Faster k-means clustering.

    Thumbnail
    View/Open
    Thesis (1.020Mb)
    Copyright availability form (795.3Kb)
    Access rights
    Worldwide access
    Date
    2013-09-24
    Author
    Drake, Jonathan, 1989-
    Metadata
    Show full item record
    Abstract
    The popular k-means algorithm is used to discover clusters in vector data automatically. We present three accelerated algorithms that compute exactly the same clusters much faster than the standard method. First, we redesign Hamerly’s algorithm to use k heaps to avoid checking distance bounds for all n points, with little empirical gain. Second, we use an adaptive number of distance bounds to avoid redundant calculations (Drake and Hamerly 2012). Experiments show the superior performance of adaptive k-means in medium dimension (20 ≤ d ≤ 200) on uniform random data. Finally, we reformulate the triangle inequality to constrain the search space for a point’s nearest center to an annular region centered at the origin. For uniform random data, annulus k-means is competitive with or much faster than other algorithms in low dimension (d < 20), and it outperforms other algorithms on five of six naturally-clustered, real-world datasets tested (d ≤ 74).
    URI
    http://hdl.handle.net/2104/8826
    Department
    Computer Science.
    Collections
    • Electronic Theses and Dissertations
    • Theses/Dissertations - Computer Science

    Copyright © Baylor® University All rights reserved. Legal Disclosures.
    Baylor University Waco, Texas 76798 1-800-BAYLOR-U
    Baylor University Libraries | One Bear Place #97148 | Waco, TX 76798-7148 | 254.710.2112 | Contact: libraryquestions@baylor.edu
    If you find any errors in content, please contact librarywebmaster@baylor.edu
    DSpace software copyright © 2002-2016  DuraSpace
    Contact Us | Send Feedback
    TDL
    Theme by 
    Atmire NV
     

     

    Browse

    All of DSpaceCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    Login

    Statistics

    View Usage Statistics

    Copyright © Baylor® University All rights reserved. Legal Disclosures.
    Baylor University Waco, Texas 76798 1-800-BAYLOR-U
    Baylor University Libraries | One Bear Place #97148 | Waco, TX 76798-7148 | 254.710.2112 | Contact: libraryquestions@baylor.edu
    If you find any errors in content, please contact librarywebmaster@baylor.edu
    DSpace software copyright © 2002-2016  DuraSpace
    Contact Us | Send Feedback
    TDL
    Theme by 
    Atmire NV