Алгоритм нахождения наиболее информативной полной группы несовместных тэгов

Облако тэгов (в новом виде)

Задача алгоритма

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

Результат алгоритма

Вместо облака тэгов, пользователь видит одну из возможных п.г.н.т и должен выбрать тот единственный из несовместных тэгов, которым помечен искомый объект. После выбора этого тэга, выбираются те объекты помеченные данным тэгом и строится новое множество тэгов (меньшее по объему) и алгоритм применяется заново. Результатом поиска является нахождение нужного объекта, либо существенное сужение выборки. Также при построении п.г.н.т должна выбираться наиболее выгодная в энтропийном смысле.

Алгоритм

Существует множество объектов O (m штук), каждый i-й элемент которого описан группой тэгов из множества тэгов T (n штук).

Шаг 1. Строим матрицу отношений тэгов (nxn).

  t1 t2 ... tn
  t1 10 0  ... 1
  t2 0  7 ... 2
  ...............
  tn 1  2  ... 5
  

Пример матрицы отношений приведен выше.

Данная матрица позволяет нам определить сколько общих объектов имеет пара тэгов В ячейках с "0" (например t1-t2) общих объектов у данных тэгов нет. Такие пары тэгов нам наиболее интересны, используя их, мы будем строить п.г.н.т.

Шаг 2. Выборка несовместных тэгов (обход в ширину)

Для удобства построения п.г.н.т. вводим понятие "группа несовместных тэгов" (G) - подмножество несовместных тэгов и понятие уровень группы (level) - разделение групп тэгов по количеству тэгов.

Создаем группы несовместных тэгов состоящих из одного тэга (level = 1, n штук G); Данные группы записаны в виде списка: | G1G2G3..Gn |

Шаг 3. Берем i-й уровень начиная с 1 (если i = количеству уровней, то Шаг 8)

Шаг 4. Берем j-ю группу из i-го уровня ( если j равен количеству групп на данном уровне,то i=i+1 и Шаг 3 иначе Шаг 5)

Шаг 5. Берем k-й тэг не присутствующий в группе (k равен уровень группы, если k равен количеству тэгов в группе, то j = j+1 и Шаг 4, иначе Шаг 6)

Шаг 6. Просматриваем данный тэг на несовместность со всеми тэгами данной группы. (если несовместен, то Шаг 5 иначе Шаг 7.

Шаг 7 Берем j-ую группу (отмечаем как не полную) и добавляем в конец k-ый тэг (новую группу отмечаем как полную), таким образом получаем новую группу на уровень выше предыдущей. Возращаемся к шагу 5.

Шаг 8 Для каждого объекта существует индекс популярности. Возьмем i-ую полную несовместную группу (если такая есть то Шаг 9, если нет то Шаг12 )

Шаг 9 Суммируем индексы популярности каждого объекта j-го тэга i-го объекта, таким образом получим сумму индексов данной группы, Шаг 9 пока все тэги и объекты не будут просмотрены, иначе Шаг 10

Шаг 10 Возьмем j-й тэг i-й группы и подсчитаем сумму популярности его объектов. Подсчитаем вероятность данного объекта разделив индекс популярности j-го тэга на индекс популярности всей i-ой группы. Pij = Nij/Mij; - вероятность данного тэга в i-й группе Шаг 10 пока все тэги не просмотрены, иначе Шаг 11

Шаг 11 Подсчитаем энтропию i-ой группы Ii = сумма Iij, где Iij = PijLog2(Pij); Перейдем к шагу 8

Шаг 12 Анализ полученных значений энтропии.

На данном этапе возможно несколько реализаций алгоритма. Так как существуют группы у которых количество элементов различно, то оценить группы в энтропийном смысле сложно.

а) Можно выбрать группы с максимальной энтропией для каждого уровня и разделив на количество тэгов в каждой группе получить среднее значение энтропии. Данный вариант не является полностью объективным, так как средняя энтропия у групп не зависит от количества тэгов в группе

б) Подсчет количества информации по формуле I = Log2(N) , где N - количество тэгов в группе. dH = (I - H) , где H - энтропия группы dH' = dH/I - коэффициент информативности, чем он меньше, тем группа информативнее. Отталкиваясь от данного коэффициента возможно найти наиболее информативную группу.

Реализация

Реализацию алгоритма произведена на Объектно-Ориентированном языке программирования, в качестве которого был выбран язык ActionScript3, позволяющий создавать Desctop и интернет приложения.

Приложение загружает информацию предоставленную в xml формате, также возможна загрузка данных с использованием языков веб программирования таких как php, pyton, ruby и др. После загрузки и нахождения наиболее информативной п.г.н.т. пользователю предоставляется список из (несовместных) Тэгов и группа "other" (это виртуальный тег, покрывающий оставшиеся объекты).

Пользователь выбирает необходимый ему параметр (тэг), после этого строится новая группа, но уже только из объектов, покрытый выбранным тэгом. Таким образом пользователь может быстро и легко найти необходимый ему объект.

Классы

Приложение разработано при соблюдении принципов ОО Проектирования и ОО программирования. Основные рабочие классы:

GenerationObjects - класс для загрузки xml или генерации объектов. на выходе: objects - массив объектов класса Label tags - массив объектов класса Tag

RelationObjects - класс создания матрицы отношений тэгов На выходе matrix - объект класса MatrixData

CombinationUGroup - класс нахождение п.г.н.т

Information - класс нахождения энтропии групп

Классы в папке model/vo - используются для хранения данных

Класс Application - рабочее приложение Класс CloudOfTags - класс просмотра групп

Исходники можно посмотреть omsku.ru/CloudOfTags.rar

omsku.ru/CloudOfTags/Application.html - Пример работы 
omsku.ru/CloudOfTags/CloudOfTags.html - Подробности анализа групп
omsku.ru/CloudOfTags/data/lol1.xml  - Загружаемые данные