eGospodarka.pl

eGospodarka.plGrupypl.comp.programming › Wyszukiwanie bliskich punktów w wielowymiarowej przestrzeni
Ilość wypowiedzi w tym wątku: 9

  • 1. Data: 2019-11-20 01:04:50
    Temat: Wyszukiwanie bliskich punktów w wielowymiarowej przestrzeni
    Od: Borneq <b...@a...hidden.pl>

    Mam szukać wielokrotnie, nie identycznych a podobnych, coś takiego jak
    wyszukiwanie podobnego obrazu czy odcisku palca bez konieczność
    przeszukania całości czy nawet znacznej części całości.
    Gdy mam przypadek 1D to najpierw sortuję.
    Dla 2D mogę zrobić boksy wystarczająco duże by nie było marnotrawstwa na
    boksy nie zawierające żadnych elementów , te boksy mają podboksy a te
    elementy.

    Jest problem, bo gdy szerokość to 100, wtedy
    szukając 401 mogę znaleźć 490 a nie znajdę bliskiego 399.
    Trzeba by szukać w boksach naokoło, w 9 zamiast w jednym. To jeszcze się
    da, ale dla 3D będzie to 27, ogólnie 3^n, co gdy mamy 512D?


  • 2. Data: 2019-11-20 04:03:29
    Temat: Re: Wyszukiwanie bliskich punktów w wielowymiarowej przestrzeni
    Od: "M.M." <m...@g...com>

    On Wednesday, November 20, 2019 at 1:04:51 AM UTC+1, Borneq wrote:
    > Mam szukać wielokrotnie, nie identycznych a podobnych, coś takiego jak
    > wyszukiwanie podobnego obrazu czy odcisku palca bez konieczność
    > przeszukania całości czy nawet znacznej części całości.
    > Gdy mam przypadek 1D to najpierw sortuję.
    > Dla 2D mogę zrobić boksy wystarczająco duże by nie było marnotrawstwa na
    > boksy nie zawierające żadnych elementów , te boksy mają podboksy a te
    > elementy.
    >
    > Jest problem, bo gdy szerokość to 100, wtedy
    > szukając 401 mogę znaleźć 490 a nie znajdę bliskiego 399.
    > Trzeba by szukać w boksach naokoło, w 9 zamiast w jednym. To jeszcze się
    > da, ale dla 3D będzie to 27, ogólnie 3^n, co gdy mamy 512D?

    Jakie wejście i jakie wyjście programu?

    Pozdrawiam


  • 3. Data: 2019-11-20 07:22:23
    Temat: Re: Wyszukiwanie bliskich punktów w wielowymiarowej przestrzeni
    Od: Borneq <b...@a...hidden.pl>

    W dniu 20.11.2019 o 04:03, M.M. pisze:
    > Jakie wejście i jakie wyjście programu?
    >
    > Pozdrawiam
    >

    Wejście, dwa zbiory A(p1,p2...pn) B(q1.q2...qm)
    gdzie pi, qk - to punktu o tym samym wymiarze

    Wyjście:
    punkty zbioru A gdzie dla jednego pi mamy podaną listę być może pustą
    iluś punktów ze zbioru B, które są w odległości co najwyżej epsilon,
    odległość może być różnie liczona, chyba że algorytm wymaga by była
    konkretnie np. jako suma po współrzędnych czy maksymalna współrzędna.


  • 4. Data: 2019-11-20 07:23:50
    Temat: Re: Wyszukiwanie bliskich punktów w wielowymiarowej przestrzeni
    Od: Borneq <b...@a...hidden.pl>

    W dniu 20.11.2019 o 07:22, Borneq pisze:
    > odległość może być różnie liczona, chyba że algorytm wymaga by była
    > konkretnie np. jako suma po współrzędnych czy maksymalna współrzędna.


    To znaczy sua po różnicy współrzędnych albo maksymalna różnica
    współrzędnych.


  • 5. Data: 2019-11-20 07:37:40
    Temat: Re: Wyszukiwanie bliskich punktów w wielowymiarowej przestrzeni
    Od: "M.M." <m...@g...com>

    On Wednesday, November 20, 2019 at 7:23:53 AM UTC+1, Borneq wrote:
    > W dniu 20.11.2019 o 07:22, Borneq pisze:
    > > odległość może być różnie liczona, chyba że algorytm wymaga by była
    > > konkretnie np. jako suma po współrzędnych czy maksymalna współrzędna.
    >
    >
    > To znaczy sua po różnicy współrzędnych albo maksymalna różnica
    > współrzędnych.

    Trzeba przeiterować i policzyć, albo najpierw zaindeksować czymś w okolicach
    kd-tree. Można posłużyć się bazą danych, np. postgres ma indeksy do tego
    celu, działa dobrze na ogromnych zbiorach danych.

    Pozdrawiam


  • 6. Data: 2019-11-20 08:51:13
    Temat: Re: Wyszukiwanie bliskich punktów w wielowymiarowej przestrzeni
    Od: Borneq <b...@a...hidden.pl>

    W dniu 20.11.2019 o 07:37, M.M. pisze:
    > Trzeba przeiterować i policzyć, albo najpierw zaindeksować czymś w okolicach
    > kd-tree. Można posłużyć się bazą danych, np. postgres ma indeksy do tego
    > celu, działa dobrze na ogromnych zbiorach danych.

    Bardziej chodzi mi o algorytm, czyli kd-tree?


  • 7. Data: 2019-11-21 01:13:56
    Temat: Re: Wyszukiwanie bliskich punktów w wielowymiarowej przestrzeni
    Od: "M.M." <m...@g...com>

    On Wednesday, November 20, 2019 at 8:51:33 AM UTC+1, Borneq wrote:
    > W dniu 20.11.2019 o 07:37, M.M. pisze:
    > > Trzeba przeiterować i policzyć, albo najpierw zaindeksować czymś w okolicach
    > > kd-tree. Można posłużyć się bazą danych, np. postgres ma indeksy do tego
    > > celu, działa dobrze na ogromnych zbiorach danych.
    >
    > Bardziej chodzi mi o algorytm, czyli kd-tree?

    Jeśli chcesz zaindeksować przed wyszukiwaniem, to można próbować kd-tree.
    Ale nie tylko, może pomysł z gridem być lepszy.

    Pozdrawiam


  • 8. Data: 2019-11-21 19:44:41
    Temat: Re: Wyszukiwanie bliskich punktów w wielowymiarowej przestrzeni
    Od: Borneq <b...@a...hidden.p>

    W dniu 21.11.2019 o 01:13, M.M. pisze:
    > On Wednesday, November 20, 2019 at 8:51:33 AM UTC+1, Borneq wrote:
    >> W dniu 20.11.2019 o 07:37, M.M. pisze:
    >>> Trzeba przeiterować i policzyć, albo najpierw zaindeksować czymś w okolicach
    >>> kd-tree. Można posłużyć się bazą danych, np. postgres ma indeksy do tego
    >>> celu, działa dobrze na ogromnych zbiorach danych.
    >>
    >> Bardziej chodzi mi o algorytm, czyli kd-tree?
    >
    > Jeśli chcesz zaindeksować przed wyszukiwaniem, to można próbować kd-tree.
    > Ale nie tylko, może pomysł z gridem być lepszy.
    >
    > Pozdrawiam
    >

    Grid sprawdza się dla małej wymiarowości,
    mam grid co 100, mam punkt 401, znajduję 490, ale nie mogę znależć już
    399 choć jest bliżej,
    więc trzeba by naokoło, zamiast jednego boxa -9!
    Dla dwóch wymiarów, a dla trzech 26, ogólnie 3^n, co z kilkuset?


  • 9. Data: 2019-11-22 00:31:42
    Temat: Re: Wyszukiwanie bliskich punktów w wielowymiarowej przestrzeni
    Od: "M.M." <m...@g...com>

    On Thursday, November 21, 2019 at 7:44:43 PM UTC+1, Borneq wrote:
    > W dniu 21.11.2019 o 01:13, M.M. pisze:
    > > On Wednesday, November 20, 2019 at 8:51:33 AM UTC+1, Borneq wrote:
    > >> W dniu 20.11.2019 o 07:37, M.M. pisze:
    > >>> Trzeba przeiterować i policzyć, albo najpierw zaindeksować czymś w okolicach
    > >>> kd-tree. Można posłużyć się bazą danych, np. postgres ma indeksy do tego
    > >>> celu, działa dobrze na ogromnych zbiorach danych.
    > >>
    > >> Bardziej chodzi mi o algorytm, czyli kd-tree?
    > >
    > > Jeśli chcesz zaindeksować przed wyszukiwaniem, to można próbować kd-tree.
    > > Ale nie tylko, może pomysł z gridem być lepszy.
    > >
    > > Pozdrawiam
    > >
    >
    > Grid sprawdza się dla małej wymiarowości,
    > mam grid co 100, mam punkt 401, znajduję 490, ale nie mogę znależć już
    > 399 choć jest bliżej,
    > więc trzeba by naokoło, zamiast jednego boxa -9!
    > Dla dwóch wymiarów, a dla trzech 26, ogólnie 3^n, co z kilkuset?

    Stosuje się też techniki zmniejszania wymiarów. W przypadku odcisków
    palców np. zlicza ilość charakterystycznych wzorów.

    Jeśli wymiarów jest dużo, np. 100 i ma być gęste wypełnienie w każdym
    wymiarze, to potrzeba M^100 elementów, gdzie M jest duże, ma wartość
    chociaż 10 :) Nie wiem jak kd-tree się sprawdzi dla dużej wymiarowości.
    By trzeba sprawdzić, albo poczytać.

    Tam piszą też że się nie nadają:
    https://stackoverflow.com/questions/37132774/why-k-d
    -trees-is-not-used-for-high-dimensional-data

    Pozdrawiam

strony : [ 1 ]



Szukaj w grupach

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: