Принятие решений

Оценим число однородных пар по ОВР. На гистограмме ОВР фиксируем первый СЗЛМ (нумерация идет слева направо), на рис. 2.22 первый СЗЛМ обнаруживается на отрезке [rq, rq+1]. Очевидно, все r(i) ОВР, которые удовлетворяют неравенству r(i) £ rq, i = 1, 2, …, i0, являются расстояниями между точками однородной пары. Тогда число однородных пар, оцениваемое по ОВР, равно i0, 31 src="images/referats/23403/image209.png">.

Учитывая, что в ОВР входят лишь все те элементы матрицы (2.36), которые стоят выше ее главной диагонали, имеем

, (2.43)

n в правой части (2.43) – это число однородных пар вида (Xi, Xi), i = 1, 2, …, n. В силу равенств (2.42), (2.43) имеем

. (2.44)

Найдем через априорные вероятности классов p1, p2, …, pk.

pi ³ 0, . (2.45)

Вероятность того, что произвольная пара точек (Xi, Xj) однородна и обе точки Хi, Хj принадлежат одному какому-то классу ws, s Î{1,2,…, k}, равна ps2. Тогда вероятность того, что произвольная пара точек (Хi, Хj) однородна, равна . Функция обладает тем свойством, что ее минимум при условиях (2.45) равен 1/k и достигается в точке p1 = p2 = … = pk = , .

Тогда имеем

(2.46)

На основании соотношений (2.44), (2.46) получим

,

или в целочисленном виде

, (2.47)

где d – некоторое малое положительное число, E[Y] – целая часть Y.

Неравенства (2.41), (2.47) оценивают число классов снизу. Дадим для числа k оценку сверху через число инвариантных пар.

Определение 2.5. Пара точек (Хi0, Хj0) инвариантна, если каждая из них является ближайшей соседней точкой для другой.

,

.

Каждое множество точек имеет хотя бы одну инвариантную пару. Например, в множестве X(n) инвариантной является та пара точек, расстояние между которыми равно r(1), r(1) – первый член ОВР этого множества. Каждый класс wS Ì X(n), s = 1, 2, …, k, имеет хотя бы одну инвариантную пару точек. Если ninv – число инвариантных пар множества X(n), то для числа его классов k имеем

k < ninv. (2.48)

Эксперименты показали, что каждый класс имеет не менее одной инвариантной пары точек и число инвариантных пар ninv растет с увеличением элементов n множества X(n), составляя от него 25–30%. Так что оценка (2.48) удобна лишь при небольших значениях n, n £ 30.

Отметим, что оценки для числа классов (2.41), (2.47), (2.48) можно использовать и в одномерном случае, если на данном множестве (2.32) предварительно задать подходящую метрику и построить гистограмму его ОВР.

Локальные минимумы гистограммы ОВР могут порождаться существованием в множестве X(n) как классов, далеко отстоящих друг от друга, так и классов с резко различающимися плотностями точек (РРПТ). Поэтому для корректного использования оценок для (2.41), (2.47) необходимо разделить множество X(n) на такие подмножества, в которых классы имеют статистически равные плотности точек.

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

Определение 2.6. Вариационный ряд минимальных расстояний ВРmin – это упорядоченное по возрастанию множество минимальных расстояний {ri min}, i = 1, 2, …, n, .

Для обнаружения классов с РРПТ при больших значениях n (n ³ 30) строится гистограмма ВРmin. Если на этой гистограмме наблюдается хотя бы один СЗЛМ или «длинный хвост», то множество X(n) содержит классы с РРПТ (рис. 2.27, 2.24).

Обнаружить классы с РРПТ можно и другим способом, применимым и для малых значениях n. Рассматривается последовательность отношений

. (2.48)

Если в последовательности (2.48) есть элементы, удовлетворяющие соотношению

, i = 1, 2,…, n – 1, (2.49)

то множество Х(n) содержит классы в РРПТ. Если неравенство (2.49) выполняется t раз, то множество Х(n) имеет не менее t + 1 классов с РРПТ,

k ³ t + 1.

В этом случае для дальнейшего исследования структуры множества Х(n) его необходимо разделить на t + 1 подмножеств с почти равными плотностями точек. Каждое из этих подмножеств может быть объединением классов.

 Скачать реферат