Temat: Obliczanie współrzędnych punktów (trudne?)

Witam serdecznie,

Wstęp
Mam problem z którym borykam się już od dosyć długiego czasu, rozmawiałem na jego temat z różnymi osobami - również w przeciwieństwie do mnie takimi które dobrze czują się w matematyce - ale niestety ostatecznie nie udało mi się uzyskać satysfakcjonującej mnie odpowiedzi.

Zadanie
"Mam 100 punktów i znam odległości między nimi wszystkimi jednocześnie. Czyli jeżeli mam trzy punkty A, B i C to znam odległości między A-B,B-C,C-A. Dodatkowo może się zdarzyć tak, że odległość pomiędzy B i C jest np. 2 razy większa niż suma odległości między A-B i A-C. Oznacza to, że należałoby niektóre odległości "naciągnąć" a inne "skrócić" o tyle o ile to będzie konieczne. Jako efekt końcowy chcę uzyskać na kwadracie wykres na którym zobaczę wszystkie 100 punktów poukładanych zgodnie za założeniami powyżej."

Przykład
mamy Piotra, Grzegorza i Asię. Piotr i Grzegorz uwielbiają Anię. Najchętniej stanęliby zaraz obok niej (odleglość= 1). Niestety Piotr z Grzegorzem szczerze się nienawidzą (odległość =100), więc żeby jakoś to wszystko zrównoważyć muszą się od siebie oddalić a tym samym oddalić się od Asi. Dlatego oddalają się od Asi na odległość 25, a między sobą na 50. Kompromis.

Czy może Ktoś z Was jest mi w stanie w tym pomóc?

PS 1: dla matematyków podobno nie ma to znaczenia bo z natury swojej operują na abstrakcjach, ale może niektórym z Was przyda się informacja, że chodzi mi o to by pokazać na takim wykresie wszystkich użytkowników serwisu http://beczkasoli.pl. W tym serwisie istnieją tylko wartości podobieństwa między poszczególnymi użytkownikami w przedziele od 0-100 (procent). Efektem ma być wykres który od razu pokaże kto z kim jest podobny, kto odstaje (jest outsiderem), kto jest typowym mainstreamowcem itd. :-)

PS 2: jeżeli to możliwe, to proszę unikać wpisywania informacji o problemach - problemy są zawsze i wszędzie w dowolnej ilości - rozwiązania będą znacznie ciekawsze :-)

Z góry dziękuję za pomoc.

Piotr GolczykPiotr Golczyk edytował(a) ten post dnia 04.10.09 o godzinie 19:52

Temat: Obliczanie współrzędnych punktów (trudne?)

jesli nie jest spelniona nierownosc trojkate, to znaczy, ze metryka podobienstwa, ktorej uzywasz jest troche bez sensu, moze zmien metryke podobienstwa.

Temat: Obliczanie współrzędnych punktów (trudne?)

Krzysztof Łatuszyński:
jesli nie jest spelniona nierownosc trojkate, to znaczy, ze metryka podobienstwa, ktorej uzywasz jest troche bez sensu, moze
zmien metryke podobienstwa.

Mógłbyś wyjaśnić szerzej bo nie rozumiem zarzutu :-)

Temat: Obliczanie współrzędnych punktów (trudne?)

Piotr Golczyk:
Dodatkowo może się zdarzyć tak, że odległość pomiędzy B i C jest np. 2 razy większa niż suma odległości między A-B i A-C.

To ozacza, że prawo trójkąta nie jestr spełnione.
Na zdrowy rozum podobieństwo użytkowników powinno byc tak zdefiniowane, że prawo trójkąt zachodzi.

Temat: Obliczanie współrzędnych punktów (trudne?)

Piotr eS:

Piotr Golczyk:
Dodatkowo może się zdarzyć tak, że odległość pomiędzy B i C jest np. 2 razy większa niż suma odległości między A-B i A-C.

To ozacza, że prawo trójkąta nie jestr spełnione.
Na zdrowy rozum podobieństwo użytkowników powinno byc tak zdefiniowane, że prawo trójkąt zachodzi.

