Автор неизвестен - Бионика интелекта информация язык интеллект№ 3 (77) 2011научно-технический журналоснован в октябре 1967 г - страница 55

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77 

2. Определение k наиболее стимулированных Т-клеток, аффинность между которыми не пре­вышает значения пороговой аффинности Afflhr. Формирование исходной популяции В-клеток по результатам отбора Т-клеток.

3. Определение принадлежности свободных антител В-клеткам по их аффинностям с центрами В-клеток.

4. Клонирование и мутация В-клеток по одно­му из предложенных вариантов.

5. Определение принадлежности антител к му­тировавшим В-клеткам по аффинностям с их цен­трами.

6. Сравнение центров В-клеток, расположен­ных в памяти, с центрами, выделенными в резуль­тате клонирования и мутации (8). В случае невы­полнения условий (9) замещение клеток памяти выделенными центрами и переход к шагу 4, иначе переход к шагу 7.

7. Конец.

В результате работы будет получено множе­ство k В-клеток (кластеров), содержащих анти­тела. Для антигенов принадлежность к кластерам (В-клеткам) определяется по принадлежности ан­тител, вступивших с ними во взаимодействие.

3. Результаты экспериментальных исследований

Тестирование алгоритмов кластеризации произ -водилось на нескольких наборах данных (табл. 1).

Таблица 1

Характеристики наборов данных

Характеристики

Набор 1

Набор 2

Набор 3

Количество объектов

100

1000

10000

Количество групп признаков

2

5

10

Размерность групп

3

6

10

признаков

 

 

 

Кол. кластеров k

3

8

14

На первом этапе работы алгоритмов для опре­деления исходных центров кластеров по стан­дартному методу k-means потребовалось меньше времени, чем его иммунным модификациям. Этап роста выделенных кластеров потребовал от всех типов алгоритмов приблизительно одинаковых за­трат времени, но стандартный метод k-means сно­ва показал лучший результат по сравнению с двумя его иммунными модификациями. Аналогичный результат наблюдался также и на этапе выделения новых центров (центроидов) к кластеров, где стан­дартному алгоритму k-means снова потребовалось меньше времени, в то время как для иммунных методов на данном этапе характерны наибольшие затраты времени, поскольку клонирование и му­тация объектов сопряжены с выполнением боль­шого количества вычислительных операций. При этом важной особенностью является наблюдае­мое различие между временными затратами раз­личных иммунных модификаций k-means: подход клонирования граничных антител при небольших наборах данных, характеризующихся малым коли­чеством объектов, небольшим количеством групп признаков и их размерностью, требует больших временных затрат, чем подход клонирования цен­тра кластера. Однако при повышении количества объектов в наборе данных, повышении количества групп признаков или повышении размерности при клонировании граничных объектов затраты вре­мени меньше, чем при клонировании и мутации центра В-клеток. На сравнение исходных центров и выделенных центроидов алгоритмам потребова­лось приблизительно одинаковое количество вре­мени.

Несмотря на то, что на выполнение одного про­хода цикла кластеризации стандартному алгорит­му k-means потребовалось значительно меньше времени, чем иммунным аналогам, его общие за­траты времени больше, т.к. для кластеризации ему потребовалось значительно большее количество проходов цикла, чем его иммунным модификаци­ям (табл. 2).

Таблица 2

Результаты работы алгоритмов

Алгоритмы

Набор 1

Набор 2

Набор 3

 

C

T

C

T

C

T

Стандартный k-means

13

100

154

100

1816

100

Иммунный k-means 1-го типа

9

96

96

87

1032

50

Иммунный k-means 2-го типа

7

88

93

83

1029

57

В табл. 2 представлены результаты работы алго­ритмов кластеризации на различных наборах дан­ных, где C количество проходов цикла кластери­зации для выделенного набора данных, T общее время, затраченное на кластеризацию выделенных наборов данных в процентах. Алгоритм, которому потребовалось максимальное количество времени T, имеет 100%, а значения затрат времени других алгоритмов определяются относительно выделен­ного максимума.

Большое значение в работе иммунных алгорит­мов приобретает коэффициент деформации клет­ки у , который используется при определении гра­ничных объектов (антител) (5) и при определении уровня мутации объектов (7), (8). Данньгй коэффи­циент отображает деформацию клеток организма, которая наблюдается в результате воздействия на них вирусов и бактерий, попавших в данный орга­низм. В предложенных иммунных алгоритмах ко­эффициент деформации равен 10% (у = 10%). При повышении коэффициента деформации В-клеток предложенные иммунные алгоритмы требуют большего количества проходов цикла кластериза­ции и уступают стандартному k-means в затратах времени на кластеризацию. Уменьшение коэффи­циента деформации уменьшает необходимое коли­чество проходов цикла кластеризации, следствием чего является уменьшение затрат времени на кла­стеризацию, но понижает точность группировки объектов, поэтому его целесообразно устанавли­вать в диапазоне 5-15%.

Выводы

В работе предложены иммунные модифика­ции алгоритма k-means, в которых используются новые подходы для решения основных задач кла­стеризации данных. Для сокращения количества вычислений, влияющих на затраты времени, не­обходимого на кластеризацию, клонированию и мутации подвергаются лишь некоторые объекты исходного множества (граничные антигены, цен­тры В-клеток). Выделение клонируемых объектов производится при использовании значения поро­говой аффинности и коэффициента деформации, что значительно уменьшает количество выделяе­мых объектов и уменьшает затраты времени при кластеризации.

Использование конкурентно-целевого отбора приводит к повышению эффективности отбора клонов при минимальных временных затратах, а определение принадлежности граничных объектов кластерам происходит на основании максималь­ной средней аффинности его клонов к централь­ному объекту кластера (центроиду), что значитель­но ускоряет процесс кластеризации и повышает её точность.

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

Список литературы: 1. Mirkin, B.G. Clustering for Data Min­ing. A Data recovery Approach / B.G. Mirkin. Taylor & Francis Group, 2005. — 278 p. 2. Дасгупта, Д. Искусствен­ные иммунные системы и их применение [Текст]: Пер. с англ. А.А. Романюха. М.: ФИЗМАТЛИТ, 2006. — 344 с. 3. An Overview of Artificial Immune Systems / J. Timmis, T. Knight, L.N. de Castro, E. Hart. Natural Computation, 2004. — 29 p. 4. Duda, R.O. Pattern classification / R.O. Duda, P.R. Hart, D.G. Stork Willey & Sons. — 2001. — 738 p. 5. Кораблёв, Н.М. Классификация объектов на основе ис­кусственных иммунных систем [Текст] / Н.М. Кораблёв, А.А. Фомичёв // Системи обробки інформації. — 2010 — Вип. 6 (87). — С. 13-17.

Поступила в редколлегию 12.07.2011

УДК 004.89

Кластеризація даних методом k-means за допомогою штучних імунних систем / М.М. Корабльов, О.О.Фомічов // Біоніка інтелекту: наук.-техн. журнал. — 2011. — № 3

(77). — С. 102-106.

У роботі запропоновані імунні підходи до вирішення задачі кластеризації даних методом k-means. Для підви­щення швидкодії алгоритму кластеризації використо­вуються принципи клонування граничних об'єктів та клонування центрів. Проведені експериментальні до­слідження запропонованих підходів вказали на високу швидкість кластеризації даних без втрат точності та хо­рошу масштабованість алгоритмів.

Табл. 2. Бібліогр.: 5 найм.

UDK 004.89

K-means data clustering using artificial immune systems

/ N.M. Korablev, А.А. Fomichev // Bionics of Intelligense: Sci. Mag. — 2011. — № 3 (77). —P. 102-106.

The paper presents the immune approaches to solving the problem of data clustering method k-means. To speed en­hancing operation of clustering algorithm is used principles of boundary objects cloning and center objects cloning of clus­ters. Experimental studies suggested approaches indicated a high rate of clustering data without loss of accuracy and good scalability algorithms.

Tab. 2. Ref. 5 items.

УДК 004.93'1

intelligence

К.В. Барило

Сумський державний університет, м. Суми, Україна, kate.barylo@gmail.com

ОПТИМІЗАЦІЯ РІВНЯ СЕЛЕКЦІЇ КООРДИНАТ ЕТАЛОННИХ ВЕКТОРІВ ПРИ РОЗПІЗНАВАННІ ЕЛЕКТРОНОГРАМ

Розглядається алгоритм оптимізації рівня селекції координат еталонних векторів-реалізацій класів розпізнавання для заданого алфавіту в рамках інформаційно-екстремальної інтелектуальної технології, що ґрунтується на максимізації інформаційної спроможності системи розпізнавання. При цьому дослі­джено вплив рівня селекції на функціональну ефективність системи розпізнавання зображень.

ЕЛЕКТРОНОГРАМА, РІВЕНЬ СЕЛЕКЦІЇ, РОЗПІЗНАВАННЯ, ІНФОРМАЦІЙНИЙ КРИТЕРІЙ, НАВЧАННЯ

Вступ

Складність машинного розпізнавання електро­нограм, одержаних в електронній мікроскопії в ре­жимі малої дифракції, обумовлена як довільними початковими умовами формування їх зображень, так і впливом неконтрольованих випадкових фак­торів (нестабільність параметрів мікроскопа та електронного пучка) [1]. Одним із перспективних напрямів аналізу і синтезу систем розпізнаван­ня електронограм є використання ідей і методів інформаційно-екстремальної інтелектуальної тех­нології (ІЕІ-технологія), що ґрунтується на мак-симізації інформаційної спроможності в процесі навчання системи [2,3]. У рамках ІЕІ-технології важливу роль в процесі навчання системи розпізна­вання відіграє рівень селекції координат двійкових еталонних векторів-реалізацій образу [4], оскільки вони визначають геометричні центри контейнерів класів розпізнавання при їх цілеспрямованому від­новленні в радіальному базисі простору ознак роз­пізнавання. Оптимізація рівня селекції дозволяє підвищити середню міжкласову кодову відстань для заданого алфавіту класів розпізнавання у від­повідності з максимально-дистанційним принци­пом теорії розпізнавання образів.

У статті розглянуто інформаційно-екстремаль­ний алгоритм оптимізації рівня селекції координат еталонних векторів з метою підвищення функціо­нальної ефективності навчання системи розпізна­вання електронограм.

1. Постановка задачі дослідження

Нехай дано алфавіт класів розпізнавання [X°m | m = 1,M}, навчальна матриця типу "об'єкт-властивість" || y(n^i ||, i = 1,N, j = 1,n, де N,n — кіль­кість ознак розпізнавання та реалізацій образу від­повідно. При цьому задано структурований вектор параметрів функціонування системи, що навчаєть­ся розпізнавати реалізації класу X": g =< x1,d1, р >, який складається відповідно з еталонної реалізації X класу X1" , геометричного параметра d1 — кодо­вої відстані гіперповерхні контейнера K1" класу X1" від вершини еталонної реалізації x1 є X" і рів­ня селекції р координат еталонних векторів класів розпізнавання, який є рівнем квантування дискрет полігону емпіричних частот потрапляння значень ознак розпізнавання у свої поля контрольних до­пусків. При цьому полігон будується так: по осі абсцис відкладаються ранги ознак розпізнавання, які відповідають номерам ознак у векторі-кортежі xm), а по осі ординат — відносні частоти mm i=ni/n, де ni — кількість випробувань, при яких значення і ознаки знаходиться в своєму полі контрольних допусків.

Задано допустимі області значень відповідних параметрів: x1 , де — бінарний простір ознак потужності N ; d1 є [0; d(x1 © xc) -1], де xc — еталонна реалізація сусіднього (найближчого до X") класу X", і рівень селекції р координат ета­лонної реалізації x1, рє [0;1].

Треба на етапі навчання за апріорно класифіко­ваними реалізаціями нечітких образів побудувати оптимальне в інформаційному розумінні чітке роз­биття 9t|M| дискретного простору ознак QB на M класів розпізнавання шляхом ітераційної опти-мізації координат вектора параметрів функціону­вання g1 за умови, що значення усередненого за алфавітом {Xm} інформаційного критерію функ­ціональної ефективності (КФЕ) навчання систе­ми розпізнавання набуває глобального максимуму в робочій (допустимій) області визначення його функції.

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77 


Похожие статьи

Автор неизвестен - 13 самых важных уроков библии

Автор неизвестен - Беседы на книгу бытие

Автор неизвестен - Беседы на шестоднев

Автор неизвестен - Богословие

Автор неизвестен - Божественность христа