Лабораторна робота №5, Реалізація алгоритмів побудови supervised моделей – Варіант №2

« Назад

Мета: Вивчити основні принципи розробки алгоритмів data mining будують supervised моделі. А також застосування цих моделей до нових даними.

Завдання: Реалізувати алгоритм відповідно до варіанта завдання будує supervised модель, яка могла б бути використана для передбачення на нових даних.

Загальні відомості

5.1. Введення

Завдання класифікації та кластеризації відносяться до типу завдань з учителем - supervised learning. Такі завдання вирішуються в кілька етапів. Спочатку за допомогою якого-небудь алгоритму data mining, будується модель аналізованих даних - класифікатор. Потім, класифікатор піддається «навчанню». Іншими словами, перевіряється якість його роботи і, якщо вона незадовільна, то відбувається «додаткове навчання» класифікатора. Так відбувається до тих пір, поки ми не досягнемо необхідного рівня якості або не переконаємося, що обраний алгоритм не працює коректно з даними, або ж самі дані не мають структури, яку можна виявити. До цього типу задач відносять задачі класифікації і регресії.

У результаті описаних відмінностей в стандарт CWM були введені спеціальні класи для такого виду завдань:

SupervisedMiningModel - успадковується від класу MiningModel і використовується при вирішенні supervised завданнях (задач класифікації та регресії).

SupervisedMiningSettings - успадковується від класу MiningSettings і використовується для визначення установок для задач з учителем.

У відповідності зі стандартами бібліотека Xelopes також підтримує даний підхід. Більш того за аналогією з класами моделей і налаштувань був доданий клас SupervisedMiningAlgorithm.

У бібліотеку був доданий інтерфейс Classifier, який описує метод applay(), що виконує класифікацію на основі побудованої моделі нових даних. Даний метод має реалізовуватися усіма класами, що реалізують інтерфейс Classifier.

До типу завдань з учителем ставляться задачі класифікації і регресії. Для тих хто будує відповідні моделі в бібліотеці присутні наступні класи:

• ClassificationMiningModel - розширює SupervisedMiningModel для задачі класифікації;

• DecisionTreeMiningModel - розширює ClassificationMiningModel для моделей дерев рішень;

• RegressionMiningModel - розширює SupervisedMiningModel для задачі регресії;

• SupportVectorModel - розширює RegressionModel для моделей побудованих методом Support Vector Machines;

• ClassificationMiningSettings - розширює SupervisedMiningSettings для налаштування процесу вирішення задачі класифікації;

• DecisionTreeSettings - розширює ClassificationSettings для дерев рішень,

• RegressionMiningSettings - розширює SupervisedMiningSettings для налаштування процесу рішення задачі регресії;

• SupportVectorSettings - розширює RegressionSettings для методу Support Vector Machines;

• ClassificationAlgorithm - розширює SupervisedMiningAlgorithm для задачі класифікації;

• DecisionTreeMiningAlgorithm - розширює ClassificationMiningAlgorithm для алгоритмів дерева рішень;

• RegressionAlgorithm - розширює SupervisedMiningAlgorithm для задачі регресії;

• SupportVectorAlgorithm - розширює RegressionAlgorithm для алгоритмів Support Vector Machines.

Перераховані класи та їх підкласи необхідні для реалізації власних алгоритмів вирішують завдання класифікації і регресії.

5.2. Завдання класифікації

Завдання класифікації зводиться до визначення класу об'єкта за його характеристикам. Необхідно зауважити, що в цьому завданні безліч класів, до яких може бути віднесений об'єкт заздалегідь відомо.

Розглянемо реалізацію алгоритмів, що будують дерева рішень класифікації даних. Такі алгоритми повинні успадковуватися від класу com.prudsys.pdm.Models.Classification.DecisionTree.DecisionTreeAlgorithm. В результаті він повинен реалізувати наступні методи, що викликаються з методу buildModel() класу DecisionTreeAlgorithm.

protected void runAlgorithm() - реалізація алгоритму

protected Classifier getClassifier() - повертає класифікатор, що виконує класифікацію нових даних. Класифікатор представляється екземпляром класу, що реалізовує інтерфейс Classifier

Розглянемо, більш докладно метод buildModel() класу DecisionTreeAlgorithm. Далі представлений код методу, що створює модель класу DecisionTreeMiningModel.

public MiningModel buildModel() throws MiningException

{

runAlgorithm();

DecisionTreeMiningModel model = new DecisionTreeMiningModel();

model.setMiningSettings( miningSettings );

model.setInputSpec( applicationInputSpecification );

model.setClassifier( getClassifier() );

ApplicationAttribute target = applicationInputSpecification.getTargetApplicationAttribute();

model.setTarget( target );

this.miningModel = model;

return model;

}

Спочатку запускається алгоритм, реалізований підкласом. Далі створюється екземпляр моделі, що представляє собою дерево рішень і їй передаються налагодження, при яких вона була створена. Далі за допомогою методу getClassifier() моделі присвоюється екземпляр класу, що виконує класифікацію нових об'єктів.

Тепер більш докладно зупинимося на методах, які повинні реалізовувати підкласи класу DecisionTreeAlgorithm.

5.2.1. Метод runAlgorithm

Метод runAlgorithm() реалізує алгоритм побудови класифікаційної функції на підставі навчальної вибірки. Вихідні дані, налаштування процесу побудови алгоритму і специфічні параметри алгоритм отримує через змінні класу MiningAlgorithm

protected MiningInputStream miningInputStream;

protected MiningSettings miningSettings;

protected MiningAlgorithmSpecification miningAlgorithmSpecification;

Доступ до них здійснюється за допомогою відповідних методів set/get.

При побудові класифікуючої функції виду дерева рішень змінна miningSettings повинна бути екземпляром класу DecisionTreeSettings. Вона за допомогою методів get надає доступ до наступних параметрів процесу побудови моделі:

getCostMatrix() - матриця вартості;

getTarget() - посилання на екземпляр класу MiningAttribute, що визначає незалежну змінну;

getPredictedAttributeName() - ім'я атрибута значення, яке необхідно передбачити (ім'я залежної змінної);

getConfidenceAttributeName() - ім'я атрибута, що визначає степінь довіри передбачення.

getCostFunction() - функція, що визначає вартість некоректного передбачення. Значеннями можуть бути entropy, Gini, costMatrix, pnorm або none

5.2.2. Метод getClassifier

Метод getClassifier() повинен повертати класифікатор, що виконує класифікацію нових даних. Класифікатор представляється екземпляром класу, що реалізовує інтерфейс Classifier.

Інтерфейс Classifier описує один єдиний метод:

public double apply(MiningVector miningVector)

У якості аргументу методу передається вектор, що описує якийсь об'єкт, який необхідно віднести до одного з відомих класів (тобто класифікувати). В якості значення, що повертається передається оцінка класифікації/регресії для даного вектора.

Для класифікації даних за допомогою дерев рішень в бібліотеці знаходиться клас com.prudsys.pdm.Models.Classification.DecisionTree.DecisionTreeNode, що реалізує інтерфейс Classifier. Цей клас успадковується від класу com.prudsys.pdm.Core.MiningTreeNode який реалізує функціональність, яка необхідну для переміщення по дереву від одного вузла до іншого. Крім неї клас DecisionTreeNode реалізує метод applay():

public double apply( MiningVector miningVector ) throws MiningException

{

if(leaf) return score;

else

{

for(int i=0;i<children.length;i++)

{

DecisionTreeNode dtn = (DecisionTreeNode)children[i];

if(dtn.predicate.evaluate(miningVector))

return dtn.apply(miningVector);

}

throw new MiningException("bad tree mode");

}

}

У цьому методі новий вектор рекурсивно порівнюється з деяким вузлом дерева. Вибір чергового вузла здійснюється залежно від результату порівняння з батьківським вузлом. Вид порівняння вузлів може бути самий різний.

Класифікатор будується в процесі роботи реалізованого алгоритму. У зв'язку з цим він може залежати від особливостей алгоритму. Отже, разом з реалізацією алгоритму в бібліотеку повинен бути доданий і коректний класифікатор.

5.3. Завдання регресії

Завдання регресії подібно завданню класифікації дозволяє визначити за відомими характеристиками об'єкта значення деякого його параметра. На відміну від задачі класифікації значенням параметра є не кінцева множина класів, а безліч дійсних чисел. У зв'язку з близькістю цих двох завдань підхід реалізації алгоритмів побудови функції регресії близький до побудови класифікатора.

Алгоритми, що будують функціональні залежності повинні успадковуватися від класу com.prudsys.pdm.Models.Regression.RegressionAlgorithm і реалізувати ті ж методи, що і у випадку з класифікацією.

protected void runAlgorithm() - реалізація алгоритму

protected Classifier getClassifier() - повертає класифікатор, що обчислює значення залежної змінної. Класифікатор представляється екземпляром класу, що реалізовує інтерфейс Classifier

Метод buildModel() класу RegressionAlgorithm створює модель класу RegressionMiningModel за аналогією з класом DecisionTreeAlgorithm.

Налаштування, реалізовані класом RegressionSettings, ті ж що й в задачі класифікації. Природно, що класифікатор, який будується різниться від розглянутого при описі задачі класифікації. Він багато в чому визначається методом data mining, що використовується і повинен бути реалізований спільно з алгоритмом.

Порядок виконання роботи

1. Вивчити алгоритм, визначений варіантом завдання.

2. Створити новий клас, наслідуваний від відповідного класу бібліотеки Xelopes.

3. Реалізувати алгоритм, визначений варіантом завдання.

4. Додати алгоритм в бібліотеку Xelopes.

5. Налагодити алгоритм.

6. Побудувати за допомогою реалізованого алгоритму моделі для всіх файлів з даними.

7. Застосувати побудовані моделі до нових даних.

8. Порівняти отримані результати з моделями, побудованими подібними алгоритмами з бібліотеки Xelopes.

Варіанти завдання

варіант	Алгоритм
1	Алгоритм 1R
2	Алгоритм Naïve Bayes
3	Використовуючи реалізацію алгоритму ID3 реалізувати алгоритм C4.5
4	Алгоритм покриття
5	Алгоритм найменших квадратів
6	Лінійний різновид алгоритму SVM
7	поліноміальний різновид алгоритму SVM
8	гауссовский різновид алгоритму SVM

Звіт по роботі

1. Титульний лист.

2. Мета роботи.

3. Блок схема алгоритму.

4. Результати застосування до вихідних даних з різних файлів з ​​поясненнями.

5. Порівняння з моделями, побудованими аналогічними алгоритмами, реалізованими в бібліотеці Xelopes.

6. Результати застосування до нових даних з поясненнями.

7. Висновки по роботі.

Контрольні питання

1. Що таке supervised моделі.

2. Що таке передбачувальні моделі.

3. Які моделі відносяться до типу supervised.

4. Які існують алгоритми побудови класифікаційних функцій

5. Які існують алгоритми побудови функцій регресії

6. Які існують алгоритми побудови класифікаційних правил

7. Які існують алгоритми побудови дерев рішень

8. Які існують алгоритми побудови математичних залежностей