Обмен технологиями

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

---

5. Оценка качества кластеризации

Кластерный анализ заключается в разложении набора данных на подмножества, каждое подмножество называется кластером, а совокупность всех подмножеств называется кластером набора объектов. Хороший алгоритм кластеризации должен создавать кластеры высокого качества и кластеры высокого качества, то есть общее сходство внутри кластеров является самым высоким, а общее сходство между кластерами — самым низким.Учитывая, что многие алгоритмы кластеризации включают$к$-Алгоритм усреднения, алгоритм DBSCAN и т. д. требуют от пользователя заранее указать количество кластеров в кластере.$к$, поэтому простой метод оценки k будет обсуждаться ниже.

(1) Оценка количества кластеров

Многие алгоритмы кластеризации, такие как $к$-Алгоритмы усреднения, даже алгоритмы DIANA и т. д., должны заранее указывать количество кластеров.$к$,и$к$Значение будет сильно влиять на качество кластеризации. Однако количество кластеров необходимо определить заранее.$к$ Непростая задача. Сначала мы можем рассмотреть два крайних случая.
(1) Поместите весь набор данных$С$рассматриваться как кластер, т.е. $к=1$, это кажется простым и удобным, но результаты такого кластерного анализа не имеют никакой ценности.
(2) Поместите набор данных$С$Каждый объект рассматривается как кластер, т. е. пусть $к=|С|=н$ , что обеспечивает наиболее детальную кластеризацию. Поэтому внутрикластерных различий в каждом кластере нет, а внутрикластерное сходство достигает наивысшего уровня.Но этот вид кластеризации нельзя использовать для$С$предоставить любую информацию о$С$общее описание.
Видно, что количество кластеров$к$должен, по крайней мере, удовлетворить $2\le к\le н-1$, но количество кластеров$к$Вопрос о том, какое именно значение является наиболее подходящим, остается неясным.
Обычно считается,$к$Значение можно оценить по форме и масштабу распределения набора данных, а также по разрешению кластеризации, требуемому пользователем, и у ученых есть множество различных методов оценки, таких как метод локтя, метод перекрестной проверки и теория информации. основанные методы и т. д.
Простой и часто используемый$к$Метод эмпирической оценки стоимости предполагает, что для тех, у кого$н$Набор данных объектов, количество кластеров, в которые он кластеризован.$к$Выбирать $\begin{array}{r}\sqrt{\frac{н}{2}}\end{array}$ Это уместно.В настоящее время при среднем ожидании каждый кластер имеет примерно$\sqrt{2н}$ объекты.На этом основании некоторые предложили дополнительные ограничения, то есть количество кластеров$к<\sqrt{н}$。
Например, предположим$н=8$, то количество кластеров $к=2$ подходит, и в среднем на кластер приходится 4 точки, а по дополнительной эмпирической формуле$к<2.83$ .Используя эти две информации о количестве кластеров$к$Эмпирическая формула как бы поясняется с одной стороны, в примере 10-5. $к=2$ — наиболее подходящее количество кластеров.

(2) Внешняя оценка качества

Если у нас есть хорошая оценка количества кластеров$к$, вы можете использовать один или несколько методов кластеризации, например,$к$ - Алгоритм усреднения, агломеративный иерархический алгоритм или алгоритм DBSCAN выполняет кластерный анализ известных наборов данных и получает множество различных результатов кластеризации. Теперь вопрос в том, какой метод дает лучшие результаты кластеризации, или, другими словами, как сравнить результаты кластеризации, полученные разными методами. Это оценка качества кластеризации.
В настоящее время существует множество методов оценки качества кластеризации, но их обычно можно разделить на две категории, а именно внешнюю (внешнюю) оценку качества и внутреннюю (внутреннюю) оценку качества.
Внешняя оценка качества предполагает, что идеальный кластер уже существует в наборе данных (обычно созданный экспертами), и сравнивает его как обычно используемый эталонный метод с результатами кластеризации определенного алгоритма. Его сравнительная оценка в основном включает энтропию кластеризации и кластеризацию. — это два распространенных метода точности классов.

1. Кластерно-энтропийный метод

Гипотетический набор данных S = {X1, X2, …, Xn} S={X_1,X_2,…,X_n}С={Икс1​,Икс2​,…,Иксн​},и Т = {Т 1 , Т 2 , … , Т м } Т={Т_1,Т_2,…,Т_м}Т={Т1​,Т2​,…,Тм​} — идеальная стандартная кластеризация, предложенная экспертами, и С = {С 1 , С 2 , … , С k } С={С_1,С_2,…,С_k}С={С1​,С2​,…,Ск​} определяется алгоритмом о$С$Кластер , то для кластера${С}_{я}$Относительно базовой кластеризации$Т$Энтропия кластеризации определяется как
$$Э({С}_{я}|Т)=-\sum _{дж=1}^{м}\frac{|{С}_{я}\cap {Т}_{дж}|}{|{С}_{я}|}{\mathrm{вотг}}_2\frac{|{С}_{я}\cap {Т}_{дж}|}{|{С}_{я}|}\text{\hspace{1em}(10-20)}$$ и$С$О тестах$Т$Общая энтропия кластеризации определяется как все кластеры${С}_{я}$О тестах$Т$Средневзвешенное значение энтропии кластеризации, т.е.
$$Э(С)=\frac{1}{\sum _{я=1}^{к}|{С}_{я}|}\sum _{я=1}^{к}|{С}_{я}|\times Э({С}_{я}|Т)\text{\hspace{1em}(10-21)}$$ Метод кластерной энтропии предполагает, что$Э(С)$ Чем меньше значение, тем$С$Относительно базового уровня$Т$Чем выше качество кластеризации.
Стоит отметить, что знаменатель первого слагаемого в правой части формулы (10-21)$\begin{array}{r}\sum _{я=1}^{к}|{С}_{я}|\end{array}$ представляет собой сумму количества элементов в каждом кластере и не может использоваться$н$ заменить.Потому что только тогда, когда$С$В случае кластера с разделением знаменатель равен$н$, а знаменатель общих методов кластеризации, таких как кластеризация DBSCAN, может быть меньше, чем$н$。

