Pull to refresh

Comments 18

О, Господи! Меня один только заголовок повергает в транс, а сам статья вообще убивает. Понял только одно — это очень круто.
Крайне интересно.
Мне приходилось столкнуться с задачей о классификации треков:
в результате некоторого процесса был дан набор треков вида
t=0 t=n
ААBBCCCDDBBBCDDCC
ABACCBBDDCCCCBBBC
и т п
Одни из этих треков описывали состояние процесса «нормального», а другие — испорченного.
Требовалось найти по некоторому треку, процесс какого вида мог к нему привести.
Задачу так удовлетворительно и не решили…
Было бы интересно попробовать примениить для классификации такой или похожий алгоритм.
В какую область математической статистики тут копать можно было бы?
Я не уверен, что правильно Вас понял, но при чем здесь матстатистика?

> процесс какого вида мог к нему привести
Похоже на предметную область теории конечных автоматов.
Чем-то похожим я сейчас занимаюсь, только вместо точек у меня фразы, и вычисление «расстояния» между ними — это самая заковыристая штука.
Делал такое. Вроде ж есть достаточно способов перевести фразу в вектор, а дальше уж сравнивать координаты, хотя бы и как в этой статье.
> Построим матрицу оценок расстояний между элементами

правильно ли я понимаю, что раз этот алгоритм строит матрицу расстояний между каждыми двумя элементами множества, то сложность такого алгоритма — квадратичная? Даже если сделать оптимизацию (матрица симметрична относительно диагонали), то получим (n^2)/2. Плюс вычислеие расстояния между объектами.
Такой алгоритм годится для относительно небольших данных (ну, скажем, до 50 000 объектов)
Да, нужно посчитать n*n/2 расстояний. Кроме того, операция свертки может быть довольно дорогой для не дискретных данных.
Очень интересно. А не разъясните «физический смысл» и назначение в данном алгоритме операции замыкания?
Идея в построение отношения, которое обладает свойством эквивалентности. В книге есть определения теоремы, которая утверждает что отношение эквивалентности разбивает множество на попарно непересекающиеся классы эквивалентных элементов.

Я бы с удовольствием интерпретировал это определение, но мои познания с теории множеств не позволяют :)
А, я так и подумал. На мой взгляд, это недостаток — не так уж много реальных задач, в которых классы действительно не пересекаются. Интересно бы попробовать вместо замыкания прикрутить сюда что-нибудь из нечёткой логики, чтобы одна точка могла принадлежать нескольким кластерам одновременно.
Благодарю покорно, прочёл с интересом. Видимо, наработок всё ещё недостаточно много, поскольку по нечёткой кластеризации у меня на подходе дисер =) Одна из идей, в частности, что на данный момент нет смысла разделять чёткую и нечёткую кластеризацию на уровне алгоритмов. Написать чёткий алгоритм и не обощить его до нечёткого — это сказать а и не сказать б.
Это хороший пример того, что как некоторые российские математики умеют все запутать, чтобы выглядеть серьезней (я имею в виду авторов книги). Зачем, к примеру, переименовывать min и max в S и T?

На самом деле min и max — это нечеткое AND и OR соответственно, и судя по тому, что авторы опирались на теорию нечетких отношений, это скорее всего действительно так. Тогда смысл замыкания здесь в том, что вначале ищется для каждого элемента и подмножества — находится ли этот элемент в отношении R с подмножеством, то есть со всеми его элементами, и здесь используется MIN потому что это выражение "(x R a1) OR (x R a2) OR… (x R aN)"; затем, вычисляется — находится ли элемент в отношении R хотя бы с одним подмножеством, и здесь используется max потому что это OR.

И та теорема, скорее всего, — перевод логики нечетких отношений в более привычную для автора алгебру матриц. Хотя, чтобы точно быть уверенным, нужен полный текст книги.
>не очень известного, но крайне интересного иерархического метода

Ну не знаю у кого он не очень известный, но в социологии и в маркетинговых исследованиях он используется очень часто (чаще чем k-means). Преимущество этого метода в том, что дерево кластеров очень наглядно показывает структуру данных. Только вот вы почему-то это дерево в статье не привели, а оно то как раз и есть самое главное в иерархических видах анализа.
Другое преимущество — нет необходимости заранее фиксировать число кластеров. В исследовательских задачах это очень важно, потому что число кластеров в массиве данных заранее неизвестно.
>он используется очень часто
Странно. До публикации статьи на гуглом находилось всего несколько научных статей-книг с упоминанием алгоритма.

> дерево кластеров
> нет необходимости заранее фиксировать число кластеров
Это всем известные преимущества иерархических методов. Не видел смысла о них упоминать еще раз.

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

Ну я имел ввиду иерерхические методы вообще. А что касается конкретных алгоритмов, то социологи могут и не знать какой метод именно они используют:). Они же просто запускают какой-нибудь SPSS или R, и считают не вдаваясь особо в те алгоритмы, которые там используются.
Теперь понятно :) Фраза

>не очень известного, но крайне интересного иерархического метода

никак не имела ввиду редкость иерархических методов вообще, а только редкость конкретного метода.

п.с. у Вас отличные статьи о распознавание образов :)
Only those users with full accounts are able to leave comments. Log in, please.