Генетический алгоритм - кластеризация

[_rip_]

Hi All!

Господа, встал вопрос - а существуют ли реализации алгоритмов кластеризации с использованием генетических алгоритмов?

Я погуглил, но ничего по сути не нашел. Может кто поделится своим опытом?

Фактически, понятие кластеризации можно свести к поиску оптимума двух функционалов:
1. Среднее внутрикластерное расстояние должно стремиться к min

$F_1 = \frac {\sum\limits_{i<j}[y_i = y_j]]\rho(x_i,x_j)} {\sum\limits_{i<j}[y_i = y_j]} \to min$

2. Среднее межкластерное расстояние должно стремиться к max

$F_2 = \frac {\sum\limits_{i<j}[y_i \neq y_j]]\rho(x_i,x_j)} {\sum\limits_{i<j}[y_i \neq y_j]} \to max$

где $\rho(x_i,x_j)$ - расстояние между двумя объектами
$y_i,y_j$ - кластера

т.е. фактически фитнесс ф-ция может быть выражена как:

${\phi = \frac {F_1} {F_2}} \to min$

Может кто сталкивался с полным описание подобного алгоритма кластеризации, буду признателен за ссылку

[Circiter]

Прежде всего, необходимо заметить, что генетические алгоритмы вообще интересны лишь в теории. Поиграться конечно с ними можно, но практическая ценность их сомнительна. Правда, это лишь мое личное мнение и решения должны приниматься для каждой конкретной ситуации отдельно.

Ok, допустим вы решите рискнуть и испробовать генетические алгоритмы в задаче кластеризации. Один из возможных подходов может быть таким. Пусть у нас есть выборка данных (вектора) $a_1,\ a_2,\ \ldots,\ a_n$ и число $k$ -- количество кластеров. Теперь выберем случайно центры кластеров $x_1,\ x_2,\ \ldots,\ x_k$. Для этих точек можно построить диаграмму Вороного, а мерой пригодности такого разбиения пространства считать достаточную близость центра каждой ячейки Вороного к среднему арифметическому точек данных попавших в эту ячейку. Например, в качестве функции пригодности можно попробовать выбрать выражение

$$\frac{1}{n}\sum_i^k\sum_{y\in\eta(x_i)} \|x_i-y\|\to\min,$$

где $\eta(x)$ -- множество точек данных, попавших в ячейку Вороного с центром $x$.

Если пространство имеет достаточно маленькую размерность, то координаты точек $x_i$ можно выписать в одну строку. Несколько таких случайно сгенерированных строк-хромосом вместе с описанной выше простой функцией пригодности теперь можно будет отдать генетическому алгоритму и ждать получения оптимального решения, наилучшим образом разбивающего наше пространство.

Вот такие вот мыслишки, думаю, их можно как-нибудь применить и в вашем случае. По мне так какие-нибудь там карты Кохонена и то эффективней, ага. :) Хотя в литературе по ГА акцент делается на том, что полученное таким образом решение (если вы его дождетесь) будет по крайней мере очень-очень хорошим (близким к глобальному экстремуму целевой функции).

-- Чт июл 29, 2010 03:13:29 --

В принципе, описанный мной подход прекрасно подходит к вашей задачке, фитнесс функция у вас есть, кластера $y_i$ тоже имеются. Вот выбирайте их случайно, кодируйте строкой и оптимизируйте с помощью ГА. Удачи вам.

[_rip_]

Circiter в сообщении #341382 писал(а):

Вот такие вот мыслишки, думаю, их можно как-нибудь применить и в вашем случае. По мне так какие-нибудь там карты Кохонена и то эффективней, ага. :) Хотя в литературе по ГА акцент делается на том, что полученное таким образом решение (если вы его дождетесь) будет по крайней мере очень-очень хорошим (близким к глобальному экстремуму целевой функции).

-- Чт июл 29, 2010 03:13:29 --

В принципе, описанный мной подход прекрасно подходит к вашей задачке, фитнесс функция у вас есть, кластера $y_i$ тоже имеются. Вот выбирайте их случайно, кодируйте строкой и оптимизируйте с помощью ГА. Удачи вам.

Спасибо. Подход действительно очень интересный. Как-то не думал использовать ячейки Вороного построения оценки качества кластеризации.

У меня тогда сразу вопрос, если мы проводим кластеризацию объектов, описанных $N$-параметрами на сколько приемлемо использование ячеек Вороного? Фактически объекты кластеризации находятся в N-мерном пространстве. В моем случае $N=5,N=6,N=7$ (это несколько не зависимых наборов данных).

Как раз это стало причиной поиска более эффективных алгоритмов кластеризации чем k-means, так как в пределах одного кластера наблюдаются биения по одной или двум координатам.

Карты Кохонена это эффективный механизм, но как перейти от цветовой модели - численной? Фактически, мне надо не одноразовое исследование выборок, а инструмент который бы дал возможность постоянно, в режиме реального времени проводить разбиение на кластеры с коррекцией центров кластеров, с учетом новых данных.

[Yuri Gendelman]

_rip_ в сообщении #341423 писал(а):

... это стало причиной поиска более эффективных алгоритмов кластеризации чем k-means, так как в пределах одного кластера наблюдаются биения по одной или двум координатам.

Вы можете попробовать методы снижения размерности (типа метода главных компонент) перед кластеризацией. Переход к ГК может сработать как "фильтр".

[Circiter]

Да уж, не думаю, что ГА будут хорошо себя вести в условиях "динамичности" данных... Хотя попробовать можно.

Кстати, когда я предлагал карты Кохонена, то как раз и подразумевал упомянутое в явном виде участником Yuri Gendelman снижение размерности данных. По-сути, карты Кохонена -- это и есть метод главных компонент, только с нейрофизиологическим уклоном. То есть, даже после фильтрации все равно придется решать задачу кластеризации, правда, уже в пространстве меньшей размерности (например на плоскости). Может быть здесь-то метод k-средних и сгодится. Однако, если вы решите использовать другие, оптимизационные методы кластеризации, то, наверное, лучше выбрать что-нибудь менее эвристичное чем ГА или ИНС, например, что-нибудь вроде обычного град. спуска... :)

Также, стоит подумать над огрубленим функции пригодности. Вот здесь-то эвристики всевозможные не помешают.

[Circiter]

Кстати, карты Кохонена можно использовать не только в качестве фильтра, снижающего размерность, но и в качестве самостоятельного механизма кластеризации. Вообще, если узлов ("нейронов") у карты Кохонена очень и очень много, то функционирование такой сети становится похожим на метод главных компонент, а если сделать количество узлов очень маленьким, --- например, совпадающим с предполагаемым количеством кластеров, --- то работа сети становится неотличимой от метода k-средних; другими словами, в последнем случае вес каждого выхода карты может рассматриваться как центр(оид) одного из кластеров, ну а для фактической кластеризации можно на конечном этапе снова воспользоваться диаграммой Вороного или пропустить через карту исходные данные в режиме классификации.

Здесь есть одна (а может быть и не одна) проблема -- хорошо "обученная" карта Кохонена становится чрезвычайно негибкой и слабо подстраивается под новые данные (хотя такой подстройки может и не понадобится). И уж тем более непонятно как все это будет себя вести при произвольных изменениях окружающей среды, в частности, при миграции точек между кластерами.

А вот ГА, наоборот, славятся своей жадностью и в некотором смысле прекрасно адаптируются в резко меняющейся обстановке. Правда, это не всегда хорошо (застревание в локальных минимумах) и для этого придется все время хранить популяцию в памяти.

Вообще, интересно было бы все-таки попроводить экспериментики со связкой КК + ГА (дабы скрестить инертность карт Кохонена с прыткостью генетических алгоритмов). То есть сначала данные пропускать через КК, а потом уже с помощью ГА кластеризовать результат. Это позволит выдумать какую-нибудь очень грубую (но зато быструю) фитнесс-функцию. Хотя на самом деле у такого подхода преумеществ мало; ну да, распараллеливаемость классная, но и всё на этом... :)

Такую связку можно усовершенствовать. Допустим количество кластеров вам заранее известно лишь примерно. В этом случае можно на уже построенную карту Кохонена накидать точек больше предполагаемого числа кластеров (скажем, раза в два) и после того как их положение будет уточнено генетическим алгоритмом можно произвести оптимизацию соответствующей диаграммы Вороного путем удаления "перегородок" между слишком близкими кластерами. В результате мы уточним (уменьшим) число кластеров, а в придачу ещё и уточним их форму (этот трюк позволит выделять кластеры невыпуклой формы). К тому же, что-то мне подсказывает, что по карте Кохонена найти диаграмму Вороного будет проще (cf. U-matrix).

