Csoportosítás

Algoritmusok

Sziasztok!
Beleütköztem egy olyan problémába, amit már egy jó hete nem tudok megoldani.
A bemenő adatom egy nxn es mátrix, ami 0-kal és 1-kel van feltöltve. A sorok és az oszlopok betegségeket reprezentálnak, és ott van a mátrixban 1, ahol a két betegség összetartozását kimutattuk a kutatásainkban. Szóval valami ilyesmi: 


+ A B C D E
A - 0 0 1 1
B 0 - 1 0 0
C 0 0 - 0 0
D 1 0 0 - 0
E 0 0 0 1 -

Azt szeretném kérdezni, hogy van e arra valami algoritmus, amivel ebből kinyerhetem a csoportokat. A példában szereplő mátrix két csoportot ad:
A D E illetve B C. Tehát igazából csak az 1 nek van információértéke (ami két betegség összecsoportosítását jelenti, a 0 nak nincs, mert lehet, hogy csak nem tudtuk kimutatni az összetartozást.
Bármilyen ötletet szívesen fogadnék.

Csaba

  • 1481 megtekintés

( machobymb v | 2008. 01. 17., cs – 08:49 )

Ez nem egy szimmetrikus mátrix lenne?
Amit leírtál, aszerint így nézne ki a mátrix:

+ A B C D E
A - 0 0 1 1
B 0 - 1 0 0
C 0 1 - 0 0
D 1 0 0 - 1
E 1 0 0 1 -

Hogyan tárolod a tömböt?
Szerintem úgy kellene, hogy megnézed melyik sorban/oszlopban van 1-es, ha talál, akkor összetartoznak, ha nem, akkor nem. Az én olvasatomban ez nem egy problémás dolog lenne.
Kicsit bővebben írhatnál róla.

OK, valóban szimmetrikus.

Vedd figyelembe, hogy nem vagyok programozó, így gőzöm nincs, hogy milyen algoritmus csinálna egy ilyen mátrixból listák listáját.

Az igazi mátrix, amivel dolgozom, 158x158 méretű, és valóban szimmetrikus. Viszont nem tudom előre, hogy hány csoportom lesz a végén.

Mint mondtam, nem mindenhol szerepel 1, ahol a csoportosítás szerint lennie kellene, így nem elég, ha azt mondom, hogy A val egy csoportban vannak azok, ahol az A oszlopban 1 van. Mert lehet, hogy az A-E összetartozást nem mutattuk ki, csak az A-D-t és a D-E-t, A,D,E mégis egy csoportba kell, hjogy kerüljön.

Remélem, így világosabb.

Csaba

Ez nekem ugy tunik, hogy egy tranzitiv lezaras algoritmus lenne. Ilyenbol meg nem lattam _igazan_ hatekonyat.
Mondjuk lehet olyat csinalni, hogy ez a matrix megfelel egy iranyitatlan grafnak. Felrajzolod a grafot, es az osszefuggo komponensek adnak egy csoportot.
Vagy nem vizualizalni kell?

Az összefüggő komponensek kinyerése, ha valóban ez a feladat, viszonylag egyszerű.

1. átalakítod a gráfot éllistás reprezentációra
2. felveszel egy unió-holvan adatstruktúrát n ponttal
3. minden (i,j) élre végzel egy unió(i,j) összevonást
4. a végén i és j akkor van egy komponensben, ha holvan(i)=holvan(j)

Az unió-holvan adatszerkezetről egy kis infó + pszeudokód:
http://en.wikipedia.org/wiki/Disjoint-set_data_structure

( mazursky | 2008. 01. 17., cs – 09:23 )

Pár dolog jutott eszembe:

Mivel ez a mátrix szimmetrikus, így elegendő lenne a felső háromszöget tárolni. Azaz ez n adat esetén (ahol n az oszlopok száma = sorok száma) szumma i megy egytől n-ig i, tehát 1+2+3+...+(n-1)+n, és ez jóval kisebb, mint n*n. kb a fele.

De ha maradunk a klasszikus négyzet alakú mátrixnál, akkor pedig egyszerűnek látszik a megoldás (valami Pascal féle kódban):

i=oszlop
j=sor

for i= 1 to n do
for j= 1 to n do
if matrix(i,j)=1 then writeln(i,j,"betegségek összetartoznak")

de ha gyorsabb lefutást akarsz:

for i= 1 to n do
for j= 1 to i do
if matrix(i,j)=1 then writeln(i,j,"betegségek összetartoznak")

ez kb fele-idő alatt lefut

De ez csak két elemű listában adja vissza...

talán azért segítettem

/mazursky

Igen, eddig még én is eljutottam, az a kérdés, hogy ha ki tudom listázni az összetartozó párokat, akkor abból hogyan csinálok csoportokat.

Vedd figyelembe, hogy a valódi problémánál több mint 600 összetartozó párom van. A párokat hogyan konvertálom csoportokká?

Csaba

( Tyra3l | 2008. 01. 17., cs – 09:28 )

Szerintem vagy a matrix rossz, vagy a magyarazat.
Mert ha AE-nel 1-es van, akkor EA-nal is 1-esnek kellene lennie, ergo szimmetrikus matrix lenne.
De mivel nem az, ezert azt tudom elkepzelni, hogy nem azt mutatja a matrix, hogy mely betegsegek tartoznak ossze, hanem ez valami fuggosegi matrix.
Tehat A betegseg okozhatja E betegseget, de E betegseg mar nem noveli A betegseg kialakulasanak veszelyet.
Ebben az esetben csak annyi kellene, hogy a matrixot egyszer egyik tengely, masszor a masik szerint jarod be, es megnezed, hogy a masik "dimenzioban" levo parja egyes-e.

Tyrael

tehat akkor nem az a problemad, hogy megkeresd a parokat, hanem hogy az osszefuggoket csoportba rendezt.
Tehat pl. ha:
A betegseg egyutt jarhat B-vel
B betegseg egyutt jarhat F-fel
F betegseg egyutt jarhat C-vel
Akkor ABCF az egy csoport.
Jol ertem a feladatot?

Ugye ebben az esetben min 1 csoportod lesz (ha minden mindennel osszefugg), max N (minden betegseg fuggetlen).
Lenne 1 tombom, amiben tarolnam, hogy mely betegseg nem lett meg besorolva egy csoportba (ugye a fenti relacio miatt 1 betegseg, csak egy csoport resze lehet, mert 1 kozos elem osszevonja azokat a csoportokat, amelyeknek resze)

elkezdtem irni egy pszeudo kodot ra, csak kozben melozni is kell, majd irok kesobb.

Tyrael

naszoval addig megy a kereses, amig el nem fogynak a nem besorolt elemek(aminek nincs barja, az egy olyan csoportba kerul, aminek o az egyeduli eleme, szoval el fognak fogyni).
rafut a ciklus az elso be nem sorolt elemre, letrehoz egy uj csoportot.
lenne egy fuggvenyunk, ami kikeresi, hogy a matrixban a parameterul kapott elem mely mas elemekkel all parban(ahol 1-es van).
ezutan berakja az uj csoportba a keresendo elemet, es a parjait(csak azokat, amelyek nem szerepelnek meg.).
ezutan a kapott uj parokat vegigjarja, es megnezi hogy a mar meglevo csoportokban (sajat magan kivul) melyikben szerepel, es azokbol az elemeket athelyezi ide (csak azokat az elemeket, amelyek meg nincsenek benne), majd torli azt a csoportot(csoportokat), majd az ujjonnan besorolt elemekre megint osszesit, egeszen addig, amig nem kerul uj elem az aktualis csoportba, vegul torli a be nem sorolt elemek kozul az aktualisat.

tudsz adni egy nagyobb peldat(akar privatban is), akkor irok ra valami scriptet, mert muszaj tesztelnem :)

