Теория управления. Принципы системного анализа

При большом числе факторов т для оценивания параметров линейной функции регрессии (1) можно строить дробные реплики высокой степени дробности. Так, при т=7 можно построить дробную реплику из полного факторного плана 2³ для первых трех факторов, приравняв четыре остававшихся фактора к двухфакторным и трехфакторному взаимодействиям трех других факторов, положив, например

(15)

Такую реплику записывают как 2^7-4.

В общем случае дробную реплику обозначают через 2^т-p, если р факторов приравнены к произведениям остальных т--p факторов, уровни которых выбраны согласно полному факторному плану. Дробную реплику 2^т-p можно строить различными способами. Для анализа системы смешивания коэффициентов пользуются понятиями генерирующих и определяющих соотношений.

Генерирующими называют соотношения, с помощью которых построена дробная реплика. Так, для реплики, представленной в табл. 5, генерирующим является соотношение х₃=x₁х₂, а это указывает, что фактор х₃ занимает в матрице столбец, соответствующий взаимодействию x₁x₂. Для указанной выше реплики 2^7-4 генерирующим является соотношение (15).

Определяющим соотношением (определяющим контрастом) называют равенство, в левой части которого стоит единица, а в правой -- какое-либо произведение факторов. Для дробной реплики 2^т-p можно получить p различных определяющих соотношений из генерирующих путем умножения обеих частей последних на их левые части с последующей заменой (х_i)² на 1 (i=1, .., т). Другие определяющие соотношения получаются путем перемножения ранее полученных и выделения среди них новых. Например, для реплики (табл. 5) определяющим является соотношение (12).

Построим определяющие соотношения для реплики 2^7-4, задаваемой генерирующими соотношениями (15). Умножая обе части равенств (15) на их левые части, получаем четыре определяющих соотношения:

(16)

Попарное перемножение этих четырех соотношений дает шесть новых:

(17)

Перемножение каждой тройки из четырех соотношений (16) Дает еще три определяющих соотношения:

(18)

Наконец, перемножая все четыре соотношения (16), получаем

(19)

Легко понять, что кроме (16) - (19), других определяющих соотношений для рассмотренной реплики 2^+7-4 нет.

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

Определим, например, с какими взаимодействиями смешан главный эффект b₃ в дробной реплике 2^7-4, определяемой генерирующими соотношениями (15). Для этого умножим все определяющие соотношения (16) - (19) на х₃. Получим

Следовательно, главный эффект b₃ смешан с эффектами взаимодействий первого порядка с эффектами взаимодействий второго порядка третьего порядка четвертого порядка и пятого порядка

В конкретной практической ситуации для выбора подходящей дробной реплики полного факторного плана необходимо использовать все априорные сведения теоретического и интуитивного характера об объекте планирования с целью выделения тех факторов и произведений факторов, влияние которых на результаты измерений существенно. При этом смешивание нужно производить так, чтобы общее среднее b₀ и главные эффекты b₁,..., b_m были смешаны с эффектами взаимодействий самого высокого порядка (так как обычно они отсутствуют) или с эффектами таких взаимодействий, о которых известно, что они оказывают несущественное влияние на результаты измерений. Отсюда следует, в частности, что недопустимо произвольное разбиение полного факторного плана 2³ на две части для выделения полуреплики 2^3-1.

Качество дробного факторного плана иногда характеризуют с помощью разрешающей способности плана, которая равна наименьшему числу символов в правых частях определяющих соотношений. В частности, для плана разрешающей способности III ни один главный эффект не смешан ни с каким другим главным эффектом, но главные эффекты смешаны с эффектами двухфакторных взаимодействий. Для плана разрешающей способности IV главные эффекты не смешаны друг с другом и с эффектами двухфакторных взаимодействий, но последние друг с другом смешаны. Для плана разрешающей способности V главные эффекты и эффекты двухфакторных взаимодействий не смешаны, но последние смешаны с эффектами трехфакторных взаимодействий. Все три рассмотренные выше дробные реплики имеют разрешающую способность III.

12.3 Метод наименьших квадратов

Рассмотрим особенности регрессионного анализа результатов моделирования на примере построения линейной регрессионной модели.

На рис. 3.9 показаны точки (x_i, y_i), полученные в эксперименте. Делаем предположение, что функция отклика может быть представлена в виде прямой линии

Требуется получить такие значения коэффициентов b₀ и b₁, при которых сумма квадратов ошибок будет минимальной. На рисунке ошибки e_i для каждой экспериментальной точки равны расстояниям по вертикали от этой точки до линии регрессии (рис. 3).

Рис. 3. К построению регрессионной модели

Обозначим (y_t)_{i =}b₀+ b₀x_i (здесь (у_t)_i - величина, предсказываемая регрессионной моделью), тогда выражение для ошибок будет иметь вид а функция ошибки

Для получения коэффициентов b₀ и b₁ при которых функция F₀ будет минимальной, приравняем нулю частные производные dF₀ /db₀ и dF₀ /db₁. Будем иметь:

(20)

Таким образом, получена система двух линейных алгебраических уравнений:

(21)

Решая систему этих уравнений, получим

(22)

где N - число реализаций при моделировании.

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

(23)

система уравнений типа (22), (23) будет иметь вид

(24)

Для оценки точности совпадения теоретических и экспериментальных данных следует определить среднюю квадратичную ошибку на единицу веса

(25)

или среднее абсолютное отклонение

(26)

где r - число вычисляемых (табличных) значений;

s - число параметров.

Последовательность вычислений при построении уравнения регрессии на основе метода наименьших квадратов рассмотрим на конкретном примере.

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

Вначале попытаемся в качестве типа эмпирической формулы принять линейную зависимость, удерживая в формуле два первых члена:

Составим нормальные уравнения, для чего предварительно заполним таблицу В таблице предусмотрим дополнительные столбцы 4, 5 и 8, которые нам могут потребоваться в дальнейшем (таблица 7).

Таблица 7

Пользуясь данными столбцов 1, 2, 3, 6, 7, составим нормальные уравнения (3.26), которые применительно к нашему случаю при удержании только двух первых членов формулы будут иметь вид:

Подставляя табличные данные, получим:

Решая эти уравнения, найдем: b₀ =6,68; b₁ = -3,48, следовательно,

Оценим точность выполненных построений. Подставив в полученную формулу значения x (табл. 8), определим вычисленные значения у_t и отклонения.

Таблица 8

Суммируя данные последнего столбца, будем иметь:

Средняя квадратическая ошибка на единицу веса

Среднее абсолютное отклонение (5.9) равно

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

Повторим все операции, используя более точное выражение

Для записи нормальных уравнений (7) дополним вспомогательную табл. 3.8 новыми данными, которые приведены в столбцах 4, 5, 8 и выделены курсивом. Составим нормальные уравнения:

После решения этой системы найдем b₀=7.00; b₁=-4.74; b₂=0.63 и запишем искомую зависимость:

Для определения средней квадратической ошибки составим табл. 9.

Таблица 9

Суммируя последний столбец, получим

Средняя квадратическая ошибка на единицу веса

Среднее абсолютное отклонение

Следовательно, формула вполне удовлетворительно соответствует экспериментальным данным.

Литература

1. Ильина Н.В. Системный анализ и моделирование процессов в техносфере: Учеб. пособие / Н.В. Ильина, Д.Д. Лапшин, В.И. Федянин. - Ч. 1. Воронеж: ГОУВПО «Воронежский государственный технический университет, 2008. - 206 с.

Лекция 13. Кластерный анализ

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

Иерархическое дерево

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

В результате, вы связываете вместе всё большее и большее число объектов и агрегируете (объединяете) все больше и больше кластеров, состоящих из все сильнее различающихся элементов. Окончательно, на последнем шаге все объекты объединяются вместе. На этих диаграммах горизонтальные оси представляют расстояние объединения (в вертикальных древовидных диаграммах вертикальные оси представляют расстояние объединения). Так, для каждого узла в графе (там, где формируется новый кластер) вы можете видеть величину расстояния, для которого соответствующие элементы связываются в новый единственный кластер. Когда данные имеют ясную "структуру" в терминах кластеров объектов, сходных между собой, тогда эта структура, скорее всего, должна быть отражена в иерархическом дереве различными ветвями. В результате успешного анализа методом объединения появляется возможность обнаружить кластеры (ветви) и интерпретировать их.

Меры расстояния

Объединение или метод древовидной кластеризации используется при формировании кластеров несходства или расстояния между объектами. Эти расстояния могут определяться в одномерном или многомерном пространстве. Например, если вы должны кластеризовать типы еды в кафе, то можете принять во внимание количество содержащихся в ней калорий, цену, субъективную оценку вкуса и т.д. Наиболее прямой путь вычисления расстояний между объектами в многомерном пространстве состоит в вычислении евклидовых расстояний. Если вы имеете двух- или трёхмерное пространство, то эта мера является реальным геометрическим расстоянием между объектами в пространстве (как будто расстояния между объектами измерены рулеткой). Однако алгоритм объединения не "заботится" о том, являются ли "предоставленные" для этого расстояния настоящими или некоторыми другими производными мерами расстояния, что более значимо для исследователя; и задачей исследователей является подобрать правильный метод для специфических применений.

Евклидово расстояние. Это, по-видимому, наиболее общий тип расстояния. Оно попросту является геометрическим расстоянием в многомерном пространстве и вычисляется следующим образом:

расстояние(x,y) = {_i (x_i - y_i)² }^1/2

Заметим, что евклидово расстояние (и его квадрат) вычисляется по исходным, а не по стандартизованным данным. Это обычный способ его вычисления, который имеет определенные преимущества (например, расстояние между двумя объектами не изменяется при введении в анализ нового объекта, который может оказаться выбросом). Тем не менее, на расстояния могут сильно влиять различия между осями, по координатам которых вычисляются эти расстояния. К примеру, если одна из осей измерена в сантиметрах, а вы потом переведете ее в миллиметры (умножая значения на 10), то окончательное евклидово расстояние (или квадрат евклидова расстояния), вычисляемое по координатам, сильно изменится, и, как следствие, результаты кластерного анализа могут сильно отличаться от предыдущих.

Квадрат евклидова расстояния. Иногда может возникнуть желание возвести в квадрат стандартное евклидово расстояние, чтобы придать большие веса более отдаленным друг от друга объектам. Это расстояние вычисляется следующим образом (см. также замечания в предыдущем пункте):

расстояние(x,y) = _i (x_i - y_i)²

Расстояние городских кварталов (манхэттенское расстояние). Это расстояние является просто средним разностей по координатам. В большинстве случаев эта мера расстояния приводит к таким же результатам, как и для обычного расстояния Евклида. Однако отметим, что для этой меры влияние отдельных больших разностей (выбросов) уменьшается (так как они не возводятся в квадрат). Манхэттенское расстояние вычисляется по формуле:

расстояние(x,y) = _i |x_i - y_i|

Расстояние Чебышева. Это расстояние может оказаться полезным, когда желают определить два объекта как "различные", если они различаются по какой-либо одной координате (каким-либо одним измерением). Расстояние Чебышева вычисляется по формуле:

расстояние(x,y) = Максимум|x_i - y_i|

Степенное расстояние. Иногда желают прогрессивно увеличить или уменьшить вес, относящийся к размерности, для которой соответствующие объекты сильно отличаются. Это может быть достигнуто с использованием степенного расстояния. Степенное расстояние вычисляется по формуле:

расстояние(x,y) = (_i |x_i - y_i|^p)^1/r

где r и p - параметры, определяемые пользователем. Несколько примеров вычислений могут показать, как "работает" эта мера. Параметр p ответственен за постепенное взвешивание разностей по отдельным координатам, параметр r ответственен за прогрессивное взвешивание больших расстояний между объектами. Если оба параметра - r и p, равны двум, то это расстояние совпадает с расстоянием Евклида.

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

расстояние(x,y) = (Количество x_i y_i)/ i

Правила объединения или связи

На первом шаге, когда каждый объект представляет собой отдельный кластер, расстояния между этими объектами определяются выбранной мерой. Однако когда связываются вместе несколько объектов, возникает вопрос, как следует определить расстояния между кластерами? Другими словами, необходимо правило объединения или связи для двух кластеров. Здесь имеются различные возможности: например, вы можете связать два кластера вместе, когда любые два объекта в двух кластерах ближе друг к другу, чем соответствующее расстояние связи. Другими словами, вы используете "правило ближайшего соседа" для определения расстояния между кластерами; этот метод называется методом одиночной связи. Это правило строит "волокнистые" кластеры, т.е. кластеры, "сцепленные вместе" только отдельными элементами, случайно оказавшимися ближе остальных друг к другу. Как альтернативу вы можете использовать соседей в кластерах, которые находятся дальше всех остальных пар объектов друг от друга. Этот метод называется метод полной связи. Существует также множество других методов объединения кластеров, подобных тем, что были рассмотрены.

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

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

