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

3. Анализ одномерной гистограммы расстояний между всеми различными точками данного множества. Рассмотрим этот метод подробно.

На множестве x(n) в (2.28) задается подходящее расстояние r (метрика) и находятся расстояния между всеми его точками rij = r(xi, xj), i, j = 1,2, …, n, которые можно записать в виде квадратной матрицы

. (2.36)

В силу свойств расстояния имеем rii = 0, rij= rji, i, j = 1, 2, …, n.

Поэтому в матрице (2.36) достаточно исследовать множество элементов, стоящих выше или ниже главной диагонали, например

. (2.37)

Упорядочив элементы множества (2.37) по возрастанию, получим основной вариационный ряд (ОВР) множества X(n)

r(1) £ r(2) £ … £ r(s), (2.38)

Сначала предположим, что плотности классов множества Х(n) статистически равны, т.е. отличаются незначительно. Очевидно, если множество Х(n) имеет классы, далеко отстающие друг от друга, то гистограмма его ОВР имеет хотя бы один СЗЛМ.

Определение 2.3. Пара точек однородна, если эти точки принадлежат одному какому-то классу ws, Xi, Xj Î ws, s Î{1,2, …, k}.

Определение 2.4. Пара точек (Xi, Xj) неоднородна, если эти точки принадлежат разным классам, Xi Î ws, Xj Î wt, s = t, s, t Î{1,2, …, k}.

На рис. 2.19 изображено множество Х(n), состоящее из трех классов, далеко отстоящих друг от друга. Гистограмма ОВР множества Х(n) имеет один СЗЛМ (рис. 2.20), наблюдаемый на отрезке [rq, rq+1].

Расстояние между точками каждой однородной пары меньше расстояния между точками каждой неоднородной пары ,

< ,

так что некоторая точка отрезка [rq, rq+1] является границей множеств расстояний между точками однородных пар {} и неоднородных пар {}. Левый конец отрезка [rq, rq+1] можно считать оценкой (приближенным значением) наибольшего диаметра классов dmax,

. (2.39)

На рис. 2.21. представлено множество Х(n), состоящее из трех классов, далеко отстоящих друг от друга. Гистограмма ОВР такого множества имеет два СЗЛМ (рис. 2.22). Первый СЗЛМ (нумерация идет слева направо) наблюдается в промежутке [rq, rq+1]. Расстояние между точками почти каждой однородной пары лежит на отрезке [r1, rq], а расстояния между точками каждой неоднородной пары лежат на отрезке [rq+1, r(s)], причем на отрезке [rq+1, ru] находятся расстояния между точками из классов w1, w2 и w2, w3, а на отрезке [ru+1, r(s)] – расстояния между точками из классов w1, w3.

Можно привести пример, когда гистограмма ОВР множества Х(n), состоящего из трех далеко отстоящих друг от друга классов имеет три СЗЛМ.

Если данное множество Х(n) однородно или состоит из классов, близко расположенных друг другу (рис. 2.23), то гистограмма его ОВР не содержит ни одного СЗЛМ и имеет вид, аналогичный представленным на рис. 2.15, 2.18. Из наших рассуждений делаем следующие выводы:

1. Если гистограмма ОВР данного множества Х(n) имеет хотя бы один СЗЛМ, то в этом множестве есть классы, далеко отстоящие друг от друга, и оценка наибольшего диаметра таких классов определяется равенством (2.39).

2. Если гистограмма ОВР данного множества Х(n) не имеет ни одного СЗЛМ, то это множество однородно или состоит из классов, близко расположенных друг к другу.

3. Если гистограмма ОВР имеет «длинный хвост», то множество Х(n) содержит резко выделяющиеся наблюдения (рис. 2.24), которые можно считать классами с малым числом элементов (рис. 2.25).

Отметим, что исследование структуры множества Х(n) по ОВР можно проводить и в одномерном случае, предварительно задав на этом множестве подходящую метрику.

Полагаем, что классы исследуемого множества имеют статистически (почти) равные плотности точек, а на гистограмме ОВР этого множества наблюдается хотя бы один СЗЛМ (рис. 2.22).

Оценим число классов k множества Х(n) по числу СЗЛМ гистограммы его ОВР. Пусть - число наблюдаемых СЗЛМ на гистограмме ОВР, а m – максимальное число СЗЛМ этой гистограммы, которое обусловлено наличием k классов, далеко отстоящих друг от друга. Очевидно,

.

Тогда

.

Решая это квадратное неравенство, получим

. (2.40)

Переходя в неравенстве (2.40) к целочисленным решениям, получим

, (2.41)

где e – малое положительное число, Е[Y] – целая часть Y.

Оценку снизу для числа классов можно получить другим способом, по числу однородных пар. Число пар точек множества Х(n) равно n2, пусть n0 – число его однородных пар. Тогда оценка вероятности того, что произвольная пара (Xi, Xj) точек множества Х(n) однородна, равна

. (2.42)

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