Многомерная кластеризация при построении регрессионных моделей

Предположим, что рассматриваемая совокупность случайной величины Х неоднородна (рис. 3.1) и в нее входят, например, три группы совокупностей случайной величины с существенно различными параметрами распределений (математическим ожиданием и средним квадратическим отклонением).

Рис. 3.1. Кластеризация однородных групп

Истинные зависимости y=y (x) для этих групп совокупности показаны на рис. 3.1. Там же пунктиром показана линия регрессии y на x, построенная для совокупности всех групп. Таким образом, обработка неоднородной совокупности теми же методами, какие применимы для однородных, могут привести к серьезным ошибкам.

Кластеризация конечного множества элементов на основе кратчайшего остовного дерева. Алгоритм Прима

По заданному графу заполняется матрица весов W (N, N). Веса несуществующих ребер предполагаются сколь угодно большими. Образуется массив P (N) меток вершин графа (столбцов матрицы весов). Алгоритм решения задачи заключается в последовательном заполнении массива меток столбцов и состоит из следующих этапов.

Предварительный этап. Обнуляется массив P (N) меток столбцов таблицы. Произвольно выбранному столбцу присваивается значение метки, равная его номеру.

Этап, повторяющийся N-1 раз (общий этап). В строках, номера которых равны номерам помеченных столбцов, находится минимальный элемент среди элементов непомеченных столбцов. Столбец, в котором находится минимальный элемент, помечается меткой, номер которой равен номеру его строки. В случае, если минимальных элементов несколько, то выбирается любой. После помечивания очередного столбца элементу, симметричному относительно главной диагонали (для многомерного графа с «транспонированными индексами»), присваивается сколь угодно большое значение.

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

Кластеризация множества элементов производится путем удаления части ребер графа по критерию минимальной суммарной дисперсии классов. Пример расчета на MS Excel показан на рис. 3.2.

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

Содержание отчета по разделам лабораторного практикума

• 1. Краткое описание алгоритма (основные соотношения).
• 2. Результаты решения задачи (привести последовательность решения с пояснениями каждого этапа).
• 3. Выводы (соответствие теоретических и экспериментальных результатов).