Ależ ono oczywiście że zachodzi.
Przykład: masz Piotra, Grzegorza i Asię. Piotr i Grzegorz uwielbiają Anię. Najchętniej stanęliby zaraz obok niej (odleglość= 1). Niestety Piotr z Grzegorzem szczerze się nienawidzą (odległość =100), więc żeby jakoś to wszystko zrównoważyć muszą się od siebie oddalić a tym samym oddalić się od Asi. Dlatego oddalają się od Asi na odległość 25, a między sobą na 50. Po prostu kompromis - równowaga energetyczna. To przykład z życia. Jeżeli tu działa to i w matematyce na pewno też :-)Piotr Golczyk edytował(a) ten post dnia 04.10.09 o godzinie 19:41

Temat: Obliczanie współrzędnych punktów (trudne?)

Więc możesz to przedstawić na trójwymiarowym wykresie słupkowym.
na osi x wypisujesz nazwiska. Na osi y te same nazwiska.
W punktach przecięcia wpisujesz odległości (tak samo jak w odległości pomiędzy miastami w atlasach samochodwych). Możesz tez liczby zamienić na słupki, reprezentujące te liczby.
W ten sposób otrzymasz trójwymiarowy wykres.

Żeby wyłonić outsiderów i mainstreamowców wystarczy zsumować wartości należące do osób (np pionowo) i przedstawić w postaci wykresu słupkowego. Ci co mają najmniejszy słupek top mainstreamowcy, a ci z największym będa outsiderami.

Temat: Obliczanie współrzędnych punktów (trudne?)

Chodzi mi coś takiego, tylko zamiast miejscowości masz nazwiska, a w miejsce liczb możesz wstawić słupki je reprezentujące.



Do wyłonienia outsiderów i upstreamowców sumujesz kolumny.

Temat: Obliczanie współrzędnych punktów (trudne?)

Wydaje mi sie, ze chcesz zrobic skalowanie wielowymialreowe.

Poszukaj w internecie pod tym haslem.

Albo w ksiazce Koronacki, Cwik.

Na tej stronie www popatrz na cwiczenia 7 z przykladami skalowania wielowymiarowego zrobionego w R i (na czerwono) przykladem z wykladu zrobionym w R.
http://akson.sgh.waw.pl/~klatus/WNEstatMatII.htmKrzysztof Łatuszyński edytował(a) ten post dnia 04.10.09 o godzinie 21:04

Temat: Obliczanie współrzędnych punktów (trudne?)

Piotr eS:
Więc możesz to przedstawić na trójwymiarowym wykresie słupkowym.
na osi x wypisujesz nazwiska. Na osi y te same nazwiska.
W punktach przecięcia wpisujesz odległości (tak samo jak w odległości pomiędzy miastami w atlasach samochodwych). Możesz tez liczby zamienić na słupki, reprezentujące te liczby.
W ten sposób otrzymasz trójwymiarowy wykres.

Żeby wyłonić outsiderów i mainstreamowców wystarczy zsumować wartości należące do osób (np pionowo) i przedstawić w postaci wykresu słupkowego. Ci co mają najmniejszy słupek top mainstreamowcy, a ci z największym będa outsiderami.

Dokładnie tak samo to rozumiem jak tablicę z odległościami miast. Ogólnie jestem w stanie nawet samodzielnie zrobić jakąś wizualizację tego o czym mówię. Problem w tym, że ta wizualizacja musi być wyjątkowo "ludzka". Dlatego stwierdziłem, że układ jaki zaproponowałem - czyli punkty (użytkownicy) odpowiednio w stosunku do siebie poustawiani będą najbardziej naturalnym sposobem przedstawienia zależności w grupie ludzi.

Temat: Obliczanie współrzędnych punktów (trudne?)

Krzysztof Łatuszyński:
Wydaje mi sie, ze chcesz zrobic skalowanie wielowymialreowe.

Czy chodzi o coś takiego jak Simmon Mapping (coś obiło mi się o uszy). Tylko że w sumie to ja nie muszę mieć 3 wymiarów rzutowanych na 2. Od razu chciałbym to rozegrać na 2 wymiarach.

Temat: Obliczanie współrzędnych punktów (trudne?)

Piotr Golczyk:

Dokładnie tak samo to rozumiem jak tablicę z odległościami miast. Ogólnie jestem w stanie nawet samodzielnie zrobić jakąś wizualizację tego o czym mówię. Problem w tym, że ta wizualizacja musi być wyjątkowo "ludzka". Dlatego stwierdziłem, że układ jaki zaproponowałem - czyli punkty (użytkownicy) odpowiednio w stosunku do siebie poustawiani będą najbardziej naturalnym sposobem przedstawienia zależności w grupie ludzi.

