Wybór funkcji drzewa decyzyjnego o stałej długości w celu zminimalizowania średniej wydajności wyszukiwania

Mam złożone zapytanie używane do przeszukiwania zestawu danych celu znalezienia . Każde zapytanie zajmuje średni czas więc całkowity czas w wyszukiwaniu liniowym wynosi. Mogę podzielić zapytanie na prostsze zapytania częściowe q_i i znaleźć i gdzie . Każde podzapytanie jest znacznie szybsze do obliczenia, więc ogólnie szybciej jest znaleźć a następnie użyć aby znaleźć .$Q$$S$$H_\text{exact} = \{s \in S \mid \text{where $Q(s)$ is True}\}$$t$$t\cdot |S|$$H_\text{approx} = \{s\in S \mid \forall q_j(s) \text {is True}\}$$H_\text{exact}\subseteq H_\text{approx}$$q_i$$H_\text{approx}$$Q$$H_\text{exact}$

Każde ma wiele . Nakładanie się różnych jest duże. Szukam sposobu na ustalenie zestawu stałych pytań do drzewa decyzyjnego które minimalizują średni czas znalezienia H_exact, na podstawie dużej próby zapytań.$Q$$q_i$$Q$$q_j$

Mówiąc konkretniej, załóżmy, że zestaw danych zawiera 7 miliardów ludzi na świecie, a złożone zapytania to np. „Kobieta, która mieszka w czerwonym domu na rogu 5. i Lexington w mieście zaczynającym się na B.”

Oczywistym rozwiązaniem jest sprawdzenie każdej osoby na świecie i sprawdzenie, kto pasuje do zapytania. Może być więcej niż jedna taka osoba. Ta metoda zajmuje dużo czasu.

Mógłbym dokładnie obliczyć to zapytanie, w takim przypadku byłoby to bardzo szybkie .. ale tylko dla tego pytania. Wiem jednak, że inne pytania dotyczą kobiety mieszkającej w niebieskim domu w tym samym rogu, mężczyzny mieszkającego w tym samym rogu, tego samego pytania, ale w mieście zaczynającym się na C lub czegoś zupełnie innego, na przykład król Szwecji. ”

Zamiast tego mogę rozbić złożone pytanie na zestaw łatwiejszych, ale bardziej ogólnych zestawów. Na przykład wszystkie powyższe pytania zawierają zapytanie oparte na roli płci, więc mogę wstępnie obliczyć zbiór wszystkich ludzi na świecie, którzy uważają się za „kobiety”. To pod-zapytanie zasadniczo nie zajmuje czasu, więc ogólny czas wyszukiwania zmniejsza się o około 1/2. (Zakładając, że z innej wiedzy wiemy, że szwedzki „król” nie może być „kobietą”. Hatszepsut była Egipską kobietą, która była królem.)

Czasami jednak pojawiają się zapytania, które nie są oparte na płci, np. „Osoba, która mieszka na 8 ulicy w czerwonym domu w mieście, zaczynając od A.” Widzę, że podzapytanie „mieszka w czerwonym domu” jest powszechne i wstępnie oblicza listę wszystkich ludzi, którzy mieszkają w czerwonym domu.

To daje mi drzewo decyzyjne. W zwykłym przypadku każda gałąź drzewa decyzyjnego zawiera inne pytania, a metody wyboru optymalnych terminów dla drzewa decyzyjnego są dobrze znane. Opieram się jednak na istniejącym systemie, który wymaga, aby wszystkie oddziały musiały zadawać te same pytania.

Oto przykład możliwego ostatecznego zestawu decyzji: pytanie 1 brzmi „czy osoba jest kobietą?”, Pytanie 2 brzmi „czy dana osoba mieszka w czerwonym domu?”, Pytanie 3 brzmi „czy dana osoba mieszka w mieście zaczynając od A lub czy dana osoba mieszka w mieście zaczynającym się na B? ”, A pytanie 4 brzmi„ czy dana osoba mieszka na ponumerowanej ulicy? ”.

Kiedy pojawia się zapytanie , sprawdzam, czy jego pasuje do któregoś z wcześniej obliczonych pytań , które ustaliłem. Jeśli tak, to otrzymuję skrzyżowanie tych odpowiedzi i zadaję pytanie w tym podzbiorze skrzyżowań. Na przykład, jeśli pytanie brzmi „ludzie, którzy mieszkają w czerwonym domu na wyspie”, to okaże się, że „osoba mieszka w czerwonym domu” jest już wstępnie obliczona, więc chodzi tylko o znalezienie podzbioru tych, którzy również mieszkają na wyspie.$Q$$q_i$$q_j$$Q$

Mogę uzyskać model kosztu, patrząc na zestaw wielu i sprawdzając, czy jest odpowiedni rozmiar . . Chcę zminimalizować średni rozmiar .$Q$$H_\text{approx}$$H_\text{approx}$

Pytanie brzmi: jak zoptymalizować wybór możliwych aby stworzyć to drzewo decyzji? Próbowałem GA, ale zbiegało się powoli. Prawdopodobnie dlatego, że moja przestrzeń funkcji ma kilka milionów możliwych . Wymyśliłem chciwą metodę, ale nie jestem zadowolony z rezultatu. To także jest bardzo powolne i myślę, że optymalizuję złą rzecz.$q_j$$q_j$

Na jakie istniejące badania powinienem szukać pomysłów?

Rozwiązaniem, które znalazłem (zadałem pytanie), jest zastosowanie kodowania nałożonego, a dokładniej wariant Zatocoding, który ma lepszą obsługę deskryptorów hierarchicznych.

Metoda, której użyłem, pochodzi z „Efektywnego projektu do wyszukiwania struktury chemicznej. I. Screens ”, Alfred Feldman i Louis Hodes, J. Chem. Inf. Comput. Sci., 1975, 15 (3), s. 147–152.

Niehierarchicznym rozwiązaniem jest sprawdzenie gęstości informacji. Każdy deskryptor zostanie przypisany$s_i=-log_2(f_i)$ bitów gdzie $f_i$ to częstotliwość w zestawie danych ($0<$f_i <= 1,0). Oblicz całkowitą liczbę bitów$D$ (rozmiar drzewa decyzyjnego) za pomocą $D=\sum(s_i f_i)/M_c$ gdzie $M_c$ to współczynnik kompresji Mooersa 0,69 (od $log_e 2$). Po określeniu całkowitej liczby bitów do użycia wybierz$s_i$ bity losowo dla każdego deskryptora do przypisania bitów.

Hierarchiczne rozwiązanie Feldman i Hodes zastępuje $s_i=-log_2(f_i)$dla deskryptorów będących podzbiorem innych deskryptorów. W takim przypadku użyj$s_i=-log_2(f_i/g_i)$ gdzie $g_i$to częstotliwość najmniejszego rodzica. Ponadto, wykonując przypisanie bitów, nie wybieraj bitów, które są również używane przez przypisanie bitów przez rodzica.

Nadal istnieje problem ze znalezieniem odpowiednich deskryptorów, ale będzie to zależało od domeny.