Seskupování

Biclustering , block clustering , [1] co - clustering , také dvoumodální clustering [2] [3] je technika dolování  dat , která umožňuje současné shlukování řádků a sloupců matice . Tento termín byl poprvé navržen Mirkinem, [4] i když samotná metoda byla vytvořena mnohem dříve [4] (JA Hartigan [5] ).

Vezmeme-li jako vstup sadu řádků ve sloupcích (matici velikosti ), generuje algoritmus biclustering biclustery, podmnožinu řádků, které vykazují podobné chování prostřednictvím podmnožiny sloupců.

Historie vývoje

Biclustering poprvé představil JA Hartigan v roce 1972 [6] . Termín biclustering později zavedl Mirkin. Tento algoritmus nebyl zobecněn až do roku 2000, kdy Y. Cheng a GM Church navrhli algoritmus biklastrování založený na rozptylu a aplikovali jej na data biologické exprese genů [7] . Jejich článek je stále jednou z nejdůležitějších literatur v oblasti biklastrování genové exprese.

V letech 2001 a 2003 navrhl IS Dhillon dva algoritmy, které aplikují biclustering na soubory a slova. Jedna z verzí byla založena na rozdělení bipartitních spektrálních grafů [8] . Druhý byl založen na teorii informace. Dhillon předpokládal, že vzájemná ztráta informace během biclusteringu je KL ( Kulback-Leibler distance ) mezi P a Q. P znamená distribuci souborů a charakteristických slov před biklusterováním. Q je zase distribuce po shlukování. KL-vzdálenost je potřebná jako míra rozdílu mezi dvěma náhodnými distribucemi. KL = 0, když jsou obě rozdělení stejná, a zvyšuje se, když se rozdíl zvětšuje [9] . Cílem algoritmu tedy bylo minimalizovat KL vzdálenost mezi P a Q. V roce 2004 použil A. Banerjee váženou Bregmanovu vzdálenost místo KL vzdálenosti k vývoji biklastrovacího algoritmu vhodného pro jakýkoli typ matice, na rozdíl od Algoritmus KL [10] .

Za účelem shlukování více než dvou typů objektů rozšířil Bekkerman v roce 2005 vzájemnou informaci v Dhillonově teorému z jednoho páru na mnoho párů.

Obtížnost úkolu

Složitost problému biklastrování závisí na konkrétní formulaci, zejména na funkci použité k hodnocení kvality výsledného biclusteru. Nejzajímavější varianty těchto problémů jsou NP-úplné a vyžadují velký výpočetní výkon nebo použití heuristických přístupů [11] [12] .

Typy klastrů

Různé algoritmy biklusteru mají různé definice biklusteru [12]

Hlavní typy:

  1. Bicluster s konstantními hodnotami (a),
  2. Bicluster s konstantními hodnotami v řádcích (b) nebo sloupcích (c),
  3. Sdružení s propojenými hodnotami (d, e).

Viz také

Poznámky

  1. ↑ G. Govaert, M. Nadif. Blokové shlukování s modely bernoulliho směsi: Porovnání různých přístupů,  (anglicky)  // Computational Statistical and Data Analysis  : deník. - Elsevier, 2008. - Sv. 52 . - str. 3233-3245 .
  2. ↑ G. Govaert, M. Nadif. Co-clustering: modely, algoritmy a aplikace  (anglicky) . - ISTE, Wiley, 2013. - ISBN 978-1-84821-473-6 .
  3. ↑ Van Mechelen I., Bock HH, De Boeck P. Dvourežimové metody shlukování: strukturovaný přehled  (nedefinováno)  // Statistické metody v lékařském výzkumu . - 2004. - T. 13 , č. 5 . - S. 363-394 . - doi : 10.1191/0962280204sm373ra . — PMID 15516031 .
  4. ↑ 1 2 Mirkin, Boris. Matematická klasifikace a shlukování . - Kluwer Academic Publishers , 1996. - ISBN 0-7923-4159-7 .  
  5. ↑ Hartigan JA Přímé shlukování datové matice  //  Journal of the American Statistical Association  : journal. - Americká statistická asociace, 1972. - Sv. 67 , č. 337 . - str. 123-129 . - doi : 10.2307/2284710 . — .
  6. ↑ Hartigan J A. Přímé shlukování datové matice[J]. Journal of the American Statistical Association, 1972, 67(337): 123-129. . Získáno 30. dubna 2016. Archivováno z originálu 15. března 2022.
  7. ↑ https://www.cs.princeton.edu/courses/archive/fall03/cs597F/Articles/biclustering_of_expression_data.pdf Archivováno 4. března 2016 ve Wayback Machine Cheng Y, Church G M. Biclustering of expression data[C] / /Ismb. 2000, 8:93-103.
  8. ↑ Dhillon I S. Společné shlukování dokumentů a slov pomocí bipartitního dělení spektrálních grafů[C]//Sborník ze sedmé mezinárodní konference ACM SIGKDD o objevování znalostí a dolování dat. ACM, 2001: 269-274.
  9. ↑ Dhillon IS, Mallela S, Modha D S. Informační-teoretický co-clustering[C]//Sborník z 9. mezinárodní konference ACM SIGKDD o KKluwer Academic Publishersnowledge discovery and data mining. ACM, 2003: 89-98.
  10. ↑ Banerjee A, Dhillon I, Ghosh J, et al. Zobecněný přístup maximální entropie ke společnému shlukování Bregman a aproximaci matic[C]//Sborník z desáté mezinárodní konference ACM SIGKDD o objevování znalostí a dolování dat. ACM, 2004: 509-514.
  11. ↑ Peeters R. Problém s maximální hranou biclique je NP-úplný[J]. Discrete Applied Mathematics, 2003, 131 (3): 651-654. . Získáno 30. dubna 2016. Archivováno z originálu 24. září 2015.
  12. ↑ 1 2 . Madeira SC, Oliveira AL Biclustering Algorithms for Biological Data Analysis: A Survey  //  IEEE Transactions on Computational Biology and Bioinformatics: journal. - 2004. - Sv. 1 , ne. 1 . - str. 24-45 . - doi : 10.1109/TCBB.2004.2 . — PMID 17048406 .

Literatura

Odkazy