Hi,

Wlasnie sie zastanawiam jak najefektywniej napisac algorytm
"grupujacy" dane wg
pewnych "obszarow". A dokladnie mam zbior punktow (x,y), wsrod
ktorych dla niektorych
zakresow x pojawia sie wiecej punktow niz w innych - czyli powiedzmy,
ze "grupuja" sie
one wokol x +/- delta.

Np:
(1,4), (2,5), (3,10), (2, 12),
(10,1), (11,5), (13,8),
(38, 4), (39, 9), (38, 15)

I teraz chcialbym je wlasnie podzielic wg polozenia w okolicach
takich "zgrupowan".
Taki troche histogram, ale sprobkowany tylko dla okolic pewnych
wartosci dla ktorych
wystepuje najwiecej punktow. Akurat w podanych danych latwo zauwazyc,
ze
grupowanie powinno byc wg x ~= 2, x ~= 11, x ~= 38. Ale w
rzeczywistych danych to
niekoniecznie musi byc tak latwo.

Pierwsze co mi przychodzi do glowy to zalozyc sobie jakas wartosc
delta i przeiterowac sie po
punktach sprawdzajac juz jest zbior dla wartosci x +/- delta i tam
dodac, ewentualnie taki zbior
nowy stworzyc itd. Ale widze pewne "niedogodnosci":wyznaczenie
wartosci delta "na czuja"
moze spowodowac ze moga sie zdarzyc punkty, ktore beda pasowac do
roznych grup
(ale ok, mozna wybrac ta ktara jest "blizej") oraz moga byc takie,
ktore stworza osobne "grupy",
ale beda tam jedynymi punktami (w przypadku kiedy beda "oddalone" od
innych "skupisk").
Tak wiec delta powinna byc dobierana bardziej adaptacyjnie i nie do
konca powinna byc
stala dla calego przedzialu x.

Pewnie jest na taki podzial jakis sprytny algorytm :) Moze ktos
podpowie?

m.

do góry

context pisze:

>
> Pewnie jest na taki podzial jakis sprytny algorytm :) Moze ktos
> podpowie?

Oczyma duszy zobaczy?em taki algorytm jak 'pixeluje' czy 'pixelizuje'
sie; twarze w TV.

Oczywis'cie zak?ada to skwantowanie w jednakowych przedzia?ach (pixelach)

Gdzie masz 'ciemniej', tam sie; zag?e;biasz.
Z?oz.onos'c' z grubsza kwadratowa wzgle;dem ilos'c' kwantów.

Byc' moz.e wymys'li cos' co leci w dziedzinie punktów (odleg?os'c' kaz.dego
punktu do innego punktu) - tu jest wyk?adnicza wzgl punktów.

ALE!!!!!

Mam g?e;bokie przeczucie, z.e matma, matma, matma. Z.e istnieje algorytm
oparty na dorobku matematycznym (prawdopodobnie mocno abstrakcyjny jak
na masowa; newsowa; publicznos'c') który bije nasze naiwne na g?owe;.

do góry

context pisze:
> Hi,
>
> Wlasnie sie zastanawiam jak najefektywniej napisac algorytm
> "grupujacy" dane wg
> pewnych "obszarow". A dokladnie mam zbior punktow (x,y), wsrod
> ktorych dla niektorych
> zakresow x pojawia sie wiecej punktow niz w innych - czyli powiedzmy,
> ze "grupuja" sie
> one wokol x +/- delta.

Brzmi jak "odwrócone" wyrównywanie histogramu :) (całkiem ładny opis
wyrównywania jest tutaj
http://atol.am.gdynia.pl/tc/Radzienski/Polepszanie.h
tm ) Może coś z tym
poczniesz.
Pozdrawiam
GRG

do góry

On Wed, 1 Jul 2009 09:56:21 -0700 (PDT), context <c...@f...pl>
wrote:

