Как сделать кластеризацию на основе хэширования?

Question

[tsvikm]

Дано:
Есть много входных данных, пусть будет 1ТБ. Представим их в виде бинарного кода. Получившуюся бинарную последовательность разделим на части длины N. То есть будет очень большое количество бинарных последовательностей (далее сегментов) фиксированной длины N (длина N может быть разной, от 8 до 65536).

Цель:
Нужно выделить K кластеров, в каждом из которых будут содержаться похожие сегменты (степень похожести нужно задать).

Очевидно, что представить их как вектора размерности N и делать классическую кластеризацию по расстоянию (Хэмминга, Евклида и тп) выйдет слишком дорого, т.к. придется считать расстояния между всеми векторами (побитовое сравнение), которых очень много. Нужен какой-то алгоритм, который позволит делать кластеризацию по хеш-кодам. То есть сначала нужна хеш-функция, которая похожим векторам будет давать похожие хеш-коды. Или необязательно нужна такая хеш-функция, а нужен только алгоритм, который будет определять степень похожести векторов через их хеш-коды. Есть идеи, как это сделать? Или подскажите какие-нибудь алгоритмы. Такие есть, но на русском языке не нашел описания подходящего под эту задачу, а на английском такую литературу пока не могу переваривать. Заранее благодарен.

upd. Нашел вроде что-то подходящее, но не могу разобраться с этим (технический английский страдает): roussev.net/pubs/2010-IFIP--sdhash-design.pdf
Тут рассматриваются Rabin Fingerprinting, Fuzzy Hashing и то, как это работает. Кто-нибудь знает подобные статьи на русском языке или может помочь с адаптацией этой?

Answer 1

[Сергей]

Что в вашем понимании степень похожести векторов ?

Если вы берете хеш от данных, то он никак не связан с "похожестью вектора".
Для кластеризации по хешу, достаточно использовать хеш как 32 (64, или другое) битное число, и взять остаток от деления на кол-во необходимых вам групп.

Comments

[tsvikm]

Степень похожести интуитивная. Лучше всего, чтобы она определялась по коэффициенту Жаккара (пересечение двух множеств поделено на их объединение).

В том то и дело, что есть алгоритмы, которые могут связать вектор с хешем так, чтобы можно было определить похожесть по хешу.
Ваш вариант совсем не понял. У меня есть много последовательностей из 65536 единиц и нулей каждая, причем тут 2^n битное число и остаток от деления - не понятно. Может это я чего-то не знаю просто, если можно объясните поподробнее.

[Сергей]

хеш в общем случае это 2^n битное число. Если вам надо организовать m кластеров, то просто берете остаток от деления на m, получаете m кластеров.

> (пересечение двух множеств поделено на их объединение).
вы опять не определились что считать под элементами такого множества ? байты ? может ваш двоичный поток структурирован ?

[tsvikm]

Сергей: хеш далеко не всегда число. Очень часто это строка из шестнадцатиричного кода. Что делить на m нужно? У меня нету чисел, чтобы делить их на m. У меня есть бинарное представление данных и все.

Есть вектора длинной N.
Пусть N = 10:
Вектор А: 0010111010
Вектор Б: 0010011011
Вектор А похож на вектор Б на 80% т.к. 8 (совпавших битов, то есть пересечение) делим на 10 (объединение деленное на 2, прошу прощения. Это коэффициент Серенсина). Элементами считать биты. Но считать напрямую расстоянием Хэмминга или подобным - не вариант. Я уже писал выше. Нужно через хеш вычислять похожесть. Я там обновил пост, посмотрите

[Сергей]

Ну например, вы можете использовать нейронную сеть, чтобы натренировать её на выдачу одинакового числа для похожих данных. Т.е. например имеем:
Нейронную сеть с 65000 бинарными (0,1) входами, и 1 числовым выходом.
Вам нужно определить "очень много" образцов, чтобы НС поняла что вам от неё нужно. Натренировать. И далее по числу выдаваемому такой НС вы можете судить насколько 2 вектора похожи.

Еще вы можете свести вектор у одному числу используя некоторый многочлен. Например:
f(n, X) = -0.5 * X[n-1] + X[n] - 0.5 * X[n+1]
где n - индекс, X - текущий вектор.

последовательно пробигая по вектору X и вычисляя f(n,X) для каждого n = 1... len(X) - 1, мы преобразовываем вектор в вектор Y с n-2 элементами.
Далее применяете аналогично f к Y.
И т.о. вы можете последовательно свой вектор свести к одному числу.

[tsvikm]

Сергей: Нейронная сеть - из пушки по воробьям. И долго. Нужно быстро работающий алгоритм на больших входных данных (1ТБ минимум).

Я мало чего понял из вашего объяснения про полином, но из того, что я сумел понять, это будет очень долго, такой полином считать. И то, это только для сведения вектора к одному числу, которое, кстати, весьма сомнительное и не факт, что у похожих векторов будут похожие числа. Быстрее будет напрямую расстояние Хэмминга считать даже. Я не понял, на самом деле, откуда у вас взялись магические константы эти, как, собственно, и все остальное. Может это я дурачок и ничего не понимаю, конечно, но если бы вы поясняли понятнее, было бы намного лучше

[Сергей]

Сам придумал :) Читай про нормальное распределение.
Расстояние Хэминга считать не быстрее.

[Сергей]

А вот вам наметки: habrahabr.ru/post/250673

[tsvikm]

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

[Сергей]

Ну так опишите для будущих поколений.

[tsvikm]

Сергей: Там сложный достаточно алгоритм мы придумали, но если в кратце, он основан на алгоритме Рабина и циклическом хеше.

[Сергей]

Опишите, а то как брать у сообщества --- так все горазды, а как отдавать - так хрен.

[tsvikm]

Сергей: я подписывал документ о неразглашении. Любой алгоритм, придуманный нами там не может поддаваться огласке, увы

Answer 2

[xmoonlight]

Пусть бинарные последовательности - это предложения.
А набор характеристик в них - это слова.
Пусть разделитель - символ пробела.
Тогда используя этот алгоритм Как определить похожесть двух строк?
мы можем выбрать нужные нам записи с наименьшими затратами на производительность.