Да предположим, че са ни дадени данни в полуструктуриран формат като дърво. Като пример, дървото може да се формира като валиден XML документ или като валиден JSON документ. Можете да си представите, че това е S-израз, подобен на lisp, или (G)алгебричен тип данни в Haskell или Ocaml.
Дават ни се голям брой „документи“ в дървовидната структура. Нашата цел е да групираме документи, които са подобни. Под групиране имаме предвид начин за разделяне на документите в j групи, така че елементите във всяка да изглеждат един на друг.
Сигурен съм, че има документи, които описват подходи, но тъй като не съм много известен в областта на AI/Clustering/MachineLearning, искам да попитам някой, който е какво да търся и къде да копая.
Настоящият ми подход е нещо подобно:
- Искам да конвертирам всеки документ в N-измерен вектор, настроен за групиране на K-означава.
- За да направя това, рекурсивно обикалям дървото на документа и за всяко ниво изчислявам вектор. Ако съм във връх на дърво, повтарям всички подвърхове и след това сумирам техните вектори. Също така, когато се повторя, се прилага фактор на мощността, така че има все по-малко значение колкото по-надолу по дървото отивам. Крайният вектор на документа е коренът на дървото.
- В зависимост от данните в лист на дърво, прилагам функция, която пренася данните във вектор.
Но със сигурност има по-добри подходи. Една слабост на моя подход е, че ще клъстери само дървета по сходство, които имат върхова структура, която много прилича едно на друго. Ако приликата е налице, но се появява по-надолу в дървото, тогава подходът ми вероятно няма да работи много добре.
Предполагам, че има решения и при търсене в пълен текст, но искам да се възползвам от полуструктурата, присъстваща в данните.
Функция за разстояние
Както беше предложено, трябва да се дефинира функция за разстояние между документите. Без тази функция не можем да приложим алгоритъм за групиране.
Всъщност може да се окаже, че въпросът е точно за тази функция за разстояние и примери за нея. Искам документи, в които елементи близо до корена са еднакви, да се групират близо един до друг. Колкото по-надолу по дървото слизаме, толкова по-малко значение има.
Гледната точка за една крачка назад:
Искам да клъстерирам следи на стека от програми. Това са добре оформени дървовидни структури, където функцията близо до корена е вътрешната функция, която се проваля. Имам нужда от прилична функция за разстояние между следите на стека, които вероятно се случват, защото същото събитие се е случило в кода.
