Selection of features into the object's own space based on the measure of its compactness.pdf Понятие «собственное пространство объекта» связанно с принятием решения. Принятие решения зависит от закономерностей (как правило, скрытых), которые наиболее точно передают особенности объекта. В [1] эти особенности было предложено искать в виде логических закономерностей в окрестности объекта. Аргументом в пользу такого подхода служило отсутствие машинных алгоритмов, позволяющих производить поиск логических закономерностей за приемлемое время. Отбор информативного набора признаков в окрестности объекта и вычисление индекса здоровья (оценки объекта) по нему рассматривался в [2]. В качестве критерия для отбора использовался поиск максимума разности частоты встречаемости представителей двух классов по системе вложенных гипершаров. Центром гипершаров являлся рассматриваемый объект. Выбор эвристик для построения алгоритмов распознавания образов основывается на гипотезе о компактности объектов классов. Общепринятого определения меры компактности не существует [3]. Показано [4], что в метрических алгоритмах классификации компактность зависит от многообразия структур отношений между объектами классов. Различаются между собой и численные методы для количественного оценивания компактности. В одномерном случае для оценивания используются интервальные методы, в многомерном - вычисление меры компактности объектов классов и выборки в целом по заданной метрике. Общим для одномерного и многомерного случаев является наличие областей признакового пространства, в границах которых вычисляется мера компактности. В одномерном случае на числовой оси можно производить сравнение объектов по значениям их исходных и латентных признаков, используя отношения «больше», «меньше» или «равно». При вычислении меры компактности в многомерном случае [4] применялось отношение связанности объектов по подмножеству (оболочке) граничных объектов классов по заданной метрике. Связанность объектов Si, Sj рассматривалось как свойство логических закономерностей в форме гипершаров, центрами которых они являлись. Объекты Si и Sj считались связанными, если в пересечении их гипершаров были объекты оболочки. Связанность объектов применялась для анализа кластерной структуры классов с помощью меры компактности. Для вычисления меры компактности в (0; 1] использовались число непересекаю-щихся групп и количество объектов, в них входящих. Отбор информативных признаков на основе методов кластеризации рассматривался в [5]. Использовалось разбиение признаков на группы, и в каждой группе выделялось по одному наиболее типичному представителю. Результаты группировки существенно зависели от вводимой меры расстояния между признаками. 55 Н.А. Игнатьев, А.И. Мирзаев В [6] в качестве критерия информативности признаков применялась функция конкурентного сходства (FRiS-функция). Среднее значение функции конкурентного сходства зависит от того, как близко группы объектов находятся от разделяющей границы. Те объекты, которые располагаются в тесном окружении своих объектов и значительно удалены от объектов других классов, имеют более высокое значение функции, чем периферийные объекты, близкие к другим классам. Отбор информативных признаков позволяет сделать прозрачным способ построения решающих правил и количественно оценить компактность классов. При реализации алгоритмов отбора информативных наборов признаков объекта необходимо учитывать: - наличие или отсутствие свойства инвариантности признаков к масштабам измерений; - выбор меры близости между объектами со свойствами метрики; - наличие шумовых объектов в выборке и способов их обнаружения; - истинность отношения связанности объектов классов; - выбор способа вычисления меры компактности объекта класса. В работе определяется бинарное отношение связанности объектов одного отдельно взятого класса обучающей выборки. Это отношение используется для вычисления меры компактности объекта класса с целью отбора признаков в его собственное пространство. Мера компактности рассматривается в качестве индекса объекта по определяемому набору признаков и служит средством для поиска скрытых закономерностей в базах данных. 1. Постановка задачи Одной из целей анализа кластерной структуры данных в [4] через отношение связанности объектов классов было решение задачи о минимальном покрытии обучающей выборки объектами-эталонами. Объекты каждого класса разбивались на непересекающиеся группы. Отношение связанности объектов гарантировало единственность числа групп и их состава. Поиск объектов-эталонов минимального покрытия производился по каждой группе в отдельности. Среднее число объектов выборки, притягиваемых одним эталоном, использовалось как показатель обобщающей способности алгоритма распознавания. В идеале отдельно взятый объект выборки мог быть единственным эталоном всего класса. Научный и практический интерес представляет оценка вклада объекта в обобщающую способность. Количественная мера компактности объекта зависит от структуры его отношений с другими объектами обучающей выборки. Среди факторов, влияющих на оценку структуры, особое значение имеет размерность признакового пространства [7] и расстояния между объектами по заданной метрике ρ(x, y). С этими факторами связано такое понятие, как «проклятие размерности пространства» [8]. Задача вычисления меры компактности объекта в рамках его собственного признакового пространства формулируется так. Считается, что задано множество объектов Eq = {S1, ..., Sm}, разделенное на непересекающиеся классы K1 и K2. Описание объектов производится с помощью набора из n разнотипных признаков: X(n) = (xi, _ , Xn), ξ из которых измеряются в интервальных шкалах, (n - ξ) - в номинальной. На множестве объектов Еq задана метрика ρ(x, у). Пусть = ρ (Si, S,) = min ρ (Si, S-) - расстояние от Sd ≡ Kt, t = 1, 2, до ближайшего (граничноd d u Sj∈Kt-t d j t-t го) объекта Su ∈ K3-t, Γ(Kt, р) - множество граничных объектов класса K3-t. Обозначим через O(.Sd,ρ) = = {Si ∈ Kt∣ρ(Si, Sd) < rd} и Z(Sd, р) = {Si ∈ O(Sd, ρ)∣ρ(Si, S*) ≤ rd}, S* ∈ Γ(K, р). Объекты Sd, Su ∈ Kt считаются связанными, если O(Su,ρ) n Z(Sd,ρ) ≠ 0. Компактность объекта Sd ∈ Kt на наборе X(k) X(n), к ≤ n, вычисляется как Q,(X(k)) = ∣{S, ∈Kt∣O(S,,р)nZ(Sd,ρ)≠0∣/Ktl. (1) Очевидно, что 0 < θd(X(k)) ≤ 1, так как K1 n K2 = 0. Требуется найти такой набор X(u) ⊂ X(n), при котором θd(X(u)) = max θd(X(k)). (2) X (k )oX (n) 56 Отбор признаков в собственное пространство объекта на основе меры его компактности Определяемый по (2) набор X(u) применяется для описания собственного признакового пространства объекта Sd ∈ Kt, а значение θd(X(u)) используется как мера его компактности. 2. Отбор признаков в собственное пространство объекта При отборе набора X(k) ⊂ X(n), k ≤ n, для описания признакового пространства объекта S ∈ E0 необходимо: - произвести выбор метрики в качестве меры расстояния между объектами; - задать способ нормирования значений количественных признаков для унификации масштабов измерений; - определить наличие шумовых объектов в окрестности объекта S. Описание допустимого объекта в рамках его собственного пространства из информативных признаков необходимо для нахождения индивидуальной меры сходства (различия) с другими объектами. Эта мера должна отражать отношения между объектами и служить средством для принятия решения. Обозначим через i, j - множество индексов соответственно количественных и номинальных признаков в наборе X(n). Для унификации масштабов измерений значения количественных признаков дробно-линейным преобразованием отобразим в [0; 1]. В качестве меры расстояния между объектами Su,Sv ∈ E0 (Sc = (ac1, ac^), c = 1, _, m) будем использовать метрику Журавлёва р( Su, Sv ) = ∑ |«и, - av^∖ +∑∣1, "au "" "av ’ i∈7 i^J ^°, aui = avt. Для выбора информативного набора признаков X(r) X(n), r ≤ n, из собственного пространства объекта предлагается производить предобработку данных. Смысл предобработки заключается в поиске первой пары признаков (xi, Xj) ⊂ X(n), i ≠ j, для информативного набора. Множество расстояний объектов Eq от Sd ∈ Kt по паре (xi, Xj), i, j ∈ {1, .^, n} рассматривается как радиусы вложенных гипершаров, представленных в виде упорядоченной последовательности р( Sd, Sd),..., p(Sd, Sdμ),..., p(Sd, S^^^), Sd = S1, (3) где μ = |Kt|. Обозначим через ηt(i, j)(η3-t(i, j)) число ближайших к Sd объектов по (3) из Kt (K3-t) при условии, что ηt(i, j) + η3-t(i, j) = μ. При η3-t(i, j) = 0 все объекты класса Kt содержатся в гипершаре с центром в Sd. С помощью значения ηt(i, j) решается проблема выбора первого шага при отборе собственного пространства объекта. В процессе предобработки необходимо исключить появление сходных с Sd ∈ Kt описаний объектов из K3-t. Плотность распределения представителей класса Kt в окрестности объекта Sd по наборам из {(xi, xj)} предлагается определять по значениям (4) 3-t θij = max (Zt (u)- Z3-t (u)),γij = arg max (Zt (u)- Z3-t (u)), j 1≤u≤η,(≈;.^-P \\ 3 J 1≤u≤η,(z;.^-P 3 где zt(u)( z3-t(u)) - число объектов класса Kt (K3-t) в гипершаре радиуса р(¾,) из последовательности (3). Пусть р(Si,, к ≥ 2 - значение радиуса гипершара из (3), определяемого по расстоянию до первого ближайшего объекта S^ ∈ Kj t. Для выбора первой пары признаков в X(r) X(n), r ≤ n, из множества наборов {(xi, xj)} используется матрица B(Sd) = {bij}n×n, значения элементов которой вычисляются как ij 0,ρ(S.,S,^) = 0, b =IlO(S,,р)×θj /γj,ρ(Sd,S,^) >0. (5) Целью вычисления значений bij ≠ 0 является поиск кластеров данных с максимальной плотностью объектов одного с Sd ∈ Kt класса. 57 Н.А. Игнатьев, А.И. Мирзаев Существует зависимость количества связанных с Sd ∈ Kt объектов для вычисления (2) от наличия или отсутствия шумовых объектов. Шумовые объекты из Кз-t по X(p), p ≤ п, и метрике ρ(x, у) для объекта Sd ∈ Kt предлагается определять следующим образом. Пусть Γ(p) - множество граничных объектов классов по X(p) ∈ X(n), p ≤ п, и метрике ρ(x, у), g (p) = {^i }s,≡Γ(,), где gi = = {^j ≡ K3_c ∣P (sJ , sP ) = mKn P (sJ , Sr )} - число объектов, для которых Si ∈ Kc ∩ Γ(p), c = 1, 2, является граничным. Объект Si ∈ Кз-t ∩ Γ(p), t = 1, 2, считается шумовым относительно объекта Sd ∈ Kt если: 1) P(sd,si)= minP(sd,sr); 2) gi∕∣Kt∣ > ∣O(Si, ρ)∣∕∣K3-t∣. Результаты предобработки с использованием (3), (4) в виде пары признаков H(2) = (xi, xj) рассматриваются в качестве начального приближения эвристического алгоритма пошагового отбора информативных признаков объекта Sd ∈ Kt. Последовательность шагов по реализации алгоритма такова. Шаг 1. Ввод H(2). p = 2. X(p) = H(2). count = 0. T = 0. Шаг 2. По набору X(p) вычислить множество граничных объектов Γ(p) и G (p) = {g ). Шаг 3. Определить объект Sc ∈ K3-t ∩ Γ(p) с p (S^, Sd ) = min p (Sd, Sr). Если gc∕∣Kt∣ > O(Sc, ρ)∕∣K3-t∣, Sr eK3_j nΓ( p^ то обновить множество граничных объектов Γ(p) по X(p) на E0\\{Sc}. Шаг 4. Вычислить значения элементов множества Z(Sd, ρ) и θd(X(p)) по (1). Если θd(X(p)) > T, то T = θd(X(p)), H(p) = X(p), u = p. Если T = 1, то идти 7. Шаг 5. count = count + 1. Если count = n, то идти 7. Шаг 6. R = 0. v = 0. Начало цикла: Для всех xa ∈ X(n)\\X(p) вычислять значения θij, γij по (3) и (4) на X(p + 1) = X(p) ∪ {xa}. Если ∣O(Sd,ρ)∣ × θij∕γij > R, то R = ∣O(Sd, р)| × θij∕γij, v = a. Конец цикла. X(p + 1) = X(p) ∪ {xv}. p = p + 1. Идти 2. Шаг 7. Вывод T, H(u). Шаг 8. Конец. Рис. 1. Иллюстрация процесса выбора связанных объектов для S4 до и после удаления шумового объекта S7 Fig. 1. Illustration of the process of selecting connected objects for S4 before and after removing the S7 noise object aS2 A≡3 aS4 aS1 S? .S6 *Ss aS2 aS3 *84 _ S6 *85 Процесс выбора связанных объектов для вычисления меры компактности (1) до и после удаления шумового объекта показан на рис. 1. 3. Вычислительный эксперимент Для эксперимента была взята выборка данных German из [9]. Выборка представлена 1 000 объектами, разделенными на два класса K1 и K2. Каждый объект рассматривается как кредитная история 58 Отбор признаков в собственное пространство объекта на основе меры его компактности клиента банка. Кредитная история описывается 20 признаками, 7 из которых измеряются в количественных шкалах, 13 - в номинальных. В табл. 1 и 2 представлена последовательность отбора признаков в собственное пространство для объектов S907 є K1 и S5 є K2 алгоритмом из разд. 2. Количество объектов в гипершаре и связанных получено после удаления шумовых объектов. Таблица 1 Отбор признаков в собственное пространство объекта S907 є K1 Набор признаков Количество объектов Значение (1) в гипершаре связанн^іх X9, X20 23 23 0,0000 X5, X9, X20 32 31 0,0443 X5, X6, X9, X20 63 58 0,0829 X5, X6, X9, X14, X20 55 54 0,0771 X5, X6, X9, X12, X14, X20 59 90 0,1286 X5, X6, X9, X12, X14, X16, X20 49 85 0,1214 X5, X6, X9, X11, X12, X14, X16, X20 77 96 0,1371 X2, X5, X6, X9, X11, X12, X14, X16, X20 72 91 0,1300 X2, X5, X6, X9, X11, X12, X14, X15, X16, X20 63 101 0,1443 На наборе x9, x20 (см. табл. 1) значение (1) равно 0, так как существует объект из K1, описание которого совпадает (пересекается) с описанием ближайшего к S907 є K1 объекта из K2. Таблица 2 Отбор признаков в собственное пространство объекта S8 є K2 Набор признаков Количество объектов Значение (1) в гипершаре связанн^іх X8, X13 7 16 0,0000 X4, X8, X13 16 23 0,0000 X4, X8, X13, X14 16 24 0,0000 X4, X8, X13, X14, X18 18 19 0,0000 X4, X8, X11, X13, X14, X18 37 41 0,0586 X4, X5, X8, X11, X13, X14, X18 42 48 0,0686 Как видно из табл. 1 и 2 количество связанных объектов может быть больше, меньше или равно количеству объектов в гипершаре. Собственные наборы признаков для восьми случайно выбранных объектов из классов K1 и K2 приведены в табл. 3. Таблица 3 Результаты отбора признаков в собственное пространство восьми объектов из классов K1 и K2 Как видно из табл. 3, свойством собственного пространства объектов класса K2 (плохие клиенты) является относительно низкое значение компактности по отношению связанности объектов (см. значение (1)) по сравнению с K1 (хорошие клиенты). Для сравнительного анализа рассмотрим формирование собственного признакового пространства объектов из табл. 3 по критерию из [10]. Устойчивость объекта Sd є Kt по (3) на наборе X(k) ⊂ X(n) вычисляется как значение функционала Ґ zt(i^_ z3-t (i) " . ∣KJ ∣K3-J > F (Sd, X (k )) = max 3-t (6) 59 Номер объекта (класс) Набор признаков Значение (1) 310 (1) X5, X10, X11, X12, X14, X18, X20 0,0400 325 (1) X1, X5, X12 0,0871 460 (1) X1, X2, X5, X7, X8, X9, X10, X12, X13, X14, X15, X16, X18, X19, X20 0,1171 826 (1) X2, X3, X4, X5, X2, X8, X10, X11, X12, X14, X15, X16, X17, X18, X19, X20 0,0771 38 (2) X2, X4, X5, X6, XI, X16, X17 0,0167 125 (2) X1, X5, X11, X19 0,0167 707 (2) X2, X3, X5, X6, X10, X12, X14, X15, X16, X18, X19, X20 0,0300 827 (2) X1, X2, X5, X6, X8, X9, X10, X11, X12, X13, X17, X18, X20 0,0267 Н.А. Игнатьев, А.И. Мирзаев где zt(i), Z3-t(i) - число объектов в {S∕∣,...,¾ } ⊂ E, определяемых по (3), соответственно из классов Kt и K3-t. Множество допустимых значений (6) принадлежит интервалу (0; 1]. Условием для поиска набора информативных признаков X(μ), μ ≤ n, для Sd ∈ Kt является f 0 S,, x 0μ)) = rnax max f 0 S,,χ 0 k)). (7) Выбор первой пары признаков в X(2) из {(xi, xy)}i,,∈{1,^,n} производится по (7). Процесс отбора реализован в виде последовательного (пошагового) добавления признаков в X(μ), μ = 2, 3,_ Существенным отличием отбора информативных признаков для Sd ∈ Kt по (7) от (1) является «безразличие» к наличию шумовых объектов из класса Кз-t. Информативные наборы признаков, получаемые по экстремуму (7), приведены в табл. 4. Таблица 4 Информативные наборы признаков объектов по критерию (7) Номер объекта (класс) Набор признаков Значение (7) 310 (1) X2, X5, X14 0,2238 325 (1) X1, X3, X5 0,3819 460 (1) X1, XI, X5, X14, X16 0,3571 826 (1) X3, X5, X9, X19 0,2481 38 (2) X6, X10, X13, X16, X20 0,2090 125 (2) X1, XI, Xl, X15, X20 0,2143 707 (2) X2, X4, X20 0,2338 827 (2) X1, X13, X14, X16, X20 0,3014 Относительно малое различие между оценками по (7) из разных классов (см. табл. 4) объясняется отсутствием учета наличия шумовых объектов и непустого множества объектов из K1 и K2, описания которых на определяемом наборе признаков X(u) ⊂ X(n) совпадают. Заключение Разработан метод отбора признаков в собственное пространство объекта на основе отношения связанности объектов по системе гипершаров. Отношение связанности применяется для вычисления меры компактности объекта относительно своего класса в определяемом подпространстве заданного признакового пространства. Метод может быть использован для поиска скрытых закономерностей в данных в рамках информационных моделей из слабо формализованных предметных областей.

Скачать электронную версию публикации