Może i wizualizacja punktami na kwadracie byłaby ludzka. Ale wydaje mi się, że patrząc na taki kwadrat nie dałoby się od razu ocenić kto jest np. bardziej mainstreamowy: A, czy B, skoro różnice między nimi byłyby paroprocentowe. Jeśli to nie ma znaczenia to ok. A jeśli ma, to można byłoby ludziom pokazać tabelkę odległości jak w poście Piotra, lecz pokolorowaną - np. czerwony leader i niebieski outsider. Wtedy szukając absolutnych leaderów patrzę na mniejsze liczby na czerwonych polach. To zajmuje oczywiście znacznie mniej czasu niż szukanie minimalnych liczb na tabelce bez kolorów.

Temat: Obliczanie współrzędnych punktów (trudne?)

Piotr Golczyk:

Krzysztof Łatuszyński:
Wydaje mi sie, ze chcesz zrobic skalowanie wielowymialreowe.

Czy chodzi o coś takiego jak Simmon Mapping (coś obiło mi się o uszy). Tylko że w sumie to ja nie muszę mieć 3 wymiarów rzutowanych na 2. Od razu chciałbym to rozegrać na 2 wymiarach.

z powodow matematycznych, majac dana macierz odleglosci (w Twoim przypadku podobienstw), nie da sie n punktow polozyc na plaszczyznie zgodnie z ta macierza.

zeby umiescic n punktow zgodnie z macierza odleglosci, potrzebna jest przestrzen n-1 wymiarowa.

zeby zobrazowac graficznie n punktow w n-1 wymiarowej przestrzeni, znajduje sie taki kierunek rzutu na 2 wymiarowa przestrzen (plaszczyzne), zeby polozenie punktow bylo jak najbardziej zroznicowane. potem rysuje sie ten rzut.

krotko mowiac, nie da sie tego od razu rozegrac w dwoch wymiarach, tak jak nie da sie rozegrac gry w koszykowke w dwoch wymiarach, ale da sie (w sposob niedoskonaly) obejrzec w dwoch wymiarach, tak jak oglada sie gre w koszykowke na dwuwymiarowej plaszczyznie ekranu telewizora...

i, kontynuujac alegorie ;) , skalowanie wielowymiarowe w sposob automatyczny (uzywajac algorytmu) wybierze taki rzut, na ktorym duzo widac, tzn akcja dzieje sie glownie na kierunku prostopadlym do kierunku rzutu, tak jak w koszykowce w danym momencie wybiera sie (przypuszczam recznie) odpowiednia kamere, taka, zeby akcja byla na kierunku prostopadlym do tej kamery...

w standardowych procedurach R gdzies tam sa opcje ktore cos tam robia z Twoja macierza podobienstwa, jeli ona nie spelnia warunku trojkata, jesli bys tego uzywal, to powinienes tam pogrzebac.Krzysztof Łatuszyński edytował(a) ten post dnia 05.10.09 o godzinie 00:43

Temat: Obliczanie współrzędnych punktów (trudne?)

Tomasz Krzal:

Piotr Golczyk:

Dokładnie tak samo to rozumiem jak tablicę z odległościami miast. Ogólnie jestem w stanie nawet samodzielnie zrobić jakąś wizualizację tego o czym mówię. Problem w tym, że ta wizualizacja musi być wyjątkowo "ludzka". Dlatego stwierdziłem, że układ jaki zaproponowałem - czyli punkty (użytkownicy) odpowiednio w stosunku do siebie poustawiani będą najbardziej naturalnym sposobem przedstawienia zależności w grupie ludzi.

Może i wizualizacja punktami na kwadracie byłaby ludzka. Ale wydaje mi się, że patrząc na taki kwadrat nie dałoby się od razu ocenić kto jest np. bardziej mainstreamowy: A, czy B, skoro różnice między nimi byłyby paroprocentowe. Jeśli to nie ma znaczenia to ok. A jeśli ma, to można byłoby ludziom pokazać tabelkę odległości jak w poście Piotra, lecz pokolorowaną - np. czerwony leader i niebieski outsider. Wtedy szukając absolutnych leaderów patrzę na mniejsze liczby na czerwonych polach. To zajmuje oczywiście znacznie mniej czasu niż szukanie minimalnych liczb na tabelce bez kolorów.

