Теоремы о вычислении оценок

 

Из анализа этапов задания алгоритмов вычисления оценок следует, что эффективность применения этих алгоритмов во многом зависит от того, насколько часто решается задача подсчета голосов (S).

Рассмотрим теоремы, позволяющие успешно решать эту задачу.

1. Примем в качестве системы опорных множеств совокупность всех подмножеств множества { 1,2,…,n } мощности k.

2. Функцию близости зададим следующим образом:

r( S, Sq) =

Положим также, что

Г(S1,Sq) = r( S, Sq);

() = Г(S1,Sq); (S) = ()

Используем решающее правило

F[ (S), (S),…, (S)] =

Таким образом, мы описали трёхпараметрическое семейство алгоритмов (зависимых от параметров k, , ).

Предположим, что признаки принимают значения 0, (бинарные) и обозначим через (S1,Sq) число совпадающих столбцов в строках S и Sq (( (S1,Sq)= n - (S1,Sq), где - есть расстояние Хемминга); тогда справедлива следующая теорема:

Теорема 1. Число голосов, поданных строкой за класс , равно

(S) = (3.1)

Доказательство теоремы 1. Из определения алгоритма следует, что

 

(S) = ( S, Sq) = ( S, Sq) (3.2)

Вычислим величину

( S, Sq)

Напомним, что множество есть совокупность всех подмножеств мощности k множества { 1,2,…,n }. Строки S и Sq совпадают на (S1,Sq) разрядов. Величина ( S, Sq) отлична от нуля в том и только том случае, когда единичные координаты вектора будут находиться среди (S1,Sq) совпадающих разрядов строк S1 и Sq. Очевидно, что число векторов, удовлетворяющих этому условию, будет равно .

Поэтому

( S, Sq) = (3.3)

Из (3.2) и (3.3) легко следует доказательство теоремы.

2. Сохранив все другие условия п.1, примем в качестве системы опорных множеств совокупность всех непустых подмножеств { 1,2,…,n }. В этом случае имеет место следующая теорема.

Теорема 2. Число голосов, поданных строкой за класс , равно

(S) =

Доказательство теоремы 2. Обозначим через систему всех подмножеств мощности k множества { 1,2,…,n }.

Очевидно

=

Как и в теореме 1, имеем

(S) = ( S, Sq) = ( S, Sq)

Кроме того,

( S, Sq) = ( S, Sq) (3.4)

Учитывая (3.3) и свойства коэффициентов бинома Ньютона, получим

 

( S, Sq) = = + +…+ =

Подставив последний результат в (3.4), приведем к доказательству теоремы.

3. Пусть признаки принимают значения из числового отрезка [а,в] либо каждый j-й признак имеет свой отрезок значений [аj,вj]. Для каждого из таких признаков введем порог точности (некоторые заданные положительные числа).

Две строки = (, ,…, ) и

= (, ,…, )

будем считать похожими, если

| - | ; | - | ;…;| - | (3.5)

В качестве системы опорных множеств возьмем совокупноссть всех подмножеств множества { 1,2,…,n } мощности k.

Возьмем расстояние (S1,S2), равное числу невыполненных неравенств (3.5). Для заданных условий справедлива следующая теорема:

Теорема 3. Число голосов, поданных строкой S за класс равно

(S) =

Доказательство этой теоремы полностью аналогично доказательству теоремы 1.

4. Пусть выполняются все условия теоремы 3, но в качестве системы опорных множеств рассматривается совокупность всех непустых подмножеств множества { 1,2,…,n }. В этом случае имеет место

Теорема 4.

(S) =

Справедливость теоремы 4 доказывается аналогично доказательству теоремы 2.