» »

Ekvalizacija na intervalu - iščem genialne ideje

Ekvalizacija na intervalu - iščem genialne ideje

dunker ::

Lep pozdrav vsem skupaj!

Tokrat pa en malo trši oreh ... upam, da bo komu v izziv. :D Za odgovor se vam ni treba omejit na noben jezik, lahko napišete kar psevdo-kodo, lahko v bistvu podate tudi samo svojo idejo.

Problem je sledeč. Recimo, da imamo kup urejenih števil na intervalu [0, 100]. Recimo, da so ta števila preveč nagnjena k neki skrajnosti, mi pa bi jih želeli lepo razporedit po celotnem intervalu. Razporediti jih želimo tako, da se sicer nekako ohrani prvotna razporeditev in razmak med števili, ampak da se mnogo lepše razporedijo po celotnem intervalu.

Za FRI UNI maherje, v bistvu potrebujem nekaj podobnega kot je ekvalizacija histograma. Žal ta pristop ne pride v poštev, ker uporablja metanje vrednosti v diskretne "koše", jaz pa imam povsem analogne vrednosti in bi bilo košev enostavno preveč.

Torej, recimo, da imamo naslednjo množico števil: 1.1, 1.14, 1.15, 1.74, 2.2, 2.7, 3.12, 4.36, 7.12, 34.17, 100

Števila torej čisto preveč silijo k ničli, hočemo jih bolj enakomerno razporedit po intervalu, vendar obenem v neki meri tudi ohranit prvotno porazdelitev. Zadovoljiv rezultat bi bil naprimer v stilu: 1.1, 3.15, 3.25, 7, 11, 15, 23, 29, 48, 85, 100

Ima kdo kakšno idejo, kako to implementirat? :D

Enjoy, in hvala vnaprej. :D

popster ::

Ta stevila bi dal v array
V drug array bi dal stevila v random vrstnem redu
Končni array bi pa bil tako da bi random enkrav vzel stevilo iz prvega enkrat iz drugega.

Odvisno v kaki meri rabis ohranit vrstni red, bi lahko tu kaj drugega kot random, kar bi mogoče še bolj ohranilo vrstni red. (recimo z zamenjavami na naključnih mestih)

BlueRunner ::

Razporediti jih želimo tako, da se sicer nekako ohrani prvotna razporeditev in razmak med števili, ampak da se mnogo lepše razporedijo po celotnem intervalu.


Ne razumem teh dveh pogojev:
- ohraniti razmak med števili
- mnogo "lepše" razporediti po celotnem intervalu

Če "lepše" pomeni, da je število elementov na poljubnem intervalu v povprečju enako številu elementov na katerem koli drugem poljubno izbranem in enako velikem intervalu, potem nisi ohranil razmaka med števili. Optimalna rešitev za to pa je, da vzameš največje in najmanjše število iz zaporedja, jih postaviš za meje zaprtega intervala, izračunaš n-2 korakov na tem intervalu in narediš preslikavo starih vrednosti na nove vrednosti.

Če pa želiš ohraniti razmak med števili, potem pa ne moreš govoriti o drugačni gostoti razporeditve po intervalu.

Torej je verjetno potrebno še nekaj dodatne razlage o teh dveh pogojih. Ali pa vsaj kakšna malo bolj "matematična" definicija kaj je "lep razpored".

dunker ::

Pogoja sta:
- *nekako* ohrani razmak med števili
- mnogo lepše razporediti po celotnem intervalu

Obojemu seveda ni možno zadostiti. Možno pa je naresti nekaj takšnega, kot je razvidno tudi iz slike v članku o ekvalizaciji histograma. Porazdelitev ima še vedno podobno obliko, kar pomeni: tiste vrednosti, ki so bile prej blizu skupaj, so tudi sedaj relativno blizu skupaj; tiste vrednosti, ki so bile prej relativno daleč narazen, so tudi sedaj relativno daleč narazen. Se pa celotna množica iz neke lokalne zgostitve preslika na celoten interval.

Upam, da mi je zdaj uspelo kaj bolje razložit - mislim, da slika kar dobro zadane bistvo. :)

BlueRunner ::

Ah... tako torej. Čeprav to, kar se počne na histogramu nima ravno veliko povezave s tvojo zahtevo. Ampak recimo, da želiš "hribe" na histogramu "znižati" oziroma spremeniti zgoščenost točk na intervalu tam kjer je zgostitev prevelika.

1. korak: naredi nov seznam, kjer so elementi razdalje med zaporednima elementoma.

Za primer { 1.1, 1.14, 1.15, 1.74, 2.2, 2.7, 3.12, 4.36, 7.12, 34.17, 100 } dobiš seznam { .04, .01, .59, .46, .5, .42, 1.24, 2.76, 27.05, 65.83 }.

2. korak: te razdalje sedaj transformiraš s pomočjo logaritma... recimo ln((1+d) * faktor)

Tako dobiš nov seznam: { .0392, .01, .4637, .3784, .4055, .3507, .8065, 1.3244, 3.334, 4.2022 }

3. korak: znova sestaviš nazaj zaporedje posameznih števil

Tako dobiš nov seznam: { 1.1, 1.1392, 1.1492, 1.6129, 1.9913, 2.3968, 2.7475, 3.5540, 4.8784, 8.2124, 12.4146 }

4. korak: števila renormaliziraš na originalen interval [1.1, 100]

Pri temu pa upoštevaj, da sem stvari poračunal na roke in zaokrožil na 4 decimalna mesta. Zaradi tega je napaka velika... mislim pa, da je poanta vidna.

Preslikava A |-> B: (ai -> bi; i=0..n) ohrani vse urejenost med elementi: ai R aj => bi R bj; R = { <, >, = }. Ravno tako ohrani enakost med razlikami, čeprav ne ohrani absolutne velikosti teh razlik: ai - aj = ak - al => bi - bj = bk - bl.

Primer kako to na hitro narediti v Pythonu:
#!/usr/bin/python

import math

# scaling factor
factor = 5

# starting list
a = [1.1, 1.14, 1.15, 1.74, 2.2, 2.7, 3.12, 4.36, 7.12, 34.17, 100 ]

# calculate differences
d = [math.log((1 + a[i+1]-a[i]) * factor) for i in range(len(a) - 1)]

# calculate normalization factor
n = (a[-1] - a[0]) / sum(d[0:len(a)])

# calculate final result
b = [a[0] + sum(d[0:i]) * n for i in range(len(a))]

# print the result
print b

Zgodovina sprememb…

dunker ::

Uuuuu! Točno to sem iskal, genialno idejo. :D

Najlepša hvala, Eclipse se že zaganja, I think we won the battle. ;)

Hvala še 1x!


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Vprašanje iz verjetnosti

Oddelek: Šola
102074 (1260) Randomness
»

Vprašanje v zvezi z rand() funkcijo

Oddelek: Programiranje
494861 (4051) fireice
»

pra števila.. (strani: 1 2 )

Oddelek: Znanost in tehnologija
788337 (4676) Yacked2
»

[c++] nek programcek

Oddelek: Programiranje
171515 (1076) black ice
»

OpenOffice 2.0 je na poti

Oddelek: Novice / Pisarniški paketi
455016 (3620) Marjan

Več podobnih tem