May 7, 2010 MasterDiploma, Ukrainian No comments
May 7, 2010 MasterDiploma, Ukrainian No comments
Одним із найважливіших завдань для реалізації масштабування обчислень є знаходження частин алгоритму, які можна та які є оптимально розбити на деякий набір незалежних обчислень.
Велика кількість роботи по розробці масштабування обчислинь алгоритму SOM була зроблена за останні роки. Взагалі кажучи існує два основних підходи, якими є розбиття гратки (map-partitioning, MP) та розбиття даних (data-partitioning, DP).
В MP, SOM є розподілена поміж декількох потоків, таким чином, що кожен потік обробляє кожен вхідний вектор і модифікує свою частину гратки. Такий підхід зберігає порядок оновлень записаних у формулі [осн. формула оновлення]. Найбільшим недоліком цього методу є велика ціна синхронізації потоків, потоки повинні бути синхронізовані опісля кожного разу, коли був знайдений нейрон-переможець, а також кожного разу, коли пройшло оновлення. Таким чином MP є ефективним для хардверної реалізації або ж для систем із спеціальною архітектурою для паралелізації.
В DP, вхідні дані розподілені поміж потоками, так, що кожен потік містить частину вхідних даних та проганяє її на своїй копії гратки. Як бачимо цей підхід не вимагає частої синхронізації, таким чином це є перевагою над MP. Проте такий підхід не відповідає формулі оновлення, що змушує використовувати його із варіаціями SOM, зоокрема batch SOM. Та навіть попри це batch SOM не є популярним методом, із-за двох основних причин:
1. Він вимагає щоб усі вхідні вектори були наперед відомими, що не є завжди можливо.
2. Насправді дуже важко отримати добре структуровану карту на відміну від класичного алгоритму.
Існує також багато інших розробок. Для прикладу в одній із таких автори пропонують підхід схеми Master-Slave, яка базується на тому факті, що із часом радіус, у якому ми модифікуємо нейрони зменшується, а тому два послідовні нейрони-переможці можуть не мати спільних областей. Таким чином можна обробляти ці нейрони разом із частиною матриці в паралельних потоках. Master потік слідує за основними кроками класичного алгоритму, а Slave пробує здійснити обчислення в паралельному потоці для наступного нейрона переможця якщо області не перетинаються.
Мною була здійснена реалізація MP підходу до розпаралелення алгоритму із невеликими відмінностями.
Основною відмінністю є те, що в стандартній реалізації MP гратка розбивається на декілька підграток, скажімо на n частин. Опісля для заданого вхідного вектора ми шукаємо нейрон переможець у кожній із підграток в паралельних потоках. Як тільки він був знайдений, ми запускаємо модифікацію на тих самих частинах гратки. Якщо глянути на рисунку нижче, то можна побачити, що в такій ситуації для модифікації ефективно використовується лишень четвертий потік, перший та третій швидко впорюються із роботою, а другий потік взагалі простоює.
Я пропоную знайдену множину сусідів знову поділити на рівні частини, як це зображено на наступному рисунку, проте із певною відмінністю. Якщо множина нейронів для модифікації є більшою за число M, то я розбиваю цю множину на ту ж саму кількість що й розбивав гратку, і запускаю оновлення в різних потоках (перевикористовуються вже існуючі). Якщо число нейронів для модифікаціх менше за M, то модифікація проганяється в одному потоці. Число М має залежати від ціни синхронізації і ще потребує додатковго дослідження.
Такий підхід дає помітні покращення коли гратка є дуже виликих розмірів.
March 25, 2010 Education, Ukrainian 2 comments
Вступ
Алгоритми ID3 і C4.5 придумані Джоном Квінланом (John R. Quinlan) для індукування Класифікаційних Моделей(Classification Models), які ще називають Деревами прийняття рішень(Decision Trees), із даних.
Перш за все ми маємо множину рядків даних. Кожен вектор, або рядок, має таку ж структуру, складається із набору пар властивість/значення. Одна із цих властивостей представляє категорію нашого вектору. Нашим завданням є побудувати дерево прийняття рішень, яке базуючись на відповідях про властивості, що не відповідають за категорію, зробити висновок про значення категорізаційної властивості. Зазвичай категорізаційна властивість приймає тільки два значення {Так, Ні}, або {true, false}, або {success, failure}. В будь-якому випадку одне із значень буде означати невдачу.
Для прикладу, ми можемо мати результати замірів про деяку подію, зроблених експертами. Для кожної події ми знаємо рішення, яке було прийняте експертами, напр. ствердне рішення, відхилити або ж інше. Іншими словами ми маємо вектор із некатегоризаційними властивостями та категоризаційну властивісь – прийняте рішення.
Розглянемо більш детальний приклад. Ми маємо справу із записами що засвідчують погодні умови для гри в гольф. Категоризаційна властивість є рішення про те чи слід грати в гру чи ні. Некатегоризаційні властивості такі:
ВЛАСТИВІСТЬ | МОЖЛИВІ ЗНАЧЕННЯ
============+======================= небо | сонячно, хмарно, дощ ------------+----------------------- температура | значення ------------+----------------------- вологість | значення ------------+----------------------- вітряно | так, ні ============+=======================
а тут набір даних для побудови дерева:
НЕБО | ТЕМПЕРАТУРА | ВОЛОГІСТЬ | ВІТРЯНО | ГРАТИ? ===================================================== сонячно| 30 | 85 | ні | Не грати сонячно| 27 | 90 | так | Не грати хмарно | 28 | 78 | ні | Грати дощ | 21 | 96 | ні | Грати дощ | 20 | 80 | ні | Грати дощ | 18 | 70 | так | Не грати хмарно | 18 | 65 | так | Грати сонячно| 22 | 95 | ні | Не грати сонячно| 21 | 70 | ні | Грати дощ | 24 | 80 | ні | Грати сонячно| 24 | 70 | так | Грати хмарно | 22 | 90 | так | Грати хмарно | 27 | 75 | ні | Грати дощ | 22 | 80 | так | Не грати
Зауважмо, що дві властивості мають недетерміновані значення – температура і вологість. ID3 алгоритм не може напряму мати справу із такими випадками, але є модифікації, які дозволють йому працювати із такими значеннями. Дерева прийняття рішень важливі не тільки тому, що вони дозволяють узагальнити те, що ми знаємо, або відомий набір даних для навчання, але тому, що ми можемо сподіватися на те, що алгоритм правильно скласифікує нові, невідомі випадки. Таким чином коли ми будуємо класифікаційну модель (дерево), ми повиння мати дані для навчання і дані для перевірки правильності побудованої моделі.
Спрощений приклад складу магазину, який включає тільки дискретні значення властивостей речей для продажу, та виручка як категоризаційну властивість, яка може мати два значення {висока, низька}. Некатигоризаційні властивості:
ВЛАСТИВІСТЬ | МОЖЛИВІ ЗНАЧЕННЯ ============+======================= вік | старий, середній, новий ------------+----------------------- конкуренція | ні, так ------------+----------------------- тип | ПЗ, "залізо" ------------+----------------------- і дані для навчання такі: ВІК | КОНКУРЕНЦІЯ | ТИП | ВИРУЧКА ========================================= старий | так | ПЗ | низька --------+-------------+---------+-------- старий | ні | ПЗ | низька --------+-------------+---------+-------- старий | ні | залізо | низька --------+-------------+---------+-------- сер. | так | ПЗ | низька --------+-------------+---------+-------- сер. | так | залізо | низька --------+-------------+---------+-------- сер. | ні | залізо | висока --------+-------------+---------+-------- сер. | ні | ПЗ | висока --------+-------------+---------+-------- новий | так | ПЗ | висока --------+-------------+---------+-------- новий | ні | залізо | висока --------+-------------+---------+-------- новий | ні | ПЗ | висока --------+-------------+---------+--------
Основні концепції алгоритму ID3 такі:
С4.5 є доповненням до алгоритму ID3, що враховує допустимі значення, недетерміновані значення, відсікання дерева, виведення правил та інше.
Означення
Якщо є n можливих повідомлень, тоді вірогідність p кожного є рівна 1/n а інформативність передана цим повідомленням є такою -log(p) =
log(n).
Для прикладу, якщо є 16 повідомлень, тоді log(16) = 4
і нам потрібно 4 біти, щоб ідентифікувати кожне повідомлення.
В загальному, якщо ми маємо розподіл імовірностей P = (p1, p2, ..,
pn)
тоді інформативність передана цим розподілом, або Ентропія Р, визначається так::
Для прикладу, якщо P є (0.5, 0.5) тоді I(P) рівне 1, якщо P є (0.67, 0.33) тоді I(P) рівне 0.92, а якщо P є (1, 0) тоді I(P) дорівнює 0.
[Зауважте, що чим більш подібні ймовірності в розподілі, тим більша є інформативність]Якщо множина T записів є розбита на виокремлі класи
C1, C2, .., Ck базуючись на значенні категоризаційної властивості, тоді інформація, необхідна для ідентифікації класу елемента із множини Т є Info(T) = I(P), де P є ймовірнісний розподіл розбиття (C1, C2, .., Ck):
В нашому прикладі гри в гольф, ми отримуємо Info(T) = I(9/14, 5/14) = 0.94,
а в нашому прикладі із складом магазину ми отримуємо Info(T) = I(5/10,5/10) = 1.0.
Якщо перше розбиття T, базоване на значенні некатигоризованого атрибуту X буде таке T1, T2, .., Tn тоді інформація необхідна для визначення класу елементу із Т є середнім із інформацій необхідних для ідертифікації класу елемента Ti, іншими словами середнє із Info(Ti):
У випадку гри в гольф, для властивості Небо, ми маємо:
Дамо означення приросту інформації Gain(X,T) як
Це представляє різницю між інформацією необхідною для визначення елемента із Т і інформації необхідної для визначення елемента із Т, після того, якщо значення властивості Х було визначено, іншими словами приріст інформації завдяки відомості властивості Х.
В нашому прикладі із грою в гольф, для властивосіті Небо, приріст буде:
Якщо взяти властивість Вітряно, ми отримаємо такі значення
Info(Windy,T) = 0.892 та Gain(Windy,T) = 0.048. Таким чином Небо надає більше інформаційного приросту аніж Вітряно.
Ми можемо використовувати знання приросту для відсортовування властивостей і для побудови дерева прийняття рішень, де в кожному вузлі знаходиться властивість із найбільшим інформаційним приростом в порівнянні до інших властивостей, які не включені в шлях від кореня до поточного вузла.
Це впорядкування вирішує два завдання:
Алгоритм ID3
Алгоритм ID3 використовується для побудови дерев прийняття рішень, маючи множину некатегоризаційних властивостей C1, C2, .., Cn, категоризаційну властивість C,
і множину записів для навчання T.
function ID3 (R: множина некатегоризаційних властивостей, C: категоризаційна властивість, S: множина для навчання) returns дерево прийняття рішень; begin Якщо S пуста, повернути один вузол із значенням невдача; Якщо S складаєтсья із рядків, для яких значення категоризаційної властивості одне й те ж, повернути єдиний вузол із тим значенням; Якщо R пуста, тоді повернути єдиний вузол із значенням, яке є найбільш частішим серед значень катеригоційної властивості, що було знайдено серед рядків S; Нехай D є властивістю із найбільшим приростом Gain(D,S) серед властивостей в множині R; Нехай {dj| j=1,2, .., m} - значення властивості D; Нехай {Sj| j=1,2, .., m} - підмножини S, що включають відповідні рядки із значенням dj для властивості D; Повернути дерево із коренем поміченим D і дуги позначені d1, d2, .., dm що продовжуються наступними деревами ID3(R-{D}, C, S1), ID3(R-{D}, C, S2), .., ID3(R-{D}, C, Sm); end ID3;
В прикладі із грою в гольф ми отримуємо наступне дерево:
Небо / | / | хмарно / |сонячно дощ / | Грати Вологість Вітряно / | | / | | <=75 / >75| так| ні / | | Грати Не грати Не грати Грати В прикладі із магазинним складом дерево буде: Вік / | / | нов/ |сер старе / | Вис Competition Низька / / ні/ так / Вис Низька
Використання зважених приростів (Gain Ratios)
Поняття приросту (Gain) введене раніше має тенденцію одобряти властивості, що мають велику кількість значень. Для прикладу, якщо в нас є властивість D, що має різні значення для кожного рядка, тоді інформативність буде Info(D,T) рівною 0, таким чином приріст Gain(D,T)
є максимальним.
Щоб компенсувати це Квінлан запропонував використання наступного зглажування замість звичного приросту:
Gain(D,T) GainRatio(D,T) = ---------- SplitInfo(D,T) де SplitInfo(D,T) є інформація у відповідності до розбиття T на основі значень категоризаційної властивості D. Таким чином SplitInfo(D,T) є I(|T1|/|T|, |T2|/|T|, .., |Tm|/|T|) де {T1, T2, .. Tm} є розбиття множини T продуковане значенням D. У випадку нашої гри в гольф SplitInfo(Outlook,T) рівне -5/14*log(5/14) - 4/14*log(4/14) - 5/14*log(5/14) = 1.577 таким чином GainRatio для Небо буде 0.246/1.577 = 0.156. І SplitInfo(Windy,T) буде -6/14*log(6/14) - 8/14*log(8/14) = 6/14*0.1.222 + 8/14*0.807 = 0.985 отже, GainRatio для Вітряно є 0.048/0.985 = 0.049
Доповнення C4.5
С4.5 додає цілий ряд доповнень до оригінального алгоритму ID3.
Під час побудови дерева рішень ми можемо мати справу із навчальними даними, що мають рядки із невідомими значеннями властивостей під час обрахунку приросту, беручи до уваги лише рядки, де ця властивість визначена.
Під час використання дерева, ми можемо класифікувати рядки, що мають невідомі значення властивостей, вгадуючи ймовірності появи різних результатів.
Для нашого прикладу із грою у гольф, якщо ми маємо новий рядок, для якого Небо є сонячне і Вологість є невідомою, ми продовжуємо наступним чином:
Ми рухаємося від кореня Небо до вузла Вологість проходячи дугу іменовану 'сонячно'. В цій позиції, оскільки ми не знаємо значення Вологості ми спостерігаємо, що якщо вологість є менша за 75 є тільки два рядки коли слід грати, і якщо вологість є більша ніж 75 тоді є три рядки коли не слід грати. Таким чином ми можемо дати відповідь для рядка із ймовірностями (0.4, 0.6) грати або ж не грати.
Ми можемо мати справу із недетермінованими властивостями наступним чином. Припустимо що атрибут Ci є недетермінованим (число як для вологості). Ми визначаємо значення для цього атрибуту в множині для навчання. Скажімо ми маємо посортовані значення, A1, A2, .., Am. Тоді для кожного значення Aj, j=1,2,..m, ми розбиваємо рядки на такі, які менці за Aj, і такі які більші за Aj. Для кожного із розбиттів ви рахуємо приріст, або зважений приріст, і вибираємо таке розбиття, яке максимізує приріст.
В нашому прикладі із грою в гольф для вологості, якщо T є множиною навчання, ми визначаємо інформацію для кожного розбиття і знаходимо найкраще в точці 75.
Таким чином діапазон для цього атрибуду визначений як {<=75, >75}.
Зауважте що цей метод вимагає багато калькуляцій, тому є ресурсоємним.
Відсікання дерев прийняття рішень та виведення правил
Дерева прийняття рішень будуються на основі навчальних даних, таким чином вони практично завжди виводять правильні рішення для рядків із навчальної множини. Насправді для знаходження результату нерідко шлях по дереву може виявитися занадто довгим.
Відсікання дерева прийняття рішення полягає в заміні цілого піддерева листком. Заміна відбувається коли дерево виявляє, що очікувана помилка у піддереві є більша ніж у окремому листку. Для прикладу, якщо ми маємо таке просте дерево
було визначено за допомогою одного успішного червоного рядка і двох невдалих синіх рядків, нагадаємо що ці рядки були із навчальних даних, а потім у тестових даних ми виявили три червоні невдачі і один синій успіх, ми можемо застосувати зміну цілого піддерева одним листком невдачі. Таким чином після заміни ми будемо мати лише тві помилки замість п”яти.
Вінстон (Winston) показав як використати тест Фішера щоб визначити чи категорія-властивість дійсно залежить від заданої некатегоризаційної властивості. Якщо це так, то така властивість просто не має знаходитися в жодному шляху дерева.
Квінлан (Quinlan) і Брейман (Breiman) запропонували більш умудрену відсікаючу евристику.
Можна виробити набір правил на основі дерева прийняття рішення: записуємо правило для кожного шляху від кореня до листка.
В такому правилі ліва сторона легко будується із міткок вузлів і з”єднуюючих дуг.
Результуючий набір правил може бути спрощений:
Нехай LHS є ліва сторона правила. Нехай LHS’ є отриманий із LHS
шляхом вилучення деяких умов. Ми можемо впевнено замінити LHS за допомогою
LHS’
в цьому правилі, для кожного вектора із множини навчання, що задовольняє
LHS також задовольняє LHS’.
Правило може бути видалено, якщо “більш ніякі правила є незастосовні”.
This post has been translated from page: http://www.cis.temple.edu/~ingargio/cis587/readings/id3-c45.html, 02/25/2010.
Цей пост був перекладений із сторінки: http://www.cis.temple.edu/~ingargio/cis587/readings/id3-c45.html,
25.03.2010.
March 9, 2010 Education, Pedagogic Practice, Ukrainian No comments
On Friday, I will have my first teaching experience (or at least teaching students of my University). This is part of the Master Year pedagogic practice. Subject is called “Data Mining” and theme of Friday’s lesson will be “K-means” algorithm.
Few things here before I start
I will have this post mixed of English and Ukrainian. Why? Because the way I’ll be presenting algorithm in both languages and because I need some report in Ukrainian, so do not want to double write a lot – I’m lazy ass as someone said.
План уроку (Agenda)
1. Привітання та дуже загальний вступ
Даю знати хто я і про що буду розповідати. Also I have a nice joke in English that could grab attention of the students. Hope they will be able to recognize and understand my English.
2. Розуміння Partitioning алгоритмів
Тут я нагадаю що таке Cluster analysis та згадую про Hierarchical і Partitional різновиди. І дещо про різниці між ними.
3. K-means алгоритм
– завдання алгоритму
– введення позначень
– кроки алгоритму
– демонстрація алгоритму як на дошці так і на комп”ютері
– переваги та недоліки
4. Other variations of the K-means algorithm
Because of some disadvantages of standard algorithm we’ve got few different variations of it like Soft K-means, when data element is fuzzy associated with mean, or like K-means++, which is additions to the K-means to initialize cluster means better.
5. Soft K-means алгоритм
– різниця в кроках алгоритму
6. Можливий підхід до реалізації (можливо напишу програму ще раз)
7. Application
If I’ll see that we are ok with English this part will be in it, otherwise we will have this in Ukrainian.
One of the application examples is clustering colors in image to compress image.
8. Побажання зробити реалізацію алгоритму
9. Час на питання
I hope tomorrow I’ll have article with whole lesson text, more structured and with examples, also hope to write k-means plus demo from scratch. Will see how fast am I.
February 10, 2010 Success, Ukrainian 4 comments
This post is in Ukrainian and is translation to the Things you need to remember to become successful developer
1. Не переставайте вчитися
Я припускаю, що ви навіть б не читали цей пост, якщо б не мали хоча б елементарної освіти, і ви б навіть не хотіли знати як стати успішним програмістом без вищої освіти. То ж якщо ви зараз програміст навіщо зупинятися вчитися?
Це просто недозволено. Одна важлива річ тут: Стояти на одному місці не означає, що ви стоїте на місці – це означає що ви рухаєтеся назад. Просто рухатися вперед не означає що ви рухаєтеся вперед – це лишень означає, що ви не загубилися із невдахами десь в кінці. Щоб просуватися вперед вам слід вчитися постійно – не просто рухатися, а БІГТИ.
Ось мій короткий список, що підпадає під цей пункт:
• Читайте книги
• Підпишіться на RSS і читайте різні статті
• Пробуйте різні мови програмування і речі, про які ви чули
• Ходіть на семінари і готуйте власні презентації
• Вчіть будь-що, що може вам допомогти просуватися
• Вчіть інших, так як це вчить вас
2. Визначте вашу ціль і тримайтеся правильної дороги
Я думаю що важко бігти якщо не знати куди бігти. Основне завдання полягає в тому, щоб чітко уявляти свою ціль. Ваша ціль повинна бути довготермінова і велика. І після того як у вас вже є бачення своєї мети візьміть і розбийте її на дрібні завдання – тобто побудуйте свою карту до успіху. Вам слід скласти список завдань, які ви ПОВИННІ виконати за місяць, або за рік. Як тільки ви його маєте, просто чітко слідуйте за ним.
3. Будь-які проблеми є можливостями
В буденній роботі ви завжди стикаєтеся із різними траблами. Ви отримуєте нові завдання або звіти про баги від тестерів. Ви отримуєте нові проекти від Проджект менеджерів. Ваш співробітник запитує про допомогу. Вам потрібна допомога. Це все приклади проблем. І справді важливе питання тут таке: як ви зустрічаєте їх? Ви можете сказати «Ой, але так я не позбавлюся від дурної надоїдливої роботи». Ви тут абсолютно не праві. Запам’ятайте, що ваші боси будуть раді дати вам більш складну роботі як тільки побачать, що ви справляєтеся із поточними завданнями.
4. Будьте позитивно налаштовані
Ви повинні дивитися на все позитивно. Якщо ви виявили, що зробили помилку просто сприйміть це легко – кожен робить помилки. Вам подобаються люди, які ниють коли у них проблеми? Як ви думаєте ви будете виглядати у чужих очах, якщо ви скажете: «Так, хлопці, я це зробив – я це вирішу, дайте мені хвилинку» і опісля ви повертаєтеся і починаєте фіксати вашу помилку із усмішкою на лиці. Як тільки ви вирішите проблему ви будете просто щасливі.
Ваша дорога є хорошою і ви швидко рухаєтеся вперед. Ніколи, ніколи не думайте що ви не досягнете своєї цілі – ось суть цього пункту.
5. Знайдіть наставника
Це не означає, що вам потрібна людина, яка буде вам допомагати робити вашу роботу – бо це просто вчитель або ж більш досвідчений розробник. Це означає що вам потрібна людина, яка знаходиться там, де ви хочете бути. Вам потрібно брати приклад із цієї людини. Якщо ця людина недостатньо високо – просто знайдіть когось по серйозніше. Також майте друзів які будуть вам допомагати рухатися по шляху. Або просто користуйтеся підтримкою жінки або дівчини.
6. Ставайте відомими
Якщо ви не покажете іншим, що ви крутий і що ви заслуговуєте більше, як вони будуть про це знати? Є просте рішення – почніть вести блог, запитуйте і відповідайте на питання, переконайтеся що гугл знає вас. Поширюйте своє знання у вашій команді і на проекті. Якщо ви вивчили щось нове, то чому б не поділитися цим? Ви забудете ці нові речі, якщо ви не будете їх пробувати.
7. Слідкуйте за виконанням ваших завдань, будьте певні, що ви й досі на шляху
Час від часу слід перевіряти чи ви робите все правильно. Впевніться, що ви виконуєте поставлені задачі. Якщо ні, то швидко знайдіть причини і працюйте над ними. Знайдіть свої слабкі сторони і змагайтеся із ними. Це може звучати смішно, але я знаю хорошого програміста із добрими теоретичними знаннями, але його швидкість набору коду просто жахлива. Чому? Тому що в нього просто жахлива клавіатура і він не хоче провести 10-20 годин за тренажером. Хіба це не тупо? Друже, якщо ти будеш читати цю статтю, пообіцяй що ти переможеш цю слабинку.
8. Робіть гімнастику
Я зробив маленьке само-опитування, коли писав цю статтю. І «Робіть гімнастику» попало у список. Я є досить молодий і проводжу забагато часу за ноутбуком і за іншою машиною на роботі і я не можу заставити себе робити гімнастику. Але це як точіння леза. Є така історія про двох дроворубів які поспорили про те хто зрубає більше дерев. Один дроворуб був здоровий і великий, а інший худий, як я. Сильний був певен, що він переможе, оскільки він рубав дерева всі 8 годин без жодної перерви, а худий робив перериви на 15 хв. кожної години. Але боротьбу виграв худий – він зрубав 150 дерев тоді коли Силач зрубав 100. Секрет полягав у тому, що він точив лезо тоді коли відпочивав. Ваше здоров’я – це ваша сокира і якщо вона буде тупа ви не зможете вирубати собі дорогу до успіху.
Тому нехай всі ваші сокири будуть заточені!