Применение алгоритма k-means++ для кластеризации последовательностей с неизвестным количеством кластеров

Применение алгоритма k-means++ для кластеризации последовательностей с неизвестным количеством кластеров

Шокина М.О., НИУ Высшая школа экономики, МИЭМ moshokina@edu.hse.ru

Аннотация

В данной статье рассматриваются два способа кластеризации последовательностей с неизвестным числом кластеров с помощью алгоритма k-means++. Первый способ - кластерный анализ, при котором в качестве метрики используется расстояние Хэмминга. Второй способ - преобразование строковых данных в числовые и кластеризация числовых массивов, получившихся в результате преобразований.

1 Введение

Кластеризация (или кластерный анализ) — это одна из фундаментальных задач Data Mining, которая представляет собой задачу разбиения множества объектов (ситуаций) на непересекающиеся подмножества, называемые кластерами [Jain, Murty, Flynn, 1999]. Кластерный анализ, в основном, используется для понимания данных путём выявления их структуры, или наоборот, для выявления нетипичных объектов, которые не подходят по своим признакам к другим объектам выборки [MachineLearning.ru [Электронный ресурс]. URL: http://www.machinelearning.ru].

В данной работе описано применение алгоритмов кластерного анализа для понимания структуры данных символьных последовательностей. Исходные данные представляют собой файл, содержащий символьные последовательности, которые представляют собой данные, полученные с помощью секвенирования генов. Другими словами, имеется несколько исходных последовательностей (от 3 до 6, точное количество неизвестно), которые в некотором порядке считываются в файл. Считывание происходит с ошибками, поэтому исходные последовательности нам заранее неизвестны. Таким образом, целью описанной работы является восстановление исходных последовательностей с помощью кластерного анализа. Наиболее схожие друг с другом последовательности объединятся в кластеры, а усреднённое значение - центр кластера - будет считаться исходной последовательностью.

2 Исходные данные

В качестве входных данных используются синтетические данные.

Для создания входного файла с последовательностями был создан генератор последовательностей. Генератор предоставляет следующие возможности:

- количество исходных аллелей выбирается случайным образом (3 - 6 аллелей);

- длина последовательности фиксированная - 285 символов;

- последовательности могут включать в себя только 4 символа - нуклеотиды A, G, T, C;

- полученные случайным образом аллели записываются в файл для возможности последующего сравнения результата кластеризации с исходными данными;

- случайным образом выбирается следующая аллель для записи в будущий входной файл;

- случайным образом выбирается количество ошибочных символов в будущей последовательности (от 0 до 285, ошибочной может получиться даже целая строка);

- случайным образом выбирается позиция ошибочного символа, и заменяется на случайное значение символа.

Полученная в результате таких преобразований «ошибочная» последовательность записывается в файл, который затем пойдёт на вход алгоритма k-means++

3 Применение алгоритма k-means++ для кластеризации строковых данных 3.1 Меры расстояний между элементами

Существует 3 типа признаков, по которым ведётся оценка расстояний между объектами кластеризации:

- количественные (Евклидово расстояние, расстояние городских кварталов, расстояние Чебышева и др.);

- качественные (расстояние Хэмминга, расстояние Роджерса-Танимото и др.);

- смешанные (расстояние Журавлёва).

В данной работе для кластерного анализа использовались две меры расстояний. Первая -расстояние Хэмминга, которое обозначает число позиций, в которых соответствующие символы двух строк одинаковой длины различны [Glossary of Telecommunication Terms, 1996] . Так как

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

Вторая метрика, использующаяся в работе - Евклидово расстояние, которое является геометрическим расстоянием в многомерном пространстве (1):

3.2 Поиск центров кластеров с использованием расстояния Хэмминга

Так как большинство библиотек, в которых реализован алгоритм k-means++, работают с числовыми данными, для кластеризации последовательностей с помощью расстояния Хэмминга была создана собственная реализация k-means++ на языке python.

Первым этапом алгоритма является выбор начальных центров кластеров. В случае кластеризации последовательностей данный этап остаётся без изменений. С помощью генератора случайных чисел выбирается первый центр кластера, затем ищутся наиболее удалённые от него последовательности. Мерой расстояния служит описанное в п.2.1 расстояние Хэмминга.

Второй этап - непосредственно k-means. Суть алгоритма заключается в минимизации суммарного отклонения точек кластеров от центров этих кластеров [Мандель, 1988]

где к - число кластеров, Si - полученные кластеры ^ = 1, 2, ..., к), ц! - центры масс векторов xj е Si. В качестве отклонения использовалось описанное в п.3.1 расстояние Хэмминга.

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

Проверка работоспособности программы осуществлялась на различных наборах сгенерированных данных. Например, на данных, сгенерированных на основе 3 последовательностей (Рис.1).

Рис.1. Результат работы программы для данных, сгенерированных из 3 исходных последовательностей

Более ясную картину можно увидеть, если испытать алгоритм на данных, полученных от 6 исходных последовательностей. По результатам работы программы (Рис.2) видно, что при количестве кластеров, меньшем 6, некоторые последовательности объединяются и создают большие кластеры.