Za bardzo się przywiązaliśmy do tego kto jest outsiderem a kto nie. Ten wykres powinien mi powiedzieć, że jestem np. w grupce niewielkiej ale ścisłej gdzieś na krańcu wykresu - "odrzuceni". Chodzi w tym wypadku bardziej o formę niż precyzyjność obliczeń. Dlatego bardziej próbowałbym rozwiązać problem rozmieszczenia tych punktów - który jest trudny - niż szukał rozwiązania innego.

Temat: Obliczanie współrzędnych punktów (trudne?)

Krzysztof Łatuszyński:

Piotr Golczyk:

Krzysztof Łatuszyński:
Wydaje mi sie, ze chcesz zrobic skalowanie wielowymialreowe.

Czy chodzi o coś takiego jak Simmon Mapping (coś obiło mi się o uszy). Tylko że w sumie to ja nie muszę mieć 3 wymiarów rzutowanych na 2. Od razu chciałbym to rozegrać na 2 wymiarach.

z powodow matematycznych, majac dana macierz odleglosci (w Twoim przypadku podobienstw), nie da sie n punktow polozyc na plaszczyznie zgodnie z ta macierza.

zeby umiescic n punktow zgodnie z macierza odleglosci, potrzebna jest przestrzen n-1 wymiarowa.

zeby zobrazowac graficznie n punktow w n-1 wymiarowej przestrzeni, znajduje sie taki kierunek rzutu na 2 wymiarowa przestrzen (plaszczyzne), zeby polozenie punktow bylo jak najbardziej zroznicowane. potem rysuje sie ten rzut.

krotko mowiac, nie da sie tego od razu rozegrac w dwoch wymiarach, tak jak nie da sie rozegrac gry w koszykowke w dwoch wymiarach, ale da sie (w sposob niedoskonaly) obejrzec w dwoch wymiarach, tak jak oglada sie gre w koszykowke na dwuwymiarowej plaszczyznie ekranu telewizora...

i, kontynuujac alegorie ;) , skalowanie wielowymiarowe w sposob automatyczny (uzywajac algorytmu) wybierze taki rzut, na ktorym duzo widac, tzn akcja dzieje sie glownie na kierunku prostopadlym do kierunku rzutu, tak jak w koszykowce w danym momencie wybiera sie (przypuszczam recznie) odpowiednia kamere, taka, zeby akcja byla na kierunku prostopadlym do tej kamery...

w standardowych procedurach R gdzies tam sa opcje ktore cos tam robia z Twoja macierza podobienstwa, jeli ona nie spelnia warunku trojkata, jesli bys tego uzywal, to powinienes tam pogrzebac.

Wiesz co - brzmi to wiarygodnie. Brzmi to też strasznie ;-)). Wychodzi bowiem, że oprócz tego że muszę tworzyć powiedzmy 400-wymiarową przestrzeń, to muszę potem ją rzutować na 2 wymiary. Dwa skomplikowane (?) jak sądze procesy programistyczne (a może się mylę?)

A obliczać tego sekwencyjnie się nie da? Najpierw wrzucam dwa punkty. Potem dorzucam trzeci. Potem czwarty, piąty i tak bez końca aż nie osiagnę tego co chce?

Jakieś sekwencyjne operacje na trójkątach? (tak rzucam bo nie wiem)Piotr Golczyk edytował(a) ten post dnia 05.10.09 o godzinie 11:28

Temat: Obliczanie współrzędnych punktów (trudne?)

Ten drugi proces wcale trudny nie jest - załatwia Ci to PCA, standardowa procedura w R.

Można też całkiem inaczej. Układasz punkty na płaszczyźnie tak, by ich macierz odległości była w jakimś sensie blisko Twojej macierzy. Powiedzmy, że masz rozrzucone punkty. Dla każdego z nich liczysz odległości do pozostałych, a potem procentowe różnice między policzonymi i danymi odległościami. Sumujesz wszystko (wykluczając symetryczne przypadki) i otrzymujesz "stratę". Minimalizujesz tę stratę po wszystkich układach punktów.

Temat: Obliczanie współrzędnych punktów (trudne?)

Tomasz Szmidt:
Ten drugi proces wcale trudny nie jest - załatwia Ci to PCA, standardowa procedura w R.

Można też całkiem inaczej. Układasz punkty na płaszczyźnie tak, by ich macierz odległości była w jakimś sensie blisko Twojej macierzy. Powiedzmy, że masz rozrzucone punkty. Dla każdego z nich liczysz odległości do pozostałych, a potem procentowe różnice między policzonymi i danymi odległościami. Sumujesz wszystko (wykluczając symetryczne przypadki) i otrzymujesz "stratę". Minimalizujesz tę stratę po wszystkich układach punktów.

Parafrazując: biorę punkty i układam je obok siebie "tak mniej więcej" jakie są odległości, potem je uszczegóławiam?

Druga sprawa co to jest PCA?

Temat: Obliczanie współrzędnych punktów (trudne?)

Możesz użyć to:

http://www.xlstat.com/en/support/tutorials/mds.htm

Temat: Obliczanie współrzędnych punktów (trudne?)

Piotr Golczyk:

Parafrazując: biorę punkty i układam je obok siebie "tak mniej więcej" jakie są odległości, potem je uszczegóławiam?

"Tak mniej więcej" może być dobrym punktem startu. Jeśli funkcję celu (stratę) zadasz tak, by była kwadratowa, a punkty ograniczysz do jakiegoś kwadratu, to Twój problem jest wypukły, a jego rozwiązanie spełnia układ równań dany przez warunki KKT.

Druga sprawa co to jest PCA?

Obrót Twojej chmury punktów, po którym zróżnicowanie w kierunku kolejnych osi jest coraz mniejsze. Dzięki temu zrzutowanie punktów na płaszczyznę rozpiętą przez dwie pierwsze osie będzie tym, czego potrzebujesz ;-).
Skalowanie wielowymiarowe to inne podejście do tego samego problemu. Poczytaj.

Temat: Obliczanie współrzędnych punktów (trudne?)

Tomasz Szmidt:

Piotr Golczyk:
Parafrazując: biorę punkty i układam je obok siebie "tak mniej więcej" jakie są odległości, potem je uszczegóławiam?

"Tak mniej więcej" może być dobrym punktem startu. Jeśli funkcję celu (stratę) zadasz tak, by była kwadratowa, a punkty ograniczysz do jakiegoś kwadratu, to Twój problem jest wypukły, a jego rozwiązanie spełnia układ równań dany przez warunki KKT.

A co to jest KKT?

Druga sprawa co to jest PCA?

Obrót Twojej chmury punktów, po którym zróżnicowanie w kierunku kolejnych osi jest coraz mniejsze. Dzięki temu zrzutowanie punktów na płaszczyznę rozpiętą przez dwie pierwsze osie będzie tym, czego potrzebujesz ;-).
Skalowanie wielowymiarowe to inne podejście do tego samego

Słuchaj a ja dzisiaj doszedłem do wniosku, że jest to nie do obliczenia. Mam powiedzmy 100 punktów. Poruszenie jednego punktu powoduje ruch 99 pozostałych, jednak każdy z tych punktów generuje ruch 98 punktów o ile się nie mylę to jest 100 do 100-potęgi operacji. czy ja się mylę?

problemu. Poczytaj.

Temat: Obliczanie współrzędnych punktów (trudne?)

Piotr Golczyk:

A co to jest KKT?

Warunki Karusha-Kuhna-Tuckera, które spełnia rozwiązanie w problemie minimalizacji funkcji wypukłej na zbiorze wypukłym. Układ równań dany przez ten warunki rozwiązujesz jakąś procedura numeryczną (np. Newtona), otrzymując współrzędne wszystkich punktów na płaszczyźnie.

Jeśli nie chcesz tego programować, to poszukaj gotowych procedur minimalizacji funkcji.

Słuchaj a ja dzisiaj doszedłem do wniosku, że jest to nie do obliczenia. Mam powiedzmy 100 punktów. Poruszenie jednego punktu powoduje ruch 99 pozostałych, jednak każdy z tych punktów generuje ruch 98 punktów o ile się nie mylę to jest 100 do 100-potęgi operacji. czy ja się mylę?

Dlaczego generuje? Przecież wzajemne odległości tych punktów i tak nie będą (w ogólności) równe zadanym. Chcemy tylko, by za dużo się nie różniły - jeśli strata jest ciągłą funkcją ich położenia, to rozwiązanie będzie istniało.

A w ogóle musisz koniecznie to rysować??? Mając odległości możesz zrobić fajną klasteryzację, zwaną niekiedy - od nazwiska słynnego skoczka - analizą skupień ;), czyli wydzielić kółka wzajemnej adoracji...