Визуализация списка результатов в виде графа

[alexanderpanchenko]

Мотивация

Сейчас визуализация результатов поиска производится в виде упорядоченного списка слов. Следует предложить так же пользователю альтернанивный способ визаулизации результатов -- в виде интерактивного графа. Это должно предоставить пользователю более быстро и удобно исследовать связи между словами, формулировать запросы, переходить по связанным словам и т.п.

Данный вид интерфейса в был реализован в некоторых проектах и показал свою эффективность при визуализации лексико-семантических сетей:

• http://visualworld.ru/search.jsp?text=%E0%F0%E1%F3%E7&vmode=32&page=0
• http://about.viwo.ru/semantic.html
• http://www.visualsynonyms.com/index.php
• http://www.visualthesaurus.com/trialover/ 
• http://dev.sigwp.org/WikiVisSL.Web/Visualizer.aspx
• http://www.touchgraph.com/seo
• https://uby.ukp.informatik.tu-darmstadt.de/webui/tryuby/

  Реализация

Общие требования

На данном этапе задача состоит в реализации простейшей версии такого графового интерфейса. Должена производится визуализация результата запроса в виде графа. В центре графа отображается запрос, дугами обозначаются связанные слова. При нажатии на узел производится запрос по этому узлу, этот узел становиться центральным (например как здесь http://thejit.org/static/v20/Jit/Examples/Hypertree/example1.html). Узлы которые не являются результатами по новому запросу удаляются. Стандартные результаты в виде списка слов тоже обновляются по нажатию на узел графа. Обратное тоже верно -- при нажатии на слово из стандартного списка граф обновляется.

Это должно выглядеть примерно так:

Параметры визуализации

• Количество визуализируемых результатов, 20 по умолчанию
• Длина дуги между запросом и результатом
  • единичная по умолчанию
  • пропорциональна рангу слова в результатах
  • пропорциональна мере семантической связности слов (для первого слова единична, для второго 1*w_1/w_2, где w_i это сила семантической связи с i-м результатом и т.п.)
• Отображение связей между результатами
  • не отображаются по умолчанию
  • отображаются. отображаются только связи между первыми 20 результатами (banana--papaya). связь между banana--jackfruit может существовать но она не в топ 20 по запросу banana.
• Отображение дуг
  • отображаются по умолчанию
  • не отображаются
• алгоритм расположения узлов
  • RGraph http://thejit.org/static/v20/Jit/Examples/RGraph/example1.html
  • Hypertree http://thejit.org/static/v20/Jit/Examples/Hypertree/example1.html
  • Force-Directed Layout http://thejit.org/static/v20/Jit/Examples/ForceDirected/example1.html
  • Spacetree http://thejit.org/static/v20/Jit/Examples/Spacetree/example1.html

Детали реализации

Примерно должно быть понятно из картинок.

• фон белый
• рамки вокруг канвы нет
• запрос в центре не является ссылкой, цвет -- черный
• результаты запроса -- гиперссылки голубого цвета
• шрифт по возможности такой же как и на остальной странице (вкл. его размер)
• цвет дуг от запроса к результатам -- черный
• цвет дуг от результата к результатам -- серый
• узел -- просто слово без рамки, кружка и т.п.

Варианты реализации

Используется библиотека на JavaScript.

• Библиотеки в которых есть втроенный алгоритм визуализации графа
  • http://thejit.org/
  • http://mbostock.github.com/protovis/
  • http://www.graphdracula.net/
  • https://github.com/jackrusher/jssvggraph
  • http://code.google.com/p/canviz/
• Неплохой обзор http://datavisualization.ch/tools/13-javascript-libraries-for-visualizations/.
• Библиотеки в которых нет встроенного алгоритма визуализации графов
  • http://raphaeljs.com/
  • SVG (jquery-svg: http://keith-wood.name/svg.html
  • http://processingjs.org/
  • http://excanvas.sourceforge.net/
  • jQuery drag and drop -- http://jqueryui.com/demos/draggable/

Предложение

Начать с thejit.org -- попробовать 4 данных варианта:

http://thejit.org/static/v20/Jit/Examples/RGraph/example1.html http://thejit.org/static/v20/Jit/Examples/ForceDirected/example1.html http://thejit.org/static/v20/Jit/Examples/Hypertree/example1.html http://thejit.org/static/v20/Jit/Examples/Spacetree/example1.html

Вопросы

1. Стоит ли начинать с thejit.org. Почему да или нет?
2. Удовлетворяет ли thejit.org всем требованиям?
3. Сложно ли будет адоптировать thejit.org для наших требований?
4. Какие альтернативные варианты наиболее перспективны (из перечисленных или любых других) и почему?

[PomanoB]

Я попробовал thejit и несколько других библиотек, но у них у всех очень плохой алгоритм укладки графов( Самый лучший в этом плане https://github.com/anvaka/VivaGraphJS, который сейчас пока и оставил. Плюсом VivaGraph является русский разработчик, который очень быстро отвечает на вопросы :)

[alexanderpanchenko]

Да, алгоритм визуализации (graph layout algorithm) -- это ключевая состовляющая. Если граф выглядит некрасиво, нечитабельно, если узлы нагромождены друг на друга а дуги пересекаются во многих местах приложение не будет интересно пользователю. Данный интерфейс должен быть интуитивным, простым и "красивым".

Было бы неплохо сравнить в действии несколько разных методов визуализации на "живых данных". Но если это вызовет слишком много работы -- не надо.

Большинство подобных систем основаны на физических моделях (притяжение/отталкивание, пружины и т.п.) http://en.wikipedia.org/wiki/Force-based_algorithms_(graph_drawing). Какие алгоритмы испльзует VivaGraph?

[alexanderpanchenko]

Я попробовал thejit Я попробовал thejit и несколько других библиотек, но у них у всех очень плохой алгоритм укладки графов и несколько других библиотек, но у них у всех очень плохой алгоритм укладки графов

Уточни что ты имеешь ввиду. Желательно со скриншотами если можно... Несколько странно слышать это о thejit -- для простых графов там должно быть все не так плохо.

[PomanoB]

VivaGraph именно его и использует:

Force Directed - based on Barnes-Hut simulation and optimized for JavaScript language this algorithm gives N * lg(N) + V performance per iteration. GEM - Graph Embedder algorithm created by Arne Frick, Andreas Ludwig and Heiko Mehldau. Estimated compleixity of this algorithm is O(|V|^3) - though I must have made a mistake somewhere, because force directed algorithm almost always produces better results faster. This algorithm is included to demonstrate how one can implement a new layout algorithm.

Второй алгоритм - GEM, похоже, в процессе разработки.

Вот картинка для сравнения:

Мб, если как-то задать коэффициенты для расчёта, Jit будет лучше, но я не могу найти в документации, как это сделать, есть только параметр levelDistance, который не шибко-то улучшает ситуацию.

[alexanderpanchenko]

OK. Согласен VivaGraph выглядит покрасивее. Да алгоритм Барнеса-Хута распространен для быстрого построения таких визуализаций. Думаю следует действительно остановиться на VivaGraph. А ты посмотрел другие альтернативы?

Веса

А VivaGraph-е или Jit учитывает вес дуги при построении визуализации? Судя по картинкам которые ты запостил нет либо ты не передал веса либо веса примерно одинаковы. Если веса учитываются то можно указывать не абсолютный вес а относительный вес. Например:

• вес первой пары слов w_1/w_1 = 1
• вес второй пары слов = w_2/w_1
• вес третьей пары слов = w_3/w_1

Отношения второго порядка

Судя по картинкам ты отображаешь отношения второго порядка

• mango-avocado-courgette
• mango-avocado-spinach
• и т.п.

Почему они отображаются только для узла avocado? Думаю это должно происходить только при нажатии на узел avocado. По умолчанию следует визуализировать отношения между парами "результат-результат" -- например peach--apricot для запроса mango (если по запросу peach возвращается в top 20 слово apricot).

Лицензия

У нас вроде бы не должно быть проблем с лицензией, что ты думаешь? Просто явно не указан тип лицензии...

Copyright (c) 2011, Andrei Kashcha All rights reserved.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

• Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
• Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
• The name Andrei Kashcha may not be used to endorse or promote products derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL ANDREI KASHCHA BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

[PomanoB]

А ты посмотрел другие альтернативы?

Да, у них ещё хуже

OK. Согласен VivaGraph выглядит покрасивее

Он, к тому же, более "живой" и динамический.

Веса

В VivaGraph можно задавать, в Jit - нельзя

Отношения второго порядка

Они по дабл-клику подгружаются, т.е. два раза на слово кликнуть - добавятся первые двадцать его отношений. На картинке я просто показал для одного, что бы было представление как это выглядит

По умолчанию следует визуализировать отношения между парами "результат-результат"

Пробовал, так совсем плохо выглядит, они практически каждое с каждым( Пока думаю, как их организовать и что с ними сделать.

Лицензия

Ок, спрошу у автора, какие пункты уточнить?

• некоммерческое использование ?
• коммерческое использование ?
• указание копирайта ?
• ещё что-то ?

[alexanderpanchenko]

Да, у них ещё хуже

OK. Так и думал.

В VivaGraph можно задавать, в Jit - нельзя

Это хорошо. По умолчанию думаю не следует учитывать веса -- чтобы сделать визаулизацию максимально простой. Однако нужно сделать данный параметр визуализации доступным. Вообще мне кажется что все параметры визуализации (учет весов, отрисовка дуг, отрисовка вторичных дуг, алгоритм визуализации, количество результатов и т.п.) нужно вывести в группу настроек визуализации. После этого нужно будет поэкспериментировать с данными настройками и наиболее удачную конфигурацию установить по умолчанию. На данном этапе трудно сказать какие параметры здесь будут оптимальными...

Они по дабл-клику подгружаются, т.е. два раза на слово кликнуть - добавятся первые двадцать его отношений. На картинке я просто показал для одного, что бы было представление как это выглядит

Да так и надо. Только не уверен про двойной клик -- это скорее стандартно для десктопа. Для веба наверное одного клика достаточно.

Пробовал, так совсем плохо выглядит, они практически каждое с каждым( Пока думаю, как их организовать и что с ними сделать.

Оставь все равно данный параметр визуализации в отладочных целях -- не по умолчанию конечно. Можно к примеру такого рода сильно связные группы слов будет объединять в одну группу/кластер (серый кружок или что-нибудь в этом духе).

некоммерческое использование ? коммерческое использование ?

да.

указание копирайта ?

нужно ли оно только в исходных кодах или необходимо указать в интерфейсе пользователя ссылку

касается вот этого пункта... "Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution."

ещё что-то ?

нет

[PomanoB]

Ок, понял

[alexanderpanchenko]

Как ты думаешь реально ли будет к 22-му октября сделать первую версию визуального интерфейса (самую простую без доп.опций и т.п.)? Я хотел бы попробовать написать короткую статью (демо) на ECIR http://ecir2013.org/...

[PomanoB]

Да, вполне реально, даже с опциями, сейчас уже готовы вот такие опции:

[alexanderpanchenko]

OK. Здорово. Ты можешь здесь вывесить парочку таких же скриншотов (обычный и расширенный поиск) на английском. Только чтобы окно опиций не налезало на граф. Спасибо!

[PomanoB]

Куда девать окно опции я пока не придумал, тем более что оно ещё больше будет( Расширенный: Обычный:

[alexanderpanchenko]

Так нормально -- для пользователя это подойдет вполне. Просто для скриншота хотелось чтобы граф не был загорожен менюшкой. Еще одно -- у тебя есть кто-нибудь кто знаешь хорошо английский -- спроси сможет ли он перечитать около 3-4 страниц текста на орфогр и другие ошибки...

[PomanoB]

Гм, я поспрашиваю, но результат не гарантирую....

[alexanderpanchenko]

Кстати ты не смотрел в сторону? http://mbostock.github.com/d3/ex/force.html

[PomanoB]

Смотрел, но мне там не понравился способ задания связей, там только по индексам узлов в общем массиве узлов.

[alexanderpanchenko]

OK.

[alexanderpanchenko]

Выложи пожайлуста такой же скриншот что для запроса pizza, для запроса animal.

[PomanoB]

[alexanderpanchenko]

мерси

[alexanderpanchenko]

На trytoimagine сейчас последняя версия графового интерфейса? Нужно во вторник вывесить на основной сайт версию с графом. На каком этапе сейчас этот бранч, нужно ли еще что-нибудь доделать или базовая версию можно деплоить?

[alexanderpanchenko]

Посмотрел ту версию которая сейчас на trytoimagine. Мне кажется что следует сделать следующие изменения:

1. Запрос отображается черным цветом
2. По умолчанию используются связи второго порядка, но цвет дуг второго порядка -- очень светлый (еле заметный) серый. за счет этого будет достигаться более привлекательная расположение узлов графа. Сравни к примеру для запросов Jaguar и Flash.
3. По умолчанию не отображаются ссылки delete node, options и т.п. -- они должны быть доступны только в расширенном режиме.
4. Сейчас между списком результатов и графом есть большое пустое пространство (практически равное размеру графа). Его нужно уменьшить (сдвинуть граф ближе к строке с результатами).
5. Часто узлы выезжают за пределы канвы.

Отпишись пожалуйста как поправишь эти вещи сделать мердж в ветку develop -- тогда я разверну эту версию сервере.

[PomanoB]

Там не смерджены последние изменения из develop, те что с расположением кнопок. И ещё сегодня доделаю подгрузку слов по одинарному клику, а не двойному

1. Это поправлю, слетело при рефакторинге
2. Ок
3. Ок. И, может быть, не стоит показывать там окно с оценкой результата?
4. Ок
5. Это не страшно, граф можно двигать и масштабировать колёсиком, если их много, по-любому будут выезжать...

[alexanderpanchenko]

Да окно с оценкой можно выключить -- мы достаточно для статьи насобирали...

[alexanderpanchenko]

1. В идеале пользователю должен показыватся граф который полностью влезает на канву. Странно было бы заставлять пользователя передвигать граф для каждого запроса. Другое дело если он сам что-то передвинкул -- тогда еще это можно понять. Там есть принципиальные ограничения библиотеки которые не позволяют ограничивать (хотя бы изначальный) граф канвой? Как вариант можно увеличить размер канвы...в частности чтобы было место для дополнительных узлов.

[PomanoB]

Я не видел там метода, позволяющего ограничивать область.... А вообще, у меня ни разу не было такого, что бы изначальный граф вылез, он же всегда по центру......

[alexanderpanchenko]

У меня во время отрисовки иногда выезжал (в конце правда вроде возвращался). ну пока это не критично...

Я еще один момент заметил важный который было бы здорово поправить. При двойном клике в добавляются узлы но не связи между ними (в режиме отображения вторичных связей). Мне кажется что по умолчанию нужно добавлять в граф связи между новыми узлами и между новыми и старыми узлами (конечно если опция отображения вторичных связей включена). Тогда новые узлы будут органично встраиваться в текущий граф а не "висеть в воздухе". Представь что пользователь начинает поиск с запроса Jaguar. Далее он видет два кластера в реузльтатах -- машины и животные. Допустим он заинтересован в кластере машин и разворачивает связи узла BMW. Тогда дополнительные узлы должны "приклеиться" к кластеру машин (за счет связей с ними) а не быть просто связями BMW...

[PomanoB]

Ок, понял

[PomanoB]

Ну вот как-то так получилось: http://trytoimagine.org:3000/

[alexanderpanchenko]

Какой то баг нашел -- когда в расширенном режиме задаешь новый запрос иногда почему то отображаются и все узлы от старого запроса. Это происходило при включенной опции связей второго порядка и после того как у первого запроса были развернуты нсколько узлов.

Кажется они выехали тк одно из слов из нового запроса было связано со словом из старого...но не уверен.

https://www.dropbox.com/s/8uyhjaydy61d99t/gui.png

[alexanderpanchenko]

Посмотрел еще раз -- похоже баг не связан с тем что результаты из нового запроса связаны с результатами старого. Подобный баг смог воспроизвести и для никак не связанных запросов. При этом граф накапливается. В том смысле что старые результаты отображаются вместе с новыми.

[PomanoB]

Ну вроде как пофиксил

[alexanderpanchenko]

Да вроде больше не вылезает. Выглядит очень круто, особенно со связями второго порядка! :-) Реально можно исследовать кластеры из сильно связных слов. В особенности это хорошо работает на многозначных словах вроде Jaguar, Flash или Brother. Буду накатывать завтра около 14-00 по москве -- до этого времени надо потестировать.

[alexanderpanchenko]

Развернул на основном сайте бранч visualization. Потестировал сам и дал еще паре человек -- вроде бы особых багов не нашлось. Закрываю тикет т.к. считаю что базовая функциональность уже работает и удобнее будет для доработок открыть новые более точные тикеты.