2. Точность кластеризации

Основная идея оценки точности (прецизионности) кластеризации заключается в использовании наибольшего числа категорий в кластере в качестве метки категории кластера, то есть для кластера${С}_{я}$, если оно существует${Т}_{дж}$делать ∣ C i ∩ T j ∣ = макс ⁡ { ∣ C i ∩ T 1 ∣ , ∣ C i ∩ T 2 ∣ , ⋯ , ∣ C i ∩ T m ∣ } |C_icap T_j|=макс{|C_icap T_1|,|C_icap T_2|,cdots,|C_icap T_m|}∣Ся​∩Тдж​∣=Макс{∣Ся​∩Т1​∣,∣Ся​∩Т2​∣,⋯,∣Ся​∩Тм​∣}, считается, что${С}_{я}$Категория${Т}_{дж}$ .Таким образом, кластер${С}_{я}$О тестах$Т$Точность определяется как
J ( C i ∣ T ) = макс ⁡ { ∣ C i ∩ T 1 ∣ , ∣ C i ∩ T 2 ∣ , ⋯ , ∣ C i ∩ T m ∣ } ∣ C i ∣ (10-22) J(C_i|T)=frac{макс{|C_icap T_1|,|C_icap T_2|,cdots,|C_icap T_m|}}{|C_i|}тег{10-22}Дж.(Ся​∣Т)=∣Ся​∣Макс{∣Ся​∩Т1​∣,∣Ся​∩Т2​∣,⋯,∣Ся​∩Тм​∣}​(10-22) и$С$О тестах$Т$Общая точность определяется для всех кластеров${С}_{я}$О тестах$Т$Средневзвешенное значение точности кластеризации, т.е.
$$Дж.(С)=\frac{1}{\sum _{я=1}^{к}|{С}_{я}|}\sum _{я=1}^{к}|{С}_{я}|\times Дж.({С}_{я}|Т)\text{\hspace{1em}(10-23)}$$ Метод точности кластеризации предполагает, что$Дж.(С)$ Чем больше значение, тем кластеризация$С$Относительно базового уровня$Т$Чем выше качество кластеризации.
Кроме того, как правило$1-Дж.(С)$ называется$С$О тестах$Т$ общий коэффициент ошибок.Следовательно, точность кластеризации$Дж.(С)$ Большая или общая частота ошибок$1-Дж.(С)$ Маленький, он показывает, что алгоритм кластеризации может лучше группировать объекты разных категорий в разные кластеры, то есть точность кластеризации высока.

(3) Внутренняя оценка качества

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

1. Индикатор CH

Индекс CH — это аббревиатура индекса Калински-Харабаша. Он сначала вычисляет сумму квадратов расстояния между каждой точкой кластера и ее центром кластера, чтобы измерить близость внутри класса, затем вычисляет сумму квадратов расстояния; между каждой центральной точкой кластера и центральной точкой набора данных для измерения. Разделение набора данных и отношение разделения к близости - это индекс CH.
настраивать${\overline{Икс}}_{я}$представляет собой кластер$С$центральная точка (среднее),$\overline{Икс}$представляет набор данных$С$центральная точка$г({\overline{Икс}}_{я},\overline{Икс})$ для${\overline{Икс}}_{я}$приезжать$\overline{Икс}$Определенная функция расстояния от , затем кластеризация$С$Компактность среднего кластера определяется как
$$\text{След}(А)=\sum _{я=1}^{к}\sum _{{Икс}_{дж}\in {С}_{я}}г({Икс}_{дж},{\overline{Икс}}_{я}{)}^2\text{\hspace{1em}(10-24)}$$ Следовательно, Trace(A) — это кластер$С$ Сумма квадратов расстояний между центрами кластеров.И кластеризация$С$Степень разделения определяется как
$$\text{След}(Б)=\sum _{я=1}^{к}|{С}_{я}|г({\overline{Икс}}_{я},\overline{Икс}{)}^2\text{\hspace{1em}(10-25)}$$ То есть Trace(B) кластеризуется.$С$Каждая центральная точка кластера$С$Взвешенная сумма квадратных расстояний от центральной точки .
Отсюда, если$\begin{array}{r}Н=\sum _{я=1}^{к}|{С}_{я}|\end{array}$ Тогда показатель CH можно определить как
$${В}_{\text{Ч.}}(к)=\frac{\text{След}(Б)/(к-1)}{\text{След}(А)/(Н-к)}\text{\hspace{1em}(10-26)}$$ Формула (10-26) обычно используется в следующих двух ситуациях:
(1) Оцените, какая кластеризация, полученная с помощью двух алгоритмов, лучше.
Предположим, что для анализа набора данных используются два алгоритма.$С$Был проведен кластерный анализ и два разных кластера (оба содержат$к$кластеры), кластеризация, соответствующая большему значению CH, лучше, поскольку чем больше значение CH, тем больше каждый кластер в кластере находится ближе к самому себе, а кластеры более рассредоточены.
(2) Оценить, какой из двух кластеров с разным количеством кластеров, полученных одним и тем же алгоритмом, лучше.
Предположим, что алгоритм имеет набор данных$С$Был проведен кластерный анализ, и количество кластеров было получено как${к}_1$и${б}_2$ Из двух кластеров результат кластеризации с большим значением CH лучше, что также означает, что количество кластеров, соответствующих этому кластеру, является более подходящим.Следовательно, многократно применяя формулу (10-26), мы также можем получить набор данных$С$Оптимальное количество кластеров для кластеризации.

