Comments 18
Интересный алгоритм, спасибо.
О, Господи! Меня один только заголовок повергает в транс, а сам статья вообще убивает. Понял только одно — это очень круто.
Крайне интересно.
Мне приходилось столкнуться с задачей о классификации треков:
в результате некоторого процесса был дан набор треков вида
t=0 t=n
ААBBCCCDDBBBCDDCC
ABACCBBDDCCCCBBBC
и т п
Одни из этих треков описывали состояние процесса «нормального», а другие — испорченного.
Требовалось найти по некоторому треку, процесс какого вида мог к нему привести.
Задачу так удовлетворительно и не решили…
Было бы интересно попробовать примениить для классификации такой или похожий алгоритм.
В какую область математической статистики тут копать можно было бы?
Мне приходилось столкнуться с задачей о классификации треков:
в результате некоторого процесса был дан набор треков вида
t=0 t=n
ААBBCCCDDBBBCDDCC
ABACCBBDDCCCCBBBC
и т п
Одни из этих треков описывали состояние процесса «нормального», а другие — испорченного.
Требовалось найти по некоторому треку, процесс какого вида мог к нему привести.
Задачу так удовлетворительно и не решили…
Было бы интересно попробовать примениить для классификации такой или похожий алгоритм.
В какую область математической статистики тут копать можно было бы?
Чем-то похожим я сейчас занимаюсь, только вместо точек у меня фразы, и вычисление «расстояния» между ними — это самая заковыристая штука.
> Построим матрицу оценок расстояний между элементами
правильно ли я понимаю, что раз этот алгоритм строит матрицу расстояний между каждыми двумя элементами множества, то сложность такого алгоритма — квадратичная? Даже если сделать оптимизацию (матрица симметрична относительно диагонали), то получим (n^2)/2. Плюс вычислеие расстояния между объектами.
Такой алгоритм годится для относительно небольших данных (ну, скажем, до 50 000 объектов)
правильно ли я понимаю, что раз этот алгоритм строит матрицу расстояний между каждыми двумя элементами множества, то сложность такого алгоритма — квадратичная? Даже если сделать оптимизацию (матрица симметрична относительно диагонали), то получим (n^2)/2. Плюс вычислеие расстояния между объектами.
Такой алгоритм годится для относительно небольших данных (ну, скажем, до 50 000 объектов)
Очень интересно. А не разъясните «физический смысл» и назначение в данном алгоритме операции замыкания?
Идея в построение отношения, которое обладает свойством эквивалентности. В книге есть определения теоремы, которая утверждает что отношение эквивалентности разбивает множество на попарно непересекающиеся классы эквивалентных элементов.
Я бы с удовольствием интерпретировал это определение, но мои познания с теории множеств не позволяют :)
Я бы с удовольствием интерпретировал это определение, но мои познания с теории множеств не позволяют :)
А, я так и подумал. На мой взгляд, это недостаток — не так уж много реальных задач, в которых классы действительно не пересекаются. Интересно бы попробовать вместо замыкания прикрутить сюда что-нибудь из нечёткой логики, чтобы одна точка могла принадлежать нескольким кластерам одновременно.
Есть довольно много наработок на тему Fuzzy Clustering'а i.e FLAME clustering
Благодарю покорно, прочёл с интересом. Видимо, наработок всё ещё недостаточно много, поскольку по нечёткой кластеризации у меня на подходе дисер =) Одна из идей, в частности, что на данный момент нет смысла разделять чёткую и нечёткую кластеризацию на уровне алгоритмов. Написать чёткий алгоритм и не обощить его до нечёткого — это сказать а и не сказать б.
Это хороший пример того, что как некоторые российские математики умеют все запутать, чтобы выглядеть серьезней (я имею в виду авторов книги). Зачем, к примеру, переименовывать min и max в S и T?
На самом деле min и max — это нечеткое AND и OR соответственно, и судя по тому, что авторы опирались на теорию нечетких отношений, это скорее всего действительно так. Тогда смысл замыкания здесь в том, что вначале ищется для каждого элемента и подмножества — находится ли этот элемент в отношении R с подмножеством, то есть со всеми его элементами, и здесь используется MIN потому что это выражение "(x R a1) OR (x R a2) OR… (x R aN)"; затем, вычисляется — находится ли элемент в отношении R хотя бы с одним подмножеством, и здесь используется max потому что это OR.
И та теорема, скорее всего, — перевод логики нечетких отношений в более привычную для автора алгебру матриц. Хотя, чтобы точно быть уверенным, нужен полный текст книги.
На самом деле min и max — это нечеткое AND и OR соответственно, и судя по тому, что авторы опирались на теорию нечетких отношений, это скорее всего действительно так. Тогда смысл замыкания здесь в том, что вначале ищется для каждого элемента и подмножества — находится ли этот элемент в отношении R с подмножеством, то есть со всеми его элементами, и здесь используется MIN потому что это выражение "(x R a1) OR (x R a2) OR… (x R aN)"; затем, вычисляется — находится ли элемент в отношении R хотя бы с одним подмножеством, и здесь используется max потому что это OR.
И та теорема, скорее всего, — перевод логики нечетких отношений в более привычную для автора алгебру матриц. Хотя, чтобы точно быть уверенным, нужен полный текст книги.
>не очень известного, но крайне интересного иерархического метода
Ну не знаю у кого он не очень известный, но в социологии и в маркетинговых исследованиях он используется очень часто (чаще чем k-means). Преимущество этого метода в том, что дерево кластеров очень наглядно показывает структуру данных. Только вот вы почему-то это дерево в статье не привели, а оно то как раз и есть самое главное в иерархических видах анализа.
Другое преимущество — нет необходимости заранее фиксировать число кластеров. В исследовательских задачах это очень важно, потому что число кластеров в массиве данных заранее неизвестно.
Ну не знаю у кого он не очень известный, но в социологии и в маркетинговых исследованиях он используется очень часто (чаще чем k-means). Преимущество этого метода в том, что дерево кластеров очень наглядно показывает структуру данных. Только вот вы почему-то это дерево в статье не привели, а оно то как раз и есть самое главное в иерархических видах анализа.
Другое преимущество — нет необходимости заранее фиксировать число кластеров. В исследовательских задачах это очень важно, потому что число кластеров в массиве данных заранее неизвестно.
>он используется очень часто
Странно. До публикации статьи на гуглом находилось всего несколько научных статей-книг с упоминанием алгоритма.
> дерево кластеров
> нет необходимости заранее фиксировать число кластеров
Это всем известные преимущества иерархических методов. Не видел смысла о них упоминать еще раз.
> Только вот вы почему-то это дерево в статье не привели
Я бы с радостью, только здесь на порядок больше нужно было поработать над представлением результатов (дерево надо красиво нарисовать, точки на рисунках удобно пронумеровать) — а я пока так себе владею matplotlib.
Странно. До публикации статьи на гуглом находилось всего несколько научных статей-книг с упоминанием алгоритма.
> дерево кластеров
> нет необходимости заранее фиксировать число кластеров
Это всем известные преимущества иерархических методов. Не видел смысла о них упоминать еще раз.
> Только вот вы почему-то это дерево в статье не привели
Я бы с радостью, только здесь на порядок больше нужно было поработать над представлением результатов (дерево надо красиво нарисовать, точки на рисунках удобно пронумеровать) — а я пока так себе владею matplotlib.
>Странно. До публикации статьи на гуглом находилось всего несколько научных статей-книг с упоминанием алгоритма.
Ну я имел ввиду иерерхические методы вообще. А что касается конкретных алгоритмов, то социологи могут и не знать какой метод именно они используют:). Они же просто запускают какой-нибудь SPSS или R, и считают не вдаваясь особо в те алгоритмы, которые там используются.
Ну я имел ввиду иерерхические методы вообще. А что касается конкретных алгоритмов, то социологи могут и не знать какой метод именно они используют:). Они же просто запускают какой-нибудь SPSS или R, и считают не вдаваясь особо в те алгоритмы, которые там используются.
Sign up to leave a comment.
Кластеризация. Алгоритм а-квазиэквивалентности