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

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

Важно!

Интеллектуальный анализ данных не рекомендуется использовать в службах SQL Server 2017 Analysis Services, а в SQL Server 2022 Analysis Services его поддержка прекращена. Документация не обновляется для устаревших и неподдерживаемых функций. Дополнительные сведения см. в статье об обратной совместимости служб Analysis Services.

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

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

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

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

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

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

Алгоритм кластеризации можно задать с помощью параметра CLUSTERING_METHOD . По умолчанию используется масштабируемая максимизация ожидания.

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

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

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

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

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

• не требует больше одного просмотра базы данных;

• работает даже при ограниченном объеме оперативной памяти;

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

• по производительности опережает методы, требующие выборки.

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

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

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

Кластеризация методом К-средних — хорошо известный метод определения принадлежности элементов кластерам с помощью минимизации разницы между элементами кластера и максимизации расстояния между кластерами. Слово "средние" в названии метода относится к центроидам кластеров. Центроид — точка данных, которая выбирается произвольно, а затем итеративно уточняется, пока не начинает представлять собой истинное среднее всех точек данных кластера. «К» означает произвольное количество точек, используемых для формирования начальных значений процесса кластеризации. Алгоритм К-средних вычисляет квадраты евклидовых расстояний между записями данных в кластере и вектор, представляющий собой среднее данного кластера. Метод сходится, выдавая окончательный набор из К кластеров, когда упомянутая сумма минимизирована.

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

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

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

Примечание

Алгоритм кластеризации Майкрософт не предоставляет функцию расстояния, используемую при вычислении k-средних, а меры расстояния недоступны в завершенной модели. Однако с помощью прогнозирующей функции можно получить величину, соответствующую расстоянию, где расстояние вычисляется как вероятность принадлежности точки данных к кластеру. Дополнительные сведения см. в разделе ClusterProbability (DMX).

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

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

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

Примечание

Параметр NORMALIZATION является внутренним свойством алгоритма кластеризации Майкрософт и не поддерживается. В целом в моделях кластеризации рекомендуется использовать нормализацию для улучшения результатов модели.

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

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

Задание параметров алгоритма

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

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

ID	Метод
1	Масштабируемая максимизация ожидания
2	Немасштабируемая максимизация ожидания
3	Масштабируемые К-средние
4	Немасштабируемые К-средние

Значение по умолчанию — 1 (масштабируемая максимизация ожидания).

CLUSTER_COUNT
Указывает примерное количество кластеров, строящихся данным алгоритмом. Если это примерное количество кластеров не может быть построено из данных, то алгоритм строит столько кластеров, сколько возможно. Значение 0 параметра CLUSTER_COUNT приводит к тому, что алгоритм начинает использовать эвристический подход для наиболее эффективного определения числа строящихся кластеров.

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

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

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

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

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

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

Примечание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Флаг моделирования	Описание
MODEL_EXISTENCE_ONLY	Столбец будет обрабатываться так, как будто у него два возможных состояния: отсутствует и присутствует. NULL означает отсутствие значения. Применяется к столбцу модели интеллектуального анализа данных.
NOT NULL	Этот столбец не может содержать значение NULL. Если во время обучения модели службы Analysis Services обнаружат значение NULL, возникнет ошибка. Применяется к столбцу структуры интеллектуального анализа данных.

Требования

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

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

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

Столбец	Типы содержимого
Входной атрибут	Непрерывные, циклические, дискретные, дискретизированные, ключевые, табличные и упорядоченные
Прогнозируемый атрибут	Continuous, Cyclical, Discrete, Discretized, Table, Ordered

Примечание

Типы содержимого Cyclical и Ordered поддерживаются, но алгоритм обрабатывает их как дискретные величины и не производит их особой обработки.

См. также:

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