Какие алгоритмы подсчитывают частоты общих элементов в наборе множеств?

Question

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

Используя систему тегов stackoverflow в качестве примера:

Допустим, этому вопросу было присвоено 5 тегов. Допустим, есть еще 1000 вопросов, у которых есть хотя бы один из этих тегов. Сколько из этих 1000 вопросов имеют общие теги, которых нет в моем исходном сообщении?

Еще один более простой способ описать это - система автоматической пометки тегов:

"Вы отметили свой вопрос [5 выбранных мной тегов]. Другие похожие вопросы были отмечены [список тегов, которые могут представлять интерес]. Где [список тегов, которые могут представлять интерес], часто встречающиеся теги, нет в моем оригинальном списке.

Примеры кода в c #, если это возможно:)

Answer 1

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

Вы также можете потенциально использовать частичный порядок классов эквивалентности и установить включение: когда вопросы A и B имеют одинаковый набор тегов вплоть до переупорядочения, они равны, устанавливают объединение, устанавливают разность и устанавливают пересечение, а затем определяют частичный порядок сравнения <и>.

Answer 2

Я не знаю каких-либо конкретных алгоритмов или структур данных, но я мог бы предложить базовый способ обработки этого:

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

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

В (небрежном) псевдокоде используйте два цикла (если это возможно):

for each entry
    if any tag in original_tags
        tag_list[tag]++
end

for next in tag_list
    tag_count[tag_list[next]] += next
end  

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

(кэш для оптимизации, но следите за обновлениями)

Paul.