Добрый день, уважаемые слушатели. Сегодня мы с вами рассмотрим еще один вид кластеризации. Задачу, в основном, мы уже рассмотрели на предыдущих занятиях, а именно мягкую кластеризацию. Напомню вкратце, о чем идет речь. Сама по себе кластеризация, это задача группировки данных. У нас имеются объекты, объекты измерены по каким-то характеристикам, и наша задача получить групп этих объектов с более-менее близкими характеристиками, каким-либо образом. Теоретически это можно было бы сделать вручную, однако, таких объектов обычно много, переменных или самих характеристик, тоже довольно много, поэтому имеет смысл принять какие-то алгоритмы. В классической постановке, когда мы группируем наши объекты, мы считаем, что каждый объект может принадлежать одному и только одному кластеру, который к нему наиболее близок в смысле некоторого расстояния или меры сходства. В данном случае мы можем считать, что каждому кластеру принадлежит одновременно несколько объектов и наоборот, каждый объект может принадлежать нескольким кластерам сразу. То есть по сути, задача, рассчитать некую вероятность принадлежности каждого объекта каждому кластеру. Что в принципе это может нам дать? Такая мягкая постановка позволяет, на самом деле, задачу исходную решить более качественно. Почему? Потому что каждый кластер, если он жесткий, скорее всего содержит какие-то пограничные объекты, и сами эти пограничные объекты, по-хорошему, нельзя толком относить только в одно место. Соответственно, когда мы относим только в один кластер, такой вот пограничный объект, скорее всего, мы обедняем информацию у другого кластера, который с этим соприкасается. В целом пограничные объекты сами по себе тоже представляют собой отдельный интерес, то есть, даже если мы не будем их относить куда-любо, нам хотелось бы знать, какие объекты из всего что у нас есть могут одновременно принадлежать сразу нескольким сегментам или кластерам. То есть сам список этих объектов — это тоже ценная информация, возможно требующая отдельного изучения. Ну вот с такой постановкой разобрались. Теперь давайте разберемся с алгоритмами. Алгоритмов, на самом деле, довольно много, и по большей части эти алгоритмы основаны на обычных жестких алгоритмах. Наиболее, соответственно, известные из которых, это, конечно, метод под названием «k-means» или «k-средних». Соответственно, у него есть более продвинутая версия, называется «fuzzy k-means», то есть нечеткий k-means, и как раз именно эта версия производит вероятности принадлежности объектов к сегментам. Отличия в исходном алгоритме фактически нет, то есть точно также мы берем список наших объектов, берем список эталонов и дальше рассчитываем между каждым объектом и каждым эталоном расстояние. Соответственно, дальше на основании этого расстояния, чем оно меньше, мы можем посчитать вероятностную метрику, которая, как раз, скажет, от 0 до 1, в зависимости от того насколько расстояние велико или мало, куда отнести данный конкретный объект. Значит, в целом эта модификация на производительность алгоритма фактически не отражается. Поэтому его сложность вычислительная все такая же: о-малое от примерно n-в-степени-полтора. То есть, такая квазилинейная зависимость. Поэтому, в принципе, этот алгоритм точно так же имеет смысл, как и в предыдущем случае, случае обычной жесткой задачи, использовать как базу для наших вычислений. Есть и более интересные подходы. Много есть отечественных разработок, например, алгоритм FOREL. Но сегодня хотелось бы поговорить не об этом, а, наверное, об алгоритме, который является сейчас одним из таких стандартов дэ-факто, для того чтобы производить кластеризацию вообще, мягкую в том числе. И по сути говоря, его принцип тоже можно считать одним из принципов мягкой кластеризации как таковой. Итак, это алгоритм, который называется DBSCAN. Сразу забегу вперед. Его основное преимущество в том, что он работает действительно быстро и позволяет обрабатывать BigData. Если мы хотим обрабатывать BigData k-means, то по сути, нужна какая-то инфраструктура Hadoop /MapReduce, для того чтобы распараллелить его и посчитать от каких-нибудь миллионов объектов эти сегменты. В случае же DBSCAN такие ухищрения фактически нам не нужны. Более того, сам по себе k-means исходный и нечеткий тоже, он ищет кластеры в форме неких сфер. Соответственно, если наша задача на эти сферы никак не распадается, то мы в эти сферы запихиваем цепочки, спирали и так далее, что естественно неверно. Вот в случае DBSCAN, он позволяет обнаруживать и цепочечные кластере тоже. Поэтому, конечно, за счет такой точности, быстроты он сейчас является одним из самых популярных методов который вообще применяется для кластеризации. Он реализован в RapidMiner, есть реализация собственно в «Питоне», есть реализация в «R» и так далее. То есть, сам по себе DBSCAN является уже почти таким же распространённым, как и исходный k-means. Сам по себе этот алгоритм более новый, всего-то ему, с 96 года, соответственно, 20 лет, больше немного, в отличие от k-means которому уже лет 60–70 примерно.