Dvojitá klasifikace

Dual třídění nebo „ biclustering “ je technika dolování dat bez dozoru pro současné segmentaci řádků a sloupců matice. Formálně lze definici dvojí klasifikace vyjádřit následovně (pro typ klasifikace sloupců):

buď matrice nebo , pak se nazývá „ bicluster “ z , když pro všechny

\ mathrm {E}

\ mathrm {M} \ krát \ mathrm {N}

\ mathrm {I} \ subseteq \ mathrm {M} {\ text {,}} J \ subseteq \ mathrm {N}

\ mathrm {E} _ {{IJ}}

\ mathrm {E}

\ mathrm {E} _ {{i_ {1}, j}} = \ mathrm {E} _ {{i_ {2}, j}} = .. = \ mathrm {E} _ {{i_ {m}, j}}

j \ in J {\ text {and}} (i_ {1}, i_ {2}, ... i_ {m}) \ in \ mathrm {M}

aplikace

„ Biclustering “ se často používají v biologii - například v analýze genové exprese podle Yizong Cheng a George M. Church -, ale také v jiných oblastech, jako je komprese obrazu syntézy, lékařské analýzy - například ve studii o léčbě epilepsie by vagální stimulací , charakteristika emitentů nevyžádané pošty ( „ spam “ ), analýza pohybu, analýza reklamních pojmů na internetu ...

Typy

V různých algoritmech, které používají dvojitou klasifikaci, najdeme různé typy biclusterů:

„ Bi-cluster “ s konstantními hodnotami (a),
„ Bi-cluster “ s konstantními hodnotami v řádcích (b) nebo ve sloupcích (c),
„ Bi-cluster “ s koherentními hodnotami (d, e).

a) „ Bi-cluster “ s konstantními hodnotami

7.6	7.6	7.6	7.6	7.6
7.6	7.6	7.6	7.6	7.6
7.6	7.6	7.6	7.6	7.6
7.6	7.6	7.6	7.6	7.6
7.6	7.6	7.6	7.6	7.6

b) „ Bi-cluster “ s konstantními hodnotami v řádcích

1.2	1.2	1.2	1.2	1.2
2.1	2.1	2.1	2.1	2.1
3.2	3.2	3.2	3.2	3.2
4.1	4.1	4.1	4.1	4.1
4.2	4.2	4.2	4.2	4.2

c) „ Bi-cluster “ s konstantními hodnotami ve sloupcích

1.0	2.0	3.0	4.0	5.0
1.0	2.0	3.0	4.0	5.0
1.0	2.0	3.0	4.0	5.0
1.0	2.0	3.0	4.0	5.0
1.0	2.0	3.0	4.0	5.0

d) „ Bi-cluster “ s koherentními hodnotami (aditivní)

1.0	4.0	5.0	0,0	1.5
4.0	7.0	8.0	3.0	4.5
3.0	6.0	7.0	2.0	3.5
5.0	8.0	9.0	4.0	5.5
2.0	5.0	6.0	1.0	2.5

e) „ Bi-cluster “ s koherentními hodnotami (multiplikativní)

1.0	0,5	2.0	0.2	0,8
2.0	1.0	4.0	0,4	1.6
3.0	1.5	6.0	0,6	2.4
4.0	2.0	8.0	0,8	3.2
5.0	2.5	10.0	1.0	4.0

V písmenu d) se pojem aditivita chápe takto: ve sloupcích, v řádcích; v e) vzor je ve sloupcích a . $+ 3, -1, + 2, -3$ $+ 3, + 1, -5, + 1,5$ ${\ frac {1} {2}}, * 4, {\ frac {1} {10}}, * 4$ $* 2, * 1,5, {\ frac {4} {3}}, {\ frac {5} {4}}$

Algoritmy

Cílem algoritmů dvojí klasifikace je najít, pokud existuje, největší „ dvojklastr “ obsažený v matici maximalizací objektivní funkce. Můžeme vzít jako funkci s výše přijatými notacemi:

f_ {1} = \ left | \ mathrm {I} \ right | + \ left | J \ right |

nebo

f_ {2} = \ left | \ mathrm {I} \ right | * \ left | J \ right |

