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

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

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

• Содержимое модели интеллектуального анализа данных для моделей кластеризации (службы 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 в алгоритме кластеризации Майкрософт, см. в статье Масштабирование кластеризации EM (ожидание максимизации) в крупные базы данных.

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

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

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

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

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

Замечание

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

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

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

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

Замечание

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

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

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

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

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

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

Идентификатор	Метод
1	Масштабируемый EM
2	Немасштабируемый EM
3	Масштабируемый K-Средний
4	Не масштабируемый K-Средний.

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

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

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

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

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

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

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

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

Замечание

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

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

МОДЕЛИРОВАНИЕ_КАРДИНАЛЬНОСТИ
Указывает количество примеров моделей, созданных во время процесса кластеризации.

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

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

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

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

РАЗМЕР_ВЫБОРКИ
Указывает количество вариантов, используемых алгоритмом для каждого прохода, если параметр CLUSTERING_METHOD имеет значение одного из масштабируемых методов кластеризации. Установка параметра SAMPLE_SIZE значение 0 приведет к кластеризации всего набора данных в одном проходе. Загрузка всего набора данных в одном проходе может привести к проблемам с памятью и производительностью.

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

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

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

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

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

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

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

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

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

Флаг моделирования	Описание
MODEL_EXISTENCE_ONLY	Столбец будет рассматриваться как наличие двух возможных состояний: отсутствующие и существующие. Значение NULL — это отсутствующее значение. Применяется к столбцу модели данных для майнинга.
НЕ ПУСТОЙ	Столбец не может содержать значение NULL. Ошибка возникнет, если службы Analysis Services столкнутся с null'ом во время обучения модели. Применяется к столбцу структуры интеллектуального анализа данных.

Требования

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

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

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

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

Замечание

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

См. также

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