Abstract-Vi presenterar en ny metod för klusterering baserad på kompression. Metoden använder inte ämnesspecifika egenskaper eller bakgrundskunskap, och fungerar enligt följande: För det första bestämmer vi ett parameterfritt, universellt, likhetsavstånd, det normaliserade kompressionsavståndet eller NCD, beräknat från längden på komprimerade datafiler (singly och i parvis konkatenering). För det andra tillämpar vi en hierarkisk klustermetod. NCD är inte begränsad till ett specifikt tillämpningsområde och fungerar över tillämpningsområdets gränser. En teoretisk prekursor, det normaliserade informationsavståndet, som samutvecklats av en av författarna, är bevisligen optimal. Optimaliteten kommer dock till priset av att använda den icke-kompletterbara begreppet Kolmogorov komplexitet. Vi föreslår axioms för att fånga den verkliga miljön, och visa att NCD approximerar optimalitet. För att utvinna en hierarki av kluster från avståndsmatrisen bestämmer vi ett dendrogram (permanent träd) med en ny kvartettmetod och en snabb heuristisk för att genomföra den. Metoden är implementerad och tillgänglig som offentlig programvara, och är robust under val av olika kompressorer. För att underbygga våra anspråk på universalitet och robusthet rapporterar vi bevis på framgångsrik tillämpning inom så skilda områden som genomik, virologi, språk, litteratur, musik, handskrivna siffror, astronomi och kombinationer av objekt från helt olika domäner, med hjälp av statistik, ordbok och blockera sorteringskompressorer. I genomik lade vi fram nya bevis för stora frågor i mammas evolution, baserade på helmitochondrial genomic analys: Eutherian orders och Marsupionta hypotes mot Theria hypotesen. Index Termer-Heterogen dataanalys, hierarkisk oövervakad klusterbildning, Kolmogorov komplexitet, normaliserad kompression avstånd, parameter-fri databrytning, kvartet träd metod, universell olikhet avstånd.
En annan viktig milstolpe är REF, som föreslår en klusterteknik baserad på kompression och ger en rigorös analytisk ram baserad på begreppet Kolmogorov komplexitet.
Clustering by compression
{'venue': 'IEEE Transactions on Information Theory', 'journal': 'IEEE Transactions on Information Theory', 'mag_field_of_study': ['Computer Science', 'Physics', 'Biology']}