Tyrael

( bazso | 2008. 01. 17., cs – 10:59 )

Veszed az A-val kezdődő felső háromszöget, elkezdesz lépegetni az A sorában. Ha egyest találtál, akkor az adott oszlopban elkezdesz lefelé haladni, amíg egyest nem találsz, akkor az adott sorban kezdesz jobbra menni, és így tovább. A lényeg, hogy csak jobbra és lefelé kell menni, mert ha az adott ponttól balra lenne odatartozó pont, abba korábban beleütköztél volna. Ha a felső háromszög alját, vagy a jobb szélt elérted, az adott csoportnak vége van, folytathatod ugyanezt a B sarkú felső háromszöggel (duplikátumok elkerülése érdekében hatékonyabb, ha nem a B, hanem az előző csoportoknak nem tagja című legkisebb elemmel kezded).

Üdv,
BaZso

UI: ha nincs igazam kritikát elfogadok, meló közben csak 3 percem volt kiötleni.

Az a baj, hogy nem mindenhol szerepel is ott az 1, ahol két betegség összetartozik, mert lehet mérési hiba, és akkor 0 van. Ezért az eredmény olyan csoportok lesznek, amik között még mindíg lehetnek közös elemek. Ezzel viszont visszajutottunk ahhoz a problémához, hogy ezeket a csoportokat hogyan fogom összevonni.
Csaba

