• Статья

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ПримечаниеПримечание

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

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

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

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

ПримечаниеПримечание

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

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

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

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

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

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

    Идентификатор

    Метод

    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 приводит к тому, что весь набор данных разбивается на кластеры за один проход. При загрузке всего набора данных за один проход могут возникать проблемы с памятью и производительностью.

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

  • 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 поддерживаются, но алгоритм обрабатывает их как дискретные величины и не производит их особой обработки.