Tags: субъект претенденты множество признаков

Постановка задачи
Классификация множеств признаков
Идентификация субъекта по сумме одинаковых оценок признаков
Средневзвешенная оценка веса признаков
Последовательный попарный отбор претендентов на сходство
Отбор претендентов на сходство по круговой системе
Оценка признака на основе треугольного закона распределения
Полезные ссылки

Постановка задачи

На сайте рассмотрено решение двух задач:

Общее в этих задачах — определить субъекта среди претендентов на сходство с ним по множеству признаков.

Допустим, у нас есть 1 субъект и 20 претендентов на сходство с ним. Для определения сходства субъекта с одним из претендентов используются 10 признаков.

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

Претенденты характеризуются в базе данных средним значением (математическим ожиданием) и доверительным интервалом по каждому из признаков. Субъект характеризуется только лишь средним значением по каждому признаку.

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

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

Классификация множеств признаков

Множества признаков в зависимости от взаимного расположения признаков на шкале их значений можно разделить на множества сильных (1), слабых (2) и смешанных (3) признаков.

Силу признака можно оценить отношением D/d, где d — допуск признака; D — расстояние между соседними средними значениями признаков. Сильными считаются признаки, допуски значений которых не перекрываются (D/d> 2)

Идентификация субъекта по сумме одинаковых оценок признаков

Степень сходства между субъектом и каждым из 20 претендентов определяется суммой баллов набранных по всем 10 признакам. Вес каждого признака назначаем 1 балл. Выбор призеров-победителей из 20 осуществляется по наибольшей сумме набранных баллов.

Если значение признака субъекта находится в пределах доверительного интервала соответствующего признака претендента (признак обозначен прямой P), то к общей сумме баллов добавляется единица, в противном случае единица отнимается.

Если 10 признаков претендента совпадают с 10 признаками субъекта, то претендент набирает максимальную сумму баллов (10). Минимальная сумма баллов — (-10).

Этот метод сравнительно прост. Недостаток метода — победитель может точно определяться только лишь в случае множества сильных признаков.

Средневзвешенная оценка признаков

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

Из этих 20 объектов берем первый субъект и определяем, сколько есть претендентов из этой же выборки на совпадение по первому из его признаков.

Если значение признака субъекта находится в пределах доверительного интервала соответствующего признака у претендента, считаем, что признаки совпадают.

Если претендентов по признаку в обучающей выборке не оказалось (кроме самого субъекта), то оценка достоверности признака 1. Если признак совпал со всеми 20 претендентами(включая субъекта), то оценка признака 0. Если совпадение по признаку отмечено для 15 (включая субъекта) из 20 претендентов, то оценка признака определяется из сохранения отношения катетов подобных треугольников:

w = (20-15)/(20-1)=0.26

В цикле (20 итераций) из этих же 20 объектов берем следующего субъекта и по нему определяем оценку того же признака. По 20 значениям определяется среднее значение оценки признака.

Во внешнем цикле (10 итераций) аналогично определяются средние значения оценок каждого из 10 признаков.

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

Преимущества метода. Поскольку оценки признаков определяются еще «до соревнования», решение о степени сходства субъекта со всеми претендентами принимается за один «тур соревнований».

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

Последовательный попарный отбор претендентов на сходство

В предыдущем разделе степень сходства субъекта со всеми претендентами определялась «за один тур соревнований». В этом разделе описывается отбор через множества туров.

Так называемая олимпийская (или кубковая) система отбора, при которой участник выбывает после поражения. При ничейном результате назначаются дополнительные условия («overtime, пенальти или жребий»), либо остается победитель предыдущей пары (правило из бокса — при ничьей чемпионом остается действующий чемпион, а не претендент на это звание).

Из 20 претендентов выбираем первых 2-х. Определяем, какой из них наиболее соответствует субъекту. Для этого проводим проверку по каждому из 10 признаков.

Если по признаку проходит лишь один претендент, то к его сумме баллов прибавляется 1 балл («забитый мяч»), от суммы его противника 1 бал отнимается.
Если по признаку проходят оба претендента, то к сумме баллов обоих претендентов прибавляется 0 балла.
Если по признаку не проходят оба претендента, от суммы баллов обоих претендентов отнимается по одному баллу (-1).

Один и тот же признак может быть сильным для одной пары претендентов и слабый для другой. На рисунке красной линией отмечено значение признака субъекта и показаны допуски признака для 3-х претендентов.

Для пары претендентов слева признак слабый (D1/dmax < 2, где dmax — большее из значений допусков пары). К сумме баллов обоих претендентов прибавляется по 0.5 балла.

Для пары из крайнего левого и правого претендентов признак сильный (D2/dmax > 2). К сумме баллов левого претендента прибавляется 1 балл, от суммы его конкурента 1 бал отнимается. Аналогичные рассуждения для пары среднего и правого претендентов.

Выбирается победитель пары, который набрал наибольшую сумму балов по всем признакам.

Далее победитель пары соревнуется со следующим (3-м) претендентом из 18 оставшихся. Цикл (19 итераций) продолжается, пока не будут рассмотрены все 20 претендентов.

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

В чем преимущество этого метода по сравнению с предыдущим? Вес слабых признаков распределяется между конкурирующей парой претендентов, а не усредняется для всех претендентов (см. Определение веса признаков на основе обучающей выборки). Это обеспечивает более точный отбор победителя из пары, а также всей совокупности претендентов.

В чем недостатки метода?

Большое количество «туров соревнований» по сравнению с предыдущим методом.
Этот метод позволяет выбрать только одного победителя из всех претендентов — нет занявших второе и третье места.

Отбор претендентов на сходство по круговой системе

В спортивных состязаниях по олимпийской системе отбор призеров, занявших второе и третье место, весьма субъективен, поскольку реальные претенденты на второе и третье места могут быть исключены потенциальным победителем на ранней стадии отбора. Альтернативой «Олимпийской системы» может быть «Круговая система», которая предусматривает розыгрыш мест при проведении матчей между всеми участниками соревнования.

Правила отбора победителя по КРУГОВОЙ СИСТЕМЕ следующие:

За победу в туре победитель получает одно очко, у проигравшего очко вычитается.

При ничьей в туре оба претендента получают 0 очков.

При равном количестве «очков в турнирной таблице» у нескольких претендентов победитель может определяться общей суммой баллов, по которым он прошел весь турнир отбора (по аналогии с «разницей забитых и пропущенных мячей» в футболе).

Используя такую систему в нашей задаче можно оценивать степень сходства претендентов с субъектом по результатам в «турнирной таблице». Победитель выбирается более точно по сравнению с предыдущим методом, поскольку уменьшается влияние субъективных факторов — например, ничейный результат или удачное совпадение сильных признаков у пары претендентов. Победителей может быть несколько, например — которые заняли с первого по третье место.

Недостаток круговой системы — существенно возрастает количество «туров соревнований».

Оценка признака на основе треугольного закона распределения

В методе попарного отбора претендентов на сходство вес слабого признака, по которому проходят оба претендента, распределялся поровну (0.5 бала). Уточним этот метод за счет распределения веса в зависимости от положения значения признака субъекта в пределах допусков признаков претендентов.

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

Треугольник имеет единичную площадь, которая определяет вероятность попадания в допуск признака. Основание треугольника равно 2 дельта , где дельта — доверительный интервал, x – смещение признака субъекта относительно центра распределения вероятностей. Высота h сечения треугольника прямой p определяет вероятность попадания субъекта в допуск признака претендента.

Долю балла, определяем следующим образом. Если х=0, то претендент получает максимум, т.е. 1 балл. Если х не равен 0, тогда определяем долю балла отношением h к высоте треугольника:

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

А теперь рассмотрим, как распределить весовую оценку признака, если есть два претендента на один признак.

Оба треугольника имеют единичную площадь. Высота h сечения треугольника прямой p для обоих треугольников различна. Она зависит не только от места расположения прямой в пределах треугольника но и величины допуска.

Вес признака распределяется пропорционально размерам h треугольников. Этот размер определяется из соотношения:

Доля бала каждого претендента определяется из выражения:

Выводы:

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

Далее см. Идентификация по множеству признаков при помощи нейросети

Полезные ссылки:

Автор: Николай Свирневский