Файл: Айвазян, С. А. Классификация многомерных наблюдений.pdf

понимается обобщенная средняя мера рассеяния, характеризующая класс Si. Числовой параметр г здесь, как и прежде, выбирается по ус­ мотрению исследователя.

Полагая

в один дает прирост величины п [/*к) (S)]r, непосредственно характе­ ризующей среднюю меру внутриклассового рассеяния, равный

А (п [/^ К ). Если же одновременно ориентироваться и на рост взвешен­ ной концентрации Z^S), то объединение кластеров естественно под­ чинить требованию минимизации величины

а\п(ПК)у]

АZ i(S )

ская комбинация функционала, характеризующего среднее внутри­ классовое рассеяние (3.20), и функционала, характеризующего меру концентрации полученной структуры (3.18), достигала бы своего экстремума. В качестве примеров можно привести комбинации Q (S)

92

и Q' (S), задаваемые формулами (3.16) и (3.17), а также более общие выражения вида

совое рассеяние l)K) (S*) или в двойственной подстановке: при задан­ ном пороговом значении / 0 найти разбиение S* с внутриклассовым

рассеянием l (rK) (S'*) =£7 /0 и наибольшей концентрацией ZT(5*).

г) Функционалы качества и необходимые условия оптимальност разбиения. Естественно попытаться проследить, в какой мере выбор того или иного вида функционала качества определяет класс раз­ биений, в котором следует искать оптимальное. Приведем здесь неко­

Таким образом, класс Sj (E) состоит из тех точек пространства X,. которые ближе к Ej, чем ко всем остальным Et (і Ф j). Если для не­ которых точек из X самыми близкими являются сразу несколько век­ торов Ej (/ = 1, ...,&), то мы относим эти точки к классу с минималь­ ным индексом.

Разбиение S = (Sx, ..., Sk) называется несмещенным разбиением, если это разбиение с точностью до множеств меры нуль совпадает с минимальным дистанционным разбиением, порождаемым векторами

/= і

1Здесь и в дальнейшем S, означает дополнение множества S, до всего про­ странства X, т. е. совокупность всех наблюдений (элементов пространства X), не входящих в состав Sj.

93.

разбиениях. Это означает, что оптимальное разбиение обязательно должно быть несмещенным.

У т в е р ж д е н и е 2: для функционалов от разбиений на два класса. Следующее утверждение относится к довольно широкому классу функционалов качества разбиения совокупности на два класса. Разбиение на два класса может быть задано с помощью так называе­ мой разделяющей функции. А именно, точки пространства X, на кото­ рых разделяющая функция принимает неотрицательное значение, относятся к одному классу, а остальные — к другому. Поэтому поиск класса оптимальных разбиений в этом случае эквивалентен поиску класса оптимальных разделяющих функций.

Для иллюстрации дальнейшего изложения будем рассматривать вероятностную модификацию функционала Q' (3.14).

Пусть расстояние р (X, Y) задается с помощью соотношения (3.3) потенциальной функцией вида

К(Х, ¥)=-- I! Я?Фі(Х)Фі(У),

і= 1

где фі (X) (г = 1, ..., N) — некоторая система функции на X. Функционал Qj через потенциальную функцию К (X, Y) выража­

ется следующим образом:

Q’a(S) = 2 [ K ( X , X ) P ( d X ) - 2 ± SS K ( X . Y ) P ( d X ) P ( d Y ) -

X И 1 s,s,

- 2 - J - S ü K(X,Y)P(dX)P(dY).

Fi s2s„

Поскольку в правой части этого равенства первый интеграл не зави­ сит от разбиения, то минимум функционала Q' (5) достигается на тех разбиениях, на которых функционал

достигает максимума.

Введем в рассмотрение спрямляющее пространство Z, коор­

.94

функций в спрямляющем пространстве Z, среди которых следует ис­ кать разделяющую функцию, доставляющую экстремум функционалу качества разбиения. А именно, показано, что если функционал ка­

чества Ф является дифференцируемой функцией от М(г-Ѵ) (ѵ =1, ..., г),. а вероятностное распределение Д 2* сосредоточено на ограниченном множестве Z и обладает непрерывной плотностью, то если экстремум функционала Ф достигается на некоторой разделяющей функции,, то этот же экстремум достигается на разделяющей функции, являю­ щейся полиномом г-й степени вида:

f(Z)= І (сѵ, г*),

ѵ = і

где

дФ _ дФ дш[ѵ) ам^ѵ) ’

а (сѵ, Zv), означает при четном ѵ произведение чисел сѵ и Zv, а при не­ четном V — скалярное произведение векторов сѵ и Zv.

Для функционала Q' сформулированное означает, что класс раз­ деляющих функций, среди которых надо искать наилучшее в спрям­ ляющем пространстве разбиение, имеет вид

Класс разделяющих функций в спрямляющем пространстве очевидным: образом определяет класс разделяющих функций в исходном простран­ стве X.

Если К (X , Y) = (X, Y) является скалярным произведением век­ торов X и Y, то спрямляющее постранство Z совпадает с исходным

95.