Анализ неоднородностей электроэнерrетических систем - Войтов О.Н.
ISBN 5-02-031231-2
Скачать (прямая ссылка):
схем
1 Назначение порога, равного величине элемента матрицы 1 1 сходства (различия). соответствующей связи 1
О пусто ?
Фиксация состава групп П ^ и О 2 (имен включенных в них объектов )
Рис. 3.51. Алгоритм иерархической нисходящей классификации
124
Гл. 3. МЕТОДЫ АНАЛИЗА НЕОДНОРОДНОСТЕЙ ЭЭС
Основная часть алгоритма, выделенная на рис. 3.51 штриховыми линиями (тело цикла 2), реализует следующие правила разнесения объектов по группам:
если объект сходен хотя бы с одним объектом первой группы, при этом не отличается ни от одного из объектов этой группы и, кроме того, не находится в аналогичном отношении ко второй группе, то объект включается в первую кластер-группу;
если объект сходен хотя бы с одним объектом второй группы, при этом не отличным ни от одного из объектов этой группы, и, кроме того, не находится в аналогичном отношении к первой группе, то объект включается во вторую кластер - группу;
если для объекта выполняется отношение противоречия принадлежности с любой или обеими группами, то разбиение на кластеры при заданном пороге считается невозможным;
если объект находится в отношении неопределенности с обеими группами (либо в отношении неопределенности с Ql при
пустом ?22), то объект не включается ни в одну из групп, оставаясь
в совокупности нераспределенных объектов Q.
Основная часть алгоритма из заданной совокупности объектов формирует две группы - Й1 и Й2 - причем вторая группа может
остаться и пустой. Совокупность объектов, не распределенных по группам (?2), в общем случае кластером не является. Если в
результате одного шага алгоритма не встретилось противоречии и (после определения &{ и&2) & не пусто, значит, имеется более двух
групп (и соответственно более одного сечения). Первая и вторая группы уже выделены, следовательно, нужно провести аналогичную процедуру формирования для совокупности оставшихся объектов, не распределенных по этим двум группам.
Запись і ¦* QJ означает включение /-го объекта в кластер
т.е. последовательность трех операций: исключение имени /-го объекта из списка имен внесение его имени в список имен Йу;
исключение из матрицы сходства (различия) /-х строки и столбца. Запись /?07 означает процедуру определения отношения ии /-го
объекта к кластеру
Цикл 2 организуется 'круговым" (бесконечным) перебором объектов, не распределенных по двум группам, завершаясь по их исчерпании (т.е. при отсутствии объектов в списке ?2) либо после
прохождения без уменьшения числа объектов в & числа шагов,
В противном случае разбиение на кластеры при заданном значении порога
считается невозможным.
3.8. КЛАСТЕРНЫЙ АНАЛИЗ
125
равного числу этих объектов. В последнем случае (наличие более чем двух групп) цикл 2 снова вызывается — уже для распределения объектов по двум новым кластерам. При любом завершении работы цикла фиксируются составы групп €1{ и
В результате выполнения шага цикла 1 мы получим вариант разбиения на кластеры (один шаг нисходящей классификации) заданной совокупности объектов либо идентифицируем невозможность такого разбиения при заданном пороге. В первом случае, если требуются более подробные разбиения, можно продолжить цикл, увеличив пороговое сходство. Во втором случае цикл продолжается безусловно. Изменение порога осуществляется на каждом шаге цикла 1. Очередной шаг этого цикла осуществляется при невозможности получения разбиения на текущем шаге либо при необходимости получения совокупности вложенных разбиений с возрастающим уровнем подробности. Цикл 1 может быть прерван по одному или нескольким первым разбиениям.
Классификация как определение составов взаимосвязанных кластеров всегда подразумевает возможность рассмотрения каждого кластера в роли объекта (например, при продолжении процесса восходящей классификации, при эквивалентировании генераторов и т.д.). Это снижает размерность задач исследования системы, но вносит погрешность в ее представление, так как система оказывается совокупностью уже не исходных, а агрегированных объектов (кластеров). Погрешность может быть измерена величиной различия объектов, принадлежащих кластеру, поскольку именно этими различиями мы пренебрегаем, когда рассматриваем кластер как
единый объект.
В [5, 52, 103, 105] предлагаются критерии качества классификации, основанные на усреднениях различий между классифицируемыми объектами. В качестве критерия предлагается использовать отношение В /Б усредненного по всем кластерам и
объектам внутри них внутрикластерного различия между объектами /) к усредненному "междукластерному" различию 5„_ как
среднему различию всех объектов, не принадлежащих одному и тому же кластеру.
Наиболее общая форма такого критерия может быть получена следующим образом. Если общее число классифицируемых объектов равно М, то число связей между ними будет N(N — 1)/2. Если
кластер / содержит М1 объектов, то он содержит и М1(М1
1)/2 связей между ними. Тогда при общем числе кластеров на
шаге классификации, равном К, общее число связей, содержащихся
к
внутри кластеров, будет 1/2^ М1(М1 - 1), а общее число связей,
