Biklustring
Biklustring , blockklustring , Co-clustering eller tvålägesklustring är en datautvinningsteknik som möjliggör samtidig klustring av rader och kolumner i en matris . Termen introducerades först av Boris Mirkin för att namnge en teknik som introducerades många år tidigare, 1972, av JA Hartigan.
Givet en uppsättning sampel representerade av en -dimensionell funktionsvektor, kan hela datasetet representeras som rader i kolumner (dvs. en matris). Biclustering-algoritmen genererar Biclusters. En bikluster är en undergrupp av rader som uppvisar liknande beteende över en undergrupp av kolumner, eller vice versa.
Utveckling
Biclustering introducerades ursprungligen av JA Hartigan 1972. Termen "Biclustering" användes senare och förfinades av Mirkin. Denna algoritm generaliserades inte förrän 2000, när Y. Cheng och GM Church föreslog en Biclustering-algoritm baserad på varians och tillämpade den på biologiska genuttrycksdata.
2001 och 2003 publicerade IS Dhillon två algoritmer som tillämpar Biclustering på filer och ord. En version baserades på partitionering av tvådelade spektralgrafer. Den andra baserades på informationsteori. Dhillon antog att förlusten av ömsesidig information under Biclustering var lika med Kullback–Leibler-avståndet (KL-distans) mellan P och Q. P representerar distributionen av filer och funktionsord före Biclustering, medan Q är fördelningen efter Biclustering. KL-avstånd är för att mäta skillnaden mellan två slumpmässiga fördelningar. KL = 0 när de två fördelningarna är lika och KL ökar när skillnaden ökar. Alltså var syftet med algoritmen att hitta det minsta KL-avståndet mellan P och Q. År 2004 använde Arindam Banerjee ett viktat Bregman-avstånd istället för KL-avstånd för att designa en Biclustering-algoritm som var lämplig för alla slags matriser, till skillnad från KL-distansalgoritmen.
För att gruppera mer än två typer av objekt utökade Bekkerman 2005 den ömsesidiga informationen i Dhillons teorem från ett enda par till flera par.
Komplexitet
Komplexiteten av Biclustering-problemet beror på den exakta problemformuleringen, och särskilt på meritfunktionen som används för att utvärdera kvaliteten på ett givet Bicluster. De mest intressanta varianterna av detta problem är dock NP-kompletta . NP-komplett har två villkor. I det enkla fallet att det endast finns ett element a ( i , j ) antingen 0 eller 1 i den binära matrisen A, är en Bicluster lika med en biclique i motsvarande tvådelade graf . Den maximala storleken Bicluster är ekvivalent med den maximala kantbicliquen i den tvådelade grafen. I det komplexa fallet används elementet i matris A för att beräkna kvaliteten på ett givet Bicluster och lösa den mer begränsade versionen av problemet. Det kräver antingen stor beräkningsansträngning eller användning av förlustheuristik för att kortsluta beräkningen.
Typer av bikluster
Bikluster med konstanta värden (a)
När en Biclustering-algoritm försöker hitta ett Bicluster med konstant värde, ordnar den om raderna och kolumnerna i matrisen för att gruppera liknande rader och kolumner, och så småningom gruppera Biclusters med liknande värden. Denna metod är tillräcklig när data är normaliserade. En perfekt konstant Bicluster är en matris(I,J) där alla värden a(i,j) är lika med en given konstant μ. I materiella data kan dessa poster a(i,j) representeras med formen n(i,j) + μ där n(i,j) anger bruset . Enligt Hartigans algoritm, genom att dela upp den ursprungliga datamatrisen i en uppsättning Biclusters, används varians för att beräkna konstanta Biclusters. Därför kan ett perfekt Bicluster definieras ekvivalent som en matris med en varians på noll. För att förhindra partitionering av datamatrisen i Biclusters med endast en rad och en kolumn; Hartigan antar att det till exempel finns K Biclusters inom datamatrisen. När datamatrisen är uppdelad i K Biclusters slutar algoritmen.
Bikluster med konstanta värden på rader (b) eller kolumner (c)
Till skillnad från Biclusters med konstant värde kan dessa typer av Biclusters inte utvärderas enbart baserat på variansen i deras värden. För att slutföra identifieringen ska kolumnerna och raderna normaliseras först. Det finns dock andra algoritmer, utan normaliseringssteget, som kan hitta Biclusters som har rader och kolumner med olika tillvägagångssätt.
Bikluster med sammanhängande värden (d, e)
För Biclusters med koherenta värden på rader och kolumner bör en övergripande förbättring av algoritmerna för Biclusters med konstanta värden på rader eller på kolumner övervägas. Denna algoritm kan innehålla analys av varians mellan grupper, med hjälp av kovarians mellan både rader och kolumner. I Cheng och Churchs teorem definieras en Bicluster som en delmängd av rader och kolumner med nästan samma poäng. Likhetspoängen används för att mäta koherensen av rader och kolumner.
|
|
|
|
|
Relationen mellan dessa klustermodeller och andra typer av kluster såsom korrelationskluster diskuteras i.
Algoritmer
Det finns många Biclustering- algoritmer utvecklade för bioinformatik , inklusive: blockkluster, CTWC (Coupled Two-Way Clustering), ITWC (Interrelated Two-Way Clustering), δ-bicluster, δ-pCluster, δ-pattern, FLOC, OPC, Plaid Model , OPSMs (Order-preserving submatrises), Gibbs, SAMBA (Statistical-Algorithmic Method for Bicluster Analysis), Robust Biclustering Algorithm (RoBA), Crossing Minimization, cMonkey, PRMs, DCC, LEB (Localize and Extract Biclusters), QUBIC (QUalitative BIClustering) ), BCCA (Bi-Correlation Clustering Algorithm) BIMAX, ISA och FABIA ( Factor analysis for Bicluster Acquisition), runibic och nyligen föreslagna hybridmetoden EBIC (evolutionary-based Biclustering), som visade sig upptäcka flera mönster med mycket hög noggrannhet. På senare tid föreslås IMMD-CC som är utvecklad utifrån konceptet iterativ komplexitetsreduktion. IMMD-CC kan identifiera co-cluster centroider från mycket sparsam transformation erhållen genom iterativ multi-mode diskretisering.
Biklustringsalgoritmer har också föreslagits och använts i andra tillämpningsområden under namnen co-clustering, bi-dimensional clustering och subspace clustering.
Med tanke på den kända vikten av att upptäcka lokala mönster i tidsseriedata . Nyligen genomförda förslag har tagit itu med Biclustering-problemet i det specifika fallet med tidsseriegenexpressionsdata . I det här fallet kan de intressanta biklustrarna begränsas till de med sammanhängande kolumner. Denna begränsning leder till ett löst problem och möjliggör utveckling av effektiva uttömmande uppräkningsalgoritmer såsom CCC-Biclustering och e -CCC-Biclustering. De ungefärliga mönstren i CCC-Biclustering-algoritmer tillåter ett givet antal fel, per gen, relativt en uttrycksprofil som representerar uttrycksmönstret i Bicluster. Algoritmen för e-CCC-Biclustering använder ungefärliga uttryck för att hitta och rapportera alla maximala CCC-Bicluster genom en diskretiserad matris A och effektiva strängbearbetningstekniker.
Dessa algoritmer hittar och rapporterar alla maximala bikluster med koherenta och sammanhängande kolumner med perfekta/ungefärliga uttrycksmönster, i tidslinjär/ polynom som erhålls genom att manipulera en diskretiserad version av den ursprungliga uttrycksmatrisen i storleken på tidsseriegenexpressionsmatrisen med hjälp av effektiv strängbearbetningstekniker baserade på suffixträd . Dessa algoritmer används också för att lösa problem och skissa analysen av beräkningskomplexitet.
Vissa nya algoritmer har försökt inkludera ytterligare stöd för Biclustering rektangulära matriser i form av andra datatyper , inklusive cMonkey.
Det pågår en debatt om hur man ska bedöma resultaten av dessa metoder, eftersom Biclustering tillåter överlappning mellan kluster och vissa algoritmer tillåter uteslutning av svårförenliga kolumner/villkor. Alla tillgängliga algoritmer är inte deterministiska och analytikern måste vara uppmärksam på i vilken grad resultaten representerar stabila minima . Eftersom detta är ett oövervakat klassificeringsproblem gör avsaknaden av en guldstandard det svårt att upptäcka fel i resultaten. Ett tillvägagångssätt är att använda flera Biclustering-algoritmer, där majoriteten eller supermajoriteten röstar bland dem för att avgöra det bästa resultatet. Ett annat sätt är att analysera kvaliteten på skiftnings- och skalningsmönster i Biclusters. Biklustring har använts inom området text mining (eller klassificering) som populärt kallas co-clustering. Textkorpus representeras i vektorform som en matris D vars rader betecknar dokumenten och vars kolumner betecknar orden i ordboken. Matriselement D ij betecknar förekomsten av ord j i dokument i. Samklustringsalgoritmer används sedan för att upptäcka block i D som motsvarar en grupp av dokument (rader) som kännetecknas av en grupp ord (kolumner).
Textklustring kan lösa det högdimensionella glesa problemet, vilket innebär att text och ord samlas på samma gång. När vi grupperar text måste vi tänka på inte bara ordinformationen, utan också informationen om ordkluster som komponerades av ord. Sedan, i enlighet med likheten mellan funktionsord i texten, kommer så småningom att klusta karaktärsorden. Detta kallas co-clustering. Det finns två fördelar med samklustring: den ena är klustring av testet baserat på ordkluster kan extremt minska dimensionen av klustring, det kan också vara lämpligt att mäta avståndet mellan testerna. För det andra är att bryta mer användbar information och kan få motsvarande information i testkluster och ordkluster. Denna motsvarande information kan användas för att beskriva typen av texter och ord, samtidigt kan resultatet av ordklustring också användas för textutvinning och informationssökning.
Flera tillvägagångssätt har föreslagits baserat på informationsinnehållet i de resulterande blocken: matrisbaserade tillvägagångssätt som SVD och BVD, och grafbaserade tillvägagångssätt. Informationsteoretiska algoritmer tilldelar iterativt varje rad till ett kluster av dokument och varje kolumn till ett kluster av ord så att den ömsesidiga informationen maximeras. Matrisbaserade metoder fokuserar på nedbrytning av matriser i block så att felet mellan den ursprungliga matrisen och de regenererade matriserna från nedbrytningen minimeras. Grafbaserade metoder tenderar att minimera skärningarna mellan klustren. Givet två grupper av dokument d 1 och d 2 kan antalet klipp mätas som antalet ord som förekommer i dokument i grupperna d 1 och d 2 .
På senare tid har (Bisson och Hussain) föreslagit ett nytt tillvägagångssätt för att använda likheten mellan ord och likheten mellan dokument för att samklusta matrisen. Deras metod (känd som χ-Sim , för korslikhet) är baserad på att hitta dokument-dokument-likhet och ord-ord-likhet, och sedan använda klassiska klustringsmetoder såsom hierarkisk klustring . Istället för att uttryckligen gruppera rader och kolumner växelvis, överväger de förekomster av ord av högre ordning, med hänsyn till de dokument där de förekommer. Sålunda beräknas likheten mellan två ord utifrån de dokument där de förekommer och även de dokument där "liknande" ord förekommer. Tanken här är att två dokument om samma ämne inte nödvändigtvis använder samma uppsättning ord för att beskriva det, utan en delmängd av orden och andra liknande ord som är karakteristiska för det ämnet. Detta tillvägagångssätt att ta högre ordningslikheter tar hänsyn till den latenta semantiska strukturen av hela korpusen med resultatet av att generera en bättre klustring av dokumenten och orden.
I textdatabaser, för en dokumentsamling definierad av ett dokument efter term D-matris (av storlek m gånger n, m: antal dokument, n: antal termer) ger den täckkoefficientbaserade klustringsmetodologin samma antal kluster både för dokument och termer (ord) med hjälp av ett dubbelstegs sannolikhetsexperiment. Enligt begreppet täckningskoefficient kan antalet kluster också grovt uppskattas med följande formel där t är antalet poster som inte är noll i D. Observera att i D måste varje rad och varje kolumn innehålla minst ett element som inte är noll.
I motsats till andra tillvägagångssätt är FABIA en multiplikativ modell som antar realistiska icke-Gaussiska signalfördelningar med tunga svansar . FABIA använder välkända modellvalstekniker som variationsmetoder och tillämpar det Bayesianska ramverket. Det generativa ramverket tillåter FABIA att bestämma informationsinnehållet i varje Bicluster för att separera falska Biclusters från sanna Biclusters.
Se även
Andra
- NK Verma, S. Bajpai, A. Singh, A. Nagrare, S. Meena, Yan Cui, "A Comparison of Biclustering Algorithms" i International conference on Systems in Medicine and Biology (ICSMB 2010) i IIT Kharagpur Indien, s. 90 –97, 16–18 dec.
- J. Gupta, S. Singh och NK Verma "MTBA: MATLAB Toolbox for Biclustering Analysis", IEEE Workshop on Computational Intelligence: Theories, Applications and Future Directions", IIT Kanpur Indien, s. 148–152, juli 2013.
- A. Tanay. R. Sharan och R. Shamir, "Biclustering Algorithms: A Survey", i Handbook of Computational Molecular Biology , redigerad av Srinivas Aluru , Chapman (2004)
- Kluger Y, Basri R, Chang JT, Gerstein MB (2003). "Spektral biklustring av mikroarraydata: samklustring av gener och villkor" . Genomforskning . 13 (4): 703–716. doi : 10.1101/gr.648603 . PMC 430175 . PMID 12671006 .
- Adetayo Kasim, Ziv Shkedy, Sebastian Kaiser, Sepp Hochreiter, Willem Talloen (2016), Applied Biclustering Methods for Big and High-Dimensional Data Using R, Chapman & Hall/CRC Press
- Orzechowski, P., Sipper, M., Huang, X., & Moore, JH (2018). EBIC: en evolutionärt baserad parallell biklustringsalgoritm för mönsterupptäckt. Bioinformatik .