1 Свойства и структура алгоритма



Download 1,14 Mb.
bet1/12
Sana13.04.2022
Hajmi1,14 Mb.
#548151
  1   2   3   4   5   6   7   8   9   ...   12
Bog'liq
Алгоритм k средних


Алгоритм k средних (k-means)

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма


Алгоритм k средних (англ. k-means) - один из алгоритмов машинного обучения, решающий задачу кластеризации. Этот алгоритм является неиерархическим[1], итерационным методом кластеризации[2], он получил большую популярность благодаря своей простоте, наглядности реализации и достаточно высокому качеству работы. Был изобретен в 1950-х годах математиком Гуго Штейнгаузом[3] и почти одновременно Стюартом Ллойдом[4]. Особую популярность приобрел после публикации работы МакКуина[5] в 1967.
Алгоритм представляет собой версию EM-алгоритма[6], применяемого также для разделения смеси гауссиан. Основная идея алгоритма k-means заключается в том, что данные произвольно разбиваются на кластеры, после чего итеративно перевычисляется центр масс для каждого кластера, полученного на предыдущем шаге, затем векторы разбиваются на кластеры вновь в соответствии с тем, какой из новых центров оказался ближе по выбранной метрике.
Цель алгоритма заключается в разделении n наблюдений на k кластеров таким образом, чтобы каждое наблюдение принадлежало ровно одному кластеру, расположенному на наименьшем расстоянии от наблюдения.

1.2 Математическое описание алгоритма


Дано:

  • набор из n наблюдений X={x1,x2,...,xn},xi∈Rd, i=1,...,n;

  • k - требуемое число кластеров, k∈N, k≤n.

Требуется:
Разделить множество наблюдений X на k кластеров S1,S2,...,Sk:

  • Si∩Sj=∅,i≠j

  • ⋃ki=1Si=X

Действие алгоритма:
Алгоритм k-means разбивает набор X на k наборов S1,S2,...,Sk, таким образом, чтобы минимизировать сумму квадратов расстояний от каждой точки кластера до его центра (центр масс кластера). Введем обозначение, S={S1,S2,...,Sk}. Тогда действие алгоритма k-means равносильно поиску:

argminS∑i=1k∑x∈Siρ(x,μi)2,

(1)

где μi – центры кластеров, i=1,...,k,ρ(x,μi) – функция расстояния между x и μi

Download 1,14 Mb.

Do'stlaringiz bilan baham:
  1   2   3   4   5   6   7   8   9   ...   12




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