Технический справочник по алгоритму кластеризации последовательностей (Майкрософт)
Алгоритм кластеризации последовательностей (Майкрософт) — это гибридный алгоритм, использующий методы анализа марковских цепей для определения упорядоченных последовательностей и сочетает результаты этого анализа с технологией кластеризации для построения кластеров на основе последовательностей и других атрибутов модели. В данном разделе описывается реализация алгоритма и настройка его поведения. Приводятся также ссылки на дополнительную информацию о требованиях к моделям кластеризации последовательностей.
Общие сведения об алгоритме, в том числе о просмотре и запросах моделей кластеризации последовательностей, см. в разделе Microsoft Sequence Clustering Algorithm.
Реализация алгоритма кластеризации последовательностей (Майкрософт)
Алгоритм кластеризации последовательностей (Майкрософт) использует марковские модели для выявления последовательностей и определения их вероятностей. Марковская модель — это направленный граф, хранящий переходы между различными состояниями. Алгоритм кластеризации последовательностей (Майкрософт) использует марковские цепи n-го порядка, а не скрытую марковскую модель.
Число порядков марковской цепи говорит о том, сколько состояний использовалось для определения вероятности текущих состояний. В марковской модели первого порядка вероятность текущего состояния зависит только от предыдущего состояния. В марковской цепи второго порядка вероятность текущего состояния зависит от двух предыдущих состояний, и так далее. Для каждой марковской цепи переходы для каждого сочетания состояний хранятся в матрице переходов. По мере удлинения марковской цепи размер матрицы растет экспоненциально и матрица становится чрезвычайно разреженной. Время обработки также возрастает пропорционально.
Может быть удобно представить себе марковскую цепь на примере анализа маршрута перемещения посетителя по страницам веб-сайта. Каждый пользователь за каждый сеанс создает длинную последовательность переходов по элементам интерфейса. При создании модели для анализа поведения посетителя веб-сайта набор обучающих данных представляет собой последовательность URL-адресов, преобразованная в граф, включающий в себя подсчет всех экземпляров одной и той же последовательности переходов. Например, граф содержит вероятность перемещения пользователя со страницы 1 на страницу 2 (10%), со страницы 1 на страницу 3 (20%) и тому подобное. Все возможные пути и фрагменты путей в совокупности образуют граф, который может быть гораздо длиннее и сложнее, чем любой маршрут, взятый по отдельности.
По умолчанию алгоритм кластеризации последовательностей (Майкрософт) использует для кластеризации метод максимизации ожидания (EM). Дополнительные сведения см. в разделе Технический справочник по алгоритму кластеризации (Майкрософт).
Целями кластеризации являются как связанные, так и не связанные с последовательностями атрибуты. Каждый кластер выбирается случайным образом с помощью распределения вероятностей. У каждого кластера есть марковская цепь, представляющая полный набор путей, и матрица, содержащая переходы и вероятности последовательности состояний. На основе начального распределения используется правило Байеса для вычисления вероятности любого атрибута, в том числе последовательности, в конкретном кластере.
Алгоритм кластеризации последовательностей (Майкрософт) поддерживает добавление к модели атрибутов, не связанных с последовательностями. Это означает, что эти дополнительные атрибуты сочетаются с атрибутами, связанными с последовательностями, для создания кластеров вариантов с похожими атрибутами, в точности как в обычной модели кластеризации.
У модели кластеризации последовательностей есть тенденция к созданию намного большего количества кластеров, чем у обычной модели кластеризации. Поэтому алгоритм кластеризации последовательностей (Майкрософт) выполняет декомпозицию кластеровдля разделения кластеров на основе последовательностей и других атрибутов.
Выбор компонентов в модели кластеризации последовательностей
При построении последовательностей выбор компонентов не используется, однако выбор компонентов применяется на стадии кластеризации.
| Тип модели | Метод выбора компонентов | Комментарии |
|---|---|---|
| Кластеризация последовательностей | Не используется | Выбор компонентов не вызывается, но предусмотрена возможность управлять поведением алгоритма, задавая значения параметров MINIMUM_SUPPORT и MINIMUM_PROBABILIITY. |
| Кластеризация | Оценка интересности | Хотя в качестве алгоритма кластеризации могут применяться дискретные или дискретизированные алгоритмы, оценка каждого атрибута вычисляется как расстояние и является непрерывной, поэтому используется оценка интересности. |
Дополнительные сведения см. в статье Feature Selection.
Оптимизация производительности
Алгоритм кластеризации последовательностей (Майкрософт) поддерживает различные способы оптимизации обработки.
Управление числом создаваемых кластеров с помощью значения параметра 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 (DMX) для прогнозирования последовательностей. Дополнительные сведения о выпусках SQL Server, поддерживающих прогнозирование последовательностей, см. в разделе Функции, поддерживаемые выпусками SQL Server 2012 (https://go.microsoft.com/fwlink/?linkid=232473).
Алгоритм кластеризации последовательностей (Майкрософт) не поддерживает использование языка разметки прогнозной модели (PMML) для создания моделей интеллектуального анализа данных.
Алгоритм кластеризации последовательностей (Майкрософт) поддерживает детализацию, использование моделей интеллектуального анализа данных OLAP и измерения интеллектуального анализа данных.
См. также:
Алгоритм кластеризации последовательностей (Майкрософт)
Примеры запросов к модели кластеризации последовательностей
Содержимое моделей интеллектуального анализа данных для моделей кластеризации последовательностей (службы Analysis Services — интеллектуальный анализ данных)