Nem értem a problémát. Ha nincs ott egyes, akkor abban a pillanatban nem tartozik össze. Ha később rájösz, hogy mégis van ott egyes, módosítod a mátrixot, és újrafuttatod az algoritmust. Ha ez sok (bár 600 elem nem tétel) és kész csoportokat akarsz összefogni, akkor az a két csoport aminek egy egy eleme közé egyest akarsz rakni rögtön összefogható egy csoporttá.

Üdv,
BaZso

Szerintem ezen a példán kipróbálva nem jó: 


+ A B C D E
A - 0 0 1 1
B 0 - 1 0 0
C 0 1 - 0 0
D 1 0 0 - 0
E 1 0 0 0 -

Az algoritmusod ebből ezeket a csoportokat csinálja:
A D
B C
A E
Holott a helyes megfejtés A D E, B C
Az ok, hogy a mátrixban nem szerepel az E-D nél 1, mérési hibából.
Félreértettelek?
Csaba

Igazad van. így vizualizálva viszont van egy még egyszerűbb megoldás is (bár az előző után nincs akkora arcom :-) )

A csoportjaid a sorok, csak vannak üres csoportok:
A csoport: ADE
B csoport: BC
C csoport: -
D csoport: -
E csoport: -

A korábbi pszeudo példának megfelelően:

matrix[n][n]
csoport[n][n]=0 #minden elemet kinullázol,így könnyebb kezelni
k=0
for i=1 to n do
for j=i to n do
if( matrix[i][j] == 1 ) csoport[i][k] = j; k++; fi
done
done

végeredmény egy kétdimenziós tömb, ami a csoport nevével címződik (1, 2 ...) és sorban, kihagyás nélkül felsorolja az elemeket, azaz ha az első elem 0, üres a csoport, ha csak az x-edik, akkor ott a csoport vége.

Üdv,
BaZso

Ahhoz, hogy algoritmust írj, előbb definiáli kell a problémát. A postjaid alapján kb ez a definíciód:

A szimmetrikus 0-1-eket tartalmazó mátrixot mint gráfot is elképzelhetjük, ahol a csúcsok a mátrix oszlop és sorcímkéinek felelnek meg, a 0 a nincs él, az 1 a van él. A gráfon egyszerűbb megfogalmazni a feleadatot.

Ezen a gráfon definiálni kell először, hogy milyen egy csoport.

Lehetséges definíciók: A csoport csúcsai által kifeszített részgráf
1. Teljes gráf
2. összefüggő
3. 1. és 2. között valahol, tetszőleges szabályrendszerrel

Az összes, tovább nem bővíthető csoport megkeresése a feladat, ugye?
(A 2. esetet feltételezve minden csúcsot pontosan egy csoport fog tartalmazni)

ezt a feladatot gráfok körében úgy hivják hogy Erősen összefüggő komponensek keresése.

és nini, ott egy gráf szomszédsági mátrixa.

http://petra.hos.u-szeged.hu/~csaba/szakmai/algoritmusok/4/2.html legalja.

a feladat nekem nagyon tetszik, úgyhogy szivesen segitek ha van még kérdés.

Köszönöm ezt a kommentet, sokat segített.

Igen, ha a mátrixot gráffá alakítom, akkor szemléletesebb a feladat. Keresem a gráfnak az összefüggő részgráfjait. Ezeknek nem kellenek teljesnek lenniük önmagunkon belül. Az a probléma, hogy a kérdés ilyen átfogalmazásával sem kerültem közelebb a megoldáshoz. (Értsd az egy csoportba tartozó betegségek listájához.)

Csaba

( zeroms | 2008. 01. 17., cs – 11:36 )

Csak egy otlet, esetleg ha hagynank a matrixos felirast es talalnank egy modszert, amivel ezt egy adatbazisban lehetne tarolni, ami eleg gyorsan es hatekonyan vegeznel el keresesek formajaban a csoportositasokat.

Sajnos nincs idom jobban belegondolni, de ugy erzem ez is egy jarhato ut
_______________________________________________________
Type cat vmlinuz > /dev/audio to hear the Voice of God.

( apal v | 2008. 01. 17., cs – 12:19 )

Egy egyszeru implementacio: itten. Egy c program ami stdin-rol olvas be nemnegativ egesz szamparokat, majd ha elfogy az stdin, akkor kiirja a csoportokat. Maga az algoritmus relative nagyon egyszeru, hogyha van egy olyan konyvtarad vagy barmi ized, ami Ordo(log(N)) idoben tud kezelni egesz szamokbol allo tablakat (azaz egesz szamokat beszurszhatsz, kereshetsz ill. torolhetsz log(N) idoben). Igy az egesz csoportositas ( Ordo(K*log(max)) ido alatt megvan, ahol K a szamparok (1-es matrixelemek) szama, max pedig 158 ebben az esetben.

Lehet hogy van megegyszerubb algoritmus is, bar szerintem az alapproblema nem annyira nyilvanvalo, hogyha az ember gyors megoldast is szeretne...

A.

( dii | 2008. 01. 17., cs – 12:24 )

Ha a gráf módszer nem jön be íme a tenyeres-talpas:

1. Kigyűjtöd és eltárolod a párokat (ahol van egy): AD, AE, BC

2. Végignyálazod a párokat, hogy hol van egyező és összevonod.
Tehát fogod elsőként az AD-t és megnézed hol van még A. Megtalálod az AE-t. Akkor abból kiveszed az E-t és az AD-hez hozzáteszed. Az AE-t törlöd a listáról. Ha az összes A-val végeztél jöhet a következő az első elemből (D), aztán persze a hozzácsatoltakat is meg kell nézni (E). Ha nincs több összekapcsolódás, jöhet a második elem, ami itt már a BC. És így tovább.

Mivel nincs sok adat, szerintem ez bőven járható út.

( csortu v | 2008. 01. 18., p – 08:31 )

Köszönöm a segítséget mindenkinek, végül Tyra3l által javasolt algoritmust implementáltam (perlben, pedig R ben szerettem volna).

Kipróbáltam bazso módszerét is, de hibás a gondolatmenet, bizonyos esetekben megint csak nem jól csoportosít.

A gráfos megoldáson még dolgozom, elsősorban ezért, mert R-ben könnyűnek tűnik az implementáció (az igraph csomag segítségével, kösz a HUPon is jelenlévő alkotóknak!) másrészt mert majd alighanem vizualizálni is kell majd az eredményeket ha lesz ebből cikk, ahhoz meg nagyon jó ötlet a gráfos ábrázolás.

Mégegyszer köszönök minden segítséget!

Csaba