Диссертация (1137055), страница 4
Текст из файла (страница 4)
зависит от местоположения сравниваемых вариантов. В работе[10] для решения задачи ABC-анализа были предложены методы разбиения наоснове критерия сходства результирующей многомерной классификации срезультатами классификаций по каждому из критериев. Также к третьему типупринадлежат некоторые методы ранжирования с использованием информации опредпочтениях лица, принимающего решения (ЛПР) [22, 23, 24, 25, 26].
В работе[1] предложен расширенный вариант алгоритма к-средних, который используетметрику, учитывающую предпочтения ЛПР. В [27] ранжирование вариантов и ихобъединение в кластеры производится на основе матрицы парных сравненийвариантов. Также в работе [28] предлагается метод строящий ранжирующуюфункцию, на основе нелинейного общения метода главных компонент.Предлагаемый в диссертационной работе метод относится к методампервой группы, так как ранжирование достигается сверткой критериев спостоянными весами.
В основе метода лежит модель страт, параметрами которойявляются линейные веса, характеризующие ориентацию страт, и разбиение,задающее распределение объектов по стратам. В предлагаемой модели страты18являются параллельными гиперплоскостями, ортогональными вектору весовыхкоэффициентов.Сначала рассмотрим популярный метод первого типа, под названиемранжирование по влиянию (authority ranking), использующий линейную сверткувесов, получаемых с использованием собственного вектора, сродни подходу pagerank, используемому поисковой системой Гугл. Затем методы второго типа, т.е.ранжирование по несравнимым критериям: разбиение Парето (partition viamaximal elements), правило Борда [29] (Borda count), модифицированный метод ксредних (extended k-means) и метод порогового агрегирования.
И наконец, методлинейной оптимизации весов (linear weight optimization), который можно отнестик третьему типу в рассматриваемой классификации методов.1.1.1. Использование собственного вектораЭтот метод был предложен в [18] для построения ранжирования авторовнаучных публикаций, участвующих в различных конференциях, как дальнейшееразвитиеметодов,основанныхнавычислениисобственноговектора,соответствующего максимальному собственному числу определенной матрицысм., например, [30, 31, 32]. Правило, по которому строится ранг, опирается на дваположения:1.Объекты, имеющие высокий ранг, имеют высокую оценку покритериям с большими весами.2.Вес критерия тем выше, чем больше его значения для объектов свысокими рангами.Предположим, что объекты имеют ранг , а критерии имеют веса .Сформулированные положения могут быть представлены в виде системылинейных уравнений:19ri = xi1 w1 + xi2 w1 + ⋯ + xim wm , i = 1 … n{wj = x1j r1 + x2j r2 + ⋯ + xnj rn , j = 1 … m(1)В первых n уравнениях системы (1) исходные переменные заменимxijнормированными aij = ∑mj=1 xij.
Полученную из данных коэффициентов матрицуобозначим , а в оставшихся m уравнениях произведем замену = ∑=1 ,которые будут составлять матрицу . В матричном виде уравнения записываютсякак:r = Aw{w = Br(2)Подставляя из второго уравнения в первое, получаем, что искомый ранг являетсясобственнымвекторомматрицы,соответствующимеемаксимальному собственному значению, равному единице [18].1.1.2. Разбиение по ПаретоРассмотрим векторное отношение R «больше» такое, что для двухвариантов x, y ∈ X имеет место xRy если и только если xj ≥ yj для всех j, причемхотя бы одно неравенство строгое.
На каждом шаге находим множествонедоминируемых объектов x = {b ∈ X|∄y ∈ X: yRb} , которые объединяются вкласс C . Полученный класс исключается из рассмотрения, и процедураповторяется для оставшихся объектов \C пока множество X не пусто [33].Чтобы получить страты из слоев несравнимых по Парето объектов, можновоспользоваться идеей агломеративной кластеризации и расстояния до границыПарето. Заметим, что идея границ Парето использовалась также в [34] для задачиупорядоченной классификации (целевая переменная задана). Будем объединять20группы объектов, находящиеся близко друг к другу с точки зрения некоторойметрики ( , ), задающей расстояние между группами точек и . Чтобырасстояние между стратами было наибольшим, а расстояние внутри стратнаименьшим, необходимо найти две пары соседних классов, имеющихмаксимальное расстояние ( , +1 ) и ( , +1 ), затем построить страты 1 ={1 , 2 , … , }, 2 = {+1 , 2 , … , }, 3 = {+1 , 2 , … , }.Процедура получения страт из слоев недоминируемых по Парето вариантов:На входе: объекты = (1 , 2 , … , )На выходе: страты = {1 , 2 , 3 }1.
Найти разбиение Парето 1 , 2 , … , .2. Найти расстояния между соседними классами = ( , +1 ), = 1, … , − 1.3. Вычислить индексы = ( ), = ( ), > .4.Построитьстраты1 = {1 , 2 , … , },2 = {+1 , 2 , … , },3 ={+1 , 2 , … , }.В качестве функции расстояния между и можно взять одну изизвестных метрик:– single-link ( , ) = ((, )) , где ∈ , ∈ .– complete-link ( , ) = ((, )) , где ∈ , ∈ .– average-link ( , ) =1| || |∑ ∑ (, ) , где ∈ , ∈ .1.1.3.
Правило БордаДля каждого объекта xi вычисляются оценки по всем критериям ri (xj ) =|{xp ∈ X: xij > xpj , p ≠ i}| , то есть число альтернатив худших заданной порассматриваемому критерию. Затем итоговый ранг объекта xi подсчитывается каксумма оценок по всем критериям r(xi ) = ∑Mj=1 rj (xi ).211.1.4. Модифицированный метод к-среднихМетод, разработанный в статье [1] является модификацией известногоалгоритма кластеризации к-средних для стратификации. Модифицированныйметод к-средних использует функцию расстояния между объектами, основаннуюна структуре предпочтений:< P, I, J >, где отношения P – строгого предпочтения(асимметричное), – безразличия (рефлексивное и симметричное) и J –несравнимости (иррефлексивное и симметричное).
Структура предпочтенийсчитается заданной на множестве , если для любых двух элементов , из имеет место только одно из отношений: , , , . Чтобыопределить структуру предпочтений < , , >, часто используют информацию отЛПР о сравнении локальных предпочтений, включая методы AHP [35], см.
также[36], [37], ELECTRE [22], PROMETHEE [24]. Однако можно использовать ивекторное отношение больше.После того как предпочтения заданы, для каждого объекта строитсяпрофиль –( ) =< 1 ( ), 2 ( ), 3 ( ), 4 ( ) >, где:– 1 ( ) = { ∈ | } – множество вариантов, не сравнимых с .– 2 ( ) = { ∈ | } – множество вариантов, строго доминируемых .– 3 ( ) = { ∈ | } – множество вариантов, безразличных .– 4 ( ) = { ∈ | } – множество вариантов, строго доминирующих .Далее используя профиль каждого объекта, определяется расстояние между и :( , ) = 1 −∑4=1 | ( )∩ ( )|(3)Если задано множество объектов = {1 , 2 , … , }, то центром для Cназывается:(4)22с = (∑ ( , ))=1То есть центр – это тот элемент, до которого суммарное расстояние от всехдругих объектов в классе наименьшее. Для нахождения кластеров используетсяизвестный алгоритм к-средних, с той особенностью, что в качестве расстояниямежду объектами используется (3), а в качестве центра кластера - объект,удовлетворяющий (4).1.1.5.
Пороговое агрегированиеЕще одним методом агрегирования разнородных показателей являетсяметод порогового агрегирования [37, 38, 39]. Этот метод носит некомпенсаторныйхарактер, то есть низкие оценки по одним критериям не могут бытькомпенсированы высокими по другим, что в определенных ситуациях являетсяего преимуществом.
Другим его преимущество является то, что метод, в отличииот метода взвешенной суммы критериев, не требует обоснования возможностисуммирования и выбора весов.Правило порогового агрегирования позволяет вычислить индекс или рангобъекта связанный с этим правилом. Рассмотрим вычисление этого индексаподробнее. Для объекта = (1 , … , ) обозначим () количество рангов вкритериальном векторе , 0 ≤ () ≤ .
Рассмотрим отношение такое, что дляобъектов и имеет место , если найдется такой номер 0 ≤ ≤ , что () = () для всех номеров 1 ≤ ≤ − 1 и () < () . Отношение называется пороговым, а правило построения такого отношения называетсяпороговым правилом. Индекс альтернативы связанный с правилом пороговогоагрегирования:() = ∑ ,=1(5)23где и зависят от и равны:() = − () + − − 1,(6)() = ∑=1 (),(7)() = − .(8)1.1.6.
Оптимизация линейных весовПодход на основе линейной оптимизации весов был предложен в работе [9].применительно к задаче многокритериального ABC-анализа. Этот подходявляется развитием идеи оболочечного анализа [41]. Для того чтобы вычислитьранги,поочереднорешаетсязадачалинейногопрограммирования(9)относительно весов для каждого объекта :∑=1 → {∑=1 ≤ 1, = 1 … ≥ 0(9)Решая оптимизационную задачу (9), получаем весовые коэффициенты для каждого критерия, по которым вычисляются искомые ранги ri = ∑Mj=1 xij wij .1.2. Модель автоматической линейной многокритериальной стратификациии ее свойства1.2.1. Модель и пример линейной стратификации.Будем исходить из данных, представленных NM матрицей X=(xij), гдеi=1,2,…, N – индексы N объектов, а j=1,2,…, M – индексы M критериев.Агрегированный критерий ищется в виде выпуклой комбинации r=w1x1+w2x2+…+ wMxM=<w,x>, где w=(wj), x=(xj)- вектор-столбцы матрицы X, причем24∑=1 = 1 и ≥ 0, Положение страт k=1,2,…,K определяется значениями c1,c2…, cK на оси r.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
