0:00
[МУЗЫКА]
[МУЗЫКА] [МУЗЫКА]
Рассмотрим относительные метрики, предназначенные для оценки качества четкой
кластеризации, то есть той, в которой не допускается пересечение кластеров.
Обратимся непосредственно к формуле.
За n мы обозначим количество точек в наборе данных,
а k — это количество кластеров.
Также нам надо будет вычислить следы матрицы B и W, соответственно,
где матрица B — это матрица дисперсии между кластерами,
а W — это матрица дисперсии внутри кластера.
За z и zi мы обозначили среднее значение для всего
набора и для кластера ci, соответственно.
Четкие кластеры имеют большую дисперсию между кластерами, а именно матрицу
дисперсии B, и небольшую дисперсию внутри класса, то есть матрицу дисперсии W.
Чем больше отношение данного индекса, тем лучше разделение данных.
Чтобы определить оптимальное количество кластеров,
необходимо максимизировать данный индекс относительно количества кластеров.
Оптимальное количество кластеров — это решение с самым высоким значением индекса
Калински — Харабаша.
Критерий Калински — Харабаша также очень хорошо подходит для алгоритма k-means.
Оценим оптимальное количество кластеров, используя индекс Калински — Харабаша.
Рассмотрим набор данных «Ирисы Фишера», а именно на графике в
нижнем левом углу полностью отделенный от двух других кластеров кластер № 1.
Он содержит цветы с наименьшей длиной и шириной чашелистиков.
Кластер 3, в свою очередь,
находится в верхнем правом углу и содержит цветы с наибольшей длиной и шириной.
А кластер 2 находится в центре между этими двумя обособленными кластерами.
На графике зависимости индекса Калински — Харабаша от количества кластеров видно,
что самое высокое значение индекса происходит при трёх кластерах,
что указывает на то, что оптимальное количество равно 3.
Индекс Дэвиса — Боулдина представляет собой индекс достоверности,
который не зависит от количества кластеров и алгоритмов кластеризации.
Чтобы определить данный индекс,
нам нужно определить меру дисперсии и сходство кластеров измерения.
В данной формуле за k обозначено количество кластеров,
ci — это центр кластера ci большое, Σi — это среднее расстояние всех
элементов внутри кластера ci до непосредственно его центра.
Расстояние между центрами мы обозначаем d(ci,cj).
Таким образом, подразумевается,
что кластеры в структуре изначально отличаются друг от друга, то алгоритмы
кластеризации с наименьшим индексом Дэвиса — Боулдина считаются лучшими.
Оценим оптимальное количество кластеров,
используя критерии оценки Дэвиса — Боулдина.
На графике показаны три кластера.
Первый кластер находится в левом нижнем углу.
Второй кластер находится в центре графика,
а третий кластер находится в верхнем правом углу.
Если посмотреть на график зависимости индекса Дэвиса —
Боулдина от количества кластеров, то он укажет на то,
что оптимальное количество кластеров равно трем.
Индекс Данна предназначен для компактных и хорошо разделимых кластеров.
d(i,j) — это расстояние между кластерами i и j.
d(k) — это внутрикластерное расстояние для k-го кластера.
Данный индекс необходимо максимизировать,
если набор данных содержит компактные и хорошо разделенные кластеры,
тогда диаметр кластеров будет небольшим, а расстояние между кластерами будет велико.
Таким образом, индекс Данна должен быть максимальным.
Отметим, что данный индекс очень чувствителен к выбросам и шуму данных.
Индекс силуэта показывает, насколько хорошо кластеризуются
данные и оценивает среднее расстояние между кластерами.
Смысл этой величины можно определить как меру несхожести отдельного
элемента с элементами ближайшего кластера.
В данной формуле i-тое наблюдение принадлежит к aj кластеру.
a(i) — это среднее расстояние от i-того объекта до других объектов
из того же кластера к a(j), а b(i) — это расстояние от
i-того наблюдения до элементов другого ближайшего класса.
Таким образом, индекс силуэта, близкий к 1, означает,
что мы правильно определили i-тое наблюдение в кластер.
Если же данный индекс равен значению −1, то это означает, что мы ошибочно
назначили это наблюдение тому или иному кластеру, а значение индекса силуэта,
равное 0, означает, что данное наблюдение находится на границе двух кластеров.
Для того чтобы индекс силуэта был близок к 1, необходимо,
чтобы a(i) было сильно меньше b(i).
Поскольку a(i) является мерой того, как i-тое наблюдение относится к
собственному кластеру, небольшое значение означает, что оно хорошо сопоставимо.
Соответственно, большое значение b(i) подразумевает,
что оно плохо сопоставляется с элементами соседнего кластера.
Анализ графика силуэта более предпочтителен при количестве кластеров,
равном 2 и 4.
Кроме того, из толщины графика силуэта можно характеризовать и размер кластера.
График силуэта для кластера 0, тогда количество кластеров два больше по
размеру благодаря группировке трёх подкластеров в один большой кластер.
Однако, когда кластеров у нас четыре, все графики имеют более-менее
одинаковую толщину и, следовательно, имеют одинаковые размеры.
Для анализа графика силуэта следует учитывать следующие моменты.
Во-первых, среднее значение индекса силуэта должно быть как можно ближе к 1.
Также график каждого кластера должен быть как можно больше над средним значением,
и любая область, находящаяся ниже среднего значения, нежелательна.
Также ширина участка должна быть как можно более однородной.
Опишем наиболее известные оценки качества нечеткой кластеризации,
то есть такой кластеризации,
где объект может принадлежать потенциально нескольким кластерам.
Цель состоит в том, чтобы искать схемы кластеризации, где большая часть векторов
набора данных характеризуется высокой степенью членства в одном кластере.
Нечеткая кластеризация определяется матрицей u, где каждый элемент uij
означает, что вектор xi принадлежит кластеру j.
Наиболее популярным критерием оценки
нечеткой кластеризации является коэффициент разбиения.
В данной формуле элемент uij² принадлежит промежутку от 0 до 1,
и a — некоторая степень принадлежности (i) объекта (j) кластеру.
За N обозначено число объектов, а n с индексом c — это число кластеров.
Значение индекса,
принадлежащее к данному к отрезку: чем ближе к 1, тем лучше кластеризация.
Значение же, близкое к левой границе промежутка,
указывает на отсутствие какой-либо структуры в данном наборе данных,
либо неспособность нашего алгоритма извлечь данную структуру.
Энтропия известна как численное выражение упорядоченности системы.
Энтропия разбиения достигает минимума при наибольшей упорядоченности
в нашей системе, то есть чем больше степень принадлежности одному кластеру,
тем меньше значение энтропии и тем более качественно выполнена наша кластеризация.
Энтропия принадлежит данному промежутку.
И чем ближе данное значение к 0, тем лучше наша кластеризация.
Как и в предыдущем случае, значение индекса, близкое к верхней границе,
указывает на то, что либо наш алгоритм не справился с данной кластеризацией,
либо данный набор данных не имеет какой-либо структуры.
Главной целью использования коэффициента разбиения и энтропии разбиения является
отыскание наиболее приемлемого числа кластеров в нечеткой кластеризации.
Блеканов Иван Станиславовичдоцент
Севрюков Сергей Юрьевичстарший преподаватель
Просолупов Евгений Викторовичк.ф.-м.н., доцент
Коротков Павел Алексеевичстарший преподаватель
Мишенин Алексей Николаевичстарший преподаватель
Утешев Алексей Юрьевичпрофессор
Вольф Дмитрий Александровичассистент
Малютин Евгений Алексеевичассистент
Камалов Михаил ВалерьевичАспирант
