Szukasz porady tutaj. Czy ktokolwiek zna dobre miejsce, aby zacząć szukać zgodnego algorytmu w przestrzeni n-wymiarowej? Na przykład, każda strona randkowa musi używać jakiegoś algorytmu, aby dopasować 2 osoby. To, co przeczytałem, to to, że możemy odwzorować cechy osoby w n-wymiarowej tablicy z systemem punktowym dla każdej cechy. Kiedy już posiadamy wszystkie (dostępne) cechy danej osoby, możemy ją reprezentować w punkcie w obrębie tablicy n-wymiarowej. Następnie, aby dopasować 2 osoby byłoby tak proste, jak znalezienie najkrótszej odległości między 2 punktami w tej tablicy n-dim. Czy ktokolwiek ma jakieś odniesienia w implementacji tego rodzaju algorytmu? Jaki jest najlepszy język do pisania tego typu rzeczy?algorytm dopasowania n-wymiarowego
Odpowiedz
Po pierwsze wybierz język, który najbardziej Ci odpowiada. Algorytmy radzenia sobie z tym są dość proste i powinny działać w każdym nowoczesnym języku. (Dopóki istnieje jakaś koncepcja tablicy i potencjalnie biblioteki macierzy, powinieneś mieć się dobrze.) Zaimplementowałem wiele z nich w C, C++ i C# wcześniej, ale widziałem implementacje w pythonie, vb.net, itp.
W zależności od tego, co próbujesz zrobić, jest kilka opcji.
W związku z tym, co chcesz zrobić, zależy od celów. Jeśli chcesz po prostu znaleźć najlepsze dopasowanie, możesz użyć prostych obliczeń odległości (np. Sqrt sumy kwadratów dla każdego wymiaru/właściwości w tablicy n-wymiarowej), opcjonalnie waga każdej odległości właściwości i użyć najbliższego punktu.
Jeśli chcesz zgrupować osoby, musisz spojrzeć na numer clustering algorithms. W przypadku takich danych podejrzewam, że jakaś forma grupowania K-średnich lub rozmytych klastrów w skali C działałaby najlepiej.
Jeśli chcesz znaleźć najbliższy mecz dla jednej osoby, Bentley & Shamos opublikował wielowymiarową metodę dziel i zwyciężaj: dziel i zwyciężaj w O (N log N) czas: Divide-and-conquer in multidimensional space w obradach ósme doroczne sympozjum ACM na temat teorii komputerów w 1976 roku. Jeśli nie możesz uzyskać kopii this, może być również pomocne.
Jednak dla twojego przykładu zastosowanie znalezienia najbliższego sąsiada nie wydaje się największym problemem - dużo trudniejsze jest mapowanie danych wejściowych na wymiary. Na przykład, jeśli jeden wymiar to "lubi zwierzęta", jaką wartość dajesz osobie, która lubi psy, ale nie może znieść koni? A co z kimś, kto kocha konie, myśli, że psy są w porządku, jest zirytowany przez koty i ma ambiwalentny stosunek do złotych rybek?
Proces, o którym wspomniałeś, jest znany jako k-najbliższego sąsiada, przy k = 1. Jest to najbardziej intuicyjne podejście do wyszukiwania podobnych wektorów.
Jak o następujące rozwiązania.
Założeniem użytkowników są U1, U2, U3, U4, U5 .... Un. Atrybuty to A1, A2, A3, A4, A5 ..... Am
Przechowywać je jako
A1 - U1, U2, U3 ... A2 - U4, U6, U7 ... A3 -
Atrybut profilu jest indeksem i zapisuje wszystkich użytkowników. Teraz, jeśli pojawi się nowy użytkownik, zobacz jego atrybuty i atrybuty, znajdź zwykłych ludzi. liczba przypadków, gdy dana osoba znajduje się na tych listach - wyższa pozycja.
To, co opisujesz za pomocą swojego przykładu, nie jest dopasowaniem n-wymiarowym, ale raczej bipartite matching węzłów z wieloma funkcjami. (Musisz podać funkcję, która przy obliczaniu odległości dwóch osób). Powinny to być bardzo skuteczne algorytmy. W dopasowaniu n-wymiarowym próbowałbyś dopasować węzły z więcej niż dwóch zestawów (w twoim przykładzie, przypuśćmy, że możesz przyciąć ludzi do ciał, duszy i preferencji muzycznych, a następnie połączyć je w celu stworzenia nowych osób. odciąć ludzi od siebie i połączyć je tak, aby nowo stworzone osoby tworzyły naprawdę miłe pary: D) Oto wikipedia article for 3-dimentional matching, który jest np-complete.
Także, jak zauważyła inna osoba, jeśli twoim celem nie jest dopasowywanie osób w pary, ale raczej znajdowanie zgodnych grup, powinieneś rozważyć grupowanie ich w grupy. Można to zrobić za pomocą np. Unsupervised Learning
Dobry punkt na dopasowywaniu ludzi do wymiarów. Może coś w rodzaju skali na jeden wymiar, czyli: ktoś, kto lubi koty + psy, ale nienawidzi koni, otrzyma + 1/+ 1/-1, czyli: +1 jako wynik w tym wymiarze, lub coś podobnego. –
@danio: Możesz zawsze rozbić pojedynczy wymiar "lubi zwierzęta" na osobne wymiary "lubi psy", "lubi koty" itp. –