 |
mech_optimiz
4.4.1
microkinetic mechanism investigation tool
|
|
mech_optimiz
4.4.1
microkinetic mechanism investigation tool
|
Кластеризация данных - один из метода анализа данных, поиска в них закономерностей.
Если данные многомерны - трудно оценить, как расположены точки в пространстве, образуют ли некоторые группы. Кластеризация помогает выявить сходство и различия в точках данных, разбить данные на группы. Далее, мы устанавливаем, какие признаки позволили произвести данное разбиение, то есть, какие признаки являются определяющими в сходстве и различии индивидуальных точек.
Очевидно, что если взять число кластеров k, равным числу экспериментальных точек для кластеризации, то каждый кластер будет содержать одну экспериментальную точку, при этом средний силуэт будет равен 1 (идеальная кластеризация).
Вообще, по мере приближение k к числу экспериментальных точек, средний силуэт растет. Но мы должны выбрать такое k, которое много меньше, чем число экспериментальных точек (когда в каждом кластере находится значительное число точек, тогда можно говорить о закономерностях в данных, о наличии кластеров).
Пример, который дан ниже по ссылке, наглядно это демонстрирует. Число кластеров (по правилу максимального силуэта) в данном случае: 2 (а не 148/149) Кластеризация 150 точек
Мы используем метод 3, то есть, выбираем такое число кластеров, которое дает максимальный средний силуэт кластеров. Данный алгоритм выбора числа кластеров также хорошо описан в Wikipedia.
Кроме того, mech_optimiz имеет некоторые возможности выявления, какие параметры являются шумом в данных и лишь мешают правильной кластеризации. Для этого в mech_optimiz реализован подход Lleti и др. [6] поиска набора параметров, соответствующих максимальному среднему силуэту, поиск выполняется с помощью генетического алгоритма. Мы усовершенствовали этот подход, одновременно позволив подбирать еще один параметр - число кластеров. Таким образом, можно достичь оптимальной кластеризации, как по числу кластеров, так и по числу содержательных (несущих информацию о сходстве/различии) параметрах одновременно.
Сама кластеризация выполняется с помощью алгоритма k-means++ [1] (ссылка), который представляет собой расширение k-means. Конкретно, k-means выбор точек, используемых в качестве начальных центроидов кластеров, производится из числа точек данных случайным образом. В k-means++ выбор начальных центроидов производится не случайным образом (так выбирается только первая точка), а в соответствии с взвешенным распределением вероятности, где в качестве веса используется расстояние от точки до ближайшего центроида.
Алгоритмы кластеризации и их реализации обычно проверяют и сравнивают на хорошо известных тестовых задачах. Одной из таких задач являются "Ирисы Фишера", где по значениям ширины/длины наружной (чашелистик) и внутренней (лепесток) доли околоцветника алгоритм должен разбить экземпляры ирисов по сортам.
В зависимости от количества кластеров, получаем разные результаты кластеризации. mech_optimiz кластеризует данные в 2..N-1 кластеров, где N - число точек данных. Кластеризация повторяется для каждого числа кластеров автоматически 10 раз. Наилучшая кластеризация используется как итоговая для данного числа кластеров. Результаты кластеризации сохраняются в текущей папке, что позволяет визуализировать выбранную кластеризацию позднее с помощью утилиты plotCL.sh. Повторы кластеризации нумеруются от 0 до 9. Если новая итерация (повтор) дает лучший средний силуэт, чем предыдущие, информация о предыдущих итерациях удаляется с диска. Таким образом, наименьший номер повтора в файлах в текущей директории соответствует наилучшей кластеризации (странная функциональность, пока не исправлена - октябрь 2015).
Информация о силуэтах для разного числа кластеров сохраняется в файле K-номер_итерации_ГА-номер_особи_ГА-silhouettes.txt Сами кластеры (координаты центров, а затем список точек с указанием в последнем столбце номера кластера, которому принадлежит точка) сохраняются в файлы K-номер_итерации_ГА-номер_особи_ГА.txt Если в кластеризации участвуют все параметры, то создается файл K-номер_итерации_ГА-full.txt Этот файл будет создан в случае, если особи ГА статичны, то есть мы не ищем с помощью ГА, какие параметры следует включить в кластеризацию, а выполняется обычная кластеризация точек с учетом всех параметров (измерений данных, столбцов). Решение прямых задач
Пример "Кластеризация 150 точек", представленный выше, содержит результаты кластеризации ирисов Фишера с помощью подхода максимального силуэта кластеров. Результаты показывают, что в ирисах Фишера содержится 2 кластера, то есть, два сорта цветов. Это известная проблема указанного набора данных при кластеризации. На самом деле, набор содержит данные о 3 сортах цветов. Однако для 3 кластеров, алгоритм k-means++ верно распределяет образцы по сортам.
Алгоритм вычисления среднего силуэта также реализован в Matlab, где могут получены аналогичные результаты (Matlab clustering example)
resultIRIS.txt - 2 кластера, получено с помощью mech_optimiz (ирисы Фишера)
data1.txt - Данные с ирисами, подготовленные для mech_optimiz (data1_ml.txt - для MLPACK Wikipedia.)
resultIRIS2.txt - кластеризация ирисов Фишера по 3-м кластерам, mech_optimiz
data1_mlpack_clust.txt - результаты, полученные с помощью MLPACK
data3.txt - другой набор данных Ruspini [10].
resultRUSPINI.txt - Ruspini data with mech_optimiz
Для получения картинок и видео результатов кластеризации создан bash-скрипт plotCL.sh. Он принимает на вход 4 аргумента:
Для построения графиков и создания видео нужны временные файлы, созданные программой в текущей директории (обычно - директории запуска mech_optimiz) при кластеризации. Если они удалены, необходимо повторить кластеризацию.
./plotCL.sh 1 4 3 5
1.8.11 
