Технический справочник по алгоритму кластеризации Майкрософт

Применимо к: SQL Server 2019 и более ранних версий Analysis Services Azure Analysis Services Fabric/Power BI Premium

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

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

• Содержимое модели добычи данных для кластерных моделей (службы Analysis Services — добыча данных)

• Примеры запросов модели кластеризации

Реализация алгоритма кластеризации Майкрософт

Алгоритм кластеризации Майкрософт предоставляет два метода для создания кластеров и назначения точек данных кластерам. Первый, алгоритм K-средних, является жестким методом кластеризации. Это означает, что точка данных может принадлежать только одному кластеру, и что одна вероятность вычисляется для членства каждой точки данных в этом кластере. Второй метод, метод "Максимизация ожидания" (EM), является методом мягкой кластеризации. Это означает, что точка данных всегда принадлежит нескольким кластерам, а вероятность вычисляется для каждого сочетания точек данных и кластера.

Вы можете выбрать, какой алгоритм использовать, задав параметр CLUSTERING_METHOD . Метод по умолчанию для кластеризации — масштабируемый EM.

Кластеризация EM

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

Если пустые кластеры создаются во время процесса или если членство в одном или нескольких кластерах превышает заданное пороговое значение, кластеры с низким населением повторно удаляются в новых точках, а алгоритм EM повторно запускается.

Результаты метода кластеризации EM являются вероятностными. Это означает, что каждая точка данных принадлежит всем кластерам, но каждое назначение точки данных кластеру имеет другую вероятность. Так как метод позволяет перекрывать кластеры, сумма элементов во всех кластерах может превышать общее количество элементов в обучаемом наборе. В результатах модели интеллектуального анализа данных оценки, указывающие поддержку, корректируются с учетом этого.

Алгоритм EM — это алгоритм по умолчанию, используемый в моделях кластеризации Майкрософт. Этот алгоритм используется в качестве значения по умолчанию, так как он предлагает несколько преимуществ по сравнению с кластеризациями k-средних значений:

• Требуется не более одного сканирования базы данных.

• Будет работать, несмотря на ограниченную память (ОЗУ).

• Имеет возможность использовать однонаправленный курсор.

• Опережает подходы к выборке.

Реализация Майкрософт предоставляет два варианта: масштабируемый и немасштабируемый EM. По умолчанию в масштабируемом EM первые 50 000 записей используются для начальной проверки. Если это успешно, модель использует только эти данные. Если модель не может быть настроена с использованием 50 000 записей, будут считаны дополнительные 50 000 записей. В немасштабируемом EM весь набор данных считывается независимо от его размера. Этот метод может создавать более точные кластеры, но требования к памяти могут быть значительными. Поскольку масштабируемый EM работает в локальном буфере, итерация данных выполняется гораздо быстрее, и алгоритм гораздо лучше использует кэш памяти ЦП, чем немасштабируемый EM. Кроме того, масштабируемый EM в три раза быстрее, чем не масштабируемый EM, даже если все данные могут помещаться в основную память. В большинстве случаев повышение производительности не приводит к снижению качества полной модели.

См. технический отчет, описывающий реализацию EM в алгоритме кластеризации Microsoft, в статье Масштабирование клasterизации EM (Expectation Maximization) для работы с крупными базами данных.

Кластеризация методом K-средних

Кластеризация K-средних — это известный метод назначения членства в кластере путем минимизации различий между элементами в кластере при максимизации расстояния между кластерами. "Слово 'means' в методе k-средних относится к центроиду кластера, который сначала выбирается произвольно, а затем уточняется поэтапно, пока не будет представлять истинное среднее всех точек данных в кластере." Значение "k" относится к выбираемому количеству точек, используемых для инициации процесса кластеризации. Алгоритм k-средних вычисляет квадратные расстояния между записями данных в кластере и вектором, представляющим среднее значение кластера, и конвергентирует в окончательном наборе кластеров k, когда эта сумма достигает минимального значения.

Алгоритм k-средних назначает каждую точку данных ровно одному кластеру и не разрешает неопределенность в членстве. Членство в кластере выражается как расстояние от центроида.

Как правило, алгоритм k-средних используется для создания кластеров непрерывных атрибутов, где вычисление расстояния к среднему является простым. Однако реализация Microsoft адаптирует метод k-средних для кластеризации дискретных атрибутов с использованием вероятностей. Для дискретных атрибутов расстояние точки данных от определенного кластера вычисляется следующим образом:

1 — P(точка данных, кластер)

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

Обновления алгоритма кластеризации Майкрософт в SQL Server 2008

