Нечітка кластеризація масивів даних з пропущеними значеннями
Запропоновано алгоритм заповнення пропущених значень в масивах даних, що базується на використанні Адаліни. Цей алгоритм дозволяє заповнювати пропуски в режимі on-line. Виконано оцінку якості методів нечіткої кластеризації даних з пропущеними значеннями залежно від алгоритму їх заповнення. Предложен...
Saved in:
| Published in: | Індуктивне моделювання складних систем |
|---|---|
| Date: | 2011 |
| Main Authors: | , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
2011
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/45927 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Нечітка кластеризація масивів даних з пропущеними значеннями / В.В. Волкова, А.Ю. Шафроненко // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2011. — Вип. 3. — С. 27-32. — Бібліогр.: 4 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859809316173774848 |
|---|---|
| author | Волкова, В.В. Шафроненко, А.Ю. |
| author_facet | Волкова, В.В. Шафроненко, А.Ю. |
| citation_txt | Нечітка кластеризація масивів даних з пропущеними значеннями / В.В. Волкова, А.Ю. Шафроненко // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2011. — Вип. 3. — С. 27-32. — Бібліогр.: 4 назв. — укр. |
| collection | DSpace DC |
| container_title | Індуктивне моделювання складних систем |
| description | Запропоновано алгоритм заповнення пропущених значень в масивах даних, що базується на використанні Адаліни. Цей алгоритм дозволяє заповнювати пропуски в режимі on-line. Виконано оцінку якості методів нечіткої кластеризації даних з пропущеними значеннями залежно від алгоритму їх заповнення.
Предложен алгоритм заполнения пропущенных значений в массивах данных, основанный на использовании Адалины. Алгоритм позволяет заполнять пропуски в режиме on-line. Выполнена оценка качества методов нечеткой кластеризации данных с пропущенными значениями в зависимости от алгоритма их заполнения.
The algorithm for filling the missing values in data massive is proposed. This algorithm is based on using the Adaline and allows to close the missing values in on-line mode. An evaluation of quality of fuzzy clustering methods for data with missing values depending on algorithm of they filling is performed.
|
| first_indexed | 2025-12-07T15:18:32Z |
| format | Article |
| fulltext |
Нечітка кластеризація масивів даних
УДК 004.032.26
НЕЧІТКА КЛАСТЕРИЗАЦІЯ МАСИВІВ ДАНИХ
З ПРОПУЩЕНИМИ ЗНАЧЕННЯМИ
В.В. Волкова, А.Ю.Шафроненко
Харківський національний університет радіоелектроніки,
val_volkova@ukr.net, alinashafronenko@gmail.com
Запропоновано алгоритм заповнення пропущених значень в масивах даних, що базується на
використанні Адаліни. Цей алгоритм дозволяє заповнювати пропуски в режимі on-line.
Виконано оцінку якості методів нечіткої кластеризації даних з пропущеними значеннями
залежно від алгоритму їх заповнення.
Ключові слова: дані з пропущеними значеннями, кластеризація, алгоритм
The algorithm for filling the missing values in data massive is proposed. This algorithm is based on
using the Adaline and allows to close the missing values in on-line mode. An evaluation of quality
of fuzzy clustering methods for data with missing values depending on algorithm of they filling is
performed.
Keywords: data with missing values, clustering, algorithm
Предложен алгоритм заполнения пропущенных значений в массивах данных, основанный на
использовании Адалины. Алгоритм позволяет заполнять пропуски в режиме on-line.
Выполнена оценка качества методов нечеткой кластеризации данных с пропущенными
значениями в зависимости от алгоритма их заполнения.
Ключевые слова: данные с пропущенными значениями, кластеризация, алгоритм
Вступ
Завдання кластеризації даних є важливим елементом загальної проблеми
Data Mining, а для її вирішення сьогодні існує безліч підходів і алгоритмів від
суто інтуїтивних і евристичних до строго математичних. Разом з тим, у бага-
тьох задачах Data Mining, включаючи кластеризацію, вихідні таблиці даних
«об’єкт-властивість» можуть містити порожні клітини (пропуски), інформація в
яких з тих чи інших причин відсутня. Задачі відновлення таких пропущених
спостережень приділялося достатньо уваги [1], при тому більш ефективними в
даній ситуації опинилися підходи, що базуються на математичному апараті
м’яких обчислень (обчислювального інтелекту), і, перш за все, штучних ней-
ронних мережах [2]. Разом з тим, відомі підходи до відновлення пропусків і
традиційні алгоритми кластеризації працездатні лише у випадках, коли вихідна
таблиця задана апріорно і число її рядків або стовпців не змінюється в процесі
обробки.
У той же час існує досить широкий клас задач, коли дані надходять на
обробку послідовно в on-line режимі, при цьому заздалегідь невідомо, який з
оброблюваних векторів-образів може містити пропуски. При цьому процеси ві-
Індуктивне моделювання складних систем, випуск 3, 2011 27
mailto:@ukr.net
В.В. Волкова, А.Ю. Шафроненко
дновлення даних та їх кластеризація повинні протікати паралельно та в реаль-
ному часі.
Традиційний підхід до вирішення таких завдань передбачає, що кожне
спостереження може відноситися тільки до одного кластеру, хоча більш приро-
дною видається ситуація, коли оброблюваний вектор ознак з різними рівнями
належності може відноситись одразу до декількох класів. Ця ситуація є предме-
том розгляду нечіткого кластерного аналізу, що інтенсивно розвивається в да-
ний час [3,4]. У зв’язку з цим у даній роботі розглядається алгоритм заповнення
пропущених даних, що базується на принципах лінійної регресії, а також аналі-
зується залежність якості роботи алгоритмів нечіткої кластеризації даних з
пропущеними значеннями залежно від алгоритму заповнення пропусків.
1. Алгоритми заповнення пропущених даних
Алгоритми заповнення пропусків розробляються для емпіричних таблиць
типу «об’єкт-властивість». Таблиці типу«об’єкт-властивість» – це таблиці, в
яких у рядках перелічені об’єкти (наприклад, підприємства), а в стовпцях – їх
властивості. Ці таблиці експериментальних даних можуть містити пропуски.
Завдання алгоритмів заповнення пропущених даних полягає в заповненні
пропусків у таблицях найбільш правдоподібними значеннями з найменшою по-
хибкою. Схематично алгоритми заповнення пропусків у таблицях даних ілюст-
рує рис. 1.
Рис. 1. Алгоритми заповнення пропущених даних
Індуктивне моделювання складних систем, випуск 3, 2011 28
Нечітка кластеризація масивів даних
Як видно з рис. 1, алгоритми заповнення пропусків у емпіричних табли-
цях даних можна умовно розділити на складні та прості. До простих алгоритмів
відносяться такі методи заповнення таблиць як: середнє арифметичне, алгоритм
найближчого сусіда, метод багатовимірної лінійної регресії. Складні алгорит-
ми, в свою чергу, діляться на дві частини: глобальні та локальні. До глобальних
алгоритмів відносяться метод Барлетта, алгоритм resampling, МП-алгоритми,
ЕМ-алгоритми, локальний – алгоритм ZET.
2. Постановка задачі
Нехай задана N×n таблиця «об’єкт-властивість» (табл.1), що містить ін-
формацію про N об’єктів, кожний з яких описується (1×n)-вектором-рядком
ознак ),...,,...,,...,( 1 inijipii xxxxx = . При цьому припускається, що NG рядків мо-
жуть мати по одному пропущеному значенню, а NF =N-NG заповнені повністю.
Таблиця 1.
Таблиця виду «об’єкт-властивість».
1 … p … j … n
1 x11 … x1p … x1j … x1n
… … … … … … … …
i xi1 … xip … xij … xin
… … … … … … … …
k xk1 … xkp … xkj … xkn
… … … … … … … …
N xN … xN … xN … xN
,
В процесі обробки таблиці необхідно заповнити пропуски так, щоб відно-
влені елементи були б у певному сенсі «найбільш правдоподібні» або «близькі»
до апріорі невідомих закономірностей, що містяться в таблиці.
3. Алгоритм заповнення пропущених даних на основі Адаліни
Представимо таблицю 1 у вигляді (N × n)-матриці Х, в якій відсутній один
елемент kjx
або в більш загальному випадку відсутні NG елементів. Припуска-
ється [3], що між стовпцями T
jNkjijjj xxxxx ),...,,...,,...,( 1= існує лінійна кореляція,
на підставі якої й проводиться відновлення пропуску за допомогою регресії
knjnjkjjjkjjkjkjjkj xwxwxwxwxwwx ++++++= ++−− ...ˆ 1,1,1,1,22110 , (1)
Індуктивне моделювання складних систем, випуск 3, 2011 29
В.В. Волкова, А.Ю. Шафроненко
або
jkjkj wXx =ˆ , (2)
де T
jnjjj wwww ),...,,( 10= – ( 1n× ) -вектор параметрів, що підлягають визначенню ,
1 , 1 , 1X (1, ,..., , ,..., ) - (1 )kj k k j k j knx x x x n− +=ur × -вектор-рядок ознак k-того об’єкту без -того
елементу і з одиницею на першій позиції.
kj
Вектор невідомих параметрів jw може бути знайдений за допомогою ста-
ндартного методу найменших квадратів, для чого з матриці X слід вилучити k-
й рядок, j-й стовпець, додати зліва стовпець з одиниць та на основі отриманої
(( 1) )N − × n -матриці jX розрахувати оцінки параметрів
j
T
jj
T
jj Xw XX)X( += (3)
де T
Njjkjkijjj xxxxx ),...,,,...,,...,(X ,1,11 +−= , +•)( – символ псевдообернення по Муру-
Пенроузу [8].
Якщо ж пропуски існують в GN рядках та в інших стовпцях, з матриці X
вилучаються усі ці рядки та на підставі отриманої усіченої ( FN n× ) -матриці n
раз знаходять вектори параметрів (3) для всіх nj ,...,2,1= .
Далі за допомогою рівнянь (1) та (3) заповнюються все пропуски отрима-
ними оцінками kjx̂ .
Цей алгоритм нескладно поширити на випадок, коли дані про об’єкти в
таблицю 1 надходять послідовно об’єкт за об’єктом. При появі )1( +N -го спо-
стереження у вигляді цілком заповненого рядка 1+NX оцінка може бути відко-
ригована за допомогою рекурентного методу найменших квадратів
1,1,
1,
1, 1,
1, 1,
1, 1,
( )( X ( ))
( 1) ( ) X
1 X ( )X
( )X X ( )
( 1) ( ) ,
1 X ( )X
TN jj F N j j F
N jj F j F T
N j N jj F
T
N j N jj F j F
j F j F T
N j N jj F
P N x w N
w N w N
P N
P N P N
P N P N
P N
++
+
+ +
+ +
+ +
−⎧
+ = +⎪ +⎪
⎨
⎪ + = −⎪ +⎩
ur
ur
ur ur
ur ur
ur ur
,
(4)
після чого уточнюються відновлені значення kjx̂ .
Обробку інформації в режимі послідовного надходження даних зручно
організувати на основі нейромережевої системи, основними елементами якої є
n паралельно працюючих адаптивних лінійних асоціаторів (ALA), які навча-
ються за допомогою алгоритму (4). На рис.2 наведена схема цієї системи, яка не
потребує додаткових пояснень.
Індуктивне моделювання складних систем, випуск 3, 2011 30
Нечітка кластеризація масивів даних
Рис. 2. Адаптивна нейромережева система для відновлення пропусків
Зауважимо тільки, що індекс k тут позначає номер об’єкту, характеристи-
ки якого в поточний момент часу подаються на обробку.
4. Нечітка кластеризація даних з пропущеними значеннями
Для оцінки якості нечіткої кластеризації даних з пропущеними значення-
ми було обрано алгоритми fuzzy c-means, Gustafson-Kessel та Gath-Geva [3, 4].
Якість їх роботи перевірялась на вибірках даних UCI-репозиторію, зокрема Iris,
Wines та Breast-Cancer-Wisconsin.
У таблиці 2 наведено результати тестувань для вказаних алгоритмів для
вибірки даних Wines з відновленими 100 пропущеними значеннями.
Таблиця 2.
Оцінка якості роботи алгоритмів нечіткої кластеризації.
PC CE SC Алгоритм
кластеризації AdA Mean AdA Mean AdA Mean
Fuzzy c-means 0.5036 0.5025 0.8541 0.8559 1.6255 1.6374
Gustafson-Kessel 0.2755 0.2726 1.3386 1.3441 44.7481 51.0859
Gath-Geva 0.2542 0.2542 1.3785 1.3785 4.4064e-
005
4.4134e-
005
Індуктивне моделювання складних систем, випуск 3, 2011 31
В.В. Волкова, А.Ю. Шафроненко
Продовження табл. 2
S XB DI Алгоритм
кластеризації AdA Mean AdA Mean AdA Mean
Fuzzy c-means 0.0119 0.0120 0.0119 0.9692 0.1423 0.1423
Gustafson-Kessel 0.3350 0.3793 0.5717 0.5137 0.0782 0.0782
Gath-Geva 3.2490e-
007
3.2378e-
007 53.3548 52.2223 0.1145 0.1145
У якості критеріїв оцінки якості кластеризації було використано такі ха-
рактеристики: Partition Coefficient (PC), Classification Entropy (CE), Partition
Index (SC), Separation Index (S), Xie and Beni’s Undex (XB) та Dunn’s Index (DI).
Розглянуті критерії використовуються для оцінки роботи саме алгоритмів нечі-
ткої кластеризації та показують якість розбиття даних по кластерах.
Як можна бачити з табл.2, запропонований підхід до відновлення пропу-
щених значень має найкращі показники якості розбиття даних на кластери.
Висновки
Розглянуто задачу відновлення пропущених значень у таблицях типу
«об’єкт-властивість» у режимі послідовного надходження їх на обробку.
Запропоновано алгоритм вирішення цієї задачі на основі нейромережевої
системи, що складається з адаптивних лінійних асоціаторів, та дозволяє
обробляти дані у on-line режимі. Виконано оцінку якості роботи деяких
алгоритмів нечіткої кластеризації даних з пропущеними значеннями в
залежності від алгоритмів їх відновлення. Експериментальні дослідження
показали, що найбільш ефективною є кластеризація даних, пропущені значення
яких були відновлені за допомогою запропонованого алгоритму.
Література
1. Gorban A., Kegl B., Wunsch B., Zinovyev A. (Eds.) Principal Manifolds for Data
Visualization and Dimension Reduction. Lecture Notes in Computational Science
and Engineering, Vol. 58. – Berlin –Heidelberg– New York: Springer, 2007, – 330 p.
2. Bishop C.M. Neural Networks for Pattern Recognition. – Oxford: Clarendon Press,
1995, – 482 p.
3. Bezdek J.C. Pattern Recognition with Fuzzy Objective Function Algorithms. –
N.Y.: Plenum Press, 1981, – 272 p.
4. Höppner F., Klawonn F., Kruse R., Runkler T. Fuzzy Cluster Analysis: Methods
for Classification, Data Analysis and Image Recognition. – Chichester, Wiley, 1999,
– 300 p.
Індуктивне моделювання складних систем, випуск 3, 2011 32
|
| id | nasplib_isofts_kiev_ua-123456789-45927 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0044 |
| language | Ukrainian |
| last_indexed | 2025-12-07T15:18:32Z |
| publishDate | 2011 |
| publisher | Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| record_format | dspace |
| spelling | Волкова, В.В. Шафроненко, А.Ю. 2013-06-20T19:07:20Z 2013-06-20T19:07:20Z 2011 Нечітка кластеризація масивів даних з пропущеними значеннями / В.В. Волкова, А.Ю. Шафроненко // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2011. — Вип. 3. — С. 27-32. — Бібліогр.: 4 назв. — укр. XXXX-0044 https://nasplib.isofts.kiev.ua/handle/123456789/45927 004.032.26 Запропоновано алгоритм заповнення пропущених значень в масивах даних, що базується на використанні Адаліни. Цей алгоритм дозволяє заповнювати пропуски в режимі on-line. Виконано оцінку якості методів нечіткої кластеризації даних з пропущеними значеннями залежно від алгоритму їх заповнення. Предложен алгоритм заполнения пропущенных значений в массивах данных, основанный на использовании Адалины. Алгоритм позволяет заполнять пропуски в режиме on-line. Выполнена оценка качества методов нечеткой кластеризации данных с пропущенными значениями в зависимости от алгоритма их заполнения. The algorithm for filling the missing values in data massive is proposed. This algorithm is based on using the Adaline and allows to close the missing values in on-line mode. An evaluation of quality of fuzzy clustering methods for data with missing values depending on algorithm of they filling is performed. uk Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України Індуктивне моделювання складних систем Нечітка кластеризація масивів даних з пропущеними значеннями Article published earlier |
| spellingShingle | Нечітка кластеризація масивів даних з пропущеними значеннями Волкова, В.В. Шафроненко, А.Ю. |
| title | Нечітка кластеризація масивів даних з пропущеними значеннями |
| title_full | Нечітка кластеризація масивів даних з пропущеними значеннями |
| title_fullStr | Нечітка кластеризація масивів даних з пропущеними значеннями |
| title_full_unstemmed | Нечітка кластеризація масивів даних з пропущеними значеннями |
| title_short | Нечітка кластеризація масивів даних з пропущеними значеннями |
| title_sort | нечітка кластеризація масивів даних з пропущеними значеннями |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/45927 |
| work_keys_str_mv | AT volkovavv nečítkaklasterizacíâmasivívdanihzpropuŝenimiznačennâmi AT šafronenkoaû nečítkaklasterizacíâmasivívdanihzpropuŝenimiznačennâmi |