Презентация на тему Алгоритм кластеризації k-means (1)

кластеризації k-means (2)

Крок 4, прохід 1. Обчислюємо центроїди, до яких переміщаються центр кластерів:
Ц1= [(1+1+1/3);(3+2+1/3)]=(1;2); Ц2=[(3+4+5+4+2/5);(3+3+3+2+1/5)]=(3,6;2,4).












Крок 3, прохід 2. Для кожної точки знов визначається найближчий до неї центр нових
кластерів і відповідна належність її до цього кластеру:





Бачимо, що відносно велика зміна значення m2 призвела до того, що точка Н стала
ближче до центру m1 ставши членом кластеру 1. Нова сума квадратів помилок склала:



Помилка зменшилось, що означає краще групування об’єктів відносно центрів кластерів.

Алгоритм кластеризації k-means (3)

Крок 4, прохід 2. Обчислюємо нові центроїди для кожного кластеру:
Ц1= [(1+1+1+2/4);(3+2+1+1/4)]=(1,25;1,75); Ц2= [(3+4+5+4/4);(3+3+3+2+/4)]=(4;2,75).
У порівнянні з минулим проходом центри кластерів мало змінилася.












Крок 3, прохід 3. Визначаємо відстані точок від ближчого з центрів нових кластерів:






Нова сума квадратів помилок склала:




Сума квадратів помилок мала змінилась відносно попереднього проходу.
Крок 4, прохід 3. Обчислюємо нові центроїди кластерів. Оскільки жодний об’єкт не змінив свого
членства у кластерах і положення центроїдів практично не змінилося,алгоритм завершує
свою роботу.

Наївний Байєсовький класифікатор (1)

Для заданого набору даних, з використанням наївного байєсовського
класифікатора визначте, який статус ймовірно має особа (а) з відділу
маркетингу у віці від 31 до 35 років, з зарплатою від 46 до 50 тисяч на
місяць; (б) з відділу продажів у віці від 31 до 35 років, з зарплатою від 66
до 70 тисяч на місяць





Р(A&B)=P(A)P(B|A)=P(B)P(A|B); P(B|A)=P(B)P(A|B)/P(A);
Відповідь:
А) Р(старш|маркет; 31-35; 46-50)= Р(старш) Р(маркет|старш)
Р(31-35|старш) Р(46-50|старш) = 5/11х1/5х2/5х2/5 = 0,0145
Р(молод|маркет; 31-35; 46-50)= Р(молод) Р(маркет| молод) Р(31-35| молод)
Р(46-50| молод)= 6/11х1/6х2/6х2/6 = 0,0101
Р(старш|маркет;31-35;46-50)= 0,0145/(0,0145+0,0101)= 0,0145/0,0246=0,59
Р(молод|маркет;31-35;46-50)= 0,0101/(0,0145+0,0101)= 0,0101/0,0246=0,41

В) Р(старш|продаж; 31-35; 66-70)= Р(старш) Р(продаж|старш) Р(31-
35|старш) Р(66-70|старш) = 5/11х1/5х2/5х2/5 = 0,006
Р(молод|продаж;31-35;76-70)= Р(молод) Р(продаж| молод) Р(31-35|
молод)Р(66-70| молод)= 6/11х2/6х2/6х0/6= 0
Р(старш|продаж; 31-35; 66-70)=1
Р(молод|продаж; 31-35; 76-70)=0

ДЕРЕВА РІШЕНЬ (1)

На основі навчальної вибірки побудуйте дерево рішень для визначення
бажання різних категорій споживачів щодо купівлі комп’ютера






















I(SТАК, SНІ )= I(9,5)= -9/14 log2(9/14) – 5/14 log2(5/14)=0.94
Вік: 3 значення: <=30 (2 так,3 ні), 31..40 (4 так,0 ні), >40 (3 так,2 ні)

ДЕРЕВА РІШЕНЬ (2)

На основі навчальної вибірки побудуйте дерево рішень для визначення
бажання різних категорій споживачів щодо купівлі комп’ютера








I(SТАК, SНІ )= I(9,5)= -9/14log(9/14) – 5/14log(5/14)=0.94
Вік: 3 значення: <=30 (2 так,3 ні), 31..40 (4 так,0 ні), >40 (3 так,2 ні)
Entropy(вік) = 5/14 (-2/5 log(2/5)-3/5log(3/5)) +4/14 (0) + 5/14 (-3/5log(3/5)
2/5log(2/5)) = 5/14(0.9709) + 0 + 5/14(0.9709) = 0.6935
Gain(age) = 0.94 – 0.6935 = 0.2465
Дохід 3 значення: високий (2так,2ні), середній (4так,2ні), низький (3так,1ні)
Entropy(дохід) = 4/14(-2/4log(2/4)-2/4log(2/4)) + 6/14 (-4/6log(4/6)-2/6log(2/6))
+ 4/14 (-3/4log(3/4)-1/4log(1/4)) = 4/14 (1) + 6/14 (0.918) + 4/14 (0.811)=
0.285714 + 0.393428 + 0.231714 = 0.9108 Gain(дохід) = 0.94–0.9108=0.0292
Студент: 2 значення: так (6 так, 1 ні), ні (3 так, 4 ні)
Entropy(студент) = 7/14(-6/7log(6/7)) + 7/14(-3/7log(3/7)-4/7log(4/7) =
7/14(0.5916) + 7/14(0.9852) = 0.2958 + 0.4926 = 0.7884
Gain (студент) = 0.94 – 0.7884 = 0.1516
Кредит: 2 значення: гарна (6 так, 2 ні), відмінна (3 так, 2 ні)
Entropy(кредит) = 8/14(-6/8log(6/8)-2/8lo g(2/8)) + 6/14(-3/6log(3/6)-3/6log
(3/6)) = 8/14(0.8112) + 6/14(1) = 0.4635 + 0.4285 = 0.8920
Gain(кредит) = 0.94 – 0.8920 = 0.048

ДЕРЕВА РІШЕНЬ (3)

Ентропія блоку: I(SТАК, SНІ)= I(2,3)= -2/5 log(2/5) – 3/5 log(3/5)=0.97
Дохід: 3 значення: високий (0так,2 ні),середній (1так,1 ні),низький (1так,0ні)
Entropy(дохід) = 2/5(0) + 2/5 (-1/2log(1/2)-1/2log(1/2)) + 1/5 (0) = 2/5 (1) = 0.4
Gain(дохід) = 0.97 – 0.4 = 0.57
Студент: 2 значення: так (2 так, 0 ні), ні (0 так, 3 ні)
Entropy(студент) = 2/5(0) + 3/5(0) = 0
Gain (student) = 0.97 – 0 = 0.97
Можна робити розбиття по атрибуту студент без перевірки інших
атрибутів, оскільки значення показника Gain для атрибуту Студент є
максимальним

ДЕРЕВА

РІШЕНЬ (4)

Ентропія блоку: I(SТАК, SНІ)= I(3,2)= -3/5log(3/5) – 2/5log(2/5)=0.97
Дохід: 2 значення: середній (2 так, 1 ні), низький (1 так, 1ні)
Entropy(дохід) = 3/5(-2/3log(2/3)-1/3log(1/3)) + 2/5 (-1/2log(1/2)-1/2log(1/2)) =
3/5(0.9182)+2/5 (1) = 0.55+0. 4= 0.95 Gain(income) = 0.97 – 0.95 = 0.02
Студент: 2 значення: так (2 так, 1 ні), ні (1 так, 1 ні)
Entropy(студент)=3/5(-2/3log(2/3)-1/3log(1/3))+2/5(-1/2log(1/2)-1/2log(1/2))=
0.95 Gain (student)=0.97–0.95 = 0.02
Кредит: 2 значення: гарна (3 так, 0 ні), відмінна (0 так, 2 ні)
Entropy(кредит) = 0 Gain(кредит) = 0.97 – 0 = 0.97
Здійснюємо розбиття по атрибуту КРЕДИТ, яке дасть два чисті класи:

АСОЦІАТИВНІ ПРАВИЛА (1)

T1{M,O,N,K,E,Y}; T2{D,O,N,K,E,Y}; T3{M,A,K,E}; T4{{M,U,C,K,Y};
T5{C,O,O,K,I,E};підтримка – 60%; довіра – 80%.















ПРАВИЛА: A→B: P(B|A)=|B∩A|/|A| o,k→e [0,6;1]; o,e→k[0,6;1]; k,e→o[0,6;0,75]
m→ k [0,6;1]; k→m [0,6;0,6] o→k [0,6;1] k→o [0,6;0,6] o→e [0,6;1]; e→o[0,6;0,75];
y→k[0,6;1]
Відповідь: o→k,e [0,6;1]; o,k→e [0,6;1]; o,e→k[0,6;1]; m→ k [0,6;1]; o→k [0,6;1];
o→e [0,6;1]; y→k[0,6;1]

МЕРЕЖА КОХОНЕНА (1)

Розглянемо приклад роботи мережі Кохонена, що містить 2 х 2 нейрона у
вихідному шарі, а множина даних представлена атрибутами Вік і Дохід з
попередньо нормалізованими даними. У зв’язку з малим розміром мережі
встановимо радіус навчання R=0, тобто можливість підстроювати ваги
буде надаватися лише нейрону-переможцю. Коефіцієнт швидкості
навчання встановимо =0,5.

МЕРЕЖА КОХОНЕНА (2)

Випадковим чином виберемо початкові значення ваг нейронів:



Сформуємо набір записів вхідної вибірки:







Конкуренція. Обчислимо евклідову відстань між вхідним вектором Х1 і векторами ваг усіх чотирьох нейронів вихідного шару.







Переміг нейрон 1, який формує кластер для захоплення літніх людей з високим доходом
Об’єднання. Оскільки радіус навчання дорівнює нулю, тільки нейрон-переможець буде нагороджений можливістю підстроювання свого вектора ваг.
Підстроювання. Для першого нейрона отримуємо формулу:
wi1нове = wi1поточне + (х1i - wi1,поточне).
Для Віку: w11нове = w11поточне + (х11 - w11поточне) = 0,9+0,5х(0,8 -0,9)=0,85.
Для Доходу w21нове = w21поточне + (х12 - w21поточне) = 0,8+0,5х(0,8 -0,8)=0,8.
Дане налагоджування дозволить нейрону 1 у подальшому більш успішно захоплювати записи з інформацією про літніх людей з високим доходом.

МЕРЕЖА КОХОНЕНА

(3)

Початкові значення
ваг нейронів:

Hабір записів
вхідної вибірки:





Виконавши операції конкуренції та підстроювання для другого вхідного вектору Х2=(0,8;0,1), отримуємо:



Переміг нейрон 2. Він відкриває кластер для захоплення літніх людей з малим доходом.
Для третього і четвертого нейронів, відповідно, отримаємо такі нові значення ваг




які будуть відповідати кластерам для молодих людей з високим доходом і молодих людей з низьким доходом.
Таким чином 4 вихідні нейрони представляють 4 різних кластера
Кількість вихідних нейронів мережі Кохонена має відповідати кількості кластерів, які треба побудувати.

ГЕНЕТИЧНІ АЛГОРИТМИ (1)
Знайдіть

найкраще розташування вершин
графу, за умов розміщення їх в один ряд,
після трьох циклів роботи ГА при заданому
початковому наборі хромосом. Якість
розміщення оцінюється сумою довжини
ребер графа. Єдиною операцією, що
здійснюється на кожній ітерації роботи алгоритму є мутація, яка
застосовується до кращої хромосоми покоління по розряду, який відповідає
номеру ітерації і полягає у інверсії порядку розташування значень всіх
генів хромосоми, розташованих за вибраним для мутації. Оцініть якість кожної
з отриманих популяцій.
1.Розміщаємо хромосоми відповідно з генами
(номерами вершин) хромосом.
2. Кількість горизонтальних відрізків між
вершинами: L1=3+4+2+2=11, L2=1+2+3+3=9,
L3=1+2+2+4=9. Хромосома 2 є найменшою.
Піддаємо її мутації оператором інверсії по першому елементу. Тобто перша
вершина залишається на своєму місці, а інші записуються у зворотному
порядку: 25431. Довжина ребер: L4=1+2+3+2=2. Отож, міняємо L1 на L4 і
отримуємо другу популяцію. Краща
хромосома після мутації набуде вигляду:
25134 з довжиною 8. Третя популяція:

ГЕНЕТИЧНІ АЛГОРИТМИ (2)

Задано початкову популяцію з
4 хромосом, кожна з яких має
по 2 гени x i y. Пристосованість
хромосоми оцінюється функцією
Z. При однакових Z перевагу має
хромосома з більшим номером.
На кожній ітерації найкраща
хромосома a породжує 4 нові
хромосоми b1,c1,b2,c2, схрещенням
з хромосомами b i c з більш низькими значеннями Z за схемою, наведеною
на рисунку. Хромосома з найгіршою пристосованістю вилучається з
популяції. Знайдіть показник найкращої пристосованості хромосоми в
популяції и значення середньої пристосованості популяції після 3-х етапів
еволюції.

ГЕНЕТИЧНІ АЛГОРИТМИ (2)

ГЕНЕТИЧНІ АЛГОРИТМИ (3)