Vi studerar ämnet dimensionalitetsreduktion för k-medelsklustring. Dimensionalitetsminskningen omfattar en förening av två tillvägagångssätt: 1) urval av funktioner och 2) utvinning av särdrag. En funktionsbaserad algoritm för k-means klustring väljer en liten delmängd av inmatningsfunktionerna och tillämpar sedan k-means klustring på de valda funktionerna. En funktionsextraktion-baserad algoritm för k-means klusterbildning konstruerar en liten uppsättning av nya artificiella funktioner och sedan tillämpar k-means kluster på de konstruerade funktionerna. Trots betydelsen av k-medel klustering samt rikedomen av heuristiska metoder som tar itu med det, är bevisligen korrekt funktion urvalsmetoder för k-medel kluster inte kända. Å andra sidan är två bevisligen korrekta utvinningsmetoder för k-medel kluster kända i litteraturen; en är baserad på slumpmässiga projektioner och den andra är baserad på singular value decomposition (SVD). Detta dokument gör ytterligare framsteg mot en bättre förståelse av dimensionalitetsminskning för k-medelskluster. Nämligen presenterar vi den första bevisligen korrekta funktionen urvalsmetod för k-medel kluster och dessutom presenterar vi två funktion utvinningsmetoder. Den första funktionen extraktion metod är baserad på slumpmässiga prognoser och det förbättrar på de befintliga resultaten i form av tid komplexitet och antal funktioner som behövs för att extraheras. Den andra funktionen extraktion metod är baserad på snabb ungefärlig SVD factorizations och det förbättrar också på de befintliga resultaten i termer av tid komplexitet. De föreslagna algoritmerna är randomiserade och ger konstanta approximationsgarantier med avseende på det optimala k-medelvärdet objektivt värde. Termer-Clustering, dimensionalitetsreduktion, randomiserade algoritmer. Nu, målet för dimensionalitet minskning för k-medel klustering är att konstruera point på P = {p 1,p 2,. ................... } R r 0018-9448.....................................................................................................
Boutsidis m.fl. implementerade två olika dimensionella reduktionsmetoder för klustring av K-medel: den första baserad på RP och den andra baserad på SVD REF.
Randomized Dimensionality Reduction for $k$ -Means Clustering
{'venue': 'IEEE Transactions on Information Theory', 'journal': 'IEEE Transactions on Information Theory', 'mag_field_of_study': ['Computer Science', 'Mathematics']}