2. Индикатор Данна

Индикатор Данна использует кластеры${С}_{я}$с кластером${С}_{дж}$минимальное расстояние между ${г}_{с}({С}_{я},{С}_{дж})$ рассчитать разделение между кластерами, используя наибольший диаметр кластера среди всех кластеров макс ⁡ { Φ ( C 1 ) , Φ ( C 2 ) , . . . , Φ ( C k ) } макс{varPhi(C_1), varPhi(C_2),...,varPhi(C_k)}Макс{Φ(С1​),Φ(С2​),...,Φ(Ск​)} Для характеристики тесноты внутри кластера индекс Данна представляет собой минимальное значение отношения между первым и вторым, то есть
VD ( k ) = min ⁡ i ≠ jds ( Ci , C j ) max ⁡ { Φ ( C 1 ) , Φ ( C 2 ) , . . . , Φ ( C k ) } (10-27) V_D(k)=min_{i≠j}frac{d_s(C_i,C_j)}{max{varPhi(C_1), varPhi(C_2),...,varPhi (C_k)}}тег{10-27}ВД​(к)=я=джмин​Макс{Φ(С1​),Φ(С2​),...,Φ(Ск​)}гс​(Ся​,Сдж​)​(10-27) Чем больше значение Данна, тем дальше расстояние между кластерами и тем лучше соответствующая кластеризация.Подобно индексу оценки CH, индекс Данна можно использовать для оценки качества кластеров, полученных разными алгоритмами, а также для оценки того, какие кластеры, полученные одним и тем же алгоритмом с разным количеством кластеров, лучше, то есть можно использовать для поиска$С$оптимальное количество кластеров.

6. Добыча выбросов

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

(1) Обзор сопутствующих вопросов

Слово Outlier обычно переводится как выброс, но также и как аномалия. Однако в различных ситуациях применения существует множество псевдонимов, таких как изолированные точки, аномальные точки, новые точки, точки отклонения, точки исключений, шум, аномальные данные и т. д. В китайской литературе интеллектуальный анализ выбросов имеет схожие термины, такие как интеллектуальный анализ данных аномалий, обнаружение аномальных данных, интеллектуальный анализ данных выбросов, интеллектуальный анализ данных исключений и интеллектуальный анализ редких событий.

1. Генерация выбросов

(1) Данные поступают из-за аномалий, вызванных мошенничеством, вторжением, вспышками заболеваний, необычными экспериментальными результатами и т. д. Например, средний счет за телефон составляет около 200 юаней, но в определенный месяц внезапно увеличивается до нескольких тысяч юаней; чья-то кредитная карта обычно расходует около 5000 юаней в месяц, но в определенный месяц потребление превышает 30 000 юаней и т. д. Такие выбросы обычно представляют интерес для интеллектуального анализа данных и являются одной из ключевых точек применения.
(2) Вызвано внутренними изменениями переменных данных, отражающими естественные характеристики распределения данных, такие как изменение климата, новые модели покупок клиентов, генетические мутации и т. д. Тоже одно из интересных направлений.
(3) Ошибки измерения и сбора данных в основном происходят из-за человеческой ошибки, неисправности измерительного оборудования или присутствия шума. Например, оценка студента -100 по определенному курсу может быть связана с установленным программой по умолчанию значением; зарплата топ-менеджеров компании существенно превышает зарплату рядовых сотрудников. Может показаться, что это выброс, но это так. Разумные данные.

2. Проблема постороннего майнинга

Обычно проблему обнаружения выбросов можно разложить на три подзадачи для описания.
(1) Определить выбросы
Поскольку выбросы тесно связаны с практическими проблемами, четкое определение того, какие данные являются выбросами или аномальными данными, является предпосылкой и основной задачей анализа выбросов. Как правило, необходимо объединить опыт и знания экспертов в предметной области, чтобы обеспечить точный анализ выбросов. . Дайте подходящее описание или определение.
(2) Выбросы в горнодобывающей отрасли
После того, как точки выбросов четко определены, ключевой задачей анализа выбросов является выбор алгоритма, который следует использовать для эффективной идентификации или анализа определенных точек выбросов. Алгоритм анализа выбросов обычно предоставляет пользователям подозрительные данные о выбросах с точки зрения закономерностей, которые могут быть отражены в данных, чтобы привлечь внимание пользователя.
(3) Понять выбросы
Разумное объяснение, понимание и руководство по практическому применению результатов добычи полезных ископаемых являются целями добычи выбросов. Поскольку механизм генерации выбросов неясен, то, действительно ли «выбросы», обнаруженные алгоритмом анализа выбросов, соответствуют фактическому аномальному поведению, не может быть объяснено и объяснено алгоритмом анализа выбросов, но может быть объяснено только алгоритмом анализа выбросов. Эксперты в отрасли или предметной области, которые поймут и объяснят инструкции.

3. Относительность выбросов

Выбросы — это особые данные в наборе данных, которые явно отклоняются от большинства данных, но «очевидно» и «в основном» относительны, то есть, хотя выбросы и различны, они относительны. Таким образом, существует несколько проблем, которые следует учитывать при определении и анализе выбросов.
(1) Глобальные или локальные выбросы
Объект данных может быть выбросом по отношению к своим локальным соседям, но не по отношению ко всему набору данных. Например, ученик ростом 1,9 метра является исключением в первом классе по математике нашей школы, но не среди людей по всей стране, включая профессиональных игроков, таких как Яо Мин.
(2) Количество выбросов
Хотя количество точек-выбросов неизвестно, количество нормальных точек должно значительно превышать количество точек-выбросов. То есть количество точек-выбросов должно составлять меньшую долю в большом наборе данных. Обычно считается, что это число. точек выбросов. Оно должно быть менее 5% или даже менее 1%.
(3) Фактор выброса точки
Вы не можете использовать «да» или «нет», чтобы сообщить, является ли объект выбросом. Вместо этого вы должны использовать степень отклонения объекта, то есть коэффициент выброса (коэффициент выброса) или оценку выброса (оценка выброса). охарактеризовать степень отклонения данных от группы, а затем отфильтровать объекты с факторами выбросов выше определенного порога, предоставить их лицам, принимающим решения, или экспертам предметной области для понимания и объяснения и применить их в практической работе.

(2) Дистанционный метод

1. Основные понятия

Определение 10-11 Существует целое положительное число$к$, объект$Икс$из $к$- Расстояние до ближайшего соседа — это положительное целое число, удовлетворяющее следующим условиям. ${г}_{к}(Икс)$：
(1) за исключением$Икс$Кроме того, существует как минимум$к$объекты$И$удовлетворить $г(Икс,И)\le {г}_{к}(Икс)$。
(2) за исключением$Икс$Кроме того, существует не более $к-1$ объекты$И$удовлетворить $г(Икс,И)<{г}_{к}(Икс)$。
в$г(Икс,И)$ это объект$Икс$и$И$некоторая функция расстояния между ними.

объекта $к$-Чем больше расстояние до ближайшего соседа, тем больше вероятность того, что объект находится далеко от большинства данных, поэтому объект можно$Икс$из $к$- расстояние до ближайшего соседа ${г}_{к}(Икс)$ как его исключительный фактор.

Определение 10-12 делать D ( X , k ) = { Y ∣ d ( X , Y ) ≤ dk ( X ) ∧ Y ≠ X } D(X,k)={Y|d(X,Y)≤d_k(X)клин Y≠X}Д(Икс,к)={И∣г(Икс,И)≤гк​(Икс)∧И=Икс}, то это называется $Д(Икс,к)$ да$Икс$из $к$-Ближайший сосед (домен).

Из определения 10-12 видно, что$Д(Икс,к)$ Да$Икс$как центр, расстояние$Икс$Не превышает ${г}_{к}(Икс)$ Объект$И$ Коллекция состоит из. Стоит обратить на это особое внимание,$Икс$не принадлежит к нему $к$-ближайший сосед, т.е. $Икс\notin Д(Икс,к)$ . В частности,$Икс$из $к$-ближайший сосед $Д(Икс,к)$ Количество содержащихся объектов может значительно превышать$к$,Прямо сейчас $|Д(Икс,к)|\ge к$。

Определение 10-13 Существует целое положительное число$к$, объект$Икс$из $к$- Фактор выброса ближайшего соседа определяется как
$${\text{ИЗ}}_1(Икс,к)=\frac{\sum _{И\in Д(Икс,к)}г(Икс,И)}{|Д(Икс,к)|}\text{\hspace{1em}(10-28)}$$

2. Описание алгоритма

Для данного набора данных и количества расстояний до ближайших соседей$к$, мы можем использовать приведенную выше формулу для расчета$к$-Ближайшие соседние факторы-выбросы и выводите их в порядке от большего к меньшему. Среди них несколько объектов с более крупными выбросами, скорее всего, будут выбросами. Как правило, они должны быть проанализированы и оценены лицами, принимающими решения, или отраслевыми экспертами. , Какие точки действительно являются выбросами.

Алгоритм 10-8 Алгоритм обнаружения выбросов на основе расстояния
Входные данные: набор данных$С$, количество расстояний до ближайших соседей$к$
Выходные данные: нисходящий список предполагаемых точек выбросов и соответствующих факторов выбросов.
（1）ПОВТОРИТЬ
(2) Возьмите$С$необработанный объект в$Икс$
(3) ОК$Икс$из$к$-ближайший сосед$Д(Икс,к)$
(4) Расчет$Икс$из$к$- коэффициент выброса ближайшего соседа${\text{ИЗ}}_1(Икс,к)$
（5）ДО$С$Каждый пункт обработан
(6) Да${\text{ИЗ}}_1(Икс,к)$Сортировать по убыванию и выводить$(Икс,{\text{ИЗ}}_1(Икс,к))$

3. Примеры расчета

Пример 10-12 Двумерный набор данных с 11 точками$С$Оно дается табл. 10-10, пусть$к=2$, используйте расчет квадрата евклидова расстояния ${Икс}_7,{Икс}_{10},{Икс}_{11}$ Коэффициент выброса по отношению ко всем остальным точкам.

развязать: Чтобы интуитивно понять принцип работы алгоритма, будем$С$Объекты данных отображаются на плоскости на рисунке (10-27) ниже.

Ниже вычисляются факторы выбросов указанной точки и других точек соответственно.

(1) Объект расчета${Икс}_7$посторонний фактор
Как видно из рисунка, расстояние${Икс}_7=(6,8)$ Ближайшая точка находится${Икс}_{10}=(5,7)$,и $г({Икс}_7,{Икс}_{10})=1.41$, другие ближайшие точки могут быть ${Икс}_{11}=(5,2)$，${Икс}_9=(3,2)$，${Икс}_8=(2,4)$；
Рассчитано$г({Икс}_7,{Икс}_{11})=6.08$，$г({Икс}_7,{Икс}_9)=6.71$，$г({Икс}_7,{Икс}_8)=5.66$
потому что$к=2$,так ${г}_2({Икс}_7)=5.66$, поэтому согласно определению 10-11 мы имеем D ( X 7 , 2 ) = { X 10 , X 8 } D(X_7,2)={X_{10},X_8}Д(Икс7​,2)={Икс10​,Икс8​}
Согласно формуле (10-28),${Икс}_7$посторонний фактор
$$\begin{array}{rl}{\text{ИЗ}}_1({Икс}_7,2)& =\frac{\sum _{И\in Н({Икс}_7,2)}г({Икс}_7,И)}{|Н({Икс}_7,к)|}=\frac{г({Икс}_7,{Икс}_{10})+г({Икс}_7,{Икс}_8)}{2}\\ & =\frac{1.41+5.66}{2}=3.54\end{array}$$(2) Объект расчета${Икс}_{10}$посторонний фактор ${\text{ИЗ}}_1({Икс}_{10},2)=2.83$

