Економічні науки/8. Математичні методи в економіці

Аспірант Юрченко К.Л.

Київський національний університет ім.Тараса Шевченка, Україна

Використання ансамблю алгоритмів для кластеризації категоріальних даних

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

Переваги та недоліки існуючих алгоритмів:

К-середнє - найбільш популярний метод кластеризації, був винайдений в 1950-х роках. Є інтуїтивно зрозумілим, більш швидким у порівнянні з ієрархічними алгоритмами.

Використання алгоритму К - середнє для категоріальних даних є більш проблематичним. Недоліки алгоритму [1]:

· Не гарантується досягнення глобального мінімуму сумарного квадратичного відхилення, а тільки одного з локальних мінімумів.

· Результат залежить від вибору початкових центрів кластерів, їх оптимальний вибір невідомий.

· Кількість кластерів треба знати заздалегідь. Початковий вибір кількості кластерів суттєво впливає на результат.

Зазвичай можливо використати попередню агрегацію, що призведе до суттєвого зменшення кількості аналізованих даних без втрати точності. Такий спосіб агрегації дозволяє швидко об’єднати об’єкти, характеристики яких близькі до середніх значень. У випадку категоріальних змінних можна об’єднувати без будь-якого попереднього аналізу об’єкти, що відрізняються тільки однією характеристикою [2].

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

Двоетапний алгоритм кластеризації:

Двоетапний алгоритм кластеризації – метод, розроблений для обробки дуже великих вибірок даних. Він здатний оброблювати неперервні та категоріальні змінні. Опис взятий з документації пакету SPSS. Алгоритм був розроблений на основі низки доповідей на конференціях [3,4]. Він складається з наступних кроків:

· Попередня кластеризація.

· Обробки викидів (опціональний пункт. Може ігноруватись дослідником у разі впевненості в чистоті даних).

· Безпосередньо кластеризація.

Запропонована модифікація:

1. Усі дані мають бути агреговані до категоріальних даних. Неперервні величини такі як час, відстань, вага, вартість мають бути приведені до певних груп.

2. Для кожної характеристики проводиться оцінка мультиноміальної регресії.

3. Спостереження, що були отримані як результати прогнозів на основі мультиноміальної регресії в подальшому кластеризуються за допомогою двоетапного алгоритму кластеризації.

Можна зробити висновок, що використання запропонованої модифікації є певним аналогом використання відстані Махаланобіса як відстані між спостереженнями. Використання цієї відстані в алгоритмах кластеризації є особливо доречним при аналізі даних з високими рівнями кореляції між характеристиками [2].

Висновки та зауваження:

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

Такий ансамбль моделей показав більш високу стійкість утворених кластерів, а отже його використання є доцільним. Використання прогнозів на основі мультиноміальних регресій покращує якість вхідних даних для двоетапного алгоритму кластеризації. Фактично, відбувається прибирання шумів, проводиться попередня, найбільш груба агрегація даних.

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

Перевагою даного методу можна відзначити врахування кореляції між змінними. Ця особливість є особливо актуальною при роботі з даними, що відображають фінансовий стан суб’єктів господарювання: підприємств нефінансового сектору, банків, страхових компаній, фізичних осіб.

У подальших роботах планується модифікувати метод для можливого використання неперервних величин без попереднього групування.

Література:

1. MacQueen J. В. Some methods for classification and analysis of multivariate observations. In Proc. 5th Berkeley Symp. on Math. Statistics and Probability. University of California Press. - 1967. Рages 281—297.

2. Steinhaus H. Sur la division des corps materiels en parties. Bull. Acad. Polon. Sci. – 1956. C1. III vol IV: 801—804.

3. Zhang T. BIRCH: An efficient data clustering method for very large databases. / Т. Zhang, R. Ramakrishnon, and M. Livny // In: Proceedings of the ACM SIGMOD Conference on Management of Data. Montreal, Canada: ACM. - 1996.

4. Матеріали конференції CS769 Spring 2010 Advanced Natural Language Processing: [Електронний ресурс]. – Режим доступу: http://pages.cs.wisc.edu

5. Метод k-середніх: [Електронний ресурс]. – Режим доступу: http://en.wikipedia.org/wiki/K-means_clustering.