Starting k-means-н- for 3 clusters..-

Find optimal cluster count: 3

Count of elements: [ 2471. 2540. 2551,.]

Starting k-means++ for 3 clusters...

3 clusters is not optimal.

Count of elements: [ 459. 2050. 465.] Starting k-means++ for 4 clusters,..

4 clusters is not optimal.

Count of elements: [ 459. 1431. 547. 537.] Starting k-means++ for 5 clusters...

5 clusters is not optimal.

Count of elements: [ 544. 1494. 104. 471. 361.] Starting k-means++ for 6 clusters... Find optimal cluster count: 6

Count of elements: [ 470. 547. 499. 464. 45S. 536.]

Рис. 1 Результат работы программы для данных, сгенерированных из 6 исходных последовательностей

3.3 Поиск центров кластеров с помощью Silhouette plots

Большинство существующих библиотек работают с численными массивами данных, а не со строковыми. Так как для сравнения строк используются качественные, а не количественные метрики, появилась необходимость в правильной интерпретации строки в числовые данные. Для решения этой задачи использовался следующий способ:

- каждый символ представлялся в двоичном виде: А - 00, G - 01, Т - 10, С - 11. В итоге получался массив, с длинной, в 2 раза превышающей длину строки, состоящий из последовательности нулей и единиц. Полученные данные можно использовать на существующих алгоритмах, которые используют количественные метрики для анализа данных - например, Евклидово расстояние.

Реализованный с помощью расстояний Хэмминга алгоритм в качестве выходных данных выдаёт размеры кластеров для сравнения и массив, содержащий конечный номер кластера для каждой последовательности. Для более наглядного отображения результатов использовался алгоритм k-means из библиотеки scikit-leam и silhouette plots [Scikit leam [электронный ресурс]. URL: http://scikit-learn.org] для визуализации кластеров. График, получаемый в результате работы алгоритма, позволяет оценить размеры кластеров и silhouette coefficient, который представляет собой близость каждой точки в одном кластере к точкам соседнего кластера.

Рис.3 Silhouette plot для 3 кластеров при 3 исходных аллелях

Рис.4 Silhouette plot для 6 кластеров при 3 исходных аллелях

Как и в предыдущем пункте, программа запускалась для нескольких файлах, полученных с помощью генератора последовательностей. Результат работы программы для данных, сгенерированных из 3 исходных последовательностей, представлен на Рис.3 и Рис.4. Как можно видеть на Рис.4, значение silhouette coefficient становится отрицательным, что является показателем того, что кластер является «лишним» и оптимальное количество кластеров должно быть меньшим.

При обработке данных, сгенерированных из 6 исходных последовательностей, дело обстоит иначе. В случае попытки разбиения данных на 3 кластера, мы получаем неравномерное распределение данных по кластерам (Рис.5). А в случае кластеризации с 6 центрами (Рис.6) отчётливо видно, что данные распределились по кластерам равномерно.

Рис.5 Silhouette plot для 3 кластеров при 6 исходных аллелях

The silhouette plot for the various clusters.

0.1 0.0 0.2 0.4 0.6 0.8 1.0

The silhouette coefficient values

Рис.6 Silhouette plot для 6 кластеров при 6 исходных аллелях

4 Заключение

Кластеризация символьных последовательностей является обширной и сложной задачей кластерного анализа. Текстовые данные имеют множество качественных признаков, для которых необходимо разрабатывать собственные способы формализации данных. Поэтому кластеризация символьных последовательностей сильно зависит от индивидуальных характеристик данных. В данной работе был описан кластерный анализ специфических текстовых данных -последовательностей генов. Они имеют несколько особенностей - свой алфавит, состоящий из 4 символов (A, G, T, C) и фиксированную длину строки в каждом файле. Также о данных известно то, что они с некоторыми ошибками сгенерированы из нескольких исходных последовательностей (от 3 до 6). Целью кластерного анализа являлось восстановление исходных последовательностей на основе имеющихся данных.

Программы, разработанные для решения этой проблемы позволяют определить наиболее подходящее число кластеров (то есть, количество исходных последовательностей) и центры кластеров, полученные в результате анализа (усреднённые значения для каждого кластера, которые и являются исходными последовательностями). Точность полученных результатов составляет 100%. Время выполнения кластерного анализа для каждого количества кластеров составляет 3-5с. Таким образом, данный алгоритм является быстрым и точным решением задачи кластеризации последовательностей с неизвестным количеством кластеров.

Список литературы

Jain A., Murty M., Flynn P. 1999. Data Clustering: A Review, volume 31. ACM Computing Surveys.

National Communications System Technology & Standards Division. 1996. Glossary of Telecommunication Terms

Мандель И. Д. Кластерный анализ. — М.: Финансы и Статистика, 1988. 176 с.

Scikit learn [Электронный ресурс]. URL: http ://scikit-learn. org

MachineLearning.ru [Электронный ресурс]. URL: http://www.machinelearning.ru