Невзвешенное попарное среднее. В этом методе расстояние между двумя различными кластерами вычисляется как среднее расстояние между всеми парами объектов в них. Метод эффективен, когда объекты в действительности формируют различные "рощи", однако он работает одинаково хорошо и в случаях протяженных ("цепочного" типа) кластеров. Отметим, что в своей книге Снит и Сокэл (Sneath, Sokal, 1973) вводят аббревиатуру UPGMA для ссылки на этот метод, как на метод невзвешенного попарного арифметического среднего - unweighted pair-group method using arithmetic averages.

Взвешенное попарное среднее. Метод идентичен методу невзвешенного попарного среднего, за исключением того, что при вычислениях размер соответствующих кластеров (т.е. число объектов, содержащихся в них) используется в качестве весового коэффициента. Поэтому предлагаемый метод должен быть использован (скорее даже, чем предыдущий), когда предполагаются неравные размеры кластеров. В книге Снита и Сокэла (Sneath, Sokal, 1973) вводится аббревиатура WPGMA для ссылки на этот метод, как на метод взвешенного попарного арифметического среднего - weighted pair-group method using arithmetic averages.

Невзвешенный центроидный метод. В этом методе расстояние между двумя кластерами определяется как расстояние между их центрами тяжести. Снит и Сокэл (Sneath and Sokal (1973)) используют аббревиатуру UPGMC для ссылки на этот метод, как на метод невзвешенного попарного центроидного усреднения - unweighted pair-group method using the centroid average.

Взвешенный центроидный метод (медиана). тот метод идентичен предыдущему, за исключением того, что при вычислениях используются веса для учёта разницы между размерами кластеров (т.е. числами объектов в них). Поэтому, если имеются (или подозреваются) значительные отличия в размерах кластеров, этот метод оказывается предпочтительнее предыдущего. Снит и Сокэл (Sneath, Sokal 1973) использовали аббревиатуру WPGMC для ссылок на него, как на метод невзвешенного попарного центроидного усреднения - weighted pair-group method using the centroid average.

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

13.3 Двувходовое объединение

Ранее этот метод обсуждался в терминах "объектов", которые должны быть кластеризованы (см. Объединение (древовидная кластеризация)). Во всех других видах анализа интересующий исследователя вопрос обычно выражается в терминах наблюдений или переменных. Оказывается, что кластеризация, как по наблюдениям, так и по переменным может привести к достаточно интересным результатам. Например, представьте, что медицинский исследователь собирает данные о различных характеристиках (переменные) состояний пациентов (наблюдений), страдающих сердечными заболеваниями. Исследователь может захотеть кластеризовать наблюдения (пациентов) для определения кластеров пациентов со сходными симптомами. В то же самое время исследователь может захотеть кластеризовать переменные для определения кластеров переменных, которые связаны со сходным физическим состоянием.

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

Так, возвращаясь к предыдущему примеру, можно предположить, что медицинскому исследователю требуется выделить кластеры пациентов, сходных по отношению к определенным кластерам характеристик физического состояния. Трудность с интерпретацией полученных результатов возникает вследствие того, что сходства между различными кластерами могут происходить из (или быть причиной) некоторого различия подмножеств переменных. Поэтому получающиеся кластеры являются по своей природе неоднородными. Возможно это кажется вначале немного туманным; в самом деле, в сравнении с другими описанными методами кластерного анализа (Объединение (древовидная кластеризация) и Метод K средних), двувходовое объединение является, вероятно, наименее часто используемым методом. Однако некоторые исследователи полагают, что он предлагает мощное средство разведочного анализа данных (за более подробной информацией вы можете обратиться к описанию этого метода у Хартигана (Hartigan, 1975)).

13.4 Метод K средних

Этот метод кластеризации существенно отличается от таких агломеративных методов, как Объединение (древовидная кластеризация) и Двувходовое объединение. Предположим, вы уже имеете гипотезы относительно числа кластеров (по наблюдениям или по переменным). Вы можете указать системе образовать ровно три кластера так, чтобы они были настолько различны, насколько это возможно. Это именно тот тип задач, которые решает алгоритм метода K средних. В общем случае метод K средних строит ровно K различных кластеров, расположенных на возможно больших расстояниях друг от друга.

Пример

В примере с физическим состоянием (в пункте 13.3 Двувходовое объединение), медицинский исследователь может иметь "подозрение" из своего клинического опыта, что его пациенты в основном попадают в три различные категории. Далее он может захотеть узнать, может ли его интуиция быть подтверждена численно, то есть, в самом ли деле кластерный анализ K средних даст три кластера пациентов, как ожидалось? Если это так, то средние различных мер физических параметров для каждого кластера будут давать количественный способ представления гипотез исследователя (например, пациенты в кластере 1 имеют высокий параметр 1, меньший параметр 2 и т.д.).

Вычисления

С вычислительной точки зрения вы можете рассматривать этот метод, как дисперсионный анализ "наоборот". Программа начинает с K случайно выбранных кластеров, а затем изменяет принадлежность объектов к ним, чтобы: (1) - минимизировать изменчивость внутри кластеров, и (2) - максимизировать изменчивостьмежду кластерами. Данный способ аналогичен методу "дисперсионный анализ (ANOVA) наоборот" в том смысле, что критерий значимости в дисперсионном анализе сравнивает межгрупповую изменчивость с внутригрупповой при проверке гипотезы о том, что средние в группах отличаются друг от друга. В кластеризации методом K средних программа перемещает объекты (т.е. наблюдения) из одних групп (кластеров) в другие для того, чтобы получить наиболее значимый результат при проведении дисперсионного анализа (ANOVA).

Интерпретация результатов

Обычно, когда результаты кластерного анализа методом K средних получены, можно рассчитать средние для каждого кластера по каждому измерению, чтобы оценить, насколько кластеры различаются друг от друга. В идеале вы должны получить сильно различающиеся средние для большинства, если не для всех измерений, используемых в анализе. ЗначенияF-статистики, полученные для каждого измерения, являются другим индикатором того, насколько хорошо соответствующее измерение дискриминирует кластеры.

13.5 Алгоритм нечеткой кластеризации

Алгоритм нечеткой кластеризации называют FCM-алгоритмом (Fuzzy Classifier Means, Fuzzy C-Means). Целью FCM-алгоритма кластеризации является автоматическая классификация множества объектов, которые задаются векторами признаков в пространстве признаков. Другими словами, такой алгоритм определяет кластеры и соответственно классифицирует объекты. Кластеры представляются нечеткими множествами, и, кроме того, границы между кластерами также являются нечеткими.

FCM-алгоритм кластеризации предполагает, что объекты принадлежат всем кластерам с определенной ФП. Степень принадлежности определяется расстоянием от объекта до соответствующих кластерных центров. Данный алгоритм итерационно вычисляет центры кластеров и новые степени принадлежности объектов.

Для заданного множества К входных векторов и N выделяемых кластеров предполагается, что любой принадлежит любому с принадлежностью , где j - номер кластера, a k - входного вектора. Принимаются во внимание следующие условия нормирования для :

;

Цель алгоритма - минимизация суммы всех взвешенных расстояний :

где q - фиксированный параметр, задаваемый перед итерациями.

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

, .

Совместно с условиями нормирования ид данная система дифференциальных уравнений имеет следующее решение:

(взвешенный центр гравитации) и

Алгоритм нечеткой кластеризации выполняется по шагам.

Шаг 1. Инициализация.

Выбираются следующие параметры:

необходимое количество кластеров N, ;

мера расстояний, как Евклидово расстояние;

фиксированный параметр q (обычно ~ 1,5);

начальная (на нулевой итерации) матрица принадлежности объектов x_k с учетом заданных начальных центров кластеров .

Шаг 2. Регулирование позиций центров кластеров.

На t-м итерационном шаге при известной матрице вычисляется в соответствии с вышеприведенным решением системы дифференциальных уравнений.