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

Первая процедура [77] состоит в том, что для каждой точки Х£ис­

радиуса г с центром в точке Х г. После этого можно, задавшись некото­ рым порогом с, выбрать все точки X, с плотностью

!( Хі )> с.

Многие кластер-процедуры целесообразно применять сначала лишь к тем точкам совокупности, которые удовлетворяют этому условию. Остальные совокупности по некоторому правилу затем разносятся по уже сформированным классам.

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

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

— упорядочение по принципу принадлежности «соседей» к одному классу. В работе [10] прежде чем пользоваться агломеративной иерар­

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

128

другого класса и т. д. Причем на границе между классами величина r ( S i , S i _ 1 ) будет резко убывать. Поэтому это переупорядочивание можно использовать для получения некоторого начального разбиения перед применением алгоритма, что и делается в [10]. При этом, как ука­ зано в [10], уменьшается и время счета, описанного в этой работе алго­ ритма. Кроме того, с помощью описанной процедуры можно предвари­ тельно оценить число классов разбиения, следя за скачками функции

г (Si, S £_х), [31, стр. 124].

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

§ 4. КЛАССИФИКАЦИЯ ОБЪЕКТОВ, ОПИСЫВАЕМЫХ НЕ ТОЛЬКО КОЛИЧЕСТВЕННЫМИ ПРИЗНАКАМИ (АКСИОМАТИЧЕСКИЙ ПОДХОД; ОБРАБОТКА ЭКСПЕРТНЫХ МНЕНИЙ)

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

1)количественные — если значениями признака являются числа (например, возраст, заработная плата и т. д.);

2)ранговые (качественные) — если значения признака не являют­ ся числами, но характеризуют различную степень проявления этого признака. То есть между значениями признака имеется естественное упорядочение (например, квалификация изменяется от «высокой» до «низкой», степень удовлетворенности своей работой и т. д.);

3)номинальные (классификационные) — если значения признака не являются числами и не связаны естественным упорядочением (на­ пример, профессия, причина выезда из данного города и т. д.).

При исследовании объектов с ранговыми признаками обычно каж­ дому значению приписывается некоторый балл. Применение к таким балльным признакам общих кластер-процедур и связанное с ними при­ менение к балльным признакам арифметических операций требует, вообще, говоря, обоснования в каждом конкретном случае. Разработка этих обоснований еще только начинается [23].

Еще сложнее обстоит дело с обработкой номинальных признаков. Иногда значениям номинальных признаков приписывают баллы или эвристические показатели в соответствии с какой-либо содержательной гипотезой или мнениями экспертов.

Вработах [19] — [22] предложен возможный путь создания аппара­

та обработки признаков любого типа и намечены применения этого аппарата к задачам кластер-анализа.

Будем считать, что каждый из р измеряемых признаков объекта при­

сти на піі групп. А именно, для элементов из одной группы разбиения S (i>значение г-го признака одно и то же.

Задача разбиения совокупности объектов на группы на основе р измеряемых признаков может быть поставлена теперь следующим образом: по данным разбиениям St1), ..., Soo построить разбиение S исследуемой совокупности, наиболее «близкое» ко всем «однопризна­ ковым» разбиениям (или наиболее «согласованное» со всеми однопри­ знаковыми разбиениями).

Понятие разбиения наиболее «согласованного» с несколькими раз­ биениями, может возникнуть и в других ситуациях [2]. Например, допустим, что в результате применения нескольких алгоритмов или в результате опроса нескольких (т) экспертов получено несколько раз­ биений S*1), S<2), ..., S (m) совокупности из п объектов. Нужно найти разбиение S, которое в некотором естественном смысле было бы наи­ более согласовано со всеми ими, являясь их «концентрированным» выражением.

В простейшем случае, когда число заданных разбиений мало, по сравнению с числом исследуемых объектов, часто в качестве согласо­

Іт€ [ ^ >• ■• > ^ml■

Здесь kj — число классов в разбиении S (0.

Однако, как правило, подобного рода согласованные разбиения не представляют практического интереса, так как оказываются в боль­ шинстве случаев малосодержательными и слишком дробными: общее число k различных классов такого разбиения, как легко подсчитать, может достигать величины k2 ... km. Поэтому рассмотрим другие подходы к определению единого согласованного разбиения.

В общем случае принцип согласования исходных разбиений опре­ деляется заданием некоторой функции F (St1), ..., S W ) со значения­ ми в пространстве разбиений, т. е. правилом построения S по данным разбиениям St1), ..., S W . В случае, когда мы ограничиваемся лишь упорядоченными разбиениями1 S, St1), ..., S<m), Эрроу [34] сформули­

1 Разбиение S = { . . . , S^] называется упорядоченным, если задано пра­ вило линейного упорядочения классов S; (считается, что нумерация классов соот­ ветствует этому упорядочению). Очевидно, числовые и ранговые признаки опре­ деляют упорядоченное разбиение.

130

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

В[20] рассматривается применение метода Эрроу к случаю, когда

иаргументы функции F и ее значения не упорядочены. Показано, что естественные требования (аналогичные аксиомам Эрроу) приводят к пе­ ресечению разбиений как единственному принципу согласования. В на­ иболее часто встречающихся ситуациях, когда число классов согласо­ ванного разбиения ограничено заранее, в [20] доказана теорема о не­ возможности выбора согласованного разбиения. Можно показать, что при некотором смягчении требований к функции F , а именно, при отказе от одной из приведенных в [20] пяти аксиом, общий вид согласованного разбиения, содержащего не более чем k классов, задается следующей

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

Более плодотворным подходом к решению задачи выявления единого согласованного разбиения объектов на классы нам представляется под­ ход, основанный на понятии «расстояния между разбиениями», обсуж­ даемый, в частности, в [19] — [21]. Остановимся на нем несколько под­ робнее. Пусть с каждым разбиением S связана квадратная булева матрица {S^ >} (і, / = 1, ..., п) следующим образом: если S — не­ упорядоченное разбиение, то S ‘>= 1 тогда и только тогда, когда объ­ екты Х і и Xj лежат в одном классе разбиения, а если S — упорядочен­ ное разбиение, то SiJ = 1 тогда и только тогда, когда объект Хг на­ ходится в классе, совпадающем или предшествующем классу объекта X j . Упорядоченным разбиениям ставятся в соответствие блочно-тре­ угольные, а неупорядоченным — блочно-диагональные булевы матриц.

О п р е д е л е н и е . Расстоянием d (SW, SW) между разбиениями SW и SW называется функция, удовлетворяющая некоторым естест­ венным требованиям (аксиомам).

А к с и о м а 1. Расстояние d (SW, SW) обладает следующими свой­ ствами геометрического расстояния:

исключением множества Е, являющегося объединением некоторых подклассов и в разбиении S W и в разбиении SW , то d (SW , SW ) вы­ числяется так, как если бы рассматривались лишь разбиения множе­ ства Е.

А к с и о м а 4. Эта аксиома задает масштаб измерения — макси­

Тогда в качестве единого согласованного разбиения относительно заданного набора S W , ..., S<m) можно использовать, например, так называемую медиану S<med>, определяемую соотношением

где H — некоторое множество допустимых разбиений (упорядоченных или находящихся «между» заданными и т. п.).

В [20] автор обращает внимание читателей на опасность универ­ сальности расстояния (3.37), используемого как для упорядоченных, так и для неупорядоченных разбиений. В случае большого объема ис­ следуемой совокупности (п — велико) и малого числа классов k ин­ формация об их упорядочении невелика, в то время как значение функ­ ции расстояния может зависеть очень сильно от того, упорядочено раз­ биение или нет. Например, если SW — неупорядоченное разбиение, а SW получено из него упорядочением классов, то d (SW, SW) может достигать значения п/8.

Переформулируем понятия «расстояния» и «между» для разбиений

132