Краткое изложение алгоритмов кластеризации, связанных с электрической нагрузкой (1)

искусственный интеллект алгоритм Нейронные сети Bootstrap

Краткое изложение алгоритмов кластеризации

1. Классификация методов кластеризации

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

  • 1.1 Алгоритм кластеризации на основе разделов
    Алгоритм кластеризации на основе разделов оптимизирует целевую функцию путем построения итеративного процесса.Когда оптимизация достигает минимального или минимального значения целевой функции, могут быть получены некоторые непересекающиеся подмножества набора данных.Принято считать, что каждое подмножество, полученное при на этот раз набор представляет собой кластер.
    Большинство алгоритмов кластеризации на основе разделов очень эффективны, но требуют заранее определенного количества кластеров, которое трудно определить до кластерного анализа. Алгоритм k-средних [5] и алгоритм FCM (FuzzyC Means) являются двумя наиболее известными алгоритмами этого типа. Кроме того, к этому типу алгоритмов также относятся k-центральный алгоритм PAM (PartitioningAround Medoid) и CLARA (Clustering LARgeApplications), k-модульный алгоритм (кластеризация категориальных данных) и k-прототипный алгоритм (кластеризация смешанных данных) [25]. Преимущество алгоритма кластеризации на основе разделов заключается в простоте реализации и высокой скорости кластеризации. Его временная сложность имеет линейную зависимость от количества точек данных n, размерности данных d и заданного количества кластеров k. Недостатком является то, что оптимизационная функция является NP-трудной задачей, поиск минимального значения требует больших временных затрат, легко попасть в локальное минимальное значение.
  • 1.2 Алгоритм иерархической кластеризации
    Метод иерархической кластеризации использует в качестве входных данных матрицу расстояний, а после кластеризации
    Диаграмма иерархии кластеризации ситуации. Алгоритмы иерархической кластеризации обычно делятся на две категории. Первый — это алгоритм агломеративной иерархической кластеризации, который сначала рассматривает каждую точку данных как кластер, а затем восходящим образом, непрерывно выбирая операцию слияния пар ближайших соседних кластеров, он может, наконец, построить иерархическое дерево, представляющее создается кластерная структура набора данных. Второй — алгоритм разделенной иерархической кластеризации, который сначала рассматривает все точки данных как кластер, а затем выполняет операцию разделения, непрерывно выбирая самый свободный кластер сверху вниз, и, наконец, может построить иерархическое дерево, представляющее структуру кластеризации набор данных генерируется. Хотя временные затраты методов иерархической кластеризации выше, чем у методов секционированной кластеризации, в большинстве алгоритмов иерархической кластеризации не требуется устанавливать параметр, который трудно определить заранее, и такие методы могут получить многоуровневую кластеризацию. структура, которая является самым большим преимуществом, отличным от метода кластеризации разделов.
  • 1.3 Алгоритм кластеризации на основе плотности
    Алгоритмы кластеризации на основе плотности пытаются разделить области с высокой плотностью на разреженные области, чтобы найти очевидные кластеры и выбросы, и в основном используются для кластеризации пространственных данных. Представителем является алгоритм DBSCAN.
  • 1.4 Алгоритм кластеризации на основе сетки
    Алгоритм кластеризации на основе сетки — это метод кластеризации на основе сетки с несколькими разрешениями. Сначала он делит пространство распределения набора данных на несколько регулярных сеток (таких как гиперпрямоугольные ячейки) или гибкие сетки (такие как многогранники произвольной формы), а затем получает очевидную кластеризацию. Преимущество этого типа алгоритма заключается в том, что время обработки не зависит от количества точек данных, независимо от порядка ввода данных и может обрабатывать данные любого типа. Недостаток в том, что Время обработки связано с количеством ячеек, разделенных в каждом измерении, что в определенной степени снижает качество и точность кластеризации. Типичным алгоритмом является алгоритм STING (STAtistical INformation Grid).
  • 1.5 Алгоритмы кластеризации на основе моделей
    Алгоритмы кластеризации на основе моделей полагаются на некоторые статистические модели для получения информации о распределении кластеризации набора данных. Этот метод предполагает, что набор данных генерируется совместным действием конечного числа моделей распределения вероятностей. Среди этих методов наиболее широко используется смешанная модель многомерного распределения Гаусса. Среди них алгоритм COBWEB представляет собой распространенный и простой метод поэтапной кластеризации концепций, который использует форму дерева классификации для выражения результатов иерархической кластеризации.
  • 1.6 Алгоритмы кластеризации на основе графов
    При использовании метода кластеризации графов для кластерного анализа первым шагом является создание графа, подходящего для конкретной задачи. Узлы графика представляют собой базовые единицы анализируемых данных, а ребра графа представляют меру сходства (или меру несходства) между базовыми единицами данных. Обычно между данными каждой базовой единицы существует метрическое представление, чтобы можно было поддерживать характеристики локального распределения набора данных. Метод кластеризации графа использует функцию локального соединения набора данных в качестве основного источника информации для кластеризации, поэтому легко иметь дело с характеристиками локальных данных. Алгоритм-хамелеон, предложенный Кариписом и др., также можно рассматривать как алгоритм кластеризации графов.
  • 1.7 Другие алгоритмы кластеризации
    Методы квантовой кластеризации заимствуют квантовую теорию, сначала создают функцию вероятности на основе пространственного масштаба из исходных данных, затем используют некоторые аналитические операции для получения потенциальной функции, которая определяет центр кластера в соответствии с минимальным значением, и, наконец, корректируют параметр масштаба с помощью настройка параметра масштаба для поиска кластерной структуры.
    Метод спектральной кластеризации вычисляет собственные значения через матрицу сходства исходных данных, а затем может найти очевидные области кластеризации. Многие алгоритмы спектральной кластеризации просты в реализации и превосходят традиционные алгоритмы кластеризации, такие как алгоритм k-средних, и они также были успешно реализованы во многих приложениях. Алгоритм Ши-Малик для разбиения изображения разработан на основе метода спектральной кластеризации.
    Метод кластеризации на основе детализации — это новое направление исследований в области кластеризации, разработанное с точки зрения детализации информации. В настоящее время исследования этого метода кластеризации не очень развиты, особенно исследования семантики гранулярных вычислений все еще относительно невелики.
    Вероятностный метод кластеризации графов является популярным методом кластеризации в последние годы. Наиболее известным методом кластеризации вероятностных графов является алгоритм кластеризации AP (Affinity Propagation), опубликованный в журнале Science в 2007 году.
    Алгоритм кластеризации синхронизации — алгоритм SynC (кластеризация синхронизации). Алгоритм может не только обнаруживать свою внутреннюю структуру с помощью процесса динамической синхронизации, не зная какого-либо распределения набора данных, и может хорошо обрабатывать выбросы, но также использовать принцип минимальной длины описания для достижения автоматической кластеризации.
    Поскольку алгоритмы на основе сетки в основном используются для работы с пространственными данными, а кривая мощности представляет собой временной ряд, в этой статье основное внимание уделяется другим типам алгоритмов кластеризации.

2. Метод кластеризации силовой нагрузки

В настоящее время существует множество методов кластеризации кривой мощности нагрузки, наиболее популярными из которых являются кластеризация K-средних, вейвлет-анализ, алгоритм нечеткой кластеризации C-средних (FCM), алгоритм ансамблевой кластеризации, самоорганизующаяся нейронная сеть отображения признаков (SOM), экстремальное обучение. машина (ELM), облачные модели и т. д., а также некоторые усовершенствованные алгоритмы, основанные на этих алгоритмах.

  • 1.1 Эффективность кластеризации
    Исследование эффективности кластеризации — это процесс оценки качества кластеризации и определения оптимального количества кластеров путем установления показателей эффективности. Типичные показатели эффективности кластеризации включают сумму квадратов ошибок (SSE), индекс Калински-Харабаша (CHI), индекс Дэвиса-Булди (DBI) и так далее.
    1) Индикатор ССЕ.
    Сумма квадратов ошибок SSE индекса ISSE представлена ​​евклидовым расстоянием от подкласса до центра кластера кластера, а именно:

d(ci , x) — евклидово расстояние между векторами. По мере увеличения количества кластеров ISSE будет уменьшаться. Точка перегиба кривой SSE указывает на то, что уменьшение суммы квадратов ошибок очень мало, когда количество кластеров увеличивается после этой точки. Следовательно, точка перегиба кривой SSE кривую SSE можно использовать как оптимальное количество кластеров. 2) индикатор ОМС. Индекс CHI всесторонне учитывает межклассовую дисперсию (обозначается B) и внутриклассовую компактность (обозначается W), где:

В формуле: x - среднее всех объектов, wk,i представляет собой принадлежность i-го объекта к k-му кластеру, а именно:

Видно, что чем больше ICHI, тем лучше дисперсия между кластерами и компактность внутри кластеров. 3) Индикатор ДБИ. Значение индикатора DBI аналогично значению CHI, а формула расчета:

в:

В формуле: d(Xk) и d(Xj) — расстояния внутри матрицы, d(ck, cj) — расстояния между векторами. Чем меньше IDBI, тем лучше эффект кластеризации.

  • 1.2 Индикаторный анализ

Все три индикатора достоверности кластеризации могут правильно найти оптимальное количество кластеров. Крайние точки кривых CHI и DBI меньше, чем у кривой SSE. Точка перегиба линии более интуитивно понятна, по сравнению с CHI формула расчета индикатора DBI проще, а диапазон изменения небольшой, что легко применять. Таким образом, DBI подходит в качестве эффективного индикатора кластеризации кривой мощности.

  • 2. Сравнение классических алгоритмов кластеризации Таблица 2 суммирует приведенные выше алгоритмы:

Из рисунка 2 видно, что вычислительная эффективность кластеризации значительно выше, чем у других типов алгоритмов.

Из рисунка 3 видно, что эффект от иерархической кластеризации хороший, а волатильность небольшая. Кроме того, оба типа алгоритмов имеют то преимущество, что требуют меньше входных параметров. В этой статье сочетаются высокая эффективность кластеризации разделов и высокая точность иерархической кластеризации, и предлагается интегрированный алгоритм кластеризации кривой нагрузки.

  • 3. Интегрированный алгоритм кластеризации Основная идея алгоритма ансамблевой кластеризации (EnsClust) заключается в повторении деления и кластеризации на нескольких подмножествах исходного набора данных, а также в объединении полученных центров кластеров путем иерархической кластеризации. Алгоритм ансамблевой кластеризации включает три шага: начальную повторную выборку, кластеризацию разделов и иерархическую кластеризацию. Во-первых, множественные наборы выборок исходного набора данных получаются посредством повторной выборки начальной загрузки, затем размер данных каждого набора выборок уменьшается путем деления и кластеризации, и, наконец, результаты разделения и кластеризации объединяются посредством иерархической кластеризации. 3.1 Алгоритм работы следующий:
    1) Передискретизация начальной загрузки.
    Так называемая бутстрепная повторная выборка заключается в выполнении случайной выборки с заменой исходной выборки емкостью n. Размер случайной выборки извлеченной случайной выборки равен n, и вероятность того, что каждый человек будет выбран в каждой выборке, равна. Поскольку кластеризация разделов менее стабильна и может сходиться к локальному оптимальному решению, то есть разные начальные центры кластеров или небольшие изменения в наборе данных могут привести к различным результатам кластеризации. Благодаря повторной выборке начальной загрузки кластеризация на нескольких наборах выборок может уменьшить влияние случайных факторов в начальном центре кластера и выбросов в исходном наборе данных, тем самым повысив стабильность алгоритма.
    2) Разделите кластеры.
    В алгоритме ансамблевой кластеризации кластеризацию разделов можно рассматривать как этап предварительной обработки данных для иерархической кластеризации. Если иерархическая кластеризация выполняется непосредственно на исходном наборе данных, необходимо вычислить евклидово расстояние между всеми объектами и сохранить матрицу расстояний, что требует много времени и места. Эффективность кластеризации самая высокая, а центры выходных кластеров используются для представления структуры исходного набора данных, что значительно уменьшает размер данных. По сравнению со случайной выборкой центр кластера содержит больше информации об исходном наборе данных и может устранить влияние шумовых точек и выбросов.
    3) Иерархическая кластеризация.
    В алгоритме ансамблевой кластеризации иерархическая кластеризация может рассматриваться как объединение выходных результатов кластеризации выборки. Чтобы решить проблему, состоящую в том, что кластер разделов легко попадает в локальное оптимальное решение и сильно зависит от начального центра кластера, используется иерархический алгоритм кластеризации с лучшим качеством кластера и высокой стабильностью для объединения центров кластеров, выдаваемых кластер разделов. , а затем получить окончательный результат кластеризации.
  • 3.2 Анализ алгоритма и экспериментальные результаты

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

  • 4. Интегрированный алгоритм кластеризации в сочетании с уменьшением размерности 4.1 Уменьшение размерности кривой нагрузки
    Когда масштаб набора данных велик, время расчета интегрированного алгоритма кластеризации все еще велико.Для дальнейшего повышения эффективности кластеризации необходимо уменьшить размерность набора данных. Цель уменьшения размерности состоит в том, чтобы представить кривую нагрузки с меньшим размерным вектором. С одной стороны, уменьшение размерности может уменьшить объем памяти для хранения данных, с другой – сократить время расчета евклидова расстояния между векторами и повысить эффективность алгоритма. Обычно используемые алгоритмы уменьшения размерности включают карту Саммона, самоорганизующуюся карту, анализ главных компонентов и т. д. 4.2 Классификация алгоритмов уменьшения размерности 1) картирование саммона. Отображение Саммона (SM) — это нелинейное отображение, целью алгоритма которого является минимизация функции ошибки:

Где: d(xi,xj) — расстояние между объектом i и объектом j в исходном пространстве; d(yi,yj) — расстояние между двумя объектами в спроецированном пространстве. Карта sammon решает эту проблему оптимизации с помощью градиентного спуска.
2) Самоорганизующаяся карта.
Нейронная сеть самоорганизующейся карты (SOM) может реализовать нелинейное уменьшение размерности данных [20]. Узлы входного слоя SOM являются атрибутами векторов высокой размерности, узлы выходного слоя являются атрибутами векторов низкой размерности, а сходство между атрибутами входного слоя и атрибутами выходного слоя представлено весовым вектором. Вычислите евклидово расстояние d(x(m), w(n)) между входным вектором x(m) и вектором весов w(n), возьми выходной узел, ближайший к x(m), в качестве выигрышного узла и обнови его весовой вектор:

где η — скорость обучения. В то же время обновляются весовые векторы его k ближайших соседей.
3) Анализ главных компонент.
Анализ главных компонентов (PCA) представляет собой алгоритм уменьшения линейной размерности. Комплексный индекс строится с линейной комбинацией исходных переменных, чтобы он максимально отражал информацию об исходных переменных (выраженную дисперсией). Эти всеобъемлющие показатели являются основными компонентами.

В формуле: X — нормированная матрица данных, cov(X) — ковариационная матрица, вектор-столбец V — ортогональный единичный собственный вектор cov(X). Матрица данных после уменьшения размера X до L:


4) Извлечение признаков.
Метод извлечения признаков (FE) непосредственно вычисляет характеристические индексы каждой кривой нагрузки.В этом документе извлекаются четыре основных характеристических индекса для каждой кривой нагрузки: максимальная нагрузка, минимальная нагрузка, средняя нагрузка и стандартное отклонение нагрузки.
4.3 Анализ результатов уменьшения размерности
ORG представляет исходный набор данных, а SM, SOM, PCA и FE представляют собой набор данных с уменьшением размерности после картирования sammon, самоорганизующегося картирования, анализа основных компонентов и выделения признаков соответственно. Исходный набор данных является 48-мерным, а набор данных с уменьшенной размерностью — 4-мерным. Ансамблевая кластеризация наборов данных уменьшения размерности. На рисунке 10 показано время вычисления различных методов уменьшения размерности, включая время уменьшения размерности и время кластеризации. Из рисунка 10 видно, что время расчета метода уменьшения размерности PCA наименьшее, и чем больше размер набора данных, тем очевиднее эффект.

На рисунке 11 показаны индикаторы DBI результатов кластеризации различных методов уменьшения размерности. На диаграмме DBI видно, что эффект кластеризации набора данных после уменьшения размерности с помощью анализа главных компонентов и картирования sammon лучше и сравним с эффектом кластеризации исходного набора данных, что указывает на то, что эти двумерные методы уменьшения размерности могут сохранять загружать данные в наибольшей степени набор информации.

Подводя итог, можно сказать, что точность кластеризации ансамбля после уменьшения размерности PCA кривой нагрузки очень высока. 5. Заключение
В этой статье предлагается интегрированный алгоритм кластеризации кривых мощности в сочетании с методами уменьшения размерности.
1) Показатели эффективности кластеризации SSE, CHI и DBI могут правильно определить оптимальное количество кластеров. Индекс DBI прост для расчета, а кривая интуитивно понятна, поэтому он подходит в качестве индекса достоверности кластеризации кривой нагрузки.
2) Для набора данных кривой нагрузки алгоритм иерархической кластеризации имеет самую высокую точность, а алгоритм кластеризации разделов имеет самую высокую эффективность, и по мере увеличения масштаба набора данных разница в эффективности различных алгоритмов значительно увеличивается.
3) Алгоритм ансамблевой кластеризации сочетает в себе преимущества высокой эффективности кластеризации разделов и высокой точности иерархической кластеризации.
4) Для уменьшения размерности кривой нагрузки время расчета анализа главных компонентов (включая время уменьшения размерности и время кластеризации) является самым коротким; эффект кластеризации набора данных после уменьшения размерности с помощью анализа главных компонентов и карты Саммона является лучшим.
5) Для массивных многомерных кривых нагрузки можно использовать анализ основных компонентов для уменьшения размерности набора данных, и на этой основе к кластеру применяется ансамблевый алгоритм кластеризации, а индекс эффективности DBI используется для оценки результатов кластеризации. .

Ⅱ Исследование кластеризации силовой нагрузки на основе усовершенствованного алгоритма DTW
1. Фоновые знания: алгоритм DTW
Dynamic Time Warping (DTW) — это метод измерения сходства двух временных рядов разной длины. Он также широко используется, в основном при сопоставлении шаблонов, например, при распознавании речи отдельных слов (определение того, представляют ли две части речи одно и то же слово), распознавании жестов, интеллектуальном анализе данных и поиске информации и т. д.
Во временных рядах длины двух временных рядов, которые необходимо сравнить на предмет сходства, могут быть не равными, а в области распознавания речи разные люди говорят с разной скоростью. Поскольку речевой сигнал имеет значительную случайность, даже если один и тот же человек издает один и тот же тон в разное время, невозможно получить полный отрезок времени. И скорость произношения разных фонем в одном и том же слове тоже разная, например, звук «А» некоторые люди будут тянуть очень долго, а «и» произносить очень коротко. В этих сложных случаях расстояние (или сходство) между двумя временными рядами не может быть эффективно получено с использованием традиционного евклидова расстояния.

Например, как показано на рисунке выше, сплошная и пунктирная линии представляют собой две речевые формы одного и того же слова «перо» (разнесены по оси Y для удобства наблюдения). Вы можете видеть, что их общие формы сигналов похожи, но они не выровнены на временной шкале. Например, в 20-й момент времени точка a сплошной линии соответствует точке b' пунктирной линии, поэтому традиционный расчет сходства путем сравнения расстояний явно ненадежен. Потому что очевидно, что точка a сплошной линии соответствует точке b штриховой линии. На приведенном ниже рисунке DTW может найти точку, в которой две формы волны совпадают, так что расстояние между ними рассчитывается правильно.

