Поделиться через

  • Статья

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

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

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

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

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

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

Может быть удобно представить себе марковскую цепь на примере анализа маршрута перемещения посетителя по страницам веб-узла. Каждый пользователь за каждый сеанс создает длинную последовательность переходов по элементам интерфейса. При создании модели для анализа поведения посетителя веб-узла набор обучающих данных представляет собой последовательность URL-адресов, преобразованная в граф, включающий в себя подсчет всех экземпляров одной и той же последовательности переходов. Например, граф содержит вероятность перемещения пользователя со страницы 1 на страницу 2 (10%), со страницы 1 на страницу 3 (20%) и тому подобное. Все возможные пути и фрагменты путей в совокупности образуют граф, который может быть гораздо длиннее и сложнее, чем любой маршрут, взятый по отдельности.

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

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

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

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

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

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

Тип модели

Метод выбора характеристик

Комментарии

Кластеризация последовательностей

Не используется

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

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

Оценка интересности

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

Дополнительные сведения см. в разделе Выбор компонентов.

Оптимизация производительности

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

  • Управление числом создаваемых кластеров с помощью значения параметра CLUSTER_COUNT.

  • Снижение количества последовательностей, включенных в качестве атрибутов, с помощью увеличения параметра MINIMUM_SUPPORT. В результате редко встречающиеся последовательности исключаются из рассмотрения.

  • Снижение сложности до обработки модели при помощи группирования связанных атрибутов.

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

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

  • Программным образом уменьшить значение n.

  • Хранить только вероятности, превышающие определенный порог.

Подробное обсуждение этих методов выходит за рамки данного раздела.

Настройка алгоритма кластеризации последовательностей

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

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

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

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

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

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

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

  • MINIMUM_SUPPORT
    Задает минимальное число вариантов, которые должны находиться в несущем множестве атрибута для построения кластера.

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

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

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

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

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

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

Флаги модели

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

  • NOT NULL
    Указывает, что столбец не может содержать значение NULL. Если службы Analysis Services в ходе обучения модели обнаружат столбец со значением NULL, возникает ошибка.

    Применяется к столбцу структуры интеллектуального анализа данных.

  • MODEL_EXISTENCE_ONLY
    Столбец будет обрабатываться так, как будто у него два возможных состояния: Missing и Existing. NULL означает отсутствие значения — Missing.

    Применяется к столбцу модели интеллектуального анализа данных.

Дополнительные сведения об использовании отсутствующих значений в моделях интеллектуального анализа данных и влиянии отсутствующих значений на оценки вероятности см. в разделе Отсутствующие значения (службы Analysis Services — интеллектуальный анализ данных).

Требования

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

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

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

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

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

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

Столбец

Типы содержимого

Входной атрибут

Continuous, Cyclical, Discrete, Discretized, Key, Key Sequence, Table и Ordered

Прогнозируемый атрибут

Continuous, Cyclical, Discrete, Discretized, Table и Ordered

Замечания

  • Прогнозирование последовательностей с помощью функции PredictSequence доступно только в выпуске SQL Server Enterprise.

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

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