Mnoho algoritmů bylo vyvinuto zejména v bioinformatice , včetně: „ Blokové shlukování “ , CTWC ( „Spojené obousměrné shlukování “ ), ITWC ( „ Vzájemně propojené obousměrné shlukování “ ), δ-bicluster, δ-pCluster, δ-pattern , FLOC, OPC, „ Plaid Model “ , OPSMs ( „ Order- Conserving Submatrixes “ ), Gibbs, SAMBA ( „ Statistical-Algorithmic Method for Bicluster Analysis “ ), RoBA ( „ Robust Biclustering Algorithm “ ), „ Crossing Minimization “ , CMonkey , PRM, DCC, LEB ( „ Lokalizace a extrakce Biclusterů “ ), QUBIC ( „ Kvalitativní BIClustering “ ), BCCA ( „ Bi-Correlation Clustering Algorithm “ ), FABIA ( „ Faktorová analýza pro akvizici Biclusterů “ ). Některé z těchto algoritmů porovnali Doruk Bozda, Ashwin S. Kumar a Umit V. Catalyurek, pokud jde o typ hledaných vzorů.
Tyto „ biclust “ balíček nabízí sadu nástrojů pro duální zařazeni do programu R .

Související články

Poznámky a odkazy

( fr ) Tento článek je částečně nebo zcela převzat z článku Wikipedie v angličtině s názvem „ Biclustering “ ( viz seznam autorů ) .

Tran Trang, Nguyen Cam Chi, Hoang Ngoc Minh, bi-shlukování údajů o biočipu váženými stromy s nejdelší předponou - Kapitola 1 Úvod
Sara C. Madeira, Arlindo L. Oliveira, Biclustering Biologická analýza dat
(in) Cheng Y, Church GM, „ biclustering of speech data “ , Sborník příspěvků z 8. mezinárodní konference o inteligentních systémech pro molekulární biologii ,2000, str. 93–103
Yizong Cheng, George M. Church Biclustering Expression dat
Xin Sun, Qiming Hou, Zhong Ren, Kun Zhou, Baining Guo, Radiance Transfer Biclustering pro vykreslování všech frekvencí v reálném čase
Stanislav Busygin, Nikita Boyko, Panos M. Pardalos, Michael Bewernitz, Georges Ghacibeh, Biclustering EEG data od epileptických pacientů léčených stimulací nervu vagus
Kevin S. Xu, Mark Kliger, Alfred O. Hero III, Identifikace spammerů podle vzorců využití zdrojů
Keren Erez, Jacob Goldberger, Ronen Sosnik, Moshe Shemesh, Susan Rothstein, Moshe Abeles, Analýza pohybových trajektorií pomocí metody Markov Bi-Clustering
Dmitrij I. Ignatov, koncepční Biclustering pro internetovou reklamu
Stefano Lonardi, Qiaofeng Yang, Wojciech Szpankowski, Hledání náhodných projekcí
(in) Tanay A Sharan R, M a Kupiec Sahmir R „ Odhalení modularity a organizace v kvasinkové molekulární síti integrovanou analýzou vysoce heterogenních genomových dat “ , Proc Natl Acad Sci USA , sv. 101, n o 9, 2004, str. 2981-2986 ( PMID 16749936 , PMCID 14973197 , DOI 10.1073 / pnas.0308661100 )
Ahsan Abdullah, dolování dat pomocí paradigmatu minimalizace křížení
(in) Reiss DJ, NS Baliga, R Bonneau, „ Integrované biclusterování heterogenních genomových datových souborů pro odvození globálních regulačních sítí “ , BMC Bioinformatics , sv. 2, n O 7, 2006, str. 280–302 ( PMID 16749936 , PMCID 1502140 , DOI 10.1186 / 1471-2105-7-280 )
(en) Hochreiter S, Bodenhofer U, Heusel M, Mayr A, Mitterecker A, Kasim A, Khamiakova T, Van Sanden S, Lin D, Talloen W, Bijnens L, Göhlmann HWH, Shkedy Z Clevert DA, „ FABIA: faktor analýza pro získání biclusterů “ , Bioinformatics , sv. 26, N O 12 2010, str. 1520–1527 ( PMID 20418340 , PMCID 2881408 , DOI 10.1093 / bioinformatika / btq227 )
Doruk Bozda, Ashwin S.Kumar a Umit V. Catalyurek, srovnávací analýza Biclusterových algoritmů
Sebastian Kaiser, Friedrich Leisch, Soubor nástrojů pro Biclusterovu analýzu v R.