То есть по большей части две последовательности имеют очень похожие формы в целом, но формы не выровнены по оси x. Поэтому, прежде чем мы сравним их сходство, нам нужно деформировать одну (или две) последовательности под временной шкалой, чтобы добиться лучшего выравнивания. И DTW — эффективный способ добиться этого искривления. DTW вычисляет сходство между двумя временными рядами, расширяя и сокращая временные ряды.
Откуда вы знаете, что две формы волны выровнены? Другими словами, какая деформация является правильной? Интуитивно, конечно, после деформации последовательности она может перекрываться другой последовательностью и восстанавливаться. В это время сумма расстояний всех соответствующих точек в двух последовательностях наименьшая. Поэтому интуитивно правильность деформации обычно относится к выравниванию «функции к функции».
Динамическая временная деформация DTW представляет собой типичную задачу оптимизации.В ней используется функция деформации времени W(n), которая удовлетворяет определенным условиям для описания временного соответствия между тестовым шаблоном и эталонным шаблоном и решает функцию деформации, соответствующую минимальному кумулятивному расстоянию, когда два шаблона совпадают.
Предположим, у нас есть два временных ряда Q и C, и их длины равны n и m соответственно: (В реальном приложении сопоставления речи одна последовательность является эталонным шаблоном, другая — тестовым шаблоном, и значение каждой точки в последовательности это речевая последовательность Собственное значение каждого кадра в . Например, речевая последовательность Q имеет всего n кадров, а собственное значение (число или вектор) i-го кадра равно qi. Что касается того, какой признак взять , это не влияет на обсуждение DTW здесь.Что нам нужно, так это сопоставление сходства двух фонетических последовательностей, чтобы определить, какое слово является нашей тестовой фонетикой)
Q = q1, q2,…,qi,…,qn; С = с1, с2,…, сj,…, см; Если n=m, то подбрасывать не нужно, достаточно вычислить расстояние между двумя последовательностями напрямую. Но если n не равно m, нам нужно выровнять. Самый простой способ выравнивания — линейное масштабирование. Короткая последовательность линейно увеличивается до той же длины, что и длинная последовательность, а затем сравнивается, или длинная линейная последовательность укорачивается до той же длины, что и короткая последовательность, а затем сравнивается. Однако такие расчеты не учитывают, что продолжительность каждого сегмента речи будет различаться в разных обстоятельствах, поэтому эффект распознавания может быть не оптимальным. Поэтому больше используется метод динамического программирования.
Чтобы выровнять две последовательности, нам нужно построить сетку матрицы размера nxm, элемент матрицы (i, j) представляет собой расстояние d(qi, cj) между двумя точками qi и cj (то есть каждая точка последовательности Q и C Сходство между каждой точкой , чем меньше расстояние, тем выше сходство (порядок здесь не учитывается), обычно используется евклидово расстояние, d(qi, cj) = (qi-cj)2 (может также понимать как степень искажения). Каждый элемент матрицы (i, j) представляет выравнивание точек qi и cj. Алгоритм DP можно отнести к нахождению пути через несколько узлов сетки в этой сетке, а узлы сетки, пройденные путем, являются совмещенными точками для расчета двух последовательностей.

Какой путь лучше? Вот и вопрос сейчас, какая деформация лучше.
Мы определяем этот путь как путь деформации и обозначаем его W. k-й элемент W определяется как wk=(i,j)k, что определяет отображение последовательностей Q и C. Таким образом, мы имеем:

Во-первых, этот путь не выбирается произвольно и должен удовлетворять следующим ограничениям:
1) Граничные условия: w1=(1, 1) и wK=(m, n). Произношение любой речи может измениться, но последовательность ее частей изменить нельзя, поэтому выбранный путь должен начинаться с левого нижнего угла и заканчиваться в правом верхнем углу.
2) Непрерывность: если wk-1=(a',b'), то для следующей точки пути wk=(a,b) должно удовлетворять (a-a')

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

K в знаменателе в основном используется для компенсации обычных путей разной длины. Наша цель или идея DTW состоит в том, чтобы расширить и сократить два временных ряда, чтобы получить деформацию с кратчайшим расстоянием между двумя временными рядами и наиболее похожим, Кратчайшее расстояние - это разница между двумя временными рядами. окончательный показатель расстояния. Здесь все, что нам нужно сделать, это выбрать путь, который приводит к наименьшему общему расстоянию. Здесь мы определяем кумулятивное расстояние кумулятивных расстояний. Две последовательности Q и C сопоставляются, начиная с точки (0, 0) Каждый раз, когда достигается точка, расстояния, рассчитанные по всем предыдущим точкам, будут накапливаться. После достижения конечной точки (n, m) это кумулятивное расстояние является окончательным общим расстоянием, о котором мы упоминали выше, то есть сходством между последовательностями Q и C. Совокупное расстояние γ(i,j) может быть выражено следующим образом: кумулятивное расстояние γ(i,j) – это текущее расстояние d(i,j) узла сетки, то есть евклидово расстояние (подобие) между точками qi и cj и can Сумма кумулятивных расстояний от наименьших соседей до точки:

Оптимальный путь — это путь, минимизирующий совокупное расстояние вдоль пути. Этот путь может быть получен алгоритмом динамического программирования.
2. Улучшенный алгоритм на основе DTW
1 Обзор
В данной работе предложен метод кластеризации силовой нагрузки на основе усовершенствованного алгоритма DTW, направленный на устранение недостатков исходного алгоритма DTW с высокой временной сложностью и злокачественным сопоставлением, предлагается ограничить путь поиска алгоритма DTW и управлять им вблизи диагонали матрицы.Ограничивая необоснованное сопоставление пар точек, сложность поиска значительно снижается, с O(N2) до среднего уровня O(N), в то же время для повышения точности вводится перенос кривой, т.к. насколько это возможно в пределах диапазона поиска, а ось времени немного улучшена.Метрика кривой сходства со смещением. Наконец, для кластеризации выбран алгоритм K-Medoids, и пользователи разделены.
2. Идеи реализации
Алгоритм динамической деформации времени (DTW) можно использовать для измерения сходства временных рядов, но его ограничения также весьма очевидны. Как показано на рис. 2-1, когда DTW вычисляет отношение соответствия между двумя временными рядами, он проходит всю матрицу M*N, чтобы найти оптимальный путь, а временная сложность достигает O(N2), что чрезвычайно важно. слаб при работе с большими объемами данных, алгоритм DTW имеет плохо обусловленное явление сопоставления, Во многих случаях сравнение сходства временных рядов не позволяет сильно масштабировать кривую, иначе это может привести к дополнительным ошибкам. Например, при кластеризации нагрузки на электроэнергию пользователи с разными периодами колебаний, очевидно, имеют разные привычки потребления электроэнергии.Не следует ошибочно объединять их в одну категорию путем выравнивания шкал. .считается очень похожим.

С этой целью в этой статье предлагается улучшенный алгоритм DTW, основанный на ограничении диапазона расширения и сжатия и введении преобразования кривой для достижения анализа подобия электрической нагрузки пользователя. Чем больше похожа кривая, тем ближе совпадающий путь к диагонали матрицы, наоборот, у кривой, которую можно выровнять только растяжением, путь сильно колеблется. Чтобы ограничить плохо обусловленное сопоставление кривых, мы предлагаем ограничить поиск вблизи диагонали матрицы. Для части за пределами диапазона поиска вводится преобразование кривой для поиска максимально похожего совпадения без выхода за пределы диапазона расширения и сжатия для дальнейшего улучшения результата расчета. В то же время, поскольку диапазон поиска ограничен, накладные расходы на сравнение подобия значительно сокращаются, а сложность алгоритма может быть снижена до среднего уровня O(N).
В дополнение к трем ограничениям DTW у этого метода есть еще два ограничения:
Ограничение четвертое: ограничения диапазона поиска. Диапазон поиска матрицы представляет собой степень расширения и сжатия кривой, и чем больше похож путь соответствия кривой, тем ближе к диагонали. Предполагается, что диапазон поиска пути должен находиться в пределах диапазона Limit вблизи диагонали матрицы расстояний, то есть максимальная степень расширения и сжатия кривой равна Limit.
Pi=(xa,yb), с |xa-yb|≤Limit
Ограничение пятое: ограничение перемещения кривой. Для временных рядов X и Y с очевидным сходством переноса допускается перевод кривой, а после перевода пересчет матрицы расстояний и совпадающего пути. Для начальной и конечной точек кривой, вынесенных за пределы диапазона сравнения, сохраните их оптимальное соотношение соответствия и примите во внимание начальное значение D[0,0] матрицы расстояний.

3. Алгоритм процесса

4. Выбор алгоритма кластеризации
Чтобы сгруппировать электрическую нагрузку пользователей, расстояние между кривыми потребления электроэнергии было измерено с помощью улучшенного алгоритма DTW. Исходя из этого, мы выбираем алгоритм K-Medoids для кластеризации пользователей.
Подобно алгоритму K-средних, алгоритм K-Medoids завершает кластеризацию посредством итеративного процесса случайного выбора центроида, вычисления расстояния между точкой и центроидом и обновления центроида. Разница заключается в методе построения центроида: в K-средних центроид выбирает среднее значение всех точек данных в текущем кластере, тогда как в алгоритме K-medoids мы выбираем точку с наименьшей суммой расстояний от всех другие точки в текущем кластере в качестве нового центроида.
Алгоритм LK-Medoids не чувствителен к грязным данным и аномальным данным, а отдельные пользователи с аномальным потреблением электроэнергии не повлияют на общие результаты кластеризации; алгоритм K-Medoids может получить типичную кривую потребления электроэнергии, то есть центр тяжести каждого кластер является реальным пользователем, который может достоверно отражать характеристики энергопотребления данного типа пользователей, что удобно для последующего анализа сцены в сочетании с географической, экономической и другой актуальной информацией; в то же время алгоритм K-Medoids имеет легкий - для интерпретации физического смысла каждый вектор представляет собой кривую энергопотребления пользователя, а каждые два. Расстояние между двумя векторами представляет собой подобие потребления электроэнергии разными пользователями, каждую итерацию можно рассматривать как повторную постановку пользователей в очередь, а каждый centroid представляет типичного фактического пользователя.
5. Экспериментальная оценка
В качестве показателей оценки выбраны коэффициент силуэта, SSE и индекс Calinski-Harabaz.
Коэффициент силуэта объединяет факторы сплоченности и разделения.Чем ближе SI к 1, тем лучше эффект кластеризации, тем компактнее кластеры и тем более разобщены кластеры. Формула определяется следующим образом, где a — среднее расстояние от других элементов того же класса с ним, а b — среднее расстояние от ближайших к нему отсчетов разных классов.

Квадрат ошибки SSE измеряет рациональность определения расстояния и сравнивает ошибку каждой точки от центра кластера в результате кластеризации.

Индекс Калински-Харабаз оценивает данные с точки зрения ковариации, Чем меньше ковариация данных в категории, тем лучше, и чем больше ковариация между категориями, тем лучше, тем выше оценка. Формула определяется следующим образом:

где m — количество выборок в обучающем наборе, k — количество категорий, Bk — ковариационная матрица между категориями, Wk — ковариационная матрица данных внутри категорий, а tr — след матрицы.

3. Заключение

В этой статье предлагается улучшенный алгоритм DTW, основанный на ограниченном масштабировании, который подходит для измерения сходства моделей потребления электроэнергии пользователями. Введение предела диапазона поиска регулирует степень расширения и сжатия последовательности загрузки, позволяет избежать изменения периода кривой, вызванного злонамеренным сопоставлением, и повышает вычислительную сложность до среднего уровня O(N). За счет введения сдвига последовательности повышается точность расчета алгоритма для похожих пользователей с разным временем пиковых значений.

Алгоритм навеса

Недостатком алгоритмов K-Means и K-Medoids является то, что количество кластеров K должно быть указано заранее, и во многих практических приложениях нелегко установить разумное значение K. В это время оценка количества кластеров K и центра исходного кластера может быть завершена с помощью алгоритма Canopy. Canopy — это алгоритм кластеризации, обеспечивающий грубое разделение объектов по параметрам T 1 и T 2 . На рисунке ниже показан типичный процесс кластеризации Canopy.

Процесс деления выглядит следующим образом:

Хотя алгоритм Canopy работает быстрее, точность процесса кластеризации низкая, поэтому в этой статье алгоритм Canopy используется для первоначальной параллельной кластеризации данных для получения K кластеров. Затем полученные K кластеров используются в качестве начального количества кластеров для дальнейшей кластеризации с использованием K-средних. То есть алгоритм Canopy в основном делит кластеризацию на два этапа. Первый этап — это этап предварительной обработки данных, который использует простой вычислительный метод для группировки похожих объектов в подмножество, называемое Canopy. Второй этап — это этап вычисления кластеризации с использованием алгоритма K-средних в каждом подмножестве для вычисления расстояний всех векторов данных в одном подмножестве. Среди них значения Т1 и Т2 можно определить перекрестной проверкой.

личная идея

Документ резюмируется следующим образом:
1. Показатели эффективности кластеризации SSE, CHI и DBI могут правильно определить оптимальное количество кластеров. Индекс DBI прост для расчета, а кривая интуитивно понятна, поэтому он подходит в качестве индекса достоверности кластеризации кривой нагрузки.
2. Перед алгоритмом кластеризации используйте алгоритм Canopy для предварительной классификации данных, чтобы позже заложить основу для более точного алгоритма кластеризации.
3. Интегрированный алгоритм кластеризации может сочетать в себе преимущества высокой эффективности разделения и кластеризации и высокой точности иерархической кластеризации. При использовании электрической нагрузки целесообразнее использовать K-Medoids для алгоритма разбиения и кластеризации.
4. Для массивных и многомерных кривых нагрузки можно использовать анализ главных компонент для уменьшения размерности набора данных.На этой основе алгоритм ансамблевой кластеризации применяется к кластеру, а индекс эффективности DBI используется для оценки результатов кластеризации. .

Категории