[Искусственный интеллект плиты] Машинное обучение 025 — Автоматическая оценка количества кластеров — Алгоритм DBSCAN

машинное обучение искусственный интеллект Python алгоритм

[Искусственный интеллект плиты] Машинное обучение 025 — Автоматическая оценка количества кластеров — Алгоритм DBSCAN

(Библиотеки Python и номера версий, используемые в этой статье: Python 3.6, Numpy 1.14, scikit-learn 0.19, matplotlib 2.2)

в предыдущих статьях[Stove AI] Машинное обучение 024 - Оценка производительности моделей обучения без учителя - Коэффициент силуэтаВ мы определяем функцию общего назначения для поиска наилучшего значения K для алгоритма K-средних.Хотя эта функция эффективна, она не эффективна, что требует очень много времени. Алгоритм DBSCAN — это быстрый и эффективный алгоритм автоматической оценки количества кластеров.


1. Введение в алгоритм DBSCAN

DBSCAN, Пространственная кластеризация приложений с шумом на основе плотности, представляет собой метод кластеризации на основе плотности с шумом. Это очень классический алгоритм кластеризации плотности. Алгоритм K-средних, о котором мы упоминали ранее, применим только к выпуклым наборам выборок. здесь подходит не только для выпуклых выборок, но и для невыпуклых выборок.Похоже, что область его применения намного шире, чем у метода К-средних.

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

DBSCAN основан на наборе окрестностей для описания плотности набора выборок, а параметр (ϵ, MinPts) используется для описания плотности распределения выборки в окрестности. Среди них ϵ описывает пороговое значение расстояния до окрестности выборки, а MinPts описывает порог количества выборок в окрестности, где расстояние до выборки равно ϵ.

DBSCAN聚类思想说明

Вышеприведенное является иллюстрацией идеи кластеризации.На рисунке MinPts=5, то есть параметр ϵ=5.Красные точки — все основные объекты, потому что в окрестности ϵ этих точек есть как минимум 5 выборок, а черные точки - это неосновной объект. Все эти образцы, ориентированные на плотность красного основного объекта, находятся внутри гиперсферы с центром на красном основном объекте, а если не внутри этой гиперсферы, то образцы, ориентированные на плотность, отсутствуют. Основные объекты, соединенные зелеными стрелками на рисунке, составляют последовательности выборок, достижимые по плотности, и все выборки в ϵ-окрестности этих последовательностей выборок, достижимых по плотности, связаны друг с другом по плотности. Набор выборок, связанных с максимальной плотностью, полученной из отношения достижимости плотности, является категорией или кластером нашей окончательной кластеризации.

Итак, как мы можем найти такой набор выборок кластера? Метод, используемый DBSCAN, очень прост: он произвольно выбирает основной объект без категории в качестве начального числа, а затем находит набор образцов, плотность которых может быть достигнута этим основным объектом, который является кластером. Затем продолжайте выбирать другой основной объект без класса, чтобы найти выборку с достижимой плотностью, чтобы получить еще один кластер. Запускайте до тех пор, пока все основные объекты не будут иметь категории.

Преимущества алгоритма DBSCAN:

1. По сравнению с алгоритмом K-средних не требуется вводить количество категорий K.

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

3. Он может находить выбросы при кластеризации и не чувствителен к выбросам в наборе данных.

4. Результаты кластеризации не смещены, а алгоритм К-средних относительно чувствителен к начальному значению.

Конечно, у алгоритма DBSCAN есть и некоторые недостатки, в основном в:

1. Если плотность выборки неравномерна, расстояние между кластерами сильно различается, а качество кластеров плохое, алгоритм DBSCAN не подходит.

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

3. По сравнению с алгоритмами кластеризации, такими как K-средние, настройка параметров немного сложнее.В основном требуется совместная настройка параметров порога расстояния ϵ и порога количества выборок домена MinPts.Различные комбинации параметров оказывают большее влияние на окончательный эффект кластеризации.

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


2. Создайте простую модель DBSCAN

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

# 定义一个DBCSCAN模型，并用数据集训练它
from sklearn.cluster import DBSCAN
model=DBSCAN(eps=0.5,min_samples=5) # 此处的参数是随便指定
model.fit(dataset)

# 使用轮廓系数评估模型的优虐
from sklearn.metrics import silhouette_score
si_score=silhouette_score(dataset,model.labels_)
print('si_score: {:.4f}'.format(si_score))

------------------------- ВХОД --------- ВЫХОД -------------- ------------------

si_score: 0.5134

-------------------------------Заканчивать------------------ --------------------

########################резюме########################## ######

1. Построить модель DBSCAN очень просто, sklearn уже инкапсулировал этот алгоритм, и нам нужно только вызвать его напрямую.

2. При построении модели DBSCAN нужно указать параметр eps и параметр min_samples.Эти параметры нужно оптимизировать позже.Здесь мы их просто указываем вскользь.

#################################################################


3. Оптимизация параметров модели DBSCAN

При построении модели мы случайным образом указывали параметр eps, но это точно не способствует наилучшей производительности модели, нам нужно оптимизировать параметр eps, чтобы получить оптимальное значение eps. Вот код:

# 在定义DBSCAN时，往往我们很难知道最优的eps参数，
# 故而可以通过遍历得到最优值
def get_optimal_eps(dataset,eps_list):
    '''get optimal eps param for DBSCAN 
       params: 
            dataset: the whole dataset.
            eps_list: must be in np.linspace() format or list format.
        return:
            three values：optimal eps value, 
                optimal model with optimal eps
                silhouette_scores of all candidate eps.
        '''
    scores=[]
    models=[]
    for eps in eps_list:
        model=DBSCAN(eps=eps,min_samples=5).fit(dataset)
        labels=model.labels_
        label_num=len(np.unique(labels))
        if label_num>1: # 需要判断label种类，因为如果只有一个label，silhouette_score报错
            scores.append(silhouette_score(dataset,model.labels_))
            models.append(model)
        else:
            scores.append(0)
            models.append(None)
    optimal_id=scores.index(max(scores))
    return eps_list[optimal_id],models[optimal_id],scores

optimal_eps, optimal_model,scores=get_optimal_eps(dataset,np.linspace(0.3, 1.7, num=15))
print('optimal eps: {:.4f}, \ncandidate eps: {}, \nscores: {}'.format(optimal_eps,np.linspace(0.3,1.7,15),scores))

------------------------- ВХОД --------- ВЫХОД -------------- ------------------

[0.3 0.4 0.5 0.6 0.7 0.8 0.9 1. 1.1 1.2 1.3 1.4 1.5 1.6 1.7]
optimal eps: 0.8000,
candidate eps: [0.3 0.4 0.5 0.6 0.7 0.8 0.9 1. 1.1 1.2 1.3 1.4 1.5 1.6 1.7],
scores: [0.12865164017329436, 0.3593618148137507, 0.5134143263329637, 0.616532168834258, 0.6321600450689241, 0.6366395861050828, 0.5141678956134529, 0.5629298661962946, 0.5629298661962946, 0.5629298661962946, 0, 0, 0, 0, 0]

-------------------------------Заканчивать------------------ --------------------

Поскольку в модели DBSCAN есть образцы керна и аномальные образцы, нам нужно использовать эту модель для поиска образцов керна и аномальных образцов. Вот код:

# 上述函数得到了最佳eps参数和该最佳参数下的最佳模型，我们可以从该最佳模型中得到一些属性
labels=optimal_model.labels_
label_num=len(np.unique(labels))
# 但是有标记为-1的样本
# 这些样本是没有分配集群的样本，被认为是异常点。
if -1 in labels:
    label_num-=1 # 需要减一个类别，减去异常点
print('clusters num: ',label_num) # 最佳模型划分的簇群数量，


# print(labels)
# DBSCAN模型中可以得到核心样本的数据点坐标
# 首先获取核心样本的坐标索引
core_index=optimal_model.core_sample_indices_
# print(core_index)
mask_core=np.zeros(labels.shape,dtype=np.bool)
mask_core[model.core_sample_indices_]=True
# print(mask_core)

Этот фрагмент кода сначала определяет, что DBSCAN делит набор данных на несколько кластеров в соответствии с типом меток.Из-за наличия аномальных выборок необходимо вычесть категорию. Затем используйте модель, чтобы получить индекс координат образцов керна, и после печати вы сможете увидеть конкретные координаты этих образцов.

DBSCAN算法对数据集进行聚类后的效果图

На приведенном выше рисунке вы можете видеть, что последней категорией является класс_-1, который представляет собой местонахождение аномального образца, представленного на рисунке небольшой вертикальной линией. Эти аномальные выборки не принадлежат ни к какому другому кластеру, поэтому можно видеть, что DBSCAN может автоматически избежать интерференции точек выборки с аномальными выбросами, что также является важным преимуществом алгоритма.

########################резюме########################## ######

1. Здесь я определяю функцию для оптимизации параметров EPS.Это более общая функция настройки параметров, которую можно использовать для выбора параметров любого другого набора данных.

2. Разница между моделью DBSCAN и моделью K-средних заключается в том, что полученная модель содержит основные точки выборки, неосновные выборки и аномальные выборки.Аномальные точки не принадлежат ни к какому кластеру, поэтому такие данные Одним из его преимуществ является то, что алгоритм может избежать вмешательства выбросов.

#################################################################


Примечание. Эта часть кода была загружена в (мой гитхаб), добро пожаловать на скачивание.

Использованная литература:

1. Классические примеры машинного обучения Python, Пратик Джоши, перевод Тао Цзюньцзе и Чена Сяоли.

Категории