k najbliższych sąsiadów w SQL u

Witam.

Mam do napisania procedurę realizującą algorytm k-najbliższych sąsiadów w języku MS SQL Serwer.
Pracuję na bazie dane_uśmiech na tabeli dane_uśmiech2$ ma 3000 elementów opisanych przez 3 parametry: X,Y i klasę(grupę)
Zrobiłam tyle:
CREATE PROCEDURE K_NAJBLIZSZYCH_SASIADOW
@K INT
AS
BEGIN

CREATE TABLE #DANE (
X FLOAT,
Y FLOAT,
NR_GRUPY INT)

INSERT INTO #DANE (X, Y,NR_GRUPY)
SELECT CAST (REPLACE (X, ',','.') AS FLOAT), CAST (REPLACE (Y, ',','.') AS FLOAT),KLASA FROM dbo.dane_usmiech2$

CREATE TABLE #ZBIOR_UCZACY (
A FLOAT,
B FLOAT,
NR_GRUPY INT)

INSERT INTO #ZBIOR_UCZACY(A,B,NR_GRUPY)
SELECT TOP(1000) X, Y, NR_GRUPY FROM #DANE

CREATE TABLE #ZBIOR_TESTOWY (
T FLOAT,
S FLOAT,
NR_GRUPY INT)

INSERT INTO #ZBIOR_TESTOWY(S,T)
SELECT TOP(2000) X, Y FROM #DANE
ORDER BY NR_GRUPY DESC

czyli stworzyłam tabelkę tymczasową #DANE i do niej wrzuciłam wszystkie dane z bazy czyli 3000 elementów
Następnie stworzyłam tabelkę tymczasową #ZBIOR_UCZACY wybierając 1000 elementów z #DANE (nie muszę brać więcej elementów ponieważ są tak rozmieszczone na wykresie że tyle wystarczy). Stworzyłam też #ZBIOR_TESTOWY do którego wrzuciłam resztę elementów czyli 2000. I tu napotykam problem ponieważ nie wiem jak dalej dla każdego elementu ze zb testowego wybrać takie k elementów ze zbioru uczącego żeby odleglość tych k elementów ze zbioru uczącego byla najmniejsza do danego elementu ze zbioru testowego i sprawdzić do której grupy one należą i dalej temu elementowi ze zb testowego przypisac grupę która występuje najczęściej wśród tych k elementów ze zb uczącego.
Ogólnie to się jeszcze tak zastanawiam, że istnieje możliwość że do zbioru uczącego wybiorę same elementy z jednej grupy... jak temu zapobiedz?

Bardzo proszę o pomoc
Pozdrawiam.:)

może po ludzku - chcesz dla każdego punktu z tabeli znaleźć k najbliżej leżących (licząc w płaszczyźnie dwuwymiarowej odległość na podstawie X i Y dwóch punktów) punktów? Jeśli tak to po co tutaj jakieś tabele dodatkowe jak to wszystko można załatwić na dobrą sprawę jednym zapytaniem. MSSQL ma nawet taki bajer jak SPATIAL INDEX, który powinien tutaj dużo przyśpieszyć

No tak. tylko chodzi o to że ja mam napisać procedurę która składa się ze zbioru uczącego i ze zbioru testowego i teraz do każdego elementu ze zb testowego szukam k najbliższych sąsiadów ze zb uczącego(wykorzystując metrykę euklidesową) dalej sprawdzam do jakiej grupy należy każdy z tych k sąsiadów i temu elementowi ze zb testowego przypisuję taką grupę która najczęściej występuje wśród tych k sąsiadów.

jeśli zdarzy się że np k=4 i mam 2 sąsiadów należących do gr1 i 2 do gr2 to procedura ma odrzucać najdalszego sąsiada z tych czterech i wtedy sytuacja jest już jasna.

no dobra to z czym masz problem? Bo jeśli z napisaniem zapytania to nie masz problemu tylko braki podstawowej wiedzy z SQLa i matematyki

no właśnie może dlatego że mam braki i nie wiem jak to zrobić napisałam na forum?
pisałam już że nie wiem jak wybrać ze zbioru uczącego k-najbliższych sąsiadów dla każdego elementu ze zb testowego a później napisać klasyfikator który będzie decydował do jakiej gr należą elementy ze zb testowego na podstawie tego z jakiej grupy jest najwięcej sąsiadów ze zb uczącego

