Aflevering
Snelle en bewezen goede seedings voor k-Means
wordt uitgevoerd met Olivier Bachem
Seeding - de taak van het vinden van eerste clustercentra - is essentieel voor het verkrijgen van hoogwaardige clusterings voor k-Means. K-means++ seeding, de state of the art algoritme, schaalt echter niet goed naar enorme gegevenssets omdat het inherent sequentiële gegevens is en k volledige doorvoer van de gegevens vereist. Onlangs werd aangetoond dat Markov-keten Monte Carlo-steekproeven kunnen worden gebruikt om de seedingstap van k-means++ efficiënt te benaderen. Dit resultaat vereist echter veronderstellingen over de gegevens die distributie genereren. We stellen een eenvoudig maar snel seeding-algoritme voor dat weerbaar goede clusterings produceert, zelfs zonder aannames over de gegevens. Onze analyse laat zien dat het algoritme een gunstige afweging mogelijk maakt tussen de kwaliteit van de oplossing en de rekenkosten, waardoor k-means++ seeding kan worden versneld tot verschillende ordes van grootte. We valideren onze theoretische resultaten in uitgebreide experimenten op verschillende echte gegevenssets.
Seeding - de taak van het vinden van eerste clustercentra - is essentieel voor het verkrijgen van hoogwaardige clusterings voor k-Means. K-means++ seeding, de state of the art algoritme, schaalt echter niet goed naar enorme gegevenssets omdat het inherent sequentiële gegevens is en k volledige doorvoer van de gegevens vereist. Onlangs werd aangetoond dat Markov-keten Monte Carlo-steekproeven kunnen worden gebruikt om de seedingstap van k-means++ efficiënt te benaderen. Dit resultaat vereist echter veronderstellingen over de gegevens die distributie genereren. We stellen een eenvoudig maar snel seeding-algoritme voor dat weerbaar goede clusterings produceert, zelfs zonder aannames over de gegevens. Onze analyse laat zien dat het algoritme een gunstige afweging mogelijk maakt tussen de kwaliteit van de oplossing en de rekenkosten, waardoor k-means++ seeding kan worden versneld tot verschillende ordes van grootte. We valideren onze theoretische resultaten in uitgebreide experimenten op verschillende echte gegevenssets.
Wilt u feedback geven? Dien hier een probleem in.