>Hi,
>
> Wlasnie sie zastanawiam jak najefektywniej napisac algorytm
>"grupujacy" dane wg
> pewnych "obszarow". A dokladnie mam zbior punktow (x,y), wsrod
>ktorych dla niektorych
> zakresow x pojawia sie wiecej punktow niz w innych - czyli powiedzmy,
>ze "grupuja" sie
> one wokol x +/- delta.
>


To sie nazywa "clustering algoritm" i na ten temat na googlach jest 10
milionow linkow

A.L.

do góry

Uzytkownik "A.L." <a...@a...com> napisal w wiadomosci grup
dyskusyjnych:msen45dslu8mblu993rv7uhe0bd1m25v3u@4ax.
com...
> To sie nazywa "clustering algoritm" i na ten temat na googlach jest 10
> milionow linkow

Algorytmy analizy skupien - byla taka ksiazka. Analiza skupien -
subdyscyplina czegos (informatyki? matematyki?)

slawek

do góry

Jacek Czerwinski <...@...z.pl> napisał(a):

> context pisze:
>
> >
> > Pewnie jest na taki podzial jakis sprytny algorytm :) Moze ktos
> > podpowie?
>
> Oczyma duszy zobaczy?em taki algorytm jak 'pixeluje' czy 'pixelizuje'
> sie; twarze w TV.
>
> Oczywis'cie zak?ada to skwantowanie w jednakowych przedzia?ach (pixelach)
>
> Gdzie masz 'ciemniej', tam sie; zag?e;biasz.
> Z?oz.onos'c' z grubsza kwadratowa wzgle;dem ilos'c' kwantów.
>
> Byc' moz.e wymys'li cos' co leci w dziedzinie punktów (odleg?os'c' kaz.dego
> punktu do innego punktu) - tu jest wyk?adnicza wzgl punktów.
>
> ALE!!!!!
>
> Mam g?e;bokie przeczucie, z.e matma, matma, matma. Z.e istnieje algorytm
> oparty na dorobku matematycznym (prawdopodobnie mocno abstrakcyjny jak
> na masowa; newsowa; publicznos'c') który bije nasze naiwne na g?owe;.

O ile pamiętam, nie są znane algorytmy dające optymalny (jeszcze należałoby
dokładnie sformułować kryterium, np. czy centra grup są dane, czy centra
należy ustalić, czy centra mają się pokrywać z którąś z danych, funkcja kosztu
dla rozwiązania, itd) podział na grupy w przyzwoitym czasie. Stosuje się
strategie zachłanne: np. można przyłączać do grup te dwa punkty
które spowodują najmniejszy wzrost funkcji kosztu, następnie można odłączyć
od grup ten jeden punkt który spowoduje największy spadek funkcji kosztu.

Pozdrawiam


--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

On Fri, 3 Jul 2009 00:11:23 +0000 (UTC), "Mariusz Marszałkowski"
<b...@g...pl> wrote:

>
>O ile pamiętam, nie są znane algorytmy dające optymalny (jeszcze należałoby
>dokładnie sformułować kryterium, np. czy centra grup są dane, czy centra
>należy ustalić, czy centra mają się pokrywać z którąś z danych, funkcja kosztu
>dla rozwiązania, itd) podział na grupy w przyzwoitym czasie. Stosuje się
>strategie zachłanne: np. można przyłączać do grup te dwa punkty
>które spowodują najmniejszy wzrost funkcji kosztu, następnie można odłączyć
>od grup ten jeden punkt który spowoduje największy spadek funkcji kosztu.

Owszem, po polsku sie nazywaja "algorytmy analizy skupien" po
angielsku "clustering analysis" i nazlezy ich szukac w dzialce "data
mining".

Mozna je znalezc w systemie Weka, open source zreszta

https://sourceforge.net/projects/weka/

a wiecej na ten temat napisano w ksizce "Collective Intelligence in
Action", Satnam Alag, Manning 2009.

jest wiecej narzedzi do tego celu, na przykald JDM (Java Data Mining)

http://en.wikipedia.org/wiki/Java_Data_Mining

http://www.jdmp.org/

http://sourceforge.net/projects/jdmp/

A.L.

do góry