I en tid av allt större datamängder har forskare inom många olika discipliner vänt sig till klustering som ett verktyg för dataanalys och prospektering. Befintliga klustermetoder är dock vanligtvis beroende av flera icke-triviala antaganden om datastrukturen. Här omformulerar vi klusterproblemet ur ett informationsteoretiskt perspektiv som undviker många av dessa antaganden. I synnerhet, vår formulering undanröjer behovet av att definiera en kluster "prototyp", inte kräver en a priori likhet metrisk, är invariant till förändringar i representationen av data, och naturligt fångar icke-linjära relationer. Vi tillämpar detta tillvägagångssätt på olika domäner och finner att det konsekvent producerar kluster som är mer sammanhängande än de som extraheras av befintliga algoritmer. Slutligen ger vår strategi ett sätt att samla ihop varandra på grundval av kollektiva begrepp om likhet snarare än de traditionella parvisa åtgärderna. Tanken att komplexa data kan grupperas i kluster eller kategorier är central för vår förståelse av världen, och denna struktur uppstår i många olika sammanhang (t.ex., Bild. 1 )............................................................................................................... I populärkulturen grupperar vi filmer eller böcker i genrer, i affärer grupperar vi företag i sektorer inom ekonomin, i biologin grupperar vi cellernas molekylära komponenter i funktionella enheter eller vägar, och så vidare. Vanligtvis dessa grupperingar är först konstruerade för hand med hjälp av specifika men kvalitativa kunskaper; t.ex., Dell och Apple hör till samma grupp eftersom de båda gör datorer. Utmaningen med klusterbildning är att fråga om dessa kvalitativa grupperingar automatiskt kan härledas från objektiva, kvantitativa uppgifter. Är vår intuition om ekonomiska sektorer t.ex. härledd från aktiekursernas dynamik? Kan cellens funktionella enheter härledas från genuttrycksmönster under olika förhållanden (1,2)? Litteraturen om klusterbildning, även i samband med genuttryck, är omfattande (3). Vårt mål här är inte att föreslå ännu en klusteralgoritm, utan snarare att fokusera på frågor om utformningen av klusterproblemet. Vi leds till ett tillvägagångssätt, grundat i informationsteori, som bör ha bred tillämplighet. Vår intuition om klusterbildning börjar med den uppenbara uppfattningen att liknande element bör falla inom samma kluster medan olikartade element inte bör. Men klustering uppnår också datakompression-istället för att identifiera varje datapunkt individuellt, kan vi identifiera punkter av kluster som de hör till, slutar med en enklare och kortare beskrivning av data. Rate-snedvridning teori (4,5) formulerar exakt avvägningen mellan dessa två överväganden, söker uppdrag till kluster så att antalet bitar som används för att beskriva data minimeras medan den genomsnittliga likheten mellan varje datapunkt och dess kluster representativa (eller prototyp) maximeras. En välkänd begränsning av denna formulering (som i de flesta metoder för klusterbildning) är att man måste specificera likhetsmåttet i förväg, och ganska ofta görs detta val godtyckligt. En annan fråga som får mindre uppmärksamhet är att begreppet representativ eller "klusterprototyp" är en naturlig del av denna formulering, även om det inte alltid är uppenbart hur detta begrepp ska definieras. Vår strategi ger rimliga svar på båda dessa problem, med ytterligare intressanta konsekvenser. Teoretisk formering. Föreställ dig att det finns N-element (i = 1, 2, · · · ·, N ) och N c-kluster (C = 1, 2, · · ·, N c ) och att vi har tilldelat element i till kluster C enligt vissa probabilistiska regler, P (C på), som fungerar som variabler i vår analys. 1 Om vi når in i ett kluster och drar ut element på måfå, vill vi att dessa element ska vara så lika varandra som möjligt. Likhet definieras vanligen bland par av element (t.ex. närhet av punkter i vissa metriska utrymme), men som noterats nedan kan vi också konstruera mer kollektiva mått på likhet mellan r > 2 element; kanske överraskande kommer vi att se att detta mer allmänna fall kan analyseras utan extra kostnad. Lämnar åt sidan för tillfället frågan om hur man mäter likhet, låt oss anta att beräkna likheten mellan r element i 1, i 2, · · ·, i r returnerar en likhet åtgärd s (i 1, i 2, · · ·, i r ). 1 Konventionellt skiljer man "hårda" kluster, där varje element tilldelas exakt ett kluster, och "mjuka" kluster där uppdragen är probabilistiska, beskrivs av en villkorlig fördelning P (C på engelska); vi betraktar här den mer allmänna mjuka kluster med hård klusterbildning som uppstår som ett begränsande fall. Den genomsnittliga likheten mellan element som väljs ut ur ett enda kluster är där P (i på C) är sannolikheten att hitta elementet i i kluster C. Denna genomsnittliga likhet motsvarar ett scenario där man väljer elementen {i 1, · · · ·, i r } slumpmässigt ut ur ett kluster C, oberoende av varandra; andra formuleringar kan också vara rimliga. Från Bayes' regel har vi P (i-C) = P (C-i)P (i)/P (C), där P (C) är den totala sannolikheten för att hitta något element i kluster C, P (C) = i P (C-i)P (i). I många fall elementen i förekommer med lika stor sannolikhet så att P (i) = 1/N. Vi överväger vidare detta för enkelhetens skull, även om det inte är nödvändigt. Intuitionen om klungans "godhet" uttrycks genom den genomsnittliga likheten över alla klungor, För det speciella fallet av parvis "hårda" klungor vi ob- där  på C- är storleken av kluster C. Denna enklare form visades i (6) för att uppfylla grundläggande invarians och robusthet kriterier. Uppgiften är då att välja de tilldelningsregler P (C-i) som maximerar s, medan, som i hastighetsförvrängning teori, samtidigt komprimera vår beskrivning av data så mycket som möjligt. För att genomföra denna intuition vi maximerar s samtidigt begränsa informationen som bärs av kluster identiteter (5), Således vår matematiska formulering av det intuitiva kluster problemet är att maximera den funktionella där Lagrange multiplikator T upprätthåller begränsningen på I(C; i). Lägg märke till att F, liksom i andra formuleringar av klusterproblemet, liknar den fria energin inom statistisk mekanik, där temperaturen T anger avvägningen mellan energi och entropiliknande termer. Denna formulering är intimt relaterad till konventionella hastighetsförvrängning teori. Vid hastighetsförvrängning får man ett fast antal bitar med vilka man kan beskriva datan, och målet är att använda dessa bitar för att minimera förvrängningen mellan dataelementen och vissa representanter för dessa data. I praktiken anger bitarna medlemskap i ett kluster, och representanterna är prototypiska eller genomsnittliga mönster i varje kluster. Här ser vi att vi kan formulera en liknande kompromiss utan behov av att införa begreppet representativ eller genomsnittlig; i stället mäter vi direkt likheten mellan element inom varje kluster; dessutom kan vi överväga kollektiva snarare än parvisa mått på likhet. En mer rigorös behandling som beskriver förhållandet mellan Eq. (4) och den konventionella funktionen för räntesnedvridning kommer att presenteras på annat håll. Optimal lösning. I allmänhet är det inte möjligt att hitta en explicit lösning för P (C.i) som maximerar F. Men om vi antar att F är differential med avseende på variablerna P (C.i), likställa derivatan till noll avkastning efter några algebra en uppsättning implicita, självkonsistenta ekvationer som någon optimal lösning måste lyda: där Z(i; T ) är en normalisering konstant och s(C; i) är den förväntade likheten mellan i och r − 1 medlemmar av kluster C, härledning av dessa ekvationer från optimeringen av F påminner om härledning av hastighet-distortion (5) eller information flaskhals (7) ekvationer. Denna enkla form är giltig när likhetsåtgärden är invariant under permutationer av argumenten. I det mer allmänna fallet har vi var s(C; i (r ′ ) ) är den förväntade likheten mellan i och r − 1 medlemmar av kluster C när i är r ′ argument av s. En uppenbar egenskap hos Eq. (5) är att elementet i bör tilldelas kluster C med högre sannolikhet om det är mer lik de andra elementen i klustret. Mindre uppenbart är att denna likhet måste vägas mot den genomsnittliga likheten mellan alla element i klustret. Således förkroppsligar vårt tillvägagångssätt automatiskt den intuitiva principen att "tätstickade" grupper är svårare att ansluta sig till. Vi betonar att vi inte uttryckligen påbjöd denna egendom, utan snarare framträder den direkt ur den variationsbaserade principen om maximering av F; de flesta andra klustermetoder fångar inte denna intuition. Sannolikheten P (C) i Eq. (5) har formen av en Boltzmann distribution, och ökande likhet mellan element i ett kluster spelar rollen att sänka energin; temperaturen T sätter skalan för att omvandla likhet skillnader till sannolikheter. När vi sänker denna temperatur finns det en sekvens av "fasövergångar" till lösningar med mer distinkta kluster som uppnår större genomsnittlig likhet i varje kluster (8). För ett fast 3 antal kluster, minska temperaturen ger mer deterministiska P (C på) uppdrag. Algoritm. Även om Eq. (5) är en implicit uppsättning ekvationer, kan vi förvandla denna självkonsistens villkor till en iterativ algoritm som finner en explicit numerisk lösning för P (C) som motsvarar en (kanske lokal) maximum av F. Bild. 2 presenterar en pseudo-kod för algoritmen för fallet r = 2. Att utvidga algoritmen för det allmänna fallet av mer än parvisa relationer (r > 2) är enkelt. I princip upprepar vi detta förfarande för olika initieringar och väljer den lösning som maximerar F = s − T I(C; i). Vi hänvisar till algoritmen som beskrivs här som Iclust. Vi betonar att vi använder denna algoritm främst för att den framträder direkt ur den teoretiska analysen. Andra förfaranden som syftar till att optimera samma mål funktion är säkert rimliga och vi förväntar oss framtida forskning för att belysa potentiella (dis)fördelar av de olika alternativen. Information som en liknande åtgärd. När vi formulerar kluster problemet som optimering av F, Vi har använt, som i hastighetsförvrängning teori, den allmänna informationsteori för att ge en naturlig åtgärd för kostnaden för att dela upp data i fler kluster, men likhetsmåttet förblir godtycklig och allmänt anses vara problemspecifik. Är det möjligt att använda informationsteori för att ta itu med denna fråga också? För att vara konkret, överväga fallet där elementen i är gener och vi försöker mäta förhållandet mellan genuttryck mönster över en mängd olika villkor μ = 1, 2, · · · ·, M; genen i har uttrycksnivå e i (μ) under villkor μ. Vi föreställer oss att det finns en del verklig fördelning av förhållanden som celler möter under sin livstid, och ett experiment med en ändlig uppsättning villkor ger prover ur denna distribution. Sedan, för varje gen kan vi definiera sannolikhetstätheten av uttrycksnivåer, som bör bli slät som M → ∞. På samma sätt kan vi definiera den gemensamma sannolikhetstätheten för uttrycksnivåer av r gener i 1, i 2, · · ·, i r, δ(e 1 −e i1 (μ)) · · · · δ(e r −e ir (μ)). (9) Med tanke på den gemensamma fördelningen av uttrycksnivåer ger informationsteorin naturliga mått på relationerna mellan generna. För r = 2, kan vi identifiera relationen mellan generna i och j med den ömsesidiga informationen mellan uttrycksnivåer, log 2 P ij (e 1, e 2 ) P i (e 1 )P j (e 2 ) bitar. Denna åtgärd utvidgas naturligt till multiinformation bland flera variabler (9), eller gener: log 2 P i1i2·ir (e 1, e 2, · · · ·, e r ) P i1 (e 1 )P i2 (e 2 ) · · · P ir (e r ) bitar. Vi påminner om att den ömsesidiga informationen är det unika måttet på överensstämmelse mellan ett par variabler som lyder flera enkla och önskvärda krav oberoende av antaganden om formen för de underliggande sannolikhetsfördelningarna (4). I synnerhet är den ömsesidiga (och multi-) informationen oberoende av inverterbara omvandlingar av de enskilda variablerna. Till exempel, den ömsesidiga informationen mellan uttrycksnivåer av två gener är identisk med den ömsesidiga informationen mellan logen av uttrycksnivåer: det finns ingen anledning att hitta de "rätt" variabler med vilka att representera data. Informationsåtgärdens absoluta omfattning har också en tydlig innebörd. Om t.ex. två gener delar mer än en bit information måste de underliggande biologiska mekanismerna vara mer subtila än att bara slå på och stänga av uttrycket. Dessutom återspeglar den ömsesidiga informationen alla typer av beroende mellan variabler, medan vanliga korrelationsåtgärder vanligtvis ignorerar icke-linjära beroenden. Även om dessa teoretiska fördelar är välkända, är i praktiken teoretiska storheter notoriskt svåra att uppskatta utifrån finita data. Till exempel, även om distributionerna i Eq. (8,9) bli slät i gränsen för många prover (M → ∞), med en ändlig mängd data man behöver för att legalisera eller diskretisera distributionerna, och detta kan införa artefakter. Även om det inte finns någon helt allmän lösning på dessa problem har vi funnit att svårigheterna i praktiken inte är så allvarliga som man kunde ha förväntat sig. Med hjälp av en anpassning av den "direkta" estimeringsmetod som ursprungligen utvecklades i analysen av neural kodning (10), har vi funnit att man kan få tillförlitliga uppskattningar av ömsesidiga (och ibland multi-) informationsvärden för en mängd olika datatyper, inklusive genuttrycksdata (11); se det kompletterande materialet för detaljer. I synnerhet experiment som utforskar genuttryck nivåer under > 100 betingelser är tillräckliga för att uppskatta den ömsesidiga informationen mellan par av gener med en noggrannhet av 0,1 bitar. 2 2 Det bör noteras att det i tillämpningar där det finns en naturlig likhetsåtgärd kan vara fördelaktigt att använda denna åtgärd direkt. I situationer där antalet observationer inte är tillräckligt för icke-parametriska uppskattningar av informationsförhållanden bör andra heuristiska likhetsåtgärder användas eller så kan man använda parametriska modeller för de underliggande distributionerna. Observera dock att dessa alternativa åtgärder kan införlivas i algoritmen i bild. 2............................................................... För att sammanfatta, Vi har föreslagit en rent information teoretisk strategi för klusterering och kategorisering: Relationen mellan element definieras av den ömsesidiga (eller multi-) information, och optimal klusterbildning definieras som den bästa kompromissen mellan att maximera denna genomsnittliga relativitet inom kluster och minimera antalet bitar som krävs för att beskriva data. Resultatet är en formulering av kluster som handlar bitar av likhet mot bitar av beskrivande makt, utan ytterligare antaganden. En fritt tillgänglig webbimplementering av klusteralgoritmen och förfarandet för ömsesidig informationsuppskattning finns på http://www.genomics.princeton.edu/biophysics-teorin. Genuttryck. Som ett första testfall betraktar vi experiment på genuttrycksnivåers respons i jäst på olika former av miljöpåfrestning (12). Tidigare analys identifierade en grupp på 300 stressinducerade och 600 stresstryckta gener med "nästan identiska men motsatta uttrycksmönster som svar på miljöförskjutningarna" (13), och dessa gener kallades modulen miljöstressreaktion (ESR). Faktum är att dessa gener, baserat på denna observation, uteslöts från den senaste ytterligare analysen av hela jästgenomet (14). Men som vi kommer att se härnäst avslöjar vårt tillvägagångssätt automatiskt ytterligare en rik och meningsfull understruktur i dessa uppgifter. Som setts i Fig. 3A, skillnader i uttryck profiler inom ESR modulen verkligen är relativt subtila. Men när man överväger de ömsesidiga informationsförbindelserna (Fig. 3B ) en relativt tydlig struktur uppstår. Vi har löst vårt klusterproblem för r = 2 och olika antal kluster och temperaturer. Den konkava avräkningskurvan mellan s och I(C; i) visas i bild. 4A. Vad är det för fel på dig? Vi betonar att vi inte skapar en enda lösning, utan en hel familj av lösningar som beskriver struktur på olika komplexitetsnivåer. Med antalet kluster fast, s gradvis mättas när temperaturen sänks och begränsningen på I(C; i) är avslappnad. För korthetens skull fokuserade vi vår analys på de fyra lösningar för vilka mättnaden av s är relativt klar (1/T = 25). Vid denna temperatur har 85% av generna nästan deterministiska uppdrag till en av klungorna [P (C på C) > 0,9 för en viss C]. Som en illustration är tre av de tjugo kluster som finns vid denna temperatur i själva verket de kluster som presenteras i Bild. 1................................................................ Vi har bedömt den biologiska betydelsen av våra resultat genom att beakta fördelningen av genanmärkningar över kluster och uppskatta motsvarande klusters samstämmighet 3 med avseende på alla tre Gene 3 Specifikt definieras ett kluster (14) som procentandelen element i detta kluster som kommenteras av en Ontologi (15). Nästan alla våra kluster var avsevärt berikade i synnerhet kommentarer. Vi jämförde vår prestanda med 18 olika konventionella klusteralgoritmer som rutinmässigt tillämpas på denna datatyp (16). Vi använde klusterprogramvaran, som finns tillgänglig på http://bonsai.ims.u-tokyo.ac.jp.mdehoon/software/cluster/, för att genomföra de konventionella algoritmerna. På bild. 5 Vi ser att våra kluster uppnådde den högsta genomsnittliga samstämmigheten, vanligtvis med en betydande marginal. Dessutom, även när konkurrerande algoritmer kluster log 2 av uttryck (kvot) profiler-en gemensam legalisering som används i denna ansökan utan formell motivering våra resultat är jämförbara eller överlägsen alla alternativ. I stället för att införa en hierarkisk struktur på datan, som i många populära klusteralgoritmer, undersöker vi direkt relationen mellan lösningar på olika antal kluster som hittades självständigt. 4 I bild 6 ser vi att en ungefärlig hierarki framträder som ett resultat snarare än som ett implicit antagande, där vissa funktionella moduler (t.ex. "klustret", C 18 ) är bättre bevarade än andra. Vår uppmärksamhet dras också till kluster C 7, som finns upprepade gånger på olika antal kluster. Speciellt, vid lösningen med 20 kluster, bland 114 undertryckta gener i C 7, 69 har en okaraktäriserad molekylär funktion; denna koncentrationsnivå har en sannolikhet att 10 - 15 att ha uppstått av en slump. Man kan ha misstänkt att nästan varje process i cellen har några komponenter som inte har identifierats, och därför att eftersom dessa processer regleras skulle det finnas en handfull okända gener som regleras i samförstånd med många gener av känd funktion. Åtminstone för denna kluster, våra resultat indikerar ett annat scenario där en betydande del av tätt co-uttryckta gener förblir uncharacterized hittills. Börspriserna. För att understryka det allmänna i vår strategi anser vi att det finns en mycket annorlunda datauppsättning, de dagliga prisförändringarna för aktierna i Standard and Poor's (S & P) 500-listan (finns på http://www.standardandpoors.com ), under handelsdagarna 2003. Vi samlar ihop dessa data precis som i vår analys av genuttrycksdata. De resulterande avräkningskurvorna visas i bild. 4B, och återigen fokuserar vi på de fyra lösningar där redan mättats. För att bestämma samstämmigheten i de efterföljande kluster vi annotering som befanns vara signifikant berikad i denna kluster (P-val < 0,05, med Bonferroni korrigering för flera hypoteser). Se det kompletterande materialet för en detaljerad diskussion om statistisk validering av våra resultat. 4 I standard agglomerativa eller hierarkiska kluster börjar man med den mest detaljerade uppdelningen av singleton kluster och får nya lösningar genom sammanslagning av kluster. Följaktligen måste man sluta med en trädliknande hierarki av klusterpartitioner, oavsett om datastrukturen faktiskt stöder denna beskrivning. 5 använde Global Industry Classification Standard (GICS) (tillgänglig på http://wrds.wharton.upenn.edu ) som klassificerar företag på fyra olika nivåer: sektor, industrigrupp, industri och undernäring. Således tilldelas varje företag fyra annoteringar, som är organiserade i ett hierarkiskt träd, något liknande Gene Ontology hierarkiska annotering (15). Som tidigare är vår genomsnittliga koherensprestanda jämförbar med eller överlägsen alla andra 18 klusteralgoritmer vi undersökte (Fig. 5).................................................................. Nästan alla våra kluster, på olika nivåer av Nc, uppvisar en förvånansvärt hög grad av samstämmighet med avseende på de "funktionella etiketter" som motsvarar de olika (under) sektorerna i ekonomin. De fyra oberoende lösningarna, vid N c = {5, 10, 15, 20} och 1/T = 35, bildar naturligtvis en ungefärlig hierarki (se bild). 10 av stödmaterial). Vi har i detalj analyserat resultaten för N c = 20 och 1/T = 35 där urval från tre av de härledda klusteren visas i bild. 1................................................................ Åtta av klusteren anses vara fullständigt sammanhållna (100 %) och fångar upp subtila skillnader mellan olika industrisektorer. Två av de fullständigt sammanhållna klusteren separerar exempelvis företag till antingen investeringsbanker och kapitalförvaltning (t.ex. Merill Lynch) eller kommersiella regionala banker (t.ex. PNC). Även i kluster med mindre än perfekt samstämmighet kan vi observera och förklara relationer mellan företag inom kluster över och bortom vad kommentarerna kan tyda på. Till exempel är ett kluster berikat med "Hotel Resorts and Cruise Line" företag på en sammanhållningsnivå på 30%. Ändå verkar de återstående företagen i detta kluster också vara knutna till turistindustrin, som Walt Disney Co., banker som specialiserar sig på kreditkortsutgivning och så vidare. Filmbetyg. Slutligen överväger vi ett tredje testfall av ännu en annan karaktär: filmbetyg från mer än 70 000 tittare (databasen EachMovie, se http://www.research.digital.com/SRC/eachmovie/ ). Till skillnad från tidigare fall är uppgifterna här redan naturligt kvantifierade eftersom endast sex möjliga betyg var tillåtna. Vi fortsätter som tidigare att samla de 500 filmer som fick maximalt antal röster. De resulterande avräkningskurvorna presenteras i bild. Detta beslut träder i kraft dagen efter det att det har offentliggjorts i Europeiska unionens officiella tidning. Få kluster bevaras bland lösningarna på olika antal N c, vilket tyder på att en hierarkisk struktur kanske inte är en naturlig representation av data. Klusterkonsistens bestämdes med avseende på genreetiketter som tillhandahålls i databasen: action, animation, konst-utländska, klassiska, komedi, drama, familj, skräck, romantik och thriller. Bilda. 5 visar att våra resultat är överlägsna alla andra 18 standard klusteralgoritmer. Vi har i detalj analyserat resultaten för N c = 20 och 1/T = 40 där, återigen, urval från tre av de härledda kluster visas i Bild. 1................................................................ Klustren återspeglar verkligen de olika genrerna, men verkar också fånga subtila skillnader mellan uppsättningar filmer som tillhör samma genre. Till exempel är två av klusteren båda berikade i actiongenren, men en grupp består huvudsakligen av science fiction-filmer och den andra består av filmer i samtida miljöer. Närmare uppgifter om alla tre ansökningarna finns i en separat teknisk rapport som finns på ArXiv som http://arxiv.org/abs/q-bio.QM/0511042. Att mäta sammanhållningen i kluster motsvarar att fråga om det automatiska, objektiva förfarande som ingår i vår optimeringsprincip verkligen återvinner den intuitiva märkning som konstruerats av mänskliga händer. Vår framgång med att återvinna funktionella kategorier i olika system med exakt samma princip och praktiska algoritmer är uppmuntrande. Det bör understrykas att vårt tillvägagångssätt inte är en modell för varje system och att det inte finns något behov av att fatta databeroende beslut när det gäller representationen av uppgifterna, inte heller när det gäller definitionen av likhet. De flesta klusteralgoritmer förkroppsligar implicit olika modeller av den underliggande statistiska strukturen. 5 I princip bör mer exakta modeller leda till mer meningsfulla kluster. Frågan om hur man konstruerar en korrekt modell är dock naturligtvis ganska inbegripen och väcker ytterligare frågor som ofta tas upp godtyckligt innan klusteranalysen börjar. Dessutom, som framgår av Fig. 5, en algoritm eller modell som är framgångsrik i en datatyp kan misslyckas helt i en annan domän; även i samband med genuttryck, framgångsrik analys av data som tas under en uppsättning villkor innebär inte nödvändigtvis framgång i en annan uppsättning villkor, även för samma organism. Vår användning av informationsteori gör att vi kan fånga relationen mellan olika mönster oberoende av antaganden om arten av denna relation. På motsvarande sätt har vi ett enda tillvägagångssätt som uppnår hög prestanda inom olika områden. Slutligen kan vår strategi lyckas där andra metoder skulle misslyckas kvalitativt. Konventionella algoritmer söker efter linjära eller ungefär linjära relationer mellan de olika variablerna, medan vår information teoretiska strategi är lyhörd för alla typer av beroenden, inklusive starkt icke-linjära strukturer. Dessutom, medan klusteranalyslitteraturen hittills har fokuserat på parvisa relationer och likhetsåtgärder, sätter vårt tillvägagångssätt en sund teoretisk ram för att analysera komplexa data baserade på högre ordningsrelationer. I själva verket visades det nyligen, både i princip (17) och i praktiken (18) att datastrukturen i vissa situationer är skymd på parvis nivå, men tydligt manifesterar sig endast vid 5 Till exempel motsvarar K-means algoritm att maximera sannolikheten för data på antagandet att dessa genereras genom en blandning av sfäriska Gaussians. högre nivåer. Frågan om hur vanliga sådana data är, liksom de tillhörande beräkningssvårigheterna i att analysera sådana högre ordningsrelationer, är ännu inte utforskad.
Detta liknar det "kollektiva begreppet likhet" i informationsbaserad klusterering REF.
Information based clustering
{'venue': 'Proceedings of the National Academy of Sciences of the United States of America', 'journal': 'Proceedings of the National Academy of Sciences of the United States of America', 'mag_field_of_study': ['Mathematics', 'Biology', 'Medicine']}