UPDATE #ZBIOR_TESTOWY SET NR_GRUPY = #ZBIOR_UCZACY.NR_GRUPY
FROM #ZBIOR_UCZACY
WHERE

i co dalej?

malwinka993 napisał(a)

pisałam już że nie wiem jak wybrać ze zbioru uczącego k-najbliższych sąsiadów
przecież to jest MATEMATYKA! masz dwa punkty to musisz policzyć odległość między nimi. Musisz to zrobić biorąc jeden element ze zbioru testowego i licząc odległość dla każdego elementu ze zbioru uczącego a potem uszeregować to według odległości i powtórzyć dla każdego elementu ze zbioru testowego. Czy mam rozumieć, że nie potrafisz policzyć odległości dwóch punktów na płaszczyźnie dwuwymiarowej?

nieee..
nie umiem zapisać warunku żeby ta procedura wybierała te k najbliższych pktów a później to klasyfikowała...
metryke zapisać umiem... robiłam też algorytm k średnich i tam ten warunek jest prosty a tu nie mogę zrobić że

WHERE SQRT(POWER(A-T,2) +(B-S)(B-S)) <=
ALL ( SELECT SQRT(POWER(A-T,2)+(B-S)(B-S))FROM #ZBIOR_UCZACY )

bo gdzie wtedy uwzględnię to że tych elementów z otoczenia każdego pkt ze zb testowego ma być k??

select 
  JEDEN_KONKRETNY_PKT_ZE_ZBIORU_TESTOWEGO,
  X_uczacy,
  Y_uczacy,
  obliczona_odleglosc
from
  ... 
order by 4
limit 0, k

to masz dla pojedynczego punktu ze zbioru testowego. Teraz trzeba to zrobić dla pozostałych punktów

czyli że miałoby to tak wyglądać

UPDATE #ZBIOR_TESTOWY SET NR_GRUPY = #ZBIOR_UCZACY.NR_GRUPY
FROM #ZBIOR_UCZACY
WHERE SQRT(POWER(A-T,2) +POWER(B-S,2)) <=
ALL ( SELECT SQRT(POWER(A-T,2)+POWER(B-S,2))FROM #ZBIOR_UCZACY

bo tutaj to on by sobie wybierał tylko najbliższy pkt i przypisywał od niego grupę

a ja chcę dajmy na to wybierać k=5 najbliższych sąsiadów ze zb uczącego dla elementu ze zb testowego i wśród nich żeby zliczało która grupa występuje najczęściej i taką przypisywało elementowi ze zb testowego

czemu LIMIT 0,k i order by 4 ??

i jak niby miałabym połączyć dwie tabele jak prawdę mówiąc nie mam na czym bo one są zupełnie różne??

malwinka993 napisał(a)

czemu LIMIT 0,k i order by 4 ??
bo chciałaś mieć k najbliższych punktów :>

to może inaczej. Zapomnij o SQLu. Napisz mi po swojemu, ale tak, żebyś sama rozumiała to co piszesz.
Masz JEDEN punkt, nazwijmy go A(X, Y) oraz zbiór np. 2000 INNYCH punktów (ale też opisanych przez X, Y). Chcesz wybrać ze zbioru k-punktów (np. 10) leżących na płaszczyźnie najbliżej punktu A. Jak to zrobisz?

Zależy pod jakim kątem pytasz...
Analizy matematycznej, Topologii przestrzeni metrycznych czy zwykłej geometrii ?

zaskocz mnie - opisz wszystkie jakie Ci przychodzą do głowy

no np mogę sobie rysować coraz większe kółeczka cyrklem o środku w pkt A aż w końcu do mojego kółka wpadnie k elementów

z ta granicą jedyne co mi przychodzi na myśl to liczyć ją dopóki ciąg długości nie bedzie mial k elementów

ale to moim zdaniem nie ma żadnego sensu

topologia to jedynie policzyć te odległości miedzy pkt i wywalać od najdalszego

ogolnie to chodzi mi o to jak wybrac akurat te k elementów do których z A jest najbliżej

nie wiem wydaje mi się że to trzeba zrobić w ten sposób że biorę sobie to A liczę pkt najbliżej niego później z reszty wybieram kolejny pkt najbliżej A i znów z reszty kolejny najbliższy aż do k

ja naprawdę nie mam siły - może po prostu za stary jestem. POWIEDZ MI JAK CHCESZ STWIERDZIĆ KTÓRY PUNKT JEST NAJBLIŻEJ NIE MAJĄC POLICZONYCH ODLEGŁOŚCI WSZYSTKICH PUNKTÓW????? Dla mnie to jest oczywiste, że biorę punkt A i liczę odległości WSZYSTKICH pozostałych punktów do niego, potem je sortuję od najmniejszej i biorę k-pierwszych. No przecież prościej się nie da!

po pierwsze to ja grzecznie pytam a Ty mi od samego początku wrzucasz...
po drugie jeden czort.. przecież to to samo... jakbyś nie zauważył to o to właśnie mi chodzi tylko po prostu nie wiem jak to zapisać w SQLu...
chociaż prawdę mówiąc to na wykładzie miałam to przedstawione własnie tak że wybieram pierwszy pkt ze zb uczącego który jest najbliżej pktu A(ze zb testowego) "odrzucam" go z uczącego i sprawdzam który wśród pozostałych jest najbliżej A znów go "odrzucam" i tak k razy

i te odrzucone pkty to moi najbliżsi sąsiedzi

1. no ale jak chcesz wybrać najbliższy skoro nie wiesz w jakiej są one odległości od siebie?
2. jak chcesz mogę Ci po prostu napisać SQLa bez próby tłumaczenia ale skończy się to tym, że za chwilę będziesz tu z następnym pytaniem.
3. jeśli wiesz jak to ma działać (a to napisałaś) to ja już na prawdę nie widzę problemu z zapisaniem tego w SQLu - no chyba, że jedyna Twoja znajomość SQLa to to zapytanie, które dostałaś na zajęciach i ciągle je męczysz. Ale wtedy to by wypadało napisać, że nie masz pojęcia o SQLu to nie będę sobie gitary zawracał próbą nakierowania Cię na rozwiązanie jak nie masz podstaw aby na to rozwiązanie wpaść

dobrze to może napisz mi jak wg Ciebie powinno to wyglądać razem ze wszystkimi objaśnieniami?

a skoro uważasz że nic nie umiem to prosiłabym o obszerne i zrozumiałe objaśnienia..

na przykładzie oracle bo nie mam mssqla
stworzenie tabeli

CREATE TABLE dane (
  x     NUMBER(10,0) NULL,
  y     NUMBER(10,0) NULL,
  grupa NUMBER(5,0)  NULL
);

wypełnienie jej 3000 losowych wartości (x, y z zakresu 1 - 1000, grupa z zakresu 1-100)

DECLARE
  x NUMERIC(10, 0);
BEGIN
  FOR x IN 1..3000 loop
   INSERT INTO dane VALUES (Dbms_Random.Value(1, 1000), Dbms_Random.Value(1, 1000), Dbms_Random.Value(1, 100));
  END LOOP;
END;
/

stworzenie tabeli uczacy i przepisanie 1000 pierwszych do tabeli uczacy

CREATE TABLE uczacy AS SELECT x, y, grupa FROM (SELECT ROWNUM rn, d.* FROM dane d) WHERE rn <= 1000;

stworzenie tabeli testowy i przepisanie pozostałych 2000 do niej

CREATE TABLE testowy AS SELECT x, y, grupa FROM (SELECT ROWNUM rn, d.* FROM dane d) WHERE rn > 1000;

czy dane są na miejscu

SELECT 'dane', Count(*) FROM dane UNION SELECT 'uczacy', Count(*) FROM uczacy UNION SELECT 'testowy', Count(*) FROM testowy;

wynik:

wyświetlenie każdego punktu ze zboru uczacy i wyświetlenie dla niego k (zadeklarowałem sobie 4) najbliższych ze zbioru testowy

DECLARE
  CURSOR ucz IS SELECT x, y FROM uczacy WHERE ROWNUM < 10; --to jest ograniczenie, że biorę tak naprawdę tylko 10 z uczacy żeby serwera nie zajechać
  TYPE test_rec IS RECORD (x NUMBER(10,0), y NUMBER(10,0), grupa NUMBER(5,0), odleglosc NUMERIC(20, 15));
  TYPE test_typ IS TABLE OF TEST_REC INDEX BY PLS_INTEGER;
  rec test_typ;
  k NUMERIC(10, 0);
BEGIN
  k := 5;
  FOR u IN ucz LOOP --lecimy po wszystkich ze zbioru uczacy
    SELECT --dla każdego robimy selecta, który znajduje nam k-najbliższych punktów
      X, Y, grupa, odleglosc
    BULK COLLECT INTO
      rec
    FROM
      (SELECT
        t.grupa,
        t.X,
        t.Y,
        Sqrt(Power(u.X - t.X, 2) + Power(u.Y - t.Y, 2)) odleglosc --dla każdego obliczamy odległość
      FROM
        testowy t
      ORDER BY 4) --sortujemy wg odległości rosnąco
    WHERE
      ROWNUM < k; --i bierzemy tylko k-pierwszych. W oraclu nie ma limit i trzeba kombinować z podzapytaniem
    dbms_output.put_line('uczący (' || u.X || ', ' || u.Y || '), najbliższe:'); --linijka z info o uczącym
    FOR i IN rec.first .. rec.last LOOP --i wszystkie najbliższe do niego
      dbms_output.put_line('     grupa: ' || rec(i).grupa || ', (' || rec(i).x || ', ' || rec(i).y || '), odległość: ' || rec(i).odleglosc);
    END LOOP;
  END LOOP;
END;

wynik:

Line Pos Text                                                     
29       PL/SQL block, executed in 15 ms                          
         uczący (664, 736), najbliższe:                           
              grupa: 40, (664, 737), odległość: 1                 
              grupa: 30, (675, 738), odległość: 11,180339887498948
              grupa: 34, (654, 748), odległość: 15,620499351813309
              grupa: 83, (643, 728), odległość: 22,472205054244232
         uczący (11, 568), najbliższe:                            
              grupa: 29, (12, 560), odległość: 8,06225774829855   
              grupa: 52, (16, 553), odległość: 15,811388300841897 
              grupa: 56, (30, 562), odległość: 19,924858845171275 
              grupa: 44, (33, 568), odległość: 22                 
         uczący (829, 40), najbliższe:                            
              grupa: 27, (824, 48), odległość: 9,433981132056604  
              grupa: 42, (817, 39), odległość: 12,041594578792295 
              grupa: 6, (820, 30), odległość: 13,45362404707371   
              grupa: 27, (834, 26), odległość: 14,866068747318506 
         uczący (121, 944), najbliższe:                           
              grupa: 23, (118, 937), odległość: 7,615773105863908 
              grupa: 11, (124, 953), odległość: 9,486832980505138 
              grupa: 33, (139, 940), odległość: 18,439088914585775
              grupa: 80, (108, 925), odległość: 23,021728866442676
         uczący (252, 210), najbliższe:                           
              grupa: 7, (251, 218), odległość: 8,06225774829855   
              grupa: 44, (246, 204), odległość: 8,48528137423857  
              grupa: 13, (244, 203), odległość: 10,630145812734649
              grupa: 64, (269, 210), odległość: 17                
         uczący (285, 700), najbliższe:                           
              grupa: 28, (274, 701), odległość: 11,045361017187261
              grupa: 10, (291, 682), odległość: 18,973665961010276
              grupa: 44, (294, 683), odległość: 19,235384061671345
              grupa: 58, (276, 681), odległość: 21,023796041628638
         uczący (868, 338), najbliższe:                           
              grupa: 98, (855, 340), odległość: 13,152946437965905
              grupa: 86, (881, 330), odległość: 15,264337522473748
              grupa: 10, (845, 342), odległość: 23,345235059857504
              grupa: 45, (886, 353), odległość: 23,430749027719963
         uczący (170, 282), najbliższe:                           
              grupa: 16, (165, 282), odległość: 5                 
              grupa: 68, (174, 288), odległość: 7,211102550927979 
              grupa: 66, (166, 297), odległość: 15,524174696260024
              grupa: 10, (180, 296), odległość: 17,204650534085254
         uczący (847, 618), najbliższe:                           
              grupa: 85, (855, 616), odległość: 8,246211251235321 
              grupa: 21, (855, 610), odległość: 11,31370849898476 
              grupa: 62, (839, 637), odległość: 20,615528128088303
              grupa: 33, (834, 638), odległość: 23,853720883753126
         Total execution time 47 ms

Czy coś jeszcze potrzeba?

ogólnie bardzo ciekawie to wygląda i trochę sie namęczyłeś...
ale nie o to mi chodziło... i właśnie dlatego się nie rozumieliśmy
bo ten algorytm nie ma wypisywać tych odległości(ogólnie to ma być jak najkrótszy algorytm)

ale ok... znalazłeś 4 najbliższe pkty(interesują nas tylko te punkty i ich grupa) i teraz trzeba określić do jakich grup one należą bo jak już pisałam to w zbiorze uczącym jest przyporządkowanie do grup, ja mam ich 4.
jak już wiemy do jakiej grupy należy każdy sąsiad to teraz sprawdzamy która grupa wśród nich występuje najczęściej i ją przypisujemy naszemu testowanemu elementowi za zb testowego i tu już jest prawie koniec. Prawie ponieważ trzeba jeszcze obliczyć błąd przypisania czyli ile razy wynik nie zgadza się z faktycznym przyporządkowaniem do grup elementów zb testowego.

co to jest BULK COLLECT?

no to jest jeszcze prościej. Tworzysz sobie tabelę

CREATE TABLE wynik (
  x NUMBER(10,0),
  y NUMBER(10,0),
  grupa NUMBER(5,0))

a całą procedurę wypisującą zmieniasz na

DECLARE
  CURSOR ucz IS SELECT x, y FROM uczacy;
  k NUMERIC(10, 0);
BEGIN
  DELETE FROM wynik;
  k := 5;
  FOR u IN ucz LOOP
    INSERT INTO wynik 
    SELECT
      u.x, 
      u.y,
      grupa
    FROM
      (SELECT
        t.grupa,
        t.X,
        t.Y,
        Sqrt(Power(u.X - t.X, 2) + Power(u.Y - t.Y, 2)) odleglosc
      FROM
        testowy t
      ORDER BY 4)
    WHERE
      ROWNUM < k;
  END LOOP;
END;

i wykonując zapytanie

SELECT x, y, grupa, Count(*) FROM wynik GROUP BY x, y, grupa ORDER BY x, y, 4 DESC

mam dla każdego punktu ze zbioru uczacego ile w jakiej grupie jest elementów i z tym już robisz co chcesz.
tutaj wynik dla 5 punktów

co to jest BULK COLLECT?
pomijając fakt istnienia googla najprościej to "wkłada" cały wynik zapytania do zmiennej i w wyniku mamy jakby tablicę rekordów po której możemy iterować

aha, czyli z tabelki wynika że np dla pkt (2,907) mam 2 sąsiadów z gr 3 i dwóch z gr 4 tak?

a po co tu jest ta 4 na końcu? :

SELECT x, y, grupa, COUNT(*) FROM wynik GROUP BY x, y, grupa ORDER BY x, y, 4 DESC

wg to dlaczego k:=5 skoro pisałeś że wybierasz 4 sąsiadów?

malwinka993 napisał(a)

aha, czyli z tabelki wynika że np dla pkt (2,907) mam 2 sąsiadów z gr 3 i dwóch z gr 4 tak?
tak

a po co tu jest ta 4 na końcu? :

SELECT x, y, grupa, COUNT(*) FROM wynik GROUP BY x, y, grupa ORDER BY x, y, 4 DESC

a jak pisałem, że podstaw SQLa nie masz to się wielce oburzałaś. Ponieważ kolumna nr 4 to COUNT(*) to nie możesz podać tak ...ORDER BY COUNT(*) bo to nie przejdzie. Nie wiem też czy mssql potrafi np. sortować po aliasach kolumn. Za to większość porządnych baz danych potrafi sortować po "numerze kolumny", tzn. zamiast nazwy w ORDER BY można podać numer kolumny po której chcesz posortować (kolumny liczone są od 1)

to dlaczego k:=5 skoro pisałeś że wybierasz 4 sąsiadów?
</quote> bo jest warunek < k a nie <= k czyli jeśli k = 5 to < k będą 1, 2, 3, 4

ale ja wcale nie powiedziałam ze jestem specem od SQLa ja się z tego czuje głupia jak but z lewej nogi :) Co nie znaczy że nie staram się tego zrozumieć:)

a jak teraz w tym przypadku dla tego pkt (2,907) odrzucić najdalszy element żeby można było zdecydować do której grupy ten nasz pkt należy?

to trzeba do tabelki wynik dodać pole odległość i już będziesz miała

w sensie że kolejną kolumnę tak?