Klusteranalysmetoder försöker dela upp en datamängd i homogena undergrupper. Det är användbart i en mängd olika tillämpningar, inklusive dokumentbehandling och modern genetik. Konventionella klustermetoder är oövervakade, vilket innebär att det inte finns någon utfallsvariabel eller något känt om sambandet mellan observationer i datamängden. I många situationer finns dock information om klusteren utöver egenskapernas värden. Till exempel kan klusteretiketter för vissa observationer vara kända, eller vissa observationer kan vara kända för att tillhöra samma kluster. I andra fall kan man vilja identifiera kluster som är förknippade med en viss resultatvariabel. Denna granskning beskriver flera klusteralgoritmer (semiövervakade klustermetoder) som kan tillämpas i dessa situationer. De flesta av dessa metoder är modifieringar av den populära kmeans klustermetoden, och flera av dem kommer att beskrivas i detalj. En kort beskrivning av några andra halvövervakade klusteralgoritmer ges också. Syftet med klusteranalys är att dela upp en datamängd i en grupp undergrupper (dvs. "Kluster") så att observationer inom ett kluster är mer lika varandra än observationer i andra kluster. För en mer detaljerad diskussion, se Hastie et al. 1 eller Gordon 2. Traditionella klustermetoder är oövervakade, vilket innebär att det inte finns någon resultatmått och ingenting är känt om sambandet mellan observationerna i datamängden. I många situationer kan man dock vilja utföra klusteranalys även om det finns en resultatvariabel eller någon preliminär information om klusteren är känd. Till exempel kan ett e-postklassificeringsförfarande försöka karakterisera egenskaperna hos "spam" e-post. Antag att en stor databas av e-post är tillgänglig, en liten delmängd av vilken redan 1 har klassificerats som "spam" eller "inte spam". Man kan vilja identifiera kluster i denna datamängd så att det ena klustret i första hand består av "spam" och det andra klustret består i första hand av "inte skräppost". Eller i en genetisk undersökning av cancer, kan man vilja identifiera genetiska kluster som kan användas för att bestämma prognosen för cancerpatienter. Sådana kluster skulle bara vara av intresse om de var förknippade med resultatet av intresset, nämligen patientens överlevnad. Klustermetoder som kan tillämpas på delvis märkta data eller data med andra typer av resultatmått kallas halvövervakade klustermetoder (eller ibland övervakade klustermetoder). De är exempel på halvövervakade inlärningsmetoder, som är metoder som använder både märkta och omärkta data [3] [4] [5] [6]. Denna översyn kommer kortfattat att beskriva flera halvövervakade klustermetoder som kan tillämpas på olika typer av delvis märkta datamängder. Översynen kommer främst att inriktas på variationer av k-medelsklustring, eftersom de flesta befintliga semi-övervakade klustermetoder är modifierade versioner av k-medelsklustring. En kort beskrivning av vissa halvövervakade hierarkiska klustermetoder kommer dock också att ges. I detta avsnitt beskrivs kortfattat två av de vanligaste traditionella klusteranalysmetoderna, nämligen k-medelsklustring och hierarkisk klusterbildning. K-means klusterbildning är en av de mest populära klusteranalysmetoderna. Det är allmänt tillämpas på datamängder där alla variabler är kvantitativa och avståndet mellan observationer mäts med hjälp av kvadrat Euclidean avstånd, som definieras enligt följande: Här x i och x i ′ är observationer från en datamängd med p-funktioner, och x ij representerar värdet av jth funktionen för observation i. K-means klusteralgoritm försöker tilldela varje observation till ett kluster för att minimera följande objektiv funktion: I ovanstående uttryck representerar K antalet kluster, och C i representerar det kluster som observation i tilldelas, där 1 ≤ C i ≤ K. Denna målfunktion är också känd som "inom klustersumman av kvadrater" eller WCSS. Observera att (2) kan skrivas som: där n k är antalet observationer i kluster k andx kj är medelvärdet av funktionen j i kluster k. Flera k-means kluster algoritmer har föreslagits för att minimera (2) 7-10. Varje algoritm använder dock en viss variation av följande strategi: 1. Slumpmässigt tilldela varje observation till ett första kluster. 2. Utgångspunkten är följande: För varje funktion j och kluster k, beräknax kj, medelvärdet av funktionen j i kluster k. 3. Tilldela varje observation i till ett nytt kluster C i enligt följande: Upprepa steg 2 och 3 tills algoritmen konvergerar. Ovanstående algoritm är garanterad att konvergera, men den kan konvergera till ett lokalt minimum. Därför är det lämpligt att upprepa algoritmen flera gånger med olika initiala kluster och välja den uppsättning kluster som producerar den minsta WCSS. För en mer detaljerad diskussion av k-means klustring och flera variationer av k-means algoritm se Hastie et al. 1................................................................ K-means klusteralgoritm kräver att man väljer antalet kluster K. Flera metoder har föreslagits för att välja K. En vanlig metod är den "gapstatistik" som föreslås av Tibshirani et al. 11........................................... Låt W k vara WCSS (2) när K = k. Det är enkelt att verifiera att W k alltid kommer att minska som k ökar, så man kan helt enkelt inte välja värdet av K som minimerar W K. Motiveringen för gap statistik är följande: Låt K * betecknar det verkliga värdet av K. Om k < K *, sedan minst en kluster som produceras av k-medel är faktiskt två separata kluster, och så W k+1 bör vara betydligt mindre än W k. Å andra sidan, om k > K *, sedan minst två kluster som produceras av k-medel algoritm är faktiskt en enda kluster, så W k‐1 bör bara vara något större än W k. Således gap statistik försöker identifiera den minsta K sådan att W k inte minskar signifikant för k > K. Formellt, gap statistik definieras som det förväntade värdet E [log(W k )] beräknas under en lämplig referensfördelning. Ett gemensamt val av referensfördelning är en enhetlig multivariatfördelning med samma intervall som datamängden av intresse. I detta fall kan detta förväntade värde uppskattas genom provtagning från denna (uniforma) referensfördelning. Tibshirani m.fl. 11 uppskatta antalet kluster K enligt följande: Ett antal andra metoder har föreslagits för att välja antalet kluster K 12-14. Se ovan nämnda referenser för närmare uppgifter om dessa metoder. K-means klustring är ett exempel på vad som kallas partitionella klustermetoder, som partitionerar en datauppsättning i ett fast antal separata undergrupper. Däremot pekar hierarkiska klustergrupper på en serie kluster i en trädliknande struktur. På varje nivå av trädet, kluster bildas genom att slå samman kluster på nästa lägre nivå av trädet. Således bildar varje datapunkt en singeltonskluster på trädets bottennivå, och trädets översta nivå består av en enda kluster som innehåller alla datapunkter. Det finns en mängd olika metoder för hierarkisk klusterbildning. Denna översyn kommer i korthet att beskriva några av de vanligaste hierarkiska klustermetoderna, även om många andra hierarkiska klustermetoder har föreslagits. Se Hastie m.fl. 1 för mer information (inklusive beskrivningar av flera andra hierarkiska klustermetoder). En av de vanligaste hierarkiska klustermetoderna är agglomerativ hierarkisk klusterbildning. Agglomerativa hierarkiska klustermetoder börjar med uppsättningen enskilda datapunkter och slår samman de två "mest likartade" punkterna till ett kluster. Vid varje steg i förfarandet slås de två "mest likartade" klusteren (som kan vara enskilda datapunkter) samman tills alla datapunkter har slagits samman till ett enda kluster. Se figur 1 för en illustration av agglomerativ hierarkisk klusterbildning. [ Figur 1 ungefär här.] För att kunna tillämpa den hierarkiska klusteralgoritm som beskrivs ovan måste man definiera hur paret av "mest likartade" kluster väljs. Observera att för hierarkisk klusterbildning är det inte tillräckligt att definiera en olikhet (eller avstånd) mellan par av punkter; man måste också definiera en olikhet åtgärd mellan par av kluster. Många olika olikhetsåtgärder har föreslagits för hierarkisk klusterbildning, men de vanligaste metoderna börjar med att definiera en olikhetsåtgärd mellan par av punkter. Den Euclidean avstånd definieras i (1) är ett vanligt val, men andra olikhet åtgärder är möjliga. När man till exempel samlar DNA-mikroarraydata, är det vanligt att definiera olikhetsmåttet mellan två punkter som ska vara 1 – ρ, där ρ är Pearson korrelationskoefficienten mellan de två punkterna. När en olikhet mellan två punkter har definierats finns det flera sätt att definiera avstånd mellan kluster. Två gemensamma olikhetsåtgärder är kända som "enkel koppling" och "fullständig koppling". Låta C 1 och C 2 betecknar index för elementen i två kluster. Med andra ord, i  på C 1 om och endast om datapunkt x i finns i den första klustret. Också, låt d(x i, x i ′ ) vara skillnaden mellan data 4 punkter x i och x i ′. Därefter definieras den enskilda kopplingens olikhet mellan de två klustren och den fullständiga kopplingens olikhet definieras som Andra olikhetsåtgärder mellan klustren kan också användas. Till exempel skulle man kunna definiera skillnaden mellan två kluster för att vara den genomsnittliga olikheten mellan elementen i de två klusteren: där n 1 och n 2 är antalet datapunkter i kluster 1 respektive 2. Varje sådan åtskillnad mellan kluster har vissa fördelar och nackdelar. Se Hastie m.fl. 1 för detaljer. Som tidigare nämnts kan resultaten av hierarkisk klusterbildning representeras som ett binärt träd. Varje nod av trädet representerar en klunga. (I synnerhet är rotnoden den översta kluster som innehåller alla datapunkter, och varje terminal nod motsvarar en singelton "kluster" bestående av en enda datapunkt.) Denna trädstruktur kan representeras i en grafisk form som kallas dendogram. Det är brukligt att rita dendogrammet så att höjden på varje nod i trädet motsvarar skillnaden mellan de två kluster som slogs samman för att bilda klustret. Se 2 för ett exempel på en dendogram av en enkel datauppsättning. [ Figur 2 ungefär här.] Vi ska nu kortfattat skissera flera halvövervakade klustermetoder. Dessa metoder kommer att organiseras beroende på arten av de kända utfallsdata. För det första kommer vi att överväga det enklaste fallet, nämligen det fall där uppgifterna är delvis märkta. Med andra ord är klusteruppdragen kända för någon delmängd av observationerna. Vi kommer då att överväga fallet där någon form av relation mellan funktionerna är känd, och slutligen fallet där man försöker identifiera kluster som förknippas med en viss utfallsvariabel. I vissa situationer kan klusteruppdragen vara kända för någon delmängd av uppgifterna. Syftet är att klassificera de omärkta observationerna i data till lämpliga kluster med hjälp av de kända klustertilldelningarna för denna delmängd av data. I viss mening är detta problem likvärdigt med ett övervakat klassificeringsproblem, där målet är att utveckla en modell för att tilldela observationer i en datauppsättning till en av en begränsad grupp klasser baserade på en utbildningsuppsättning där de verkliga klassetiketterna är kända. Traditionella klassificeringsmetoder som övervakas kan dock vara ineffektiva när endast en liten del av uppgifterna är märkta. Till exempel, om man vill klassificera webbsidor i ett diskret antal grupper, kan man lätt samla in miljontals omärkta observationer, men att klassificera en viss observation kräver mänsklig inblandning (och därmed är sannolikt långsam). På samma sätt, om man vill utveckla en metod för att klassificera e-post som "spam" eller "inte spam", då kan man enkelt samla många omärkta observationer, men andelen märkta observationer kommer att vara mycket mindre. För dessa typer av problem, konventionella övervakade klassificeringsmetoder kan vara ineffektiva eftersom de vanligtvis inte använder omärkta data för att bygga klassificeringsalgoritmen. Det stora flertalet av de tillgängliga uppgifterna kommer därför inte att användas. I dessa situationer kan man ofta skapa mer exakta klassificeringsregler genom att kombinera både märkta och omärkta data. Se Blum och Mitchell 3 eller Joachims 4 för en mer detaljerad diskussion och exempel. Basu m.fl. 16 utvecklade en generalisering av k-means klustring (som de kallade "konstruerade k-means") för den situation där klassetiketter är kända för en delmängd av observationerna. Återigen låter vi x i och x i ′ vara observationer från en datauppsättning med p-funktioner, och x ij representerar värdet av jth-funktionen för observation i. Antag vidare att det finns undergrupper S 1, S 2,. .., S K av x i är sådan att x i S k innebär att observation i är känd för att tillhöra kluster k. (Här K betecknar antalet kluster, som också antas vara känd i detta fall.) Låta S k  påvisar antalet algoritmer som fortskrider enligt följande: 1. För varje funktion j och kluster betyder den ursprungliga klustret följande: 3. För varje funktion j och kluster k, beräknax kj, medelvärdet av funktionen j i kluster k. 4. Upprepa steg 2 och 3 tills algoritmen konvergerar. Observera att detta förfarande är identiskt med det konventionella k-medelvärdet med undantag för de ursprungliga klustertilldelningarna (som i allmänhet är godtyckliga i alla fall) och steg 2. I steg 2 tilldelas alltid märkta observationer till deras kända kluster även om de är närmare medeltalet för ett annat kluster. Den begränsade k-means klusteralgoritm som beskrivs ovan förutsätter att ingen av de märkta observationerna är felklassificerad. Med hjälp av den begränsade k-means klustereringsprocessen kan denna felklassificering aldrig korrigeras om en märkt observation är felklassad, eftersom denna observation kommer att tilldelas samma kluster i steg 2 i varje iteration av algoritmen. Därför, Basu et al. 16 rekommenderar en alternativ algoritm (som de kallar "seeded k-means clustring") som är identisk med begränsad k-means clustring med undantag för steg 2. Den sådda k-means klusteralgoritmen tilldelar alltid observationer till närmaste kluster med hjälp av (3) även om observationen är märkt. Således, om en observation initialt felmärks, då felmärkt observation kan korrigeras om det är närmare klustercentrum i en annan kluster. Observera att såddk-means klustring är identisk med konventionell k-means klustring med undantag för det första steget i förfarandet. Således, sådd k-means klusterbildning är helt enkelt konventionella k-means klustering som använder den märkta datan för att hjälpa till att välja de ursprungliga kluster centra. En liknande metod används i den övervakade sparse klustering metod av Gaynor och Bair 17, som beskrivs nedan. Metoder för att gruppera delvis märkta data kan vara användbara vid analys av DNA-mikroarray data. I ett typiskt mikroarray-experiment mäter man genuttrycksnivåerna av p-gener för var och en av n-prov, där man normalt p  på n. Man kan vilja identifiera kluster av gener med liknande uttrycksnivåer över prover, eftersom generna i varje sådan kluster kan tillhöra samma biologiska väg. Om vissa gener är kända för att tillhöra vissa vägar före utförandet av experimentet, då klusteretiketterna för dessa gener är kända. I denna situation försöker man samla de återstående generna med hjälp av informationen från de märkta generna. Flera klustermetoder har utvecklats för det specifika problemet med att analysera delvis märkta mikroarraydata [18] [19] [20] [21] [23] [24] [25] [26]. Dessa metoder är särskilt utformade för mikroarray data och kommer inte att beskrivas i denna översyn; se referenser för detaljer. Vi överväger nu klusterbildning när mer komplexa relationer bland observationerna är kända. I synnerhet kommer vi att överväga två typer av möjliga begränsningar bland observationer: "Must-link begränsningar" kräver att två observationer måste placeras i samma kluster, och "kan inte länk begränsningar" kräver att två observationer inte får placeras i samma kluster. En möjlig tillämpning är när upprepade mätningar samlas in på någon delmängd av de experimentella enheterna. I en sådan situation, kan man vilja tilldela alla upprepade mätningar av samma experimentella enhet till samma kluster. Observera att detta är en generalisering av problemet i föregående avsnitt, där klusteruppdragen är kända för en delmängd av funktionerna. I den situationen, för varje funktion j som är känd för att tillhöra kluster k, kan man införa ett måste-länk begränsning mellan funktion j och alla andra funktioner som är kända för att tillhöra kluster k och en inte-länk begränsning mellan funktion j och funktioner som är kända för att inte tillhöra kluster k. Många metoder har föreslagits för att lösa problemet med begränsad klusterbildning. Denna översyn kommer kortfattat att beskriva några av de vanligaste metoderna, och referenser för många andra metoder listas nedan. Se även Basu et al. 27 för en mer detaljerad beskrivning av olika algoritmer för begränsad klusterbildning. Wagstaff m.fl. 28 föreslog följande algoritm (med de kallade "COP-KMEANS") för att lösa klusterproblem med tanke på denna typ av begränsning: 1. Slumpmässigt tilldela varje observation till ett första kluster. 2. Utgångspunkten är följande: För varje funktion j och kluster k, beräknax kj, medelvärdet av funktionen j i kluster k. 3. Tilldela varje observation i till ett nytt kluster C i enligt följande: där D ik = {k: inga begränsningar kränks när observation i tilldelas kluster k} 4. Upprepa steg 2 och 3 tills algoritmen konvergerar. Algoritmen misslyckas om D ik = ∅ för någon i under något steg av förfarandet. Observera att COP-KMEANS är identiskt med konventionell k-means klustring med undantag för steg 3. COP-KMEANS tilldelar varje observation den närmaste klustret sådan att inga begränsningar överträds (eftersom konventionell k-means klustring tilldelar varje observation den närmaste klustret utan att beakta begränsningarna). En potentiell nackdel med COP-KMEANS-algoritmen är att den kräver att inga begränsningar överträds. I vissa situationer kan man vilja tillåta att vissa begränsningar överträds om det finns starka bevis för att en viss begränsning är felaktig. Därför, Basu et al. 29 föreslog en metod (som de kallar "PCKmeans") som löser problemet med att identifiera kluster med tanke på en uppsättning mustlink och inte kan länka begränsningar till de observationer som gör det möjligt att bryta vissa begränsningar. PCKmeas syftar till att minimera en modifierad version av den objektiva funktionen (2) som definieras enligt följande: Låt observationer (x i, x i ′ )  på M om det finns en must-link begränsning mellan observationer i och i ′, och låt (x i, x i ′ ) Om det finns en inte kan länk begränsning mellan observationer i och i ′. Därefter PCKmeas minimerar följande objektiv funktion: Här l i,i ′ är en användardefinierad straff för brott mot ett måste-länk begränsning mellan observationer i och i ′ och l * i,i ′ är straffet för brott mot en inte-länk begränsning mellan i och i ′. Se Basu m.fl. 29 för detaljer om PCKmeas algoritm för minimering (4). De metoder som beskrivs ovan ändrar en befintlig klustermetod (nämligen k-means clustring) så att begränsningarna uppfylls. Således kallas sådana metoder ibland för "constraint-based methods" i litteraturen 6,30. "Distansbaserade metoder" (eller "metriskbaserade metoder") använder däremot en befintlig klustermetod men ändrar den metriska metod som används för att mäta "avståndet" mellan ett par observationer så att begränsningarna uppfylls. Till exempel, i stället för att använda den enkla Euclidean avstånd (1) kan man använda ett alternativt avstånd metrisk så att två observationer med en "must-link restriktion" nödvändigtvis kommer att ha ett lägre avstånd mellan dem 31-43. Dessutom har andra begränsningsbaserade metoder föreslagits [44] [45] [46] [47] [48], och ytterligare andra metoder kombinerar båda dessa metoder i en enda modell 6, 30. Andra former av begränsad klusterbildning är också möjliga, såsom klustering på grafdata 49, 50. Dessa metoder kommer inte att beskrivas närmare i denna översyn; se de ursprungliga hänvisningarna för närmare information. Hittills har vi också antagit att begränsningarna för observationerna angavs när uppgifterna samlades in. I vissa situationer kan dataanalytikern ha möjlighet att välja någon delmängd av observationerna och införa begränsningar för denna delmängd. Anta till exempel att målet är att samla en stor uppsättning textdokument baserat på frekvensen av valda ord som visas i dokumenten. Man kan manuellt undersöka ett givet par dokument för att avgöra om de bör klassificeras i samma kluster (och därmed införa antingen en must-link restriktion eller en inte-link restriktion). Anta att en forskare slog upp titlarna på tre dokument och bestämde att två av dokumenten var romaner för tonåringar och det tredje dokumentet var en artikel från en medicinsk tidskrift. I detta fall skulle forskaren införa en begränsning av must-link mellan de två romanerna och en begränsning av inter-link mellan varje roman och tidskriftsartikeln. Men det finns en kostnad i samband med att göra en sådan bestämning, så typiskt man kan bara analysera en liten delmängd av observationer. I en sådan situation är det fördelaktigt att välja denna delmängd för att maximera informationen om kluster. 29 beskriva en variant av PCKmeas (kallas "aktiv PCKmeas") som väljer en delmängd av de observationer på vilka man kan införa begränsningar så att noggrannheten hos klusteralgoritmen maximeras. De visar att denna metod överträffar den generiska PCKmeas algoritmen för denna typ av problem. För andra metoder för begränsningsval i denna situation, se Greene och Cunningham 51 eller Mallapragada et al. 52................................................................ De flesta befintliga halvövervakade klustermetoder är baserade på k-medelsklustring eller andra former av partitionerad klusterbildning. Jämförande med andra hälften övervakade hierarkiska klustermetoder har föreslagits 53. Detta beror delvis på att problemet måste formuleras annorlunda för hierarkisk klusterbildning. Som tidigare nämnts använder de flesta halvövervakade klustermetoder antingen delvis märkta data eller kända begränsningar (t.ex. "Måste länka" eller "kan inte länka" begränsningar) på observationerna. Det är svårare att definiera sådana begränsningar för hierarkisk klusterbildning, eftersom hierarkisk klusterbildning länkar samman alla observationer i en datamängd på någon nivå i klusterhierarkin. Således kommer en "must-link" begränsning alltid att vara tillfredsställd på någon nivå av hierarkin och likaså kommer en "kan inte länk" begränsning alltid att brytas. Därför har delvis övervakade hierarkiska klustermetoder övervägt olika typer av begränsningar. Miyamoto och Terami 54 kräver till exempel att observationer kopplade till en "must-link"-restriktion samlas på lägsta möjliga nivå i hierarkin. De kräver vidare att observationer åtskilda av en "kan inte länka" begränsning får inte vara en del av samma klusterhierarki. I stället för att identifiera en enda klunghierarki returnerar alltså metoden Miyamoto och Terami 54 flera klungande hierarkier. En separat hierarki skapas för varje observation som är en del av en "kan inte länka" begränsning. Flera relaterade metoder har föreslagits för att utföra hierarkisk klusterbildning under sådana begränsningar 45, [54] [55] [56]. Andra typer av begränsningar har föreslagits för halvövervakad hierarkisk klusterbildning. Bade och Nurnberger 57 beskriver en metod för att utföra hierarkisk klusterbildning med tanke på en uppsättning begränsningar av "must-link before", där vissa observationer måste samlas ihop innan de samlas med andra datapunkter. utveckla en alternativ metod för hierarkisk klusterbildning med denna typ av begränsningar. Zhao och Qi 58 anser hierarkisk klustring med "ordning begränsningar", vari observationer måste kombineras i en viss ordning. Med andra ord, med tanke på en beställning begränsning av (x 3, x 1, x 4, x 2 ), observationer x 1 och x 3 måste samlas ihop innan de kan kombineras till en kluster som innehåller x 4, och observationer x 1, x 3, och x 4 måste samlas tillsammans innan de kan kombineras till en kluster som innehåller x 2. Hamasuna m.fl. 59 definierar "klustermässigt toleransbaserade parvisa begränsningar" som definierar "måste-länk" och "kan inte länka" begränsningar mellan par av kluster baserat på en viktad räkning av antalet sådana begränsningar som finns mellan observationer i klustren. De utvecklade algoritmer för att implementera flera varianter av hierarkisk klusterbildning som är föremål för denna typ av begränsning [59] [60] [61]. De flesta av dessa metoder för halvövervakad hierarkisk klusterbildning är mycket nya och lite forskning har gjorts om för- och nackdelarna med de olika metoderna. Utvecklingen av metoder för halvövervakad hierarkisk klusterbildning är fortfarande ett aktivt forskningsområde. I andra situationer kan man vilja identifiera kluster som är förknippade med en given utfallsvariabel. Utfallsvariabeln är vanligtvis en "noisy surrogate" 62 för (oobserved) kluster av intresse. I genetiska studier av cancer kan det till exempel finnas undertyper av cancer med olika genetiska egenskaper. Vissa subtyper kan vara mer benägna att metastasera, vilket resulterar i en sämre prognos för patienter med dessa subtyper. I detta fall är dessa genetiska subtyper oobserverade, men överlevnadstiderna för patienterna i studien kan vara tillgängliga. En patient som har en "högrisk" subtyp är mer benägna att ha en låg överlevnadstid än en patient som har en "lågrisk" subtyp, men det finns betydande variation inom subtyper. Det är möjligt att observera en patient med en "lågrisk" subtyp och en låg överlevnadstid (och vice versa). Se figur 3 för en illustration av ett sådant scenario. I detta exempel, patienter i kluster 2 har en högre genomsnittlig överlevnadstid än patienter i kluster 1, men det finns betydande överlappning i de två grupperna, så det är inte möjligt att identifiera kluster med endast överlevnadstiden. [ Figur 3 ungefär här.] Eftersom konventionella klustermetoder inte använder värdena för en resultatvariabel, kan de misslyckas med att identifiera kluster som är förknippade med resultatet och i stället identifiera kluster som inte är relaterade till resultatet. Figur 4 visar ett exempel på en situation där en specialiserad klustermetod behövs för att identifiera kluster som är förknippade med en resultatvariabel av intresse. I denna situation har 1-50 form kluster som är förknippade med utfallsvariabeln och har 51-150 form kluster som inte är relaterade till utfallsvariabeln. Konventionella klustermetoder kommer dock att identifiera de kluster som definieras av funktioner 51-150, eftersom avståndet mellan centrumen av dessa kluster är större än avståndet mellan centrumen av kluster som definieras av funktioner 1-50. Därför behövs särskilda metoder för att identifiera intressekluster (dvs. De kluster som definieras av egenskaperna 1-50) i detta scenario. [ Figur 4 ungefär här.] Trots problemets betydelse har relativt få metoder föreslagits för att identifiera kluster som är förknippade med en resultatvariabel. Metoder finns för att identifiera sekundära kluster för datamängder som liknar de data som visas i figur 4 (se t.ex. Nowak och Tibshirani 63 ), men dessa metoder använder inte heller information från utfallsvariabeln för att identifiera sekundära kluster. En av de tidigaste metoderna för att identifiera kluster associerade med en utfallsvariabel är den "övervakade klustering" metoden av Bair och Tibshirani 62, som fortskrider enligt följande: 1. För varje funktion i datamängden, beräkna en teststatistik T j för att testa nollhypotesen om inget samband mellan jth-funktionen och utfallsvariabeln. Om utgångsvariabeln är binär (dvs. fall kontra kontroll), kan T j vara en t- statistik. Om resultatvariabeln är kontinuerlig kan T j vara en t-statistik för att testa nollhypotesen att regressionskoefficienten för att förutsäga resultatet baserat på funktion j är lika med 0. Om utfallsvariabeln är en högercensurerad överlevnadstid kan T j vara motsvarande teststatistik från en Cox proportionell riskmodell. 2. Utgångspunkten är följande: Välj en tröskel M, och tillämpa k-means klustering för de funktioner för vilka T j  till > M. Funktioner med  till T j  till ≤ M kastas och påverkar inte kluster uppdrag. Även om denna metod är relativt enkel, Bair och Tibshirani 62 visar att denna metod kan identifiera biologiskt relevanta kluster i flera datamängder. I synnerhet Bullinger 11 et al. 64 använde denna metod för att identifiera undertyper av akut myeloisk leukemi som var associerade med patientens överlevnad. En fördel med denna metod är att den fungerar bra även när datan är högdimensionell. Eftersom klusterering endast utförs med hjälp av en delmängd av funktionerna, kan en högdimensionell datamängd effektivt reduceras till en datamängd med färre funktioner. Detta övervakade klusterförfarande kräver valet av en inställningsparameter M, som kan väljas med hjälp av korsvalidering. Även om den metod som föreslås av Bair och Tibshirani 62 tillämpar k-means klustring på undergruppen av de funktioner som är mest förknippade med utfallsvariabeln, kan man använda samma strategi för att välja de funktioner som är mest förknippade med resultatet och sedan tillämpa hierarkisk klustring eller en alternativ klustringsmetod. Ja, Koestler m.fl. 65 föreslå en metod som kallas "halvövervakade rekursivt partitionerade blandningsmodeller (RPMM)" som använder denna strategi. Halvövervakad RPMM väljer först en uppsättning funktioner som är mest förknippade med utfallsvariabeln och sedan tillämpar RPMM metoden av Houseman et al. 66 till denna delmängd av funktionerna. En möjlig fördel med RPMM framför k-medelsklustring är att RPMM inte kräver att man väljer antalet kluster K. Koestler et al. 65 ge flera exempel där halvövervakade RPMM ger mer exakta resultat än den övervakade klustermetoden av Bair och Tibshirani 62. I andra situationer kan dock delvis övervakade RPMM misslyckas med att upptäcka kluster även när sådana kluster finns; se Gaynor och Bair 17 för exempel. En möjlig nackdel med metoder som övervakad klusterbildning och delvis övervakad RPMM är det faktum att alla funktioner som kasseras efter det inledande screeningsteget permanent utesluts från analysen. Detta är problematiskt om man vill identifiera de egenskaper som skiljer sig åt mellan kluster, eftersom det är möjligt att egenskaper som skiljer sig åt mellan kluster endast är svagt förknippade med resultatvariabeln, särskilt om sambandet mellan klusteren och utfallsvariabeln är svagt. Om sambandet mellan klusteren och utfallsvariabeln är mycket svagt, kan övervakad klusterbildning och delvis övervakad RPMM misslyckas med att identifiera rätt kluster. För att övervinna denna svårighet föreslår Gaynor och Bair 17 en metod som kallas "övervakad sparse clustring", vilket är en ändring av den "sparse clustring" metoden Witten och Tibshirani 67. Sparse clustering är en oövervakad klustering metod som är användbar när kluster skiljer sig med avseende på endast en delmängd av funktionerna. Se figur 5 för ett exempel på en datauppsättning där sparsam klustring ger bättre resultat än traditionell k-means klustring. I detta (tvådimensionella) exempel skiljer sig klustren åt med avseende på x men inte med avseende på y. Att tillämpa 2-medelskluster på både x- och y-resultat ger felaktiga resultat, men att tillämpa 2-medelskluster endast till x identifierar de rätta klustren. [ Figur 5 ungefär här.] Följande är en kort beskrivning av den sparse kluster algoritm av Witten och Tibshirani 67 : Först, notera att minimera k-medel objektiv funktion (2) är equiva-12 lånas ut till maximering Här är varje x ij en observation från en datauppsättning med n observationer och p funktioner som delas in i K kluster, där C i = k om och endast om observation i tillhör kluster k och n k är antalet observationer i kluster k. Då sparse kluster algoritm försöker identifiera vikter w 1, w 2,. .., w p för varje funktion för att maximera med förbehåll för de begränsningar som p j=1 w 2 j = 1, p j=1  och j ≤ s och w j ≥ 0 för alla j. Variabeln s är en inställningsparameter. I takt med att s ökar kommer antalet icke-noll w j: s att öka. Således, genom att välja ett lämpligt värde av s, kommer klustereringen att utföras med endast en delmängd av funktionerna (de funktioner för vilka w j > 0). Observera att sparsam klustring medför en L 1 påföljd på funktionsvikterna, som liknar L 1 påföljden på regressionskoefficienterna i Lasso regression 68 (vilket också gör att ett ökande antal koefficienter blir lika med 0 som värdet på inställningsparametern ändras). Se Witten och Tibshirani 67 för en mer detaljerad beskrivning av den glesa kluster algoritmen, inklusive en metod för att välja stämparametern s. I synnerhet Witten och Tibshirani 67 visar att denna glesa klustering metod tenderar att producera bättre resultat än flera tidigare publicerade metoder för att minska dimensionen av en datauppsättning före klusterbildning, såsom kluster på PCA poäng 69, 70. Witten och Tibshirani 67 maximeras (5) med hjälp av en algoritm som sätter w j = 1/ ε n i början av förfarandet och sedan uppdaterar w j är iterativt. Den övervakade sparse klustering metoden av Gaynor och Bair 17 liknar sparse klustering men väljer den ursprungliga funktionen vikter enligt följande: 1. För varje funktion i datamängden, beräkna en teststatistik T j för att testa nollhypotesen om inget samband mellan jth-funktionen och utfallsvariabeln. 2. Utgångspunkten är följande: Välj en tröskel M, och definiera de ursprungliga vikterna w 1, w 2,. .., w p enligt följande: där m är antalet funktioner sådan att  på T j > M. Med andra ord, snarare än att ge lika ursprungliga vikter till alla funktioner i datamängden, övervakad sparse kluster ger lika ursprungliga vikter till de funktioner som är mest förknippade med resultatet variabel och en initial vikt på 0 till alla andra funktioner. Gaynor och Bair 17 visar att denna ändring av sparsam klusterbildning är mer benägna att identifiera kluster som är förknippade med en utfallsvariabel. Observera att övervakad sparse clustering liknar flera andra semi-övervakade clustering metoder. Metoden för att välja de ursprungliga klustervikterna är jämförbar med metoden för att välja funktionerna i den övervakade klusteralgoritmen för Bair och Tibshirani 62. Det första steget i den övervakade klusteralgoritmen gäller k-means klustring av de egenskaper som är mest förknippade med resultatvariabeln, som är identisk med den övervakade klustermetoden. Skillnaden är att övervakad sparse clustering uppdaterar funktionen vikter efter att identifiera den första uppsättningen av kluster och itererar förfarandet fram till konvergens. Gaynor och Bair 17 visar att detta förfarande kan ge bättre resultat än övervakad klusterbildning i vissa situationer, särskilt när resultatvariabeln endast är svagt förknippad med klusteren. Den övervakade sparse clustering proceduren liknar också den sådda k-means clustering algoritmen av Basu et al. 16 eftersom den använder de kända utfallsdata för att "så" det första steget av sparse klustering metod och sedan itererar resten av sparse kluster algoritm utan ytterligare övervägande av utfall variabeln.
Halvövervakad klusterbildning REF tar itu med problemet när de tillhandahållna uppgifterna är delvis märkta eller med andra typer av preliminär information, och målet är att försöka tilldela de omärkta proven till rätt kluster.
Semi-supervised clustering methods
{'venue': 'WIREs Comp Stat, 2013, 5(5): 349-361', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science', 'Medicine']}