В SQL Server 2008 конфигурация алгоритма кластеризации Майкрософт по умолчанию была изменена, чтобы использовать внутренний параметр NORMALIZATION = 1. Нормализация выполняется с помощью статистики z-score и предполагает нормальное распределение. Цель этого изменения поведения по умолчанию заключается в том, чтобы свести к минимуму влияние атрибутов, которые могут иметь большие величины и многие излияния. Однако нормализация показателей z может изменить результаты кластеризации для дистрибутивов, которые не являются нормальными (например, однородными распределениями). Чтобы предотвратить нормализацию и получить то же поведение, что и алгоритм кластеризации K-средних в SQL Server 2005, можно использовать диалоговое окно "Параметры параметров" для добавления настраиваемого параметра, НОРМАЛИЗАЦИИ и задания значения 0.

Настройка алгоритма кластеризации Майкрософт

Алгоритм кластеризации компании Microsoft поддерживает несколько параметров, которые влияют на поведение, производительность и точность модели интеллектуального анализа данных (Data Mining).

Настройка параметров алгоритма

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

CLUSTERING_METHOD
Задает метод кластеризации для используемого алгоритма. Доступны следующие методы кластеризации:

Значение по умолчанию — 1 (масштабируемый EM).

ЧИСЛО_КЛАСТЕРОВ
Указывает приблизительное количество кластеров, создаваемых алгоритмом. Если приблизительное количество кластеров невозможно создать из данных, алгоритм создает максимальное количество кластеров. Установка CLUSTER_COUNT на 0 заставляет алгоритм использовать эвристические методы для наиболее точного определения количества кластеров, которые следует строить.

Значение по умолчанию равно 10.

CLUSTER_SEED
Указывает начальное число, которое используется для случайного создания кластеров для начального этапа построения модели.

Изменив это число, можно изменить способ создания начальных кластеров, а затем сравнить модели, созданные с помощью различных семян. Если начальное значение изменено, но найденные кластеры не изменяются значительно, модель может считаться относительно стабильной.

Значение по умолчанию — 0.

МИНИМАЛЬНАЯ ПОДДЕРЖКА
Указывает минимальное количество вариантов, необходимых для создания кластера. Если число случаев в кластере меньше этого числа, кластер обрабатывается как пустой и отбрасывается.

Если задать это число чересчур высоким, вы можете пропустить допустимые кластеры.

Значение по умолчанию — 1.

MODELLING_CARDINALITY
Указывает количество примеров моделей, созданных во время процесса кластеризации.

Сокращение числа моделей-кандидатов может повысить производительность, но существует риск упустить некоторые хорошие варианты.

Значение по умолчанию равно 10.

STOPPING_TOLERANCE
Указывает значение, используемое для определения достижения конвергенции, и алгоритм завершает сборку модели. Конвергенция достигается, когда общее изменение вероятностей кластера меньше, чем соотношение параметра STOPPING_TOLERANCE, разделенного размером модели.

Значение по умолчанию равно 10.

SAMPLE_SIZE
Указывает количество вариантов, используемых алгоритмом для каждого прохода, если параметр CLUSTERING_METHOD имеет значение одного из масштабируемых методов кластеризации. Установка параметра SAMPLE_SIZE значение 0 приведет к кластеризации всего набора данных в одном проходе. Загрузка всего набора данных в одном проходе может привести к проблемам с памятью и производительностью.

Значение по умолчанию — 50000.

МАКСИМАЛЬНЫЕ_ВХОДНЫЕ_АТРИБУТЫ
Указывает максимальное количество входных атрибутов, которые алгоритм может обрабатывать перед вызовом выбора компонентов. При задании этого значения значение равно 0 указывает, что не существует максимального количества атрибутов.

Увеличение числа атрибутов может значительно снизить производительность.

Значение по умолчанию — 255.

МАКСИМАЛЬНЫЕ_СОСТОЯНИЯ
Указывает максимальное количество состояний атрибута, поддерживаемых алгоритмом. Если атрибут имеет больше состояний, чем максимальное, алгоритм использует самые популярные состояния и игнорирует оставшиеся состояния.

Увеличение числа состояний может значительно снизить производительность.

Значение по умолчанию равно 100.

Флаги моделирования

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

Требования

Модель кластеризации должна содержать ключевые столбцы и входные столбцы. Можно также определить входные столбцы как прогнозируемые. Столбцы, заданные как Predict Only , не используются для создания кластеров. Распределение этих значений в кластерах вычисляется после создания кластеров.

Входные и прогнозируемые столбцы

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

См. также

Алгоритм кластеризации Майкрософт
Примеры запросов модели кластеризации
Содержимое модели добычи данных для кластерных моделей (службы Analysis Services — добыча данных)