k-mean против алгоритма LSH

Question

Я довольно новичок в интеллектуальном анализе данных и ML. Я хочу понять, насколько отличается k-средство от LSH. После чтения нескольких статей и других материалов, доступных в Интернете, кажется, что оба алгоритма пытаются добиться группировки/кластеризации похожих документов. Для таких случаев, как обнаружение спама, любой из них использовался во многих документах. Но я не совсем понимаю, как они отличаются друг от друга, и если мы вообще используем это для использования, например, для обнаружения спама, как результат будет отличаться вообще?

Answer 1

LSH не группирует ваши данные.

Он подходит для обнаружения почти двойным (!).

1. LSH по дизайну может создавать «ложные срабатывания» (хеш-колликации), которые вообще не похожи.
2. LSH имеет пороговое значение t, и только пытается произвести хеш-коллизии для объектов ниже этого порога. Для хорошей производительности вам нужно выбрать этот порог как можно меньше. Для кластеризации вам необходимо найти объекты за пределами вашего ведра (дальше, чем t) - вы не можете надежно выполнить это с помощью LSH.
3. LSH будет помещать границы ведра случайным образом; единственная причина, по которой вы этого не замечаете, - это то, что вы делаете это много раз, и надейтесь, что не все они плохо выбраны. Таким образом, вы получаете только почти все близкие соседи. Может быть, даже 90%, в зависимости от ваших параметров. Поскольку каждый объект находится в несколько ведер, какой будет его кластер? Вы получаете огромное количество перекрывающихся «кластеров», каждый из которых содержит только некоторые части ваших данных. Совершенно ясно, как эффективно найти хорошие кластеры из этого.

LSH является действительно о «почти в тех же» объектов, а не о нахождении крупной структуры в данных.

Я не думаю, что обнаружение спама является хорошим вариантом для использования - знаете ли вы о любом спам-фильтре, который на самом деле это сделает? Почти двойное обнаружение новостей, например. Однако Новость Google связана с каким-то LSH; предположительно, они используют minhashing.