Pull to refresh

Comments 41

Молодец, и тут тебе тоже «отл.» в зачетку
Хоть кто-то в наше время пишет дипломы сам
Вы еще пропустили популярную меру оценки расстояния как корреляцию между координатами (векторами значений)
Уверен, я много что еще пропустил :). Можете рассказать поподробнее про эту меру?
Спасибо большое, отличный обзор для «непосвящённого»
Спасибо, очень интересно, а главное я наконец смог понять, для чего используется функциональный анализ.
Теорию меры и метрические пространства мы изучали пока что только в курсе функционального анализа.
Вы большая умничка! У меня как раз был диплом связанный с кластеризацией. Ностальгия охватила.
Вам не приходилось сталкиваться с задачей автоматического определения числа кластеров?
Мне приходилось. Что конкретно интересует?
Интересует, какие подходы и алгоритмы применяются для решения этой задачи на ОЧЕНЬ больших объемах данных?
Алгоритмы и подходы те же, что и на небольших объемах данных. Разница заключается в том, что а) данные могут обрабатываться параллельно (или могут использоваться кластеры) б) данные могут анализироваться локально (т.е. данные разбиваются на меньшие группы), а потом сравниваться между собой (пост-процессинг) в) если есть какие-то экспертные данные, то делаются допущения на ранних этапах (пре-процессинг), но это может влиять на корректность результата. Где-то так.
А мне кажется, что любой алгоритм, явно не задающий количество кластеров, так или иначе требует задание каких-то косвенных параметров, которые влияют на итоговое количество кластеров? Или я не так понимаю смысл задачи автоматическое определение числа кластеров?
Для этого есть алгоритм X-Means, реализацию его на java можете посмотреть в системе довольно известной datamining-системе weka:
www.java2s.com/Open-Source/Java-Document/Science/weka/weka.clusterers.htm

Основываются они примерно на том, что минимизируется, так сказать, «количество дырок» внутри кластера.
у меня тоже похожий диплом… эххх
Не встретил в тексте ни слова о самоорганизующейся карте Кохонена. Ну или просто о нейросетевой кластеризации(в том числе и нейронный газ). Вы можете пояснить почему? Просто сам в своих задачах отдавал предпочтение этим алгоритмам.
А как тестировали и результаты напишете? У меня курсач был на эту тему. На новостях самые простые алгоритмы дали лучшие результаты.
С результатами, если честно, туго :). Дальше экспериментов дело не пошло, настало время защиты, и нормальных результатов нет.

Использовал квадрат эвклидова расстояния (чтоб «увеличить» расстояния), а также параметр для «разваливания» дерева (все величины предварительно нормализовывал), соответственно результаты на глаз оценивал.
Советую обратить внимание на такие алгоритмы как LSH и RBVs которые позволяют быстро определять принадлежность произвольного вектора кластеру.
>а объекты разных группы должны быть как можно отличны.
как можно более отличны, вероятно.
Из текста непонятно, а темой я, как самоучка, не владею — что понимается под размером кластера? Число элементов в нём, или «протяженность»(расстояние между самыми удаленными элементами). Интуитивно вроде первое, но вдруг…
Да, под размером кластера понимается число объектов в нем.
А не расскажите, какие меры расстояний используют для текстовой информации? Я думаю для DataMining это более актуальная задача.
Для текстовой информации используются другие методы и подходы. Хотя, в самом простом случае, тексты разбиваются на векторы объектов (слова, фразы и т.д.) и считается расстояние между двумя векторами (меры расстояния специфичны для конкретной задачи).
С Text Mining/IR я не работал, к сожалению. Знаю только, что для качественных характеристик существуют меры Чекановского-Соренсена и Жаккара.
Нужно ещё упомянуть про SVM — Support Vector Machine от профессора Вапника.
Те кто плотно работают с задачами кластеризации на практике пользуются этим подходом довольно часто. Есть и коммерческие пакеты, такие как например KXEN.
Здесь есть слайды к лекции по кластерному анализу. Общий обзор для непрофильной специальности. И пошаговый пример вычисления для иерархического алгоритма.
Спасибо. Звук на слайдбуме выносит мозг :)).
:) по-моему это стандартные звуки для PP 2010.
А можно чуть подробнее про сам диплом? В какой области поставленную задачу решали и какими средствами? Как анализируемые данные были представлены?

Сам в этом году по Data Mining дипломировался, только задачи другие были, ассоциации искал :)
В моем случае кластеризация была не в контексте data mining'а. В рамках разработки системы хранилища данных нужно было большие файлы иерархических структур (XML, JSON) разделять на более мелкие, основываясь на статистике обращения к элементам.
писал для диплома алгоритм кластеризации через генетические алгоритмы — модная кстати тема. у меня в городе один профессор этим занимается
В свое время использовал (только по учебе) простой алгоритм k-средних (евклидово расстояние) для кластеризации цветовых пятен по сходству.
Запомнился вот этот cgm.computergraphics.ru/ неплохой ресурс, только по графике правда
Вот еще вспомни общее logic.pdmi.ras.ru/~yura/internet/02ia-seminar-note.pdf «Кластеризация данных» (Александр Котов)
Высшая Школа Экономики, факультет Социологии?
Политех, факультет технической кибернетики.
Почему вы примеры не приводите? Очень трудно читать. Про «объяснение нормальным человеческим языком» я, уж ладно, промолчу, ибо понимаю, что в научной среде это нонсенс. Но хоть бы пару примеров типа «вот у нас есть набор из стапицот вислоухих кроликов, и под кластеризацией по критерию вислости ушей мы понимаем то-то, таким-то алгоритмом делаем так-то и получаем бла-бла-бла...»
Ученые объяснения большей частью производят то впечатление, что бывшее ясно и понятно становится темно и запутанно.
Л.Н. Толстой. «Дневники, 1900, сентябрь.»
В алгоритме выделения связных компонент задается входной параметр R и в графе удаляются все ребра, для которых «расстояния» меньше R. Соединенными остаются только наиболее близкие пары объектов.

Ммм… Я туплю, или правильно будет «в графе удаляются все ребра, для которых «расстояния» больше R.»?
Да, вы правы. Исправил. Спасибо!
Only those users with full accounts are able to leave comments. Log in, please.