P.S.: Вы затронули очень сложную тему... :)

[Circiter]

Кажется, нашел немного более простую функцию пригодности для использования с ГА. В первом своем сообщении я уже сделал небольшое упрощение, отказавшись от МНК, а на этот раз я предлагаю одну из сигм заменить на минимум:

$$\sum_{i=1}^n\min_{j\in[1;\ k]}\|x_j-y_i\|\to\min,$$

где $x_i$ -- затравки кластеров, $y_i$ -- данные. Интуитивно чувствуется, что вычислять такую функцию можно достаточно быстро; тем более, я что-то такое уже где-то видел... :) К тому же, для измерения расстояний можно использовать угол между векторами.

Что до карт Кохонена, то здесь ещё один довод в их пользу пришел в голову. Если снижать размерность выборки с помощью метода главных компонент (в его классической постановке), то в результате будет найден базис, в разложении по которому выборка выглядит наиболее выгодно и лучше всего кластеризуется. Однако, учитывая заявление о "биениях по всего двум координатам" (честно говоря, не понял, что это означает :) ), можно предположить, что у каждого кластера могут быть свои оптимальные ГК (i.e. кластеры ориентированы хаотично). Так вот карты Кохонена, по общим соображениям, в этом случае извлекут, в некотором смысле, больше информации... Правда, я нигде разбора этого вопроса не встречал (может быть потому, что вообще ИНС и ГА недолюбливаю, да и на чистую кластеризацию особого внимания никогда не обращал, сосредотачиваясь вместо этого на вопросах классификации и распознавания). :)

Ах да, чуть не забыл, ещё один маленький совет по ГА. Хромосомы неплохо бы было представить битовыми массивами в кодах Грея. При этом "сила" мутаций будет пропорциональна изменению решения (с одной стороны, мелкие мутации не будут приводить к непредсказуемым скачкам центроидов, с другой же -- для тонкой подстройки центроидов не понадобятся значительные мутации). Хотя, наверное, это лишнее...

Ещё я где-то слышал, что результат ГА-кластеризации хорошо "шлифуется" методом k-средних. То есть, в этом случае, кластеризация выполняется преимущественно все-таки именно методом k-средних, но, так как этот метод слишком чувствителен к начальному решению, то ГА здесь используется для выбора этого налучшего начального приближения. Даже так...

Без экспериментов лучший подход не выбрать... :) А пока выводы таковы: k-means -- не самый качественный, но, думаю, очень быстрый метод, который, однако, может потребовать предварительной подготовки данных; самоорганизующиеся карты Кохонена тормозят, но, также как и k-means, хорошо работают с большими и многомерными выборками, правда при этом саму кластеризацию почти не производят и требуют дополнительного алгоритма для интерпретации результатов, неплохих результатов; ГА хорошо себя чувствуют в малых размерностях и малых объемах информации, полезны для пред- и/или постобработки данных. Среди гибридов можно упомянуть алгоритмы FGKA и IGKA, которые описаны соответственно в Yi Lu et al., FGKA: A Fast Genetic K-means Algorithm, и в Yi Lu et al., Incremental Genetic K-means Algorithm and its Application in Gene Expression Data Analysis.

Существует ещё класс инкрементных алгоримов кластеризации, специально заточенных для работы в изменяющихся условиях (т.е. при добавлении/удалении точек данных). В основном, эти алгоритмы эксплуатируют методики классификации: когда появляется новая точка данных, такой алгоритм относит её к какому-нибудь из имеющихся классов (кластеров) или создает новый (возможно склеивая некоторые из существующих). Причем все спроектировано так, чтобы добавлять/удалять точки можно было с минимальными затратами времени/памяти. Это очень эффективные и экономичные алгоритмы кластеризации, но здесь есть один подвох... Разбиение сильно зависит от порядка поступления данных и это почти непоправимо. :) Один двольно старый метод описан в F.Can, Incremental Clustering for Dynamic Information Processing. Ещё можно глянуть M.Charikar et al., Incremental Clustering and Dynamic Information Retrieval.

Не могу не упомянуть довольно забавный и в тоже время широко используемый подход к кластеризации. Идея заключается в том, чтобы оценить распределение плотности точек данных по пространству и к полученному полю применить пороговый фильтр, после чего произвести заливку кластеров краской. Ну примерно так, есть пути для оптимизации. :) Типичные представители: алгоритмы DBSCAN (выращивающий кластеры, добавляя в них достаточно близкие точки) и OPTICS (суть усовершенствование предыдущего), их описания можно найти в Ester et al., A Density-based Algorithm for Discovering Clusters in Large Spatial Databases with Noise и в M.Ankerst et al., OPTICS: Ordering Points To Identify the Clustering Structure.

[_rip_]

Господа, всем очень признателен за обсуждение, которое натолкнуло меня решение задачи на 90% удовлетворяющее всем требованиям.
:)

[Elena_Poleno]

Ребят, а если использовать метод к-ближайших соседей и ГА, то чего можно добиться? Я новичок просто в этой теме, но придумывать и экспериментировать уже надо)

[allchemist]

Вместо k-средних спектральную кластеризацию попробуйте. Хорошая реализация, например, функция specc в пакете kernlab из R. В том же пакете еще есть нелинейный анализ главных компонент на основе ядра (функция kpca).

А с генетикой лучше не связываться. В подавляющем большинстве случаев это пустая трата процессорного времени, к сожалению.

[Elena_Poleno]

О, благодарю за совет! Просто я аспирантка и вообще не знаю, в какую сторону податься: кластеризация данных - интересно, Data Mining - то же интересная вещь. НО вот с какой стороны открытие в этой области делать - вопрос!

[Groging]

allchemist в сообщении #676440 писал(а):

А с генетикой лучше не связываться. В подавляющем большинстве случаев это пустая трата процессорного времени, к сожалению.

а можно поподробнее?
Или это на основе сравнения со скоростью работы других методов в реальных задачах ?

[Pavia]

Нейронные сети, генетические алгоритмы, datamining. - Это одного поля ягоды. Они могут решить задачу если её правильно поставить. Но когда вы задачу правильно поставите, то вы увидите что она решается другими метадами.
Дела с ними обстаят как с кашей из тапора из известного рассказа.

При неправильной постановки эти методы негарантируют ничего. Ни точности решения, ни того что оно будет найдено, даже время за которое будет найдено хоть какое решение.

Кластеризацию в эту группу не включаю, так как она нерешает неправильно поставленные задачи. Не вводила и невводит в заблуждения людей.

[allchemist]

Groging в сообщении #733031 писал(а):

а можно поподробнее?

Ну это очевидно, в общем-то. Сколько лишних телодвижений совершается!

На некоторых хитрых задачах ГА дает хорошие результаты, но опять же поверх какого-нибудь быстрого алгоритма локального поиска типа сопряженных градиентов или розенброка.

Цитата:

Или это на основе сравнения со скоростью работы других методов в реальных задачах ?

Я довольно много игрался с ГА, сам писал код и поэтому мог играться с разными необычными вариациями и комбинациями, какие не дают чужие библиотеки. К сожалению, пришел к грустному выводу.

-- Чт июн 06, 2013 23:56:31 --

Pavia в сообщении #733049 писал(а):

Нейронные сети, генетические алгоритмы, datamining. - Это одного поля ягоды.

Датамайнинг датамайнигу рознь. Слишком большая область, чтобы все так под одну гребенку. Вы напрасно отождествляете весь датамайнинг и адаптивные алгоритмы. Машины опорных векторов, вейвлеты, анализ главных компонентов сотоварищи - тоже датамайнинг.

Цитата:

Они могут решить задачу если её правильно поставить. Но когда вы задачу правильно поставите, то вы увидите что она решается другими метадами.

Дык ведь все наоборот, и в этом основное преимущество адаптивных алгоритмов!

Классические алгоритмы требуют корректной постановки задачи и корректных входных данных.

Адаптивные алгоритмы обычно работают хуже и дольше, зато могут кое-как работать даже на очень плохих данных и с некорректными задачами (кстати, тихоновское понятие некорректно поставленной задачи ходит рядом :))

Цитата:

При неправильной постановки эти методы негарантируют ничего. Ни точности решения, ни того что оно будет найдено, даже время за которое будет найдено хоть какое решение.

Именно так, но при неправильной постановке и плохих данных классические алгоритмы вообще фигу покажут.
Тогда как грамотный анализ результата (или его полного отсутствия), а также самого адаптивного процесса может реально подсказать, как лучше сформулировать задачу и подготовить данные.