[es] - Slicnost vectora/sekvenci

onako

Član broj: 256314
Poruke: 75
*.dynamic.isp.telekom.rs.

Profil

^{07.03.2011. u 11:28 - pre 172 meseci}

Date su dve sekvence iste duzine(niz brojeva, vektori), i treba odrediti koeficijent njihove 'slicnosti' PO INDEXU.
Na primer:
A=[1,4,5,6,7,2,1]
B=[1,4,5,0,0,0,1]
Prilozeni nizovi su prilicno slicni (razlikuju se u 3 unosa). Permutacija elemenata B si znacila manju slicnost, jer je poredjenje
po indexu (prvi s prvim, ...). Uzimanje u obzir unije, razlike,... bi znacilo zanemarivanje indexa. Isto, isti elementi na prvom, drugom, trecem,..
indexu bi zanemarivali absolutnu razliku; npr. B sa svim devetkama je blizi A nego B sa svim dvadeseticama.
Trenutno, slicnost izrazavam
sledecim:

no, nisam siguran da je ovako jednostavna formula dovoljna da precizno odgovori koja je od 2 sekvence slicnija trecoj, jer, pored indexa,
zavisi i od magnitude.
Drugaciji predlozi su dobrodosli. Naravno, ukoliko se problem moze interpretirati linearnom algebrom, resenja cu uzeti u obzir.
Zahvaljujem

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8704
89.216.32.*

+2801 Profil

Re: Slicnost vectora/sekvenci

^{07.03.2011. u 11:34 - pre 172 meseci}

Koja je funkcija najpodesnija za neku potrebu zavisi od same potrebe.

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu

onako

Član broj: 256314
Poruke: 75
*.dynamic.isp.telekom.rs.

Profil

Re: Slicnost vectora/sekvenci

^{07.03.2011. u 11:42 - pre 172 meseci}

Hvala na razmatranju.
Od pomoci bi bilo dati konkretan predlog.

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8704
89.216.32.*

+2801 Profil

Re: Slicnost vectora/sekvenci

^{07.03.2011. u 12:18 - pre 172 meseci}

Pa, napiši za šta ti to treba, pa da vidimo šta bi ti najviše odgovaralo. Nisi dao dovoljno informacija na osnovu kojih bi se mnoglo porediti šta je bolje, a šta gore.

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu

onako

Član broj: 256314
Poruke: 75
*.dynamic.isp.telekom.rs.

Profil

Re: Slicnost vectora/sekvenci

^{07.03.2011. u 12:48 - pre 172 meseci}

Najveci uticaj na slicnost sekvenci bi trebali imati unosi na specificnim indexima.
Manja apsolutna vrednost razlika kroz celu sekvencu znaci vecu slicnost.
Zbog toga razlika i unija ne bi radile, jer vrednosti blizu datih mogu znaciti slicnost, iako
su svi unosti razliciti po indexima. Zbog toga koristim sumaciju razlika po indexu i, ali me
zanimaju drugacija misljenja.

Odgovor na temu

atomant
Beograd

Član broj: 47540
Poruke: 263
*.dynamic.isp.telekom.rs.

+34 Profil

Re: Slicnost vectora/sekvenci

^{07.03.2011. u 13:01 - pre 172 meseci}

Iz ovoga sto si naveo ti (ne)svesno koristis Hamingovu distancu kao neku meru slicnosti. Pomenuto Haminogov rastojanje ima primenu u obradi signala i teoriji informacija za uporedjivanje vektora istih duzina, algoritam trazi

i na osnovu ovoga odredjuje koliko su nizovi slicni/razliciti. Najslicniji su oni kod kojih je rastojanje izmedju clanova najmanje (logicno).

Ako sada zamislis taj tvoj niz od n brojeva kao n-dimenzioni vektor, onda ovo rastojanje predstavlja dobru meru slicnosti u najvecem broju primena.

zaboravih da se ulogujem, obrisite post iznad.

If you can't explain it simply, you don't understand it well enough. A. Einstein

Odgovor na temu

onako

Član broj: 256314
Poruke: 75
*.dynamic.isp.telekom.rs.

Profil

Re: Slicnost vectora/sekvenci

^{07.03.2011. u 13:06 - pre 172 meseci}

Hvala na odgovoru.
Drago mi je da sam dosao do Hamingovog zakljucka.
No, je li to jedina mera slicnosti dva vektora (u obradi signala i teoriji informacija) ?

Odgovor na temu

atomant
Beograd

Član broj: 47540
Poruke: 263
*.dynamic.isp.telekom.rs.

+34 Profil

Re: Slicnost vectora/sekvenci

^{07.03.2011. u 13:11 - pre 172 meseci}

Naravno da ne. Tih normi ima koliko ti dusa pozeli (npr. Damerau-Levenstajn se koristi za DNK lance, algoritam je mnogo slozeniji; Lijeva distanca - slicna primena kao i Hamingova itd.), ali mislim da je ovo sasvim zadovoljavajuce, a i sam algoritam je jednostavan.

If you can't explain it simply, you don't understand it well enough. A. Einstein

Odgovor na temu

onako

Član broj: 256314
Poruke: 75
*.dynamic.isp.telekom.rs.

Profil

Re: Slicnost vectora/sekvenci

^{07.03.2011. u 13:44 - pre 172 meseci}

Prilicno sam zadovoljan algoritmom. Problem je u tome sto se vise uticaja dodeljuje vecim magnitudama.
Mozda bi pre-procesuiranje nizova (racunanje max vrednost, devijacije) pomogla u otklanjanju dominacije
vecih magnituda. Jedan od nacina je sumirati korene vrednosti apsolutne razlike, ili sumirati absolutnu
razliku korena pojedinacnih vrednosti.
Da li postoji nesto slicno u vasoj bransi?

Odgovor na temu

atomant
Beograd

Član broj: 47540
Poruke: 263
*.dynamic.isp.telekom.rs.

+34 Profil

Re: Slicnost vectora/sekvenci

^{07.03.2011. u 14:13 - pre 172 meseci}

Moze se i vrsiti odbacivanje najveceg i najmanjeg clana ili ne samo po jednog clana vec odredjenog broja clanova, ali simetricno, tj. ako se odbaci 5 max vrednosti, onda se mora odbaciti i 5 minimalnih. Naravno, za manje nizove ovo ne pije vodu, jer ne ostaje skoro nista za obradu.

Jedan od nacina moze da bude i Lijeva distanca. Algoritam je slican kao i za Hamingovu distancu.

, gde je q maksimalna vrednost koja se moze pojaviti. U zavisnosti od vrednosti elemenata niza ovo moze biti bolji izbor od H.d.

Ne znam kako izgleda niz koji se obradjuje pa sad nabrajam sta sve moze da se radi. Moze naravno i da se nadje medijana ili srednja vrednost (sta se pokaze kao optimalnije) pa da se onda trazi apsolutna vrednost razlike svakog clana niza i medijane, pa da se potom primeni H.d. ili L.d. Nego, je l' mozemo mi da vidimo neki primer niza, sto kaze Nedeljko. Ovako se sve svodi samo na nagadjanje. Onaj primer koji je gore dat, sa A i B je suvise jednostavan, tu bi cak i H.d. radila dobar posao. Nije bas jednostavno pogoditi algoritam ovako na pamet.

If you can't explain it simply, you don't understand it well enough. A. Einstein

Odgovor na temu

onako

Član broj: 256314
Poruke: 75
*.dynamic.isp.telekom.rs.

Profil

Re: Slicnost vectora/sekvenci

^{07.03.2011. u 14:40 - pre 172 meseci}

Uzmimo u obzir da, za sekvence koje dominiraju, vise odgovara mapiranje (poduradanje ili bliskost) vecih magnituda.
Tj, slicniji su ako je veci broj podudarnosti (ili bliskost) vecih magnituda (ukoliko sekvenca A ima isto toliko podudarnosti
sa sekvencom B kao sekvenca C, onda je slicnija B ona sekvenca koja ima podurarnost vecih magnituda)
Zbog toga i koristim Haming alg, jer daje vecu vaznost vecim magnitudama, ali moze se primeniti i odbacivanje manjih vrednosti
iz obe sekvence.
Primer sekvence can (samo delic, jer se radi o sekvencama od nekoliko hiljada elemenata), tip1:
A
0 2 2 2 3 4 3 4 5 4 5 6 5 1 3 1 3 4 5 1 2 3 4 1 1 2 2 3
B (po horizontali)
2 0 2 1 2 3 2 3 4 3 4 5 4 1 1 2 2 3 4 2 1 1 2 2 2 1 1 1
2 2 0 1 2 2 2 3 4 3 4 5 4 2 2 1 1 3 4 2 2 2 3 2 2 2 2 2
5 4 4 3 2 3 2 1 2 1 0 2 1 4 3 4 3 2 2 5 4 4 3 5 4 4 4 3
1 2 2 2 3 4 3 4 5 4 5 6 5 1 3 1 3 4 5 1 2 3 4 0 1 2 2 3

tip 2:
A
2 0 2 1 2 3 2 3 4 3 4 5 4 1 1 2 2 3 4 2 1 1 2 2 2 1 1 1 2

B
4 4 4 4 3 2 1 3 3 3 3 3 0 2 2 2 3 5 5 5 4 4 4 4 4 4 4 4 4
0 2 2 2 1 2 3 3 3 3 3 3 4 4 4 4 5 3 3 3 6 6 6 6 6 6 6 6 6
3 1 2 1 2 3 2 3 4 3 4 5 4 2 1 2 2 3 4 3 2 0 2 3 2 2 1 1 2

Citat:

U zavisnosti od vrednosti elemenata niza ovo moze biti bolji izbor od H.d.

Sta bi to znacilo za sekvence? Uticaj vecih magnitude je snizen?

Odgovor na temu

atomant
Beograd

Član broj: 47540
Poruke: 263
*.dynamic.isp.telekom.rs.

+34 Profil

Re: Slicnost vectora/sekvenci

^{07.03.2011. u 16:02 - pre 172 meseci}

Mozda bi mogla da se izvrsi redukcija dimenzija. Ako svaki element vektora posmatramo kao jednu dimenziju, onda za svaku dimenziju odredis sumu elemenata, npr. 4. element prvog vektora + 4. element drugog + 4. element .... i gledas koje su sume najmanje i njih izbacis. Moze se desiti da imas sve nule i jednu 8, pa da zbir bude 8, a da je 8 ujedno i jedna od najvecih magnituda, ali kod redukcije dimenzija moras i da izgubis odredjenu kolicinu informacija, na zalost. Sa redukovanim nizovima mozes da radis HD i da vidis da li je to zadovoljavajuce.

Mozes da uradis i ovo. Odredis im medijane, sortiras jedan po neopadajucem poretku recimo (moze i nerastucem) i na osnovu njega sortiras drugi niz, tako da ocuvas informaciju prema kojoj poredis, recimo ako je 6. element prvog niza imao najvecu magnitudu i u novom nizu ga pomeris na prvo mesto onda i 6. element drugog niza u drugom novom nizu mora biti na 1. mestu pa makar imao i vrednost 0, inace poredjenje gubi smisao. Sada poredis prvi i drugi niz sa odgovarajucim medijanama, ako su elementi veci, onda pripadaju visim magnitudama i imaju veci uticaj pri poredjenju. Elementi manji od medijane imaju manjeg uticaja. Uradis HD tako da imas 2 sabirka za svaki niz i sad radis poredjenje. Ako se desi da su 2 poredjenja jako slicna gledas im sabirak koji ima veci uticaj (recimo da je to prvi, potpuno je sve jedno koji ce biti - to samo ti odredjujes) i na osnovu njega odlucujes o poretku slicnosti.

Nadam se da sam bio jasan.

If you can't explain it simply, you don't understand it well enough. A. Einstein

Odgovor na temu