(3) Объект расчета${Икс}_{11}$посторонний фактор ${\text{ИЗ}}_1({Икс}_{11},2)=2.5$

(4) Объект расчета${Икс}_5$посторонний фактор ${\text{ИЗ}}_1({Икс}_5,2)=1$

Аналогичным образом можно рассчитать коэффициенты выбросов остальных объектов, см. следующую таблицу (10-11).

4. Порог выброса фактора

в соответствии с$к$ -Теория ближайшего соседа: чем больше фактор выброса, тем более вероятно, что это выброс. Поэтому необходимо указать порог, чтобы отличать выбросы от нормальных точек. Самый простой метод — указать количество точек выбросов, но этот метод слишком прост и иногда упускает некоторые реальные точки выбросов или приписывает слишком много нормальных точек возможным точкам выбросов, что затрудняет работу экспертов в предметной области или лиц, принимающих решения. Возникают трудности. в понимании и интерпретации выбросов.
(1) Пороговый метод сегментации факторов выбросов сначала упорядочивает факторы выбросов в порядке убывания и в то же время перенумеровывает объекты данных в порядке возрастания в соответствии с факторами выбросов.
(2) На основе фактора выброса${\text{ИЗ}}_1(Икс,к)$ – ордината, а серийный номер фактора выброса – это абсцисса, т. е. (серийный номер,${\text{ИЗ}}_1$значение) отмечаются на плоскости и соединяются, образуя невозрастающую ломаную линию, а точка, в которой ломаная линия пересекает резкий и плавный спад, соответствует коэффициенту выброса в качестве порогового значения. Объекты с коэффициентом выброса меньше. чем или равные этому порогу, являются нормальными объектами, остальные — возможными выбросами.

Пример 10-13 Набор данных для примера 10-12$С$ , его факторы выбросов суммированы в порядке убывания и порядкового номера в Таблице 10-11. Попробуйте найти порог точек выбросов на основе метода порога сегментации факторов выбросов.

развязать: Сначала используйте (серийный номер, ${\text{ИЗ}}_1$ значение) в виде точек на плоскости, отмеченных на плоскости и соединенных полилиниями. Как показано на рисунке 10-28 ниже.

Затем, глядя на рисунок 10-28, мы видим, что ломаная линия слева от четвертой точки (4, 1,27) падает очень круто, а ломаная линия справа падает очень плавно. Поэтому в качестве коэффициента выброса выбран 1,27. порог.потому что${Икс}_7、{Икс}_{10}$ и${Икс}_{11}$ Коэффициенты выбросов составляют 3,54, 2,83 и 2,5 соответственно, и все они превышают 1,27. Таким образом, эти три точки, скорее всего, будут точками-выбросами, а остальные точки — обычными точками.
Снова взглянув на рисунок 10-27, мы увидим, что${Икс}_7、{Икс}_{10}$ и${Икс}_{11}$ действительно, далеко от плотного большинства объектов слева, поэтому относитесь к ним как к набору данных$С$Выбросы разумны.

5. Оценка алгоритма

Самым большим преимуществом метода обнаружения выбросов на основе расстояния является то, что он прост в принципе и удобен в использовании. Его недостатки в основном отражаются в следующих аспектах.
(1) Параметры$к$В отборе отсутствует простой и эффективный метод определения влияния результатов испытаний на параметры.$к$Не существует общепринятого аналитического результата о степени чувствительности.
(2) Временная сложность равна$О(|С{|}^2)$, ему не хватает масштабируемости для крупномасштабных наборов данных.
(3) Из-за использования порогового значения глобального фактора выбросов сложно выявить выбросы в наборах данных с регионами с различной плотностью.

(3) Метод, основанный на относительной плотности

Метод расстояния — это метод глобальной проверки выбросов, но он не может обрабатывать наборы данных в областях с различной плотностью, то есть он не может обнаруживать выбросы в областях локальной плотности. В практических приложениях не все данные распределяются с одной плотностью. Когда набор данных содержит несколько распределений плотности или представляет собой смесь различных подмножеств плотности, глобальные методы обнаружения выбросов, такие как расстояние, обычно не работают должным образом, поскольку то, является ли объект выбросом, зависит не только от его связи с окружающими данными. Расстояние. связано с плотностью в окрестностях.

1. Понятие относительной плотности

С точки зрения плотности окружения выбросы представляют собой объекты в областях с низкой плотностью. Поэтому необходимо ввести понятия локальной плотности окружения и относительной плотности объектов.

Определение 10-14 (1) объект$Икс$из$к$-Локальная плотность (плотность) ближайших соседей определяется как
$$\text{dsty}(Икс,к)=\frac{|Д(Икс,к)|}{\sum _{И\in Д(Икс,к)}г(Икс,И)}\text{\hspace{1em}(10-29)}$$ (2) объект$Икс$из$к$-Локальная относительная плотность ближайшего соседа (относительная плотность)
$$\text{рдсти}(Икс,к)=\frac{\sum _{И\in Д(Икс,к)}\text{dsty}(Икс,к)/|Д(Икс,к)|}{\text{dsty}(Икс,к)}\text{\hspace{1em}(10-30)}$$ в$Д(Икс,к)$ Это объект$Икс$из$к$- ближайший сосед (данный в определении 10-12),$|Д(Икс,к)|$ — количество объектов в коллекции.

2. Описание алгоритма

к $\text{рдсти}(Икс,к)$ как выброс${\text{ИЗ}}_2(Икс,к)$, его расчет разбит на два этапа
(1) По количеству соседей$к$, рассчитать каждый объект$Икс$из$к$- Местная плотность ближайшего соседа $\text{dsty}(Икс,к)$
(2) Расчет$Икс$средняя плотность ближайших соседей и$к$-Местная относительная плотность ближайшего соседа $\text{рдсти}(Икс,к)$
Набор данных состоит из нескольких естественных кластеров. Относительная плотность объектов, близких к центральной точке внутри кластера, близка к 1, тогда как относительная плотность объектов на краю кластера или вне кластера относительно велика. Следовательно, чем больше значение относительной плотности, тем более вероятно, что это выброс.

Алгоритм 10-9 Алгоритм обнаружения выбросов на основе относительной плотности
Входные данные: набор данных$С$, количество ближайших соседей$к$
Выходные данные: нисходящий список предполагаемых точек выбросов и соответствующих факторов выбросов.
（1）ПОВТОРИТЬ
(2) Возьмите$С$необработанный объект в$Икс$
(3) ОК$Икс$из$к$-ближайший сосед$Д(Икс,к)$
(4) Использование$Д(Икс,к)$вычислить$Икс$Плотность$\text{dsty}(Икс,к)$
（5）ДО$С$Каждый пункт обработан
（6）ПОВТОРИТЬ
(7) Возьмите$С$первый объект в$Икс$
(8) ОК$Икс$относительная плотность$\text{рдсти}(Икс,к)$и назначьте его${\text{ИЗ}}_2(Икс,к)$
（9）ДО$С$Все объекты в обработаны
(10) Правый${\text{ИЗ}}_2(Икс,к)$Сортировать по убыванию и выводить$(Икс,{\text{ИЗ}}_2(Икс,к))$

Пример 10-14 Для двумерного набора данных, приведенного в примере 10-12$С$ (Подробнее см. в Таблице 10-10), поэтому$к=2$, попробуйте вычислить евклидово расстояние ${Икс}_7,{Икс}_{10},{Икс}_{11}$ Коэффициент выброса, основанный на относительной плотности одинаковых объектов.

развязать:потому что$к=2$, поэтому нам нужна локальная плотность 2-х ближайших соседей всех объектов.

(1) Найдите 2-ближайшего соседа каждого объекта данных в таблице 10-11. $Д({Икс}_{я},2)$。
По тому же методу расчета, что и в примере 10-12, можно получить
D (X 1 , 2 ) = {X 2 , X 3 , X 5 } ， D (X 2 , 2 ) = {X 1 , X 6 } ， D (X 3 , 2 ) = {X 1 , X 4 } ， D (X 4 , 2 ) = {X 3 , X 5 } ， D (X 5 , 2 ) = {X 1 , X 4 , X 6 , X 9 } ， D (X 6 , 2 ) = {X 2 , X 5 , X 8 } ， D (X 7 , 2 ) = {X 10 , X 8 } ， D (X 8 , 2 ) = {X 2 , X 6 } ， D (X 9 , 2 ) = { X 5 , X 4 , X 6 } ， D ( X 10 , 2 ) = { X 7 , X 8 } ， D ( X 11 , 2 ) = { X 9 , X 5 } $$begin{aligned} &D(X_1,2)={X_2,X_3,X_5}，D(X_2,2)={X_1,X_6}， D(X_3,2)={X_1,X_4}，\ &D(X_4,2)={X_3,X_5}， D(X_5,2)={X_1,X_4,X_6,X_9}，D(X_6,2)={X_2,X_5,X_8}，\ &D(X_7,2)={X_{10},X_8}， D(X_8,2)={X_2,X_6}， D(X_9,2)={X_5,X_4,X_6}，\ &D(X_{10},2)={X_7,X_8}， D(X_{11},2)={X_9,X_5} end{aligned}$$ ​Д(Икс1​,2)={Икс2​,Икс3​,Икс5​}，Д(Икс2​,2)={Икс1​,Икс6​}，              Д(Икс3​,2)={Икс1​,Икс4​}，Д(Икс4​,2)={Икс3​,Икс5​}，       Д(Икс5​,2)={Икс1​,Икс4​,Икс6​,Икс9​}，Д(Икс6​,2)={Икс2​,Икс5​,Икс8​}，Д(Икс7​,2)={Икс10​,Икс8​}，     Д(Икс8​,2)={Икс2​,Икс6​}，               Д(Икс9​,2)={Икс5​,Икс4​,Икс6​}，Д(Икс10​,2)={Икс7​,Икс8​}，     Д(Икс11​,2)={Икс9​,Икс5​}​

(2) Рассчитайте локальную плотность каждого объекта данных. $\text{dsty}({Икс}_{я},2)$：

① Рассчитать${Икс}_1$Плотность
потому что D ( X 1 , 2 ) = { X 2 , X 3 , X 5 } D(X_1,2)={X_2,X_3,X_5}Д(Икс1​,2)={Икс2​,Икс3​,Икс5​}, поэтому после расчета мы имеем $г({Икс}_1,{Икс}_2)=1$，$г({Икс}_1,{Икс}_3)=1$，$г({Икс}_1,{Икс}_5)=1$；
По формуле (10-29) получаем:
$$\begin{array}{rl}\text{dsty}({Икс}_1,2)& =\frac{|Д({Икс}_1,2)|}{\sum _{И\in Н({Икс}_1,2)}г({Икс}_1,И)}\\ & =\frac{|Н({Икс}_1,2)|}{г({Икс}_1,{Икс}_2)+г({Икс}_1,{Икс}_3)+г({Икс}_1,{Икс}_5)}\\ & =\frac{3}{1+1+1}=1\end{array}$$

② Расчет${Икс}_2$Плотность
потому что D ( X 2 , 2 ) = { X 1 , X 6 } D(X_2,2)={X_1,X_6}Д(Икс2​,2)={Икс1​,Икс6​}, поэтому рассчитанное $г({Икс}_2,{Икс}_1)=1$，$г({Икс}_2,{Икс}_6)=1$；
По формуле (10-29) получаем:
$$\begin{array}{rl}\text{dsty}({Икс}_2,2)& =\frac{|Д({Икс}_2,2)|}{\sum _{И\in Н({Икс}_2,2)}г({Икс}_2,И)}=\frac{2}{1+1}=1\end{array}$$

Локальную плотность других объектов данных можно рассчитать аналогичным образом, см. Таблицу 10-12 ниже.

(3) Рассчитайте каждый объект${Икс}_{я}$относительная плотность $\text{рдсти}({Икс}_{я},2)$и рассматривать это как посторонний фактор ${\text{ИЗ}}_2$。
① Рассчитать${Икс}_1$относительная плотность
Используя значение плотности каждого объекта из таблицы 10-12, согласно формуле относительной плотности (10-30):
$$\begin{array}{rl}\text{рдсти}({Икс}_1,2)& =\frac{\sum _{И\in Н({Икс}_1,2)}\text{dsty}(И,2)/|Н({Икс}_1,2)|}{\text{dsty}({Икс}_1,2)}\\ & =\frac{(1+1+1)/3}{1}=1={\text{ИЗ}}_2({Икс}_1,2)\end{array}$$

② Аналогичный расчет можно получить ${Икс}_2、{Икс}_3、\dots 、{Икс}_{11}$ значение относительной плотности.
например${Икс}_5$Относительная плотность:
$$\begin{array}{rl}\text{рдсти}({Икс}_5,2)& =\frac{\sum _{И\in Н({Икс}_5,2)}\text{dsty}(И,2)/|Н({Икс}_5,2)|}{\text{dsty}({Икс}_5,2)}\\ & =\frac{(1+1+1+0.79)/4}{1}=0.95={\text{ИЗ}}_2({Икс}_5,2)\end{array}$$ Результаты суммированы в таблицах 10-13 ниже.

Пример 10-15 Учитывая набор данных, показанный в Таблице 10-14, используйте евклидово расстояние для$к=2,3,5$, вычислите значение каждой точки$к$- локальная плотность ближайшего соседа,$к$-Локальная относительная плотность ближайшего соседа (коэффициент выброса${\text{ИЗ}}_2$) и на основе$к$-Коэффициент выброса для расстояния до ближайшего соседа${\text{ИЗ}}_1$。

развязать: (1) Чтобы облегчить понимание, можно$С$Относительное положение точек отмечено на двухмерной плоскости (рис. 10-30).

(2) Используйте алгоритмы на основе расстояния и относительной плотности 10-8 и 10-9 соответственно.Рассчитаем каждый объект отдельно$к$- Местная плотность ближайшего соседа$\text{dsty}$、$к$-Локальная относительная плотность ближайшего соседа (коэффициент выброса${\text{ИЗ}}_2$) и на основе$к$-Коэффициент выброса для расстояния до ближайшего соседа${\text{ИЗ}}_1$Результаты суммированы в Таблице 10-15.

(3) Простой анализ
① Как видно из рисунка 10-30,${Икс}_{15}$и${Икс}_{16}$да$С$Есть два очевидных выброса, и методы, основанные на расстоянии и относительной плотности, могут лучше их обнаружить;
② В этом примере два алгоритма имеют$к$не так чувствителен, как ожидалось, возможно, это выброс.${Икс}_{15}$и${Икс}_{16}$Отделение от других объектов очень очевидно.
③Как видно из Таблицы 10-15, независимо от$к$Возьми 2, 3 или 5,${Икс}_1$региона $\text{dsty}$ значения значительно ниже, чем${Икс}_7$региона $\text{dsty}$ значение, которое соответствует плотности площади, показанной на рисунке 10-30.Но значение относительной плотности двух регионов${\text{ИЗ}}_2$ Но очевидной разницы почти нет. Это определяется характером относительной плотности, то есть для равномерно распределенных точек данных относительная плотность основных точек равна 1, независимо от расстояния между точками.

7. Другие методы кластеризации

1. Улучшен алгоритм кластеризации.

  （1）$к$-мод ($к$-режимы) алгоритм предназначен для$к$ -Алгоритм среднего подходит только для ограничения числовых атрибутов и предлагается для достижения быстрой кластеризации дискретных данных.потому что$к$-Модульный алгоритм использует простой метод сопоставления 0-1 для расчета расстояния между двумя значениями атрибута одного и того же дискретного атрибута, что ослабляет разницу между порядковыми значениями атрибута, то есть не может полностью отразить разницу между двумя значениями атрибута. под тем же порядковым атрибутом. Еще есть возможности для совершенствования и совершенствования.
  （2）$к$-опытный образец ($к$-Прототип) алгоритм в сочетании с$к$-Алгоритм усреднения с$к$ -Преимущество модульного алгоритма заключается в том, что он может кластеризовать наборы данных как с дискретными, так и с числовыми атрибутами (так называемыми смешанными атрибутами).Для дискретных атрибутов требуется$к$-Модульный алгоритм расчета объекта$Икс$и$И$расстояние между ${г}_1(Икс,И)$, для числовых атрибутов используйте$к$-Методы в алгоритме усреднения рассчитывают расстояние между объектами ${г}_2(Икс,И)$и, наконец, использовать метод взвешивания, то есть $\alpha {г}_1(Икс,И)+(1-\alpha ){г}_2(Икс,И)$ как объект набора данных$Икс$и$И$расстояние между $г(Икс,И)$,в $\alpha \in [0,1]$ - весовой коэффициент, обычно он может быть$\alpha =0.5$。
(3) Алгоритм BIRCH (сбалансированное итеративное сокращение и кластеризация с использованием иерархий) представляет собой комплексный метод иерархической кластеризации.Он использует функции кластеризации (CF) и дерево функций кластеризации (CF-дерево, аналогичное B-дереву) для суммирования кластеров кластеров.${С}_{я}$,в ${\text{CF}}_{я}=(ни,{\text{ЛС}}_{я},{\text{SS}}_{я})$ это тройка,${н}_{я}$— количество объектов в кластере,${\text{ЛС}}_{я}$да${н}_{я}$линейная сумма компонентов объекта,${\text{SS}}_{я}$да${н}_{я}$Сумма квадратов компонентов объекта.
(4) Алгоритм CURE (кластеризация с использованием представителей) предназначен для$к$ -Еще одно улучшение алгоритма усреднения. Многие алгоритмы кластеризации хороши только для кластеризации сферических кластеров, в то время как некоторые алгоритмы кластеризации более чувствительны к изолированным точкам. Для решения двух вышеуказанных проблем алгоритм CURE изменился.$к$-Алгоритм усреднения использует сумму центра кластера$к$-Алгоритм центральной точки использует один конкретный объект для представления кластера (традиционный метод), но использует несколько репрезентативных объектов в кластере для представления кластера, чтобы он мог адаптироваться к кластеризации несферических кластеров и уменьшить влияние шум при кластеризации.
(5) Алгоритм ROCK (RObust Clustering with linK) — это алгоритм кластеризации, предложенный для наборов данных двоичных или категориальных атрибутов.
(6) Алгоритм ОПТИКА (упорядочение точек для идентификации структуры кластеризации) используется для уменьшения плотности алгоритма DBSCAN.$(\epsilon ,\text{МинПтс})$ чувствительность параметра. Он не создает кластеры результатов явно, но создает расширенный рейтинг кластеров для кластерного анализа (например, координатную диаграмму с достижимым расстоянием в качестве вертикальной оси и порядком вывода точек выборки в качестве горизонтальной оси). Этот рейтинг представляет собой основанную на плотности структуру кластеризации каждой точки выборки.Из этой сортировки мы можем получить по любому параметру плотности$(\epsilon ,\text{МинПтс})$ Результаты кластеризации алгоритма DBSCAN.

2. Другие новые методы кластеризации

Используйте некоторые новые теории или методы для разработки новых методов кластеризации.

(1) Метод кластеризации на основе сетки
Метод на основе сетки распределяет пространство объекта по ограниченному числу ячеек для формирования структуры сетки, а информация о положении точек разделения в каждом измерении сохраняется в массиве. Разделительные линии проходят через все пространство и всю кластеризацию. операции выполняются в этой сетке (т.е. пространстве квантования). Основное преимущество этого метода заключается в том, что скорость его обработки очень высока. Скорость его обработки не зависит от количества объектов данных и связана только с количеством ячеек в каждом измерении пространства количественной оценки. Однако его эффективность находится на уровне. за счет кластеризации результатов. Поскольку алгоритм кластеризации сетки имеет проблему количественного масштаба, мы обычно сначала начинаем поиск кластеров с небольших единиц, затем постепенно увеличиваем размер единиц и повторяем этот процесс до тех пор, пока не будут найдены удовлетворительные кластеры.

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

(3) Метод кластеризации на основе нечеткого множества.
На практике не существует строгого значения атрибуции, к какому кластеру принадлежит большинство объектов. Существует промежуточное значение или неопределенность в их значении атрибуции и форме, которая подходит для мягкого разделения. Поскольку анализ нечеткой кластеризации имеет то преимущество, что описывает последовательность атрибуции выборок и может объективно отражать реальный мир, он стал одной из горячих точек в сегодняшних исследованиях кластерного анализа.
Алгоритм нечеткой кластеризации — это метод обучения без учителя, основанный на нечеткой математической теории и неопределенном методе кластеризации. После того, как нечеткая кластеризация была предложена, она привлекла большое внимание академического сообщества. Нечеткая кластеризация представляет собой большое «семейство» кластеров, и исследования нечеткой кластеризации также очень активны.

(4) Метод кластеризации на основе грубого набора
Грубая кластеризация — это неопределенный метод кластеризации, основанный на грубой теории множеств. С точки зрения связи между грубыми множествами и алгоритмами кластеризации методы грубой кластеризации можно разделить на две категории: грубая кластеризация с сильной связью и грубая кластеризация со слабой связью.
Конечно, новые направления исследований в области кластерного анализа выходят далеко за рамки этих. Например, алгоритмы интеллектуального анализа потоков данных и кластеризации, неопределенные данные и алгоритмы их кластеризации, квантовые вычисления и алгоритмы квантовой генетической кластеризации — все это технологии кластеризации, появившиеся в последние годы. . новейшие темы исследований.

3. Другие методы извлечения выбросов

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

(1) Тип используемой технологии
В основном существуют статистические методы, методы на основе расстояния, методы на основе плотности, методы на основе кластеризации, методы на основе отклонений, методы на основе глубины, методы на основе вейвлет-преобразования, методы на основе графов, методы на основе шаблонов и нейронные сети. методы и т. д.

(2) Использование предшествующих знаний
В зависимости от наличия информации о нормальном или выбросном классе существует три распространенных подхода:
① Неконтролируемый метод обнаружения выбросов, то есть в наборе данных отсутствуют предварительные знания, такие как метки категорий;
② Метод контролируемого обнаружения выбросов, то есть извлечение характеристик выбросов посредством существования обучающего набора, содержащего выбросы и нормальные точки;
③ Метод полуконтролируемого обнаружения выбросов: обучающие данные содержат помеченные нормальные данные, но нет информации об объектах данных выбросов.