Microsoft Word Тараскина doc



Download 33,94 Kb.
bet2/4
Sana09.06.2023
Hajmi33,94 Kb.
#950180
1   2   3   4
т 1 т2 ... т- где ту степень принадлежности у-го элемента /-му кластеру.
Отметим, что матрица принадлежности должна удовлетворять следую­щим условиям:
0) ту е[0,1], / = 1, с, У = 1, I, с

  1. ^ту = 1, у' = 1,I , т.е. каждый объект должен быть распределён меж-

I=1
ду всеми кластерами,
I

  1. 0 < Ету < I, / = 1, с, т.е. ни один кластер не должен быть пустым или у=1

содержать все элементы.
Для оценки качества разбиения используется критерий разброса, пока­зывающий сумму расстояний от объектов до центров кластеров с соответ­ствующими степенями принадлежности:
с I
.1 = ЕЕ(ти)(4,Ху), где
I=1 7=1
d (V,, Х]) — Евклидово расстояние между у-м объектом
Ху = (Ху 1,Ху2,...,Хуп) и I-м центром кластера \>1 = (у11,V,2,...,у*),
w е (1, да) — экспоненциальный вес, определяющий нечёткость, размытость

41 42
V
21 V 22
кластеров,
с х п матрица координат центров кластеров, эле-


сп
Хс1
I
Е(т) _
менты которой вычисляются по формуле ук = ■¿1- , к = 1, п (V).
Е (ту) '
у=1
Задачей является нахождение матрицы М, минимизирующей критерий .1. Для этого используется алгоритм нечётких с-средних, в основе которого лежит метод множителей Лагранжа. Он позволяет найти локальный опти­мум, поэтому для различных запусков могут получиться разные результа­ты.
На первом шаге матрица принадлежностей М, удовлетворяющая усло­виям 0)-2), генерируется случайным образом. Далее запускается итераци­онный процесс вычисления центров кластеров и пересчёта элементов мат­рицы степеней принадлежности:
1 11, k = i
mj = — :— при dj >0 и mkj =L , _п .при djj = 0,
, 1 1 7X~' 1 10, k ^ i
(dij) w-1 z —1
k=1 (dkj )w-1
где dij = d(vi,xj) для i= 1,c, j=1,l.
Вычисления продолжаются до тех пор, пока изменение матрицы M, ха- растеризующееся величиной ||m -M*|| , где M* матрица на предыдущей итерации, не станет меньше заранее заданного параметра остановки s .
Сходимость алгоритма нечётких c-средних доказана в [8].
Остановимся на выборе значения w — экспоненциального веса. Чем больше это значение, тем матрица принадлежности более размазанная и
1
при w ^ ж элементы примут вид mj = —, что является плохим решением, c
т.к. все объекты с одинаковой степенью распределены по всем кластерам. Теоретически обоснованного правила выбора веса пока не существует, и обычно устанавливают w = 2 .

  1. ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ

Локальный минимум, полученный с помощью алгоритма нечётких с - средних, зачастую отличается от глобального минимума. Поиск глобально­го минимума функционала J не осуществим ввиду большого объема вычис­лений, но существуют алгоритмы, получающие решение, близкое к гло­бальному минимуму.
Нами был использован генетический алгоритм (ГА), основанный на ге­нетических процессах биологических организмов: биологические популя­ции развиваются в течение нескольких поколений, подчиняясь законам ес­тественного отбора и по принципу «выживает наиболее приспособленный». Программа также может развивать соответствующим образом закодиро­ванные решения, выбирая из них наиболее подходящее. Обычно ГА дают хорошие результаты для задач оптимизации многопараметрических функ­ций, а именно такую задачу мы и решаем. Однако, как и другие методы эволюционных вычислений, они не гарантирует обнаружения глобального решения за полиномиальное время. ГА не гарантируют и того, что глобаль­ное решение будет найдено, но они хороши для поиска «достаточно хоро­шего» решения задачи «достаточно быстро».
ГА работает с популяцией — совокупностью особей, которые представ­ляют собой возможные решения данной задачи. Каждая особь оценивается степенью её приспособленности, что соответствует тому, насколько «хо­рошо» данное решение задачи. Наиболее приспособленные особи могут скрещиваться и производить потомство. В результате получаются новые особи, сочетающие в себе «хорошие» характеристики, полученные от роди­телей. Возможность скрещивания менее приспособленных особей меньше, поэтому признаки, которыми они обладали, будут элиминироваться из по­пуляции в процессе эволюции. Итак, из поколения в поколение хорошие характеристики распространяются по всей популяции. Скрещивание наи­более приспособленных особей приводит к тому, что исследуются наиболее перспективные участки пространства поиска. В конечном итоге, популяция будет сходиться к оптимальному решению задачи. Также существует воз­можность мутации особи, когда часть её характеристик случайным образом изменяется. Благодаря этому можно выйти из состояния локального опти­мума, получить новое возможное решение.


  1. Download 33,94 Kb.

    Do'stlaringiz bilan baham:
1   2   3   4




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish