Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 17
Спасибо за довольно интересную статью, но лично мне немного не хватило конкретики, как минимум небольшие выдержки из кода были бы кстати, а если бы разбавить текст поясняющими картинками, то вообще было бы замечательно.
Мне очень интересен бенчмарк алгоритма на таких вот текстах:
Казнить, нельзя помиловать.
Казнить нельзя, помиловать.
следующие два текста совсем близки геометрически
Мне сразу вспомнилась эта статья на Хабре: habrahabr.ru/post/236503 — на первый взгляд, никак не связанные показатели статистики, но очень сильно коррелируют.
Вы рассмотрели интересную задачу, но, похоже, оптимизация алгоритма отрицательно сказалась на результатах. На мой взгляд, функция отображения в N-мерное пространство слишком сильно размазывает полезную информацию. Как я понял, эта функция отобразит два бесконечно длинных текста практически в одну точку? Ведь частотность конкретной буквы полностью определяется языком (в русском наиболее частая буква «о»). Думаю, функцию обязательно нужно усложнить. Первое, что приходит на ум, это увеличить размерность пространства в 2 раза. Одной букве будет соответствовать два числа: число вхождений в текст (как и сейчас) и сумма расстояний этой буквы от начала текста. Пример: допустим, алфавит всего из тех букв abc, текст «aabbbaaaccc» отобразится в точку ( (5,19), (3,9), (3,27) ). Числа 5,3,3 — это количество вхождений букв a,b,c. Число 19 для буквы a получено, как сумма позиций буквы a в тексте, то есть 0+1+5+6+7=19.
И еще один момент, по поводу куба вокруг каждой точки. Возможно, я что-то не так понял. Не проще ли было обойтись методом наименьших квадратов вместо R-tree?
Спасибо за комментарий.
«aabbbaaaccc»->( (5, 19), (3, 9), (3, 27) )
«aabbbaaacc»->( (5, 19), (3, 9), (3, 17) )
и расстояние между точками получается приличное.
Поясните пожалуйста, как тут применить метод наименьших квадратов.
функция отображения в N-мерное пространство слишком сильно размазывает полезную информациюПо-видимому Вы правы, и предложенный метод сработает только в случае коротких текстов и малом допустимом расстоянии Левенштейна. Однако на имеющейся базе скопления точек в одном кубе оказались редким исключением; как ни странно, в количестве букв довольно много информации.
Одной букве будет соответствовать два числа: число вхождений в текст (как и сейчас) и сумма расстояний этой буквы от начала текста.Боюсь это соображение я не понял. Получается, что
«aabbbaaaccc»->( (5, 19), (3, 9), (3, 27) )
«aabbbaaacc»->( (5, 19), (3, 9), (3, 17) )
и расстояние между точками получается приличное.
Не проще ли было обойтись методом наименьших квадратов вместо R-tree?
Поясните пожалуйста, как тут применить метод наименьших квадратов.
метод сработает только в случае коротких текстов
Это действительно так. Несколько лет назад в институте была курсовая, где нужно было расшифровать текст, зашифрованный методом простой замены (перестановки букв в алфавите). В исходный данных было сказано, что язык — русский. Так вот, за счет ограниченной длины (порядка 300-400 символов) преподавателю удалось добиться «нестандартного» распределения плотности различных букв, и даже эвристика с наиболее частой буквой «о» в большинстве заданий не прокатывала. Были, например, тексты с наиболее повторяемой «и».
и расстояние между точками получается приличное
Я просто привел пример, как с помощью координат можно сохранить (иными словами, сжать с потерями) какую-то информацию об исходной строке. Для определения похожести, действительно, не годится.
метод наименьших квадратов
В данном случае я имел в виду обычное определение отклонения между двумя точками X(x1,x2...xn) и Y(y1,y2...yn):
R=(x1-y1)^2+(x2-y2)^2...(xn-yn)^2
Ограничив значения R некоторым порогом R0, можно получить множество точек внутри N-мерной сферы вокруг заданной точки. Такой способ не годится?
Промахнулся
habrahabr.ru/post/262063/#comment_8492011
habrahabr.ru/post/262063/#comment_8492011
Посмотрите этот пост, особенно первый пример, про опечатки.
Вы сможете значительно повысить качество распознавания слов с исправленными опечатками, а знаки пунктуации можно отрабатывать и расстоянием Левенштейна, но не на буквах, а на словах.
Вы сможете значительно повысить качество распознавания слов с исправленными опечатками, а знаки пунктуации можно отрабатывать и расстоянием Левенштейна, но не на буквах, а на словах.
Можно брать и шар, но индекс нужен для того, чтобы сократить сложность поиска пар. Если считать без индекса, то сложность будет порядка квадрата от количества точек. С индексом — почти-линейная.
Также куб легче интерпретировать. Вставка/удаление буквы — плюс/минус к координате.
Также куб легче интерпретировать. Вставка/удаление буквы — плюс/минус к координате.
Мне кажется, стоило воспользоваться стандартными методами кластерного анализа, возможно получилось бы быстрее и более научным способом.
Кстати, для кодирования текста вашим способом тогда хорошо было бы еще использовать положение буквы по модулю, например буква «а» на первом месте добавляет 1, на втором — 2, на третьем — 3, а на четвертом — снова 1. Выбирая период (чтобы не было переполнения), но с другой стороны чтобы он был достаточно большим, можно учесть текст, в котором много одинаковых букв, но которые различаются по смыслу.
Кстати, для кодирования текста вашим способом тогда хорошо было бы еще использовать положение буквы по модулю, например буква «а» на первом месте добавляет 1, на втором — 2, на третьем — 3, а на четвертом — снова 1. Выбирая период (чтобы не было переполнения), но с другой стороны чтобы он был достаточно большим, можно учесть текст, в котором много одинаковых букв, но которые различаются по смыслу.
стоило воспользоваться стандартными методами кластерного анализа
Можно, пожалуйста, чуть подробнее этот момент.
К сожалению, я плохо разбираюсь в кластерном анализе, однако когда использовал (в другой задаче) разбиение на кластеры (в матлабе linkage/cluster), то мне пришлось вычислить заранее матрицу всех попарных расстояний. Статья же про то, что не обязательно вычислять все попарные расстояния.
Спасибо за интересную статью. Думаю, что можно взять вместо букв n-граммы и использовать Locality Sensitive Hashing. Если его использовать то можно избежать поиска ближайших точек с помощью r-дерева, которое будет плохо работать с n-граммами из-за большой размерности. Про поиск похожих текстов с помощью Locality Sensitive Hashing хорошо рассказывает Ульман в курсе Mining Massive Datasets (вторая неделя) class.coursera.org/mmds-001. Еще есть мысль попробовать понизить размерность n-грамных представлений с помощью Principal Component Analysis.
Поправьте меня, если я говорю что-то не так.
А нельзя ли пробежаться по текстам, сложить ASCII коды символов, и сравнить их? Если в тексте содержится немного опечаток, то разница между суммами символов должна быть небольшой. А если тексты отличаются друг от друга, то и разница будет большая.
А нельзя ли пробежаться по текстам, сложить ASCII коды символов, и сравнить их? Если в тексте содержится немного опечаток, то разница между суммами символов должна быть небольшой. А если тексты отличаются друг от друга, то и разница будет большая.
Спасибо, я посмотрю распределение таких сумм, может быть что-то вскроется.
Мне кажется, что это — огрубление описанного метода. Вы фактически получаете линейное отображение из многомерного пространства (где координаты соответствуют буквам) в одномерное отображение. Если точки с трудом разделяются в многомерном, то, скорее всего, в одномерном будет только хуже.
Мне кажется, что это — огрубление описанного метода. Вы фактически получаете линейное отображение из многомерного пространства (где координаты соответствуют буквам) в одномерное отображение. Если точки с трудом разделяются в многомерном, то, скорее всего, в одномерном будет только хуже.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Поиск почти-дубликатов и геометрия