Łatwy sposób na udowodnienie, że ten algorytm ostatecznie się kończy

Wprowadzenie i notacje:

Oto nowa i prosta wersja mojego algorytmu, która wydaje się kończyć (zgodnie z moimi eksperymentami), a teraz chciałbym to udowodnić.

Niech notacja odnosi się do wymiarowego punktu danych (wektora). Mam trzy zestawy A, B i C, takie że ,$x_i \in \mathbb{R}^p$$p$$|A| = n$$|B| = m$ ,$|C| = l$ :

Biorąc pod uwagę , niech oznacza średnią odległość euklidesową od do jej najbliższych punktów w ; i oznacza średnią odległość euklidesową z jego najbliższego punktów .$k \in \mathbb{N^*}$$d_{x_i}^A$$x_i$$k$$A$$d_{x_i}^C$$x_i$$k$$C$

Algorytm:

Mam następujący algorytm, który iteracyjnie modyfikuje zestawy A i B, przenosząc niektóre wybrane elementy z A na B i odwrotnie, a C pozostaje zawsze takie samo (nie zmieniaj). Upraszczając: celem algorytmu jest lepsze rozdzielenie zbiorów i taki sposób, aby „punkty były bardziej podobne do punktów znanego ustalonego zestawu ” i „punkty są w końcu samopodobne i dalej od i końcowego zestawu ":$A$$B$$B$$C$$A$$C$$B$

• $A' = \{ x_i \in A \mid d_{x_i}^A > d_{x_i}^C \}$ ... (1)
• $A = A \setminus A'$ ; ... (2)$B = B \cup A'$
• $B' = \{ x_i \in B \mid d_{x_i}^A < d_{x_i}^C$ } ... (3)
• $B = B \setminus B'$ ; ... (4)$A = A \cup B'$
• Powtarzaj (1), (2), (3) i (4), dopóki: (żaden element nie przesunie się z na lub z na , czyli A 'i B' się opróżnią) lub ( lub )$A$$B$$B$$A$$|A| \leq k$$|B| \leq k$

Algorytm kończy się w dwóch przypadkach:

• kiedylubstaje się mniejsza lub równa$|A|$$|B|$$k$
• lub najbardziej standardowy przypadek, gdy , co oznacza, że ​​nie ma już więcej elementów między A i B.$A' = B' = \emptyset$

Pytanie:

Jak udowodnić, że ten algorytm ostatecznie się kończy? Nie znalazłem wygodnej potencjalnej funkcji, którą algorytm może ściśle zminimalizować lub zmaksymalizować. Próbowałem bezskutecznie niektórych funkcji: funkcja ale nie zwiększa się przy każdej iteracji. Funkcja ale nie zmniejsza się przy każdej iteracji. Funkcja wydaje się nie zmniejszać przy każdej iteracji. Funkcja$\sum_{x \in A} d_x^C + \sum_{x \in B} d_x^A$$\sum_{x \in A} d_x^A + \sum_{x \in B} d_x^C$$\sum_{x \in A} d_x^A + \sum_{x \in B} d_x^B$$\sum_{x \in A} d_x^B + \sum_{x \in B} d_x^A$wydaje się nie rosnąć z każdą iteracją. Jaka jest wygodna potencjalna funkcja, którą można zwiększyć lub zmniejszyć przy każdej iteracji? Czy też powinniśmy pokazać, że funkcja maleje, ale nie przy każdej iteracji (raczej po kilku iteracjach)? W jaki sposób ?

Uwagi:

• najbliżej punktów w zbiorze , oznacza: punktów (inne niż ) w , mające najmniejszą euklidesową odległość . Możesz po prostu wziąć aby uprościć analizę.$k$$x$$S$$k$$x$$S$$x$$k = 1$
• Nie wiem, czy to może pomóc, czy nie, ale mam następującą właściwość dla moich początkowych zestawów : początkowo , jeśli jest najbliższym punktem do i to najbliższy punkt do a następnie zawsze . Ten intuicyjnie oznacza, że punkty są bliżej niż punktach .$A, B, C$$\forall x_i \in B, x_j \in A$$x_b \in C$$x_i$$x_a \in C$$x_j$$distance(x_i, x_b) < distance(x_j, x_a)$$B$$C$$A$
• Jeśli to ułatwi analizę: całkowicie możliwe jest rozważenie nieco innej wersji Algorytmu, w której punkt z punktu powinien zostać przeniesiony do punktu , zostaje on przeniesiony z punktu do punktu (bez omijania punktu ), a vis versa dla .$A$$B$$A$$B$$A'$$B$

Oto rozwiązanie dla przypadku k = 1 :$k = 1$

Załóżmy, że algorytm się nie kończy. Ponieważ istnieje skończona liczba stanów algorytmu (przypisanie punktów do A i B ), stan algorytmu musi się powtarzać w cyklu. Ponieważ cykl przechodzi przez różne stany, musi istnieć punkt, który przełącza się między A i B nieskończenie często.$A$$B$$A$$B$

Niech x będzie punktem, który zmienia się nieskończenie często w tym cyklu. Odebrać pierwszej iteracji algorytmu w cyklu, podczas której x zmienia się z B do A . Dla x , aby przełączyć na A , musi być co najmniej jeden punkt x ' w A , a d C x > d Jestem s T ( x , x ' ) . Arbitralnie wybierz najmniejszy taki punkt; zdefiniuj funkcję f, tak aby f ( x ) $x$$x$$B$$A$$x$$A$$x'$$A$$d_x^C > dist(x, x')$$f$x ′ . Zauważ, że x ′ również musi przełączać się między A i B nieskończenie często (ponieważ jeśli x ′ pozostanie w A na stałe, to też x ), więc możemy wziąć f ( f ( x ) ) , f ( f ( f ( x ) ) ) , itd.$f(x) = x'$$x'$$A$$B$$x'$$A$$x$$f(f(x)), f(f(f(x))),$

Ponieważ mamy skończoną liczbę punktów, iteraty f muszą ostatecznie powtórzyć: f n ( x ) = f m ( x ) dla niektórych m > n . Spójrzmy teraz na odpowiednich sekwencji odległości od C: d C f ( x ) , d C f 2 ( X ) , . . . d C f n ( x ) , . . $f^n(x) = f^m(x)$$m > n$$d_{f(x)}^C, d_{f^2(x)}^C, ... d_{f^n(x)}^C, ...$. Ponieważ się powtarza, sekwencja ta nie może być równomiernie zmniejszana. Musi istnieć iteracja o , że d C f o - 1 ( x ) ≤ d C f o ( x $o$$d_{f^{o-1}(x)}^C \leq d_{f^o(x)}^C$

Teraz f o - 1 ( x ) i f o ( x ) są wystarczająco blisko siebie, aby spowodować, że będą w A , jeśli jeden z nich jest. Oznacza to, że są bliżej siebie niż którykolwiek z nich to C : d C f o ( x ) ≥ d C f o - 1 ( x ) > d i s t ( f o - 1 ( x ) $f^{o-1}(x)$$f^o(x)$$A$$C$f o ( x ) ) (z definicji f )$d_{f^o(x)}^C \geq d_{f^{o-1}(x)}^C > dist(f^{o-1}(x), f^o(x))$$f$

Tak więc, gdy tylko f o - 1 ( x ) i f o ( x ) znajdą się w A , będą się utrzymywać w A na zawsze (patrz wiersze 1-2 algorytmu). Jest to sprzeczne z faktem, że wszystkie iteracje f muszą zmieniać zestawy nieskończenie często. Zatem w przypadku, gdy k = 1 , algorytm kończy się.$f^{o-1}(x)$$f^o(x)$$A$$A$$f$$k = 1$