Algorytmy dla problemu wyboru granic

Schematy klastrowania zorientowane na użytkownika umożliwiają klasyfikację dokumentów w oparciu o postrzeganie podobieństwa między dokumentami przez użytkownika, a nie na podstawie funkcji podobieństwa, którą projektant zakłada jako reprezentację kryteriów użytkownika. We wcześniejszym artykule wykazano, że taki schemat klasyfikacji można opracować w dwóch etapach. Pierwszy etap obejmuje akumulację ocen istotności dostarczonych przez użytkowników, w odniesieniu do poprzednich wystąpień zapytań, w odpowiednią strukturę. Drugi etap polega na identyfikacji klastrów. Gdy struktura wybrana w pierwszym etapie do akumulacji cech istotności dokumentów jest linią prostą, drugi etap można sformułować jako problem optymalizacji funkcji, zwany problemem wyboru brzegowego (Boundary Selection Problem – BSP). Opracowano algorytm rozgałęzień i ograniczeń z dobrą funkcją ograniczającą dla BSP. Chociaż dzięki funkcji ograniczającej uzyskano znaczne przycięcie, złożoność jest nadal wysoka dla problemu o dużym rozmiarze. Dla takiego problemu opracowano heurystykę, która dzieli go na szereg podproblemów, z których każdy jest rozwiązywany metodą rozgałęzień i ograniczeń. Następnie problem całościowy jest mapowany na problem plecakowy i rozwiązywany za pomocą programowania dynamicznego. Kompromis między dokładnością a złożonością może być kontrolowany, dając użytkownikowi możliwość wyboru jednego z nich. Zakładając, że heurystyka dzieląca problem całościowy nie wprowadza błędów i ma wystarczająco dużo czasu, podejście gałęzi i ograniczeń z programowaniem dynamicznym (BBDP) będzie zbieżne do optymalnego rozwiązania. Dwa inne podejścia heurystyczne, jedno z zastosowaniem wielomianowego algorytmu programowania dynamicznego i drugie działające w sposób zachłanny, są również proponowane dla BSP i przedstawiono eksperymentalne porównanie wszystkich tych podejść. Wyniki eksperymentalne wskazują, że wszystkie proponowane algorytmy wykazują lepszą wydajność w porównaniu z istniejącym algorytmem.