Comments 19
Попробовал посравнивать по вашей ссылке. Текст который был слева скопировал в правую часть. Сравнение = 1.
Удалил "," и "." (всего 9 штук) — получаю = 0.585
Даже удаление нескольких слов дает 0,9хх. Почему из-за знаков препинания резко снижается индекс?
Удалил "," и "." (всего 9 штук) — получаю = 0.585
Даже удаление нескольких слов дает 0,9хх. Почему из-за знаков препинания резко снижается индекс?
Потому что это так для поиграться сделано, на слова разбивается просто по пробелам. Знаки препинания как часть слова в этом случае воспринимаются или как отдельное слово.
но ведь хеш отдельных слов в сумме не может из-за одного символа резко так снижать индекс?
Просто я реализовывал (когда еще был студентом) для себя алгоритм подобной задачи.
Требовалось перелопатить все Excel входные файлы и привязать кривой ввод данных, от сотрудников и в особенности сотрудниц, к справочникам которые были получены и систематизированы в прошлом.
Входные данные были это были названия городов, населенных пунктов, улиц и т.д.
и у меня «ул. Чкалова» и «ул Чкалова» давали совсем не = 0.45, а 0.9х
Но я реализовывал подругому.
Просто я реализовывал (когда еще был студентом) для себя алгоритм подобной задачи.
Требовалось перелопатить все Excel входные файлы и привязать кривой ввод данных, от сотрудников и в особенности сотрудниц, к справочникам которые были получены и систематизированы в прошлом.
Входные данные были это были названия городов, населенных пунктов, улиц и т.д.
и у меня «ул. Чкалова» и «ул Чкалова» давали совсем не = 0.45, а 0.9х
Но я реализовывал подругому.
Думаю, нужно добавить, что ошибка при вычислении метрики похожести по методу MinHash нефатальна, поскольку всегда возможно пересчитать оригинальную метрику для близких множеств, выявленных по MinHash.
Иначе говоря, MinHash здесь будет работать, как предварительный фильтр, снижающий вычислительные затраты.
Иначе говоря, MinHash здесь будет работать, как предварительный фильтр, снижающий вычислительные затраты.
MinHash — это алгоритм снижения размерности, а не алгоритм поиска похожих множеств. Он используется как дополнение для алгоритмов поиска тех самых похожих множеств, когда объем данных очень велик. Изначально его применили для алгоритма поиска дубликатов документов.
А какие алгоритмы есть для поиска похожих множеств? Актуальная для меня тема.
Это — вопрос терминологии, не более того.
Поясню: кому-то точности MinHash будет вполне достаточно, да и вопрос коллизий не всегда определяющий. В этом случае метод будет вполне полноценно искать похожие множества.
Поясню: кому-то точности MinHash будет вполне достаточно, да и вопрос коллизий не всегда определяющий. В этом случае метод будет вполне полноценно искать похожие множества.
Это не различие терминологии, MinHash именно метод уменьшения размерности.
Простой пример: пусть у нас есть набор объектов, которые описываются большим вектором признаков, сравнивать такие объекты — это сравнивать их вектора-признаки, что очень дорого. Делаем чит — выбираем случайно и равновероятно объекты из этих векторов и получаем сокращенную сигнатуру, по которой и сравниваем все объекты. Вот эта случайная выборка и получается благодаря MinHash, потому что ее свойство — брать признаки равновероятно.
Простой пример: пусть у нас есть набор объектов, которые описываются большим вектором признаков, сравнивать такие объекты — это сравнивать их вектора-признаки, что очень дорого. Делаем чит — выбираем случайно и равновероятно объекты из этих векторов и получаем сокращенную сигнатуру, по которой и сравниваем все объекты. Вот эта случайная выборка и получается благодаря MinHash, потому что ее свойство — брать признаки равновероятно.
Я об этом способе использования MinHash выше написал.
А Ваш пример мой не опровергает, присмотритесь повнимательнее.
Кстати, интересно, свойство равновероятности для MinHash, хотя бы на уровне ассимптоты доказано?
А Ваш пример мой не опровергает, присмотритесь повнимательнее.
Кстати, интересно, свойство равновероятности для MinHash, хотя бы на уровне ассимптоты доказано?
Возможно ли равновероятно брать значения? В идеале да, на практике стремятся к идеалу. Когда писал свой диплом, то тестировал этот MinHash и результаты мне понравились — в среднем алгоритм работает идеально, есть дисперсия, значение которой зависит от числа функций.
Для оценки равномерности распределения одной дисперсии маловато будет.
Не стоит ли оценить близость самого распределения, например, через обычную метрику скалярного произведения?
Не стоит ли оценить близость самого распределения, например, через обычную метрику скалярного произведения?
Например, построим гистограмму, и оценим ее отклонения от равномерности.
Sign up to leave a comment.
MinHash — выявляем похожие множества