« Назад

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

Завдання: Реалізувати алгоритм відповідно до варіанту завдання будуючий unsupervised модель.

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

4.1. Введення

Бібліотека Xelopes дозволяє додавати нові тим самим розширюючи її. В бібліотеці є необхідна інфраструктура для роботи алгоритмів data mining за рахунок чого процес упровадження нового алгоритму не складний. Сумісність з такими стандартами data mining як CWM і PMML дозволяє інтегрувати реалізовані алгоритми в існуючі системи з мінімальними витратами.

Відповідно до стандарту CWM загальну концепцію роботи алгоритмів бібліотеки Xelopes можна представити оскільки це зображено на рис. 1.

Рис. 1 - Загальна концепція роботи алгоритмів в бібліотеці Xelopes

Згідно даній концепції на вхід будь-якого алгоритму подаються початкові дані у вигляді потоку представленого класом MiningInputStream. Окрім даних перед роботою алгоритму повинні бути виконані відповідні налагодження. Вони діляться на два типи: налагодження специфічні для вирішуваної задачі (моделі, що будується) і налагодження специфічні для конкретного алгоритму. Перші реалізуються за допомогою спадкоємства від класу MiningSettings, другий тип спадкоємство від класу MiningAlgorithmSpecification. Результат роботи алгоритму представляється у вигляді моделей є екземплярами класу MiningModel. Самі алгоритми успадковуються від класу MiningAlgorithm.

У бібліотеці Xelopes реалізовані класи налагодження, моделей і алгоритмів для основних задач data minig (табл. 1). Необхідно помітити, що вхідні дані не залежать від вирішуваної задачі і для будь-якого алгоритму представляються у вигляді екземпляра класу MiningInputStream.

Таблиця 4.1. Основні класи бібліотеки Xelopes

№	Задача	Клас налагодження	Клас моделі	Клас алгоритму
1	Статистические задачи	StatisticsMiningSettings	StatisticsMiningModel	StatisticsAlgorithm
2	Поиск ассоциативных правил	AssociationRulesSettings	AssociationRulesMiningModel	AssociationRulesAlgorithm
3	Сиквинциальный анализ	SequentialSettings	SequentialMiningModel	SequentialAlgorithm
4		CustomerSequentialSettings	CustomerSequentialMiningModel	CustomerSequentialAlgorithm
5	Кластеризация	ClusteringMiningSettings	ClusteringMiningModel	ClusteringAlgorithm
6	Регрессии	SupportVectorSettings	SupportVectorMiningModel	SupportVectorAlgorithm
7		SparseGridsSettings	SparseGridsMiningModel	SparseGridsAlgorithm
8	Классификации	DecisionTreeSettings	DecisionTreeMiningModel	DecisionTreeMiningModel

Для реалізації власного алгоритму необхідно реалізувати клас, успадкований від одного з підкласів класу MiningAlgorithm (залежно від тієї задачі, яка розв'язується). В підкласі реалізувати метод runAlgorithm(). Даний метод викликається з методу вже реалізованого buildModel(). В цьому ж методі після після запуску алгоритму виконується створення моделі відповідного підкласу класу MiningModel. Для коректної побудови моделі необхідно щоб клас алгоритму реалізовував методи визначені як абстрактні в класі предку.

Алгоритм повинен враховувати налагодження. Для цього в класі MiningAlgorithm реалізовані методи setMiningSettings( MiningSettings miningSettings ) і setApplicationInputSpecification( ApplicationInputSpecification арplicationInputSpecification ). Вхідні дані передаються в алгоритм за допомогою реалізованого в цьому ж класі методу setMiningInputStream( MiningInputStream miningInputStream ).

Таким чином, при для додавання в бібліотеку Xelopes нового алгоритму достатньо реалізувати абстрактні методи одного з підкласів класу MiningAlgorithm (залежно від тієї задачі, яка розв'язується). Особливості реалізації вже залежать від задачі вирішуваної створюваним алгоритмом.

4.2. Задача пошуку асоціативних правил

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

Розглянемо реалізацію алгоритмів вирішальних задачу пошуку асоціативних правил він повинен успадковуватися від класу com.prudsys.pdm.Models.AssociationRules.AssociationRulesAlgorithm, який в свою чергу успадковується від класу com.prudsys.pdm.Core. MiningAlgorithm. В результаті він повинен реалізувати наступні абстрактні методи викликаються з методу buildModel() класу AssociationRulesAlgorithm:

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

protected Vector getAssociationRules() – повертає вектор містить побудовані асоціативні правила. Асоціативне правило представляється екземпляром класу RuleSet

protected Vector getLargeItemSets() – повертає вектор частих наборів. Частий набір представляється екземпляром класу ItemSet.

Перш ніж перейти до докладнішого опису цих методів, розглянемо, як вони викликаються з методу buildModel() класу AssociationRulesAlgorithm. Далі представлена частина коду методу створююча модель класу AssociationRulesMiningModel що відображає загальний принцип:

runAlgorithm();

AssociationRulesMiningModel model = new AssociationRulesMiningModel();

model.setMiningSettings( miningSettings );

model.setInputSpec( арplicationInputSpecification );

Vector rules = getAssociationRules();

model.setAssociationRules( rules );

model.setLargeItemSets( getLargeItemSets() );

this.miningModel = model;

return model;

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

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

4.2.1. Метод runAlgorithm

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

protected MiningInputStream miningInputStream;

protected MiningSettings miningSettings;

protected MiningAlgorithmSpecification miningAlgorithmSpecification;

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

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

getItemId() – повертає категоріальний атрибут класу CategoricalAttribute що є ідентифікатором досліджуваних об'єктів (елементів).

getTransactionId() – повертає категоріальний атрибут класу CategoricalAttribute що є ідентифікатором транзакцій.

getMinimumSupport() – повертає значення типу double що є значенням мінімальної підтримки для шуканих частих наборів.

getMinimumConfidence() - повертає значення типу double що є значенням мінімального ступеня довір'я для шуканих асоціативних правил.

4.2.2. Метод getAssociationRules

Метод getAssociationRules() повинен повертати вектор, що містить побудовані асоціативні правила. Асоціативне правило представляється екземпляром класу RuleSet.

Клас RuleSet має наступні змінні характеризуюче правило, що представляється ним:

public ItemSet premise – змінна представляюча умовну частину правила як набір елементів класу ItemSet.

public ItemSet conclusion – змінна представляюча завершальну частину правила як набір елементів класу ItemSet.

public int size – розмір правила (кількість елементів в умовній і завершальній частині)

public double support – підтримка правила;

public double confidence – ступінь довір'я правила.

4.2.3. Метод getLargeItemSets

Метод getLargeItemSets() повинен повертати вектор, частих наборів. Частий набір представляється екземпляром класу ItemSet.

Клас ItemSet має наступні змінні, що характеризують частий набір, що представляється ним:

private IntVector itemList – список індексів елементів входять в набір (реалізований як вектор цілих чисел).

private int supportCount – підтримка набору;

private int size – кількість елементів входять в набір.

4.3. Задача кластеризації

Задача кластеризації полягає в пошуку незалежних груп (кластерів) і їх характеристик у всій безлічі аналізованих даних. Рішення цієї задачі допомагає краще зрозуміти дані. Крім того, угрупування однорідних об'єктів дозволяє скоротити їх число, а отже і полегшити аналіз.

Розглянемо реалізацію неієрархічних алгоритмів вирішальних задачу кластеризації. Такі алгоритми повинні успадковуватися від класу com.prudsys.pdm.Models.Clustering.CDBased.CDBasedClusteringAlgorithm, який успадковується від класу com.prudsys.pdm.Models.Clustering.ClusteringAlgorithm, який в свою чергу успадковується від класу com.prudsys.pdm.Core.MiningAlgorithm. В результаті він повинен реалізувати наступні методи, що викликаються з методу buildModel() класу CDBasedClusteringAlgorithm.

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

protected Cluster[] getClusters() – повертає масив містить побудовані кластери. Кластер представляється екземпляром класу Cluster

public Distances getDistances() – повертає міру відстані, що використовується. Міра представляється екземпляром класу Distances.

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

public MiningModel buildModel() throws MiningException

{

runAlgorithm();

CDBasedClusteringMiningModel model = new CDBasedClusteringMiningModel();

model.setMiningSettings( miningSettings );

model.setInputSpec( арplicationInputSpecification );

model.setClusters( getClusters() );

model.setDistanceType( getDistances() );

this.miningModel = model;

return model;

}

Так само як і у разі асоціативних правил спочатку запускається алгоритм, реалізовуваний підкласом. Далі створюється екземпляр центрованої/розподіленої моделі кластерів і їй передаються налагодження, при яких вона була створена. Далі за допомогою методу getClusters() моделі привласнюється масив кластерів. Модель також повинна містити і міру відстані, яка може бути одержана методом getDistances, що використовується.

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

4.3.1. Метод runAlgorithm

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

protected MiningInputStream miningInputStream;

protected MiningSettings miningSettings;

protected MiningAlgorithmSpecification miningAlgorithmSpecification;

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

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

getClusterIdAttributeName() – повертає ім'я атрибуту є ідентифікатором кластерів.

getMaxNumberOfClusters() – максимальна кількість кластерів, що будуються.

4.3.2. Метод getClusters

Метод getClusters () повинен повертати масив, що містить побудовані кластери. Кластер представляється екземпляром класу Cluster.

Клас Cluster має наступні змінні характеризуюче кластер, що представляється ним:

private String name – ім'я кластера;

private MiningVector сеnterVec – вектор визначальний центр даного вектора;

private Vector сеnterVectors – набір векторів представляючих центр даного кластера (декілька векторів можливі у разі перетворення категоріальних типів в числові);

private Vector containedVectors – містить набір векторів (об'єктів) входять в даний кластер;

4.3.3. Метод getDistances

Метод getDistances () повинен повертати міру відстані, що використовується. Міра представляється екземпляром класу Distances.

Клас Distances має наступні змінні характеризуюче міру відстані, що представляється ним:

private int type - код типу функції використовується для обчислення відстані (наприклад, Euclidean, Squared Eucliden, City-Block, і т.п.).

private int measureType – код типу міри відстані (distance, similarity)

private int compareFunction - код типу функції використовується для порівняння (наприклад, Abs Diff, Gauss-Sim, і т.п.).

private double[] fieldWeights – масив терезів для кожного атрибуту даних;

private boolean normalized – визначає чи використовувати при обчисленні відстані нормалізацію;

private double[] minAtt – масив мінімальних значень всіх атрибутів (необхідні при нормалізації);

private double[] maxAtt – масив максимальних значень всіх атрибутів (необхідні при нормалізації).

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

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

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

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

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

5. Відладити алгоритм.

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

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

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

Варіант		Алгоритм
1	Apriori TID на підставі реалізації алгоритму Apriori в Xelopes
2	Алгоритм KMeans
3	Дівізімний алгоритм кластеризації
4	Аггломератівний алгоритм кластеризації

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

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

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

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

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

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

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

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

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

2. Що таке описові моделі.

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

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

5. Які існують алгоритми сиквенціального аналізу.

6. У чому ідея алгоритму KMeans.

7. Які існують дівізімні алгоритми і ніж вони відрізняються один від одного.

8. Які існують аггломератівні алгоритми і ніж вони відрізняються один від одного.