Modern robust fuzzy c-means clustering techniques  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
103921
Type PD
Principal investigator Szilágyi, László
Title in Hungarian Korszerű robusztus fuzzy klaszterező eljárások kutatása
Title in English Modern robust fuzzy c-means clustering techniques
Keywords in Hungarian mesterséges intelligencia, felügyelet nélkül osztályozó algoritmusok, fuzzy logika
Keywords in English artificial intelligence, clustering algorithms, fuzzy logic
Discipline
Information Technology (Council of Physical Sciences)100 %
Ortelius classification: Applied informatics
Panel Informatics and Electrical Engineering
Department or equivalent Department of Control Engineering and Information Technology (Budapest University of Technology and Economics)
Starting date 2012-10-01
Closing date 2015-12-31
Funding (in million HUF) 19.800
FTE (full time equivalent) 2.19
state closed project
Summary in Hungarian
A kutatás összefoglalója, célkitűzései szakemberek számára
Itt írja le a kutatás fő célkitűzéseit a témában jártas szakember számára.
Jelen kutatási projekt keretében forradalmasítani kívánjuk a jelenlegi robusztus c-means típusú klaszterezési modellek zajérzékenységét, javítani pontosságukat és hatékonyságukat, egy olyan négyzetes költségfüggvény bevezetésével, mely minőségében újszerűen keveri a valószínűségi és lehetőségfüggvény alapú összetevőket. A jelenlegi algoritmusoknál van egy felső távolsági határ: ha a kívülálló adat ennél távolabb esik, az osztályozás összeomlik. Az általunk javasolt, jelenleg validálásra és publikálásra váró módszer várhatóan elnyomja a távol eső kívülálló adat hatását, ahogyan a gravitációs rendszerek teszik.

Továbbá szándékunkban áll kidolgozni az ún. elnyomott fuzzy c-means algoritmus (s-FCM) általánosított elméletét, egy korábbi dolgozatunkban bevezetett matematikai jellemzőre, a kvázi tanulási rátára alapozva.

A kidolgozott algoritmusok univerzálisak, bármilyen pontszerű csoportokat képező vektoradatok feldolgozására alkalmasak lesznek. Módosított verziók kidolgozására is szükség lesz olyan esetekre, amikor speciális alakú osztályokat kívánunk felismerni. Algoritmusainknak számos alkalmazási felülete várható az alakfelismerő rendszerek, képfeldolgozás, adatbányászat és bioinformatika terén.

A kutatás eredményeit rangos szakfolyóiratokban kívánjuk közölni (legalább 3 cikk), továbbá minimum 2 konferencia dolgozatra számítunk a kutatás minden évében. A kutatást záró évben egy monográfia megírását is tervezzük a kidolgozott algoritmusok alapján.

Mi a kutatás alapkérdése?
Ebben a részben írja le röviden, hogy mi a kutatás segítségével megválaszolni kívánt probléma, mi a kutatás kiinduló hipotézise, milyen kérdéseket válaszolnak meg a kísérletek.
A kutatásnak három alapkérdése van:
(1) Hogyan lehet egy felügyelet nélkül osztályozó, determinisztikus és optimális algoritmust megalkotni, mely egyáltalán nem érzékeny a bemeneti adathalmazban fellelhető kívülálló adatok jelenlétére, és kiváló minőségű partíciót készít ilyen zavarok hiányában is?
(2) Hogyan lehet az alapvetően pontszerű osztályokra működő algoritmust kiterjeszteni speciális alakú osztályok hatékony megkeresésére?
(3) Olyan alkalmazási felületeket (pl. echográf képek vagy szeizmológiai felvételek elemzése) kívánunk keresni a megalkotott algoritmusoknak, melyekben jelentős minőségjavulást kapunk az új algoritmusok alkalmazásakor.

Mi a kutatás jelentősége?
Röviden írja le, milyen új perspektívát nyitnak az alapkutatásban az elért eredmények, milyen társadalmi hasznosíthatóságnak teremtik meg a tudományos alapját. Mutassa be, hogy a megpályázott kutatási területen lévő hazai és a nemzetközi versenytársaihoz képest melyek az egyediségei és erősségei a pályázatának!
A kutatás jelentősége három alapgondolatban összegezve:
(1) A jelenlegi szakirodalom nem ismer olyan felügyelet nélkül tanuló algoritmust, amely annyira figyelmen kívül képes hagyni a kívülálló adatokat, mint amennyire a gravitációs rendszerek képesek a nagyon távoli tárgyakat.
(2) Számos olyan alkalmazási felület van, amelyik csak zajos adatokat tud szolgáltatni. Ezek analíziséhez rendkívüli zajelnyomó algoritmusokra van szükség.
(3) Az újonnan kidolgozott algoritmusok univerzálisak, azaz alkalmasak lesznek bármilyen vektorhalmaz osztályozására, melyben az adatok pontszerű osztályokat képeznek. Az alapalgoritmusokat könnyedén ki lehet terjeszteni speciális alakú osztályok kezelésére létező elméletek alapján.

Ezeket az alapvető hézagokat fogja betömni a javasolt kutatás.

A kutatás összefoglalója, célkitűzései laikusok számára
Ebben a fejezetben írja le a kutatás fő célkitűzéseit alapműveltséggel rendelkező laikusok számára. Ez az összefoglaló a döntéshozók, a média, illetve az érdeklődők tájékoztatása szempontjából különösen fontos az NKFI Hivatal számára.
Amikor ún. felügyelet nélküli osztályozást végzünk, akkor a bemeneti adatok közötti hasonlóságok vagy eltérések figyelembevételével próbálunk olyan csoportokat képezni, hogy az egy csoportban levő elemek hasonlóak legyenek egymáshoz, míg a különböző osztályokhoz tartozó elemek jelentősen térjenek el egymástól. Amikor az adatok közé egy vagy több, ún. kívülálló adat kerül (pl. bogarak méret szerinti osztályozásakor bejuttatunk az egyedek közé egy elefántot és egy papucsállatkát), a szakirodalomban fellelhető algoritmusok vagy pontatlanul, vagy egyáltalán nem fognak működni. A gyakorlatban számos olyan alkalmazási terület van, ahol erős zajos környezetben történő adatokat kell feldolgozni (pl. szeizmikus adatok, echográf felvételek, stb.). Az ilyen forrásból származó adatok osztályozásához szükségünk van erős zajelnyomó képességű algoritmusok alkalmazására. Jelen kutatás fő célja, hogy általános érvényű, az alkalmazások széles körében bevethető módszereket dolgozzunk ki az ilyen zajos adatok megbízható, stabilan működő, pontos eredményeket szolgáltató osztályozására.
A közelmúltban kidolgozott és leközölt alapötletünk, melyre építeni kívánjuk jelen kutatásunkat, ígéretes részeredményeket szolgáltatott, így a kutatás jövőbeni sikere valószínűsíthető.
Summary
Summary of the research and its aims for experts
Describe the major aims of the research for experts.
This project intends to revolutionize the robust fuzzy-possibilistic c-means clustering models in terms of sensibility to outlier data, and to improve their accuracy and efficiency, by proposing a quadratic objective function that qualitatively differs from existing ones. Current algorithms fail if the outlier vector departs beyond a certain boundary. Our proposed method is expected to suppress the effect of outliers and behave similarly to gravity systems, where more distant objects have less effect upon the system.

Further on, we intend to elaborate a complete theory of the suppressed fuzzy c-means algorithm, based on previous results that include a mathematical characterization of the process using a quasi learning rate, and certain generalization rules of the algorithm.

The elaborated algorithms will be suitable for unsupervised classification of vectorial data, to group data into clusters with point-type prototypes. Special formulations of the algorithms will be provided for clusters of special shapes. The general purpose algorithms will surely find several successful applications in pattern recognition, image segmentation, data mining, and bioinformatics.

Results of the research will be published in prestigious journal papers (at least 3), and 2 conference papers every year. A summarizing monograph will also be elaborated in the third year and submitted for publication.

What is the major research question?
Describe here briefly the problem to be solved by the research, the starting hypothesis, and the questions addressed by the experiments.
This research has three main questions:
(1) How is it possible to create a deterministic and optimal c-means clustering algorithm, that is totally insensitive to the presence of outlier data int he input data set, and provides fine partitions also in the absence of outliers?
(2) How to adapt the algorithms developed for clusters with point-type prototypes to special cases where the classes to detect have certain known shapes?
(3) We are looking for application domains (e.g. analysis of echography images or seismologic records), where the newly created algorithms bring significant improvement compared to existing methods.

What is the significance of the research?
Describe the new perspectives opened by the results achieved, including the scientific basics of potential societal applications. Please describe the unique strengths of your proposal in comparison to your domestic and international competitors in the given field.
The significance of the research is threefold:
(1) In the current state-of-the-art, there is no c-means clustering algorithm that rejects the effect of outlier data the way gravity systems act with outlier objects.
(2) Several application fields can only provide noisy data and thus require classification algorithms that can reject the effect of outliers.
(3) The algorithms that we investigate are universal and can be used to analyze any type of vectorial data that agglomerate in the vicinity of point-type prototypes. The base algorithms can be adapted to clusters of special shapes via existing, straightforward methods.
These are the main problems that the proposed research will solve.

Summary and aims of the research for the public
Describe here the major aims of the research for an audience with average background information. This summary is especially important for NRDI Office in order to inform decision-makers, media, and others.
When a so-called unsupervised clustering is performed, certain groups of data are formed based on similarity or differences in the input data such a way, that items in the same group appear alike and items from different groups significantly differ from each other. Those items which strongly differ from all others are usually considered outliers (e.g. an elephant or a virus would be outlier when insects are clustered based on physical size). Whenever a few outliers are present in the input data set, the existing algorithms will have difficulties in providing accurate results or will actually crash. Certain specific real-life applications (e.g. echography, seismology) can only provide noisy or very noisy data, thus they require classification methods that are able to reject the effect of outliers. The main goal of the proposed research is to create some general purpose clustering methods that can reliably work in such noisy environments and provide accurate results.
The basic idea upon which the research will be built, recently published in a conference paper, provided promising preliminary results. Consequently this research is very likely to succeed.




 

Final report

  
Results in Hungarian
Alapkutatási eredmények: (1) Két általánosítási eljárás az ún. elnyomott partíciójú FCM algoritmus részére, számos általánosítási szabállyal mindkettő esetében; (2) Egy új elmélet kidolgozása, mely egyesíti az ún. elnyomott és javított partícójú FCM algoritmusok családját; (3) Bizonyítást nyert az elnyomott partíciójú FCM algoritmus optimális volta; (4) Megmutattam, hogy az elnyomott és javított patíciók alkalmazása hogyan hat az FCM algoritmus által előállított fuzzy tagságfüggvény multimodális viselkedésére; (5) Kiterjesztettem a korábban bevezetett FP3CM algoritmusomat változatos alakú (pl. sokdimenziós gömb vagy ellipszis) klaszterek felismerésére; (6) Kidolgoztam számos hatékony és pontos Markov klaszterező algoritmus verziót. Jelentős eredmények a következő alkalmazásokban: (1) protein szekvencia hálózatok klaszterezése; (2) agyi tumor felismerése és szegmentálása többcsatornás MRI felvételekből; (3) képek színredukciója (optimális színpaletta számítása); (4) komputertomográf felvételek szegmentálása; (5) hangfeldolgozás; (6) vércukor szabályozás; (7) kórházi fertőzések megelőzése. Publikációk: öt szakcikk impakt faktoros folyóiratokban (Pattern Recognition Letters, Neurocomputing, Computers in Medicine and Biology, Journal of Hospital Infection, Acta Polytechnica Hungarica) és 17 konferencia dolgozat, melyből 10 dolgozat rangos (CORE A) konferencián került bemutatásra.
Results in English
Theoretical contributions: (1) Two different generalization schemes, each with several distinct generalization rules, for the suppressed fuzzy c-means clustering algorithm; (2) a unification theory for fuzzy c-means clustering models with so-called improved and suppressed partition; (3) proved the optimality of suppressed fuzzy c-means clustering algorithms; (4) showed how the improved and suppressed partition affect the multimodality of the fuzzy c-means algorithm; (5) extended the fuzzy-possibilistic product partition c-means algorithm to detect clusters of various shapes (spheroid, ellipsoid); (6) introduced several efficient and accurate Markov clustering algorithm variants. Application fields with relevant advances: (1) protein sequence network analysis; (2) brain tumor detection and segmentation from multispectral MR images; (3) image color reduction (palette extraction); (4) segmentation of computer tomography images; (5) blind speaker classification; (6) blood glucose control; (7) hospital infection prevention. Publications: five articles in peer-reviewed journals (Pattern Recognition Letters, Neurocomputing, Computers in Medicine and Biology, Journal of Hospital Infection, Acta Polytechnica Hungarica); 17 conference papers, ten of which presented at highly ranked (CORE A) conferences.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=103921
Decision
Yes





 

List of publications

  
Szilágyi L, Szilágyi SM: Generalization rules for the suppressed fuzzy c-means clustering algorithm, Neurocomputing 139:298-309, 2014
Szilágyi L: Lessons to learn from a mistaken optimization, Pattern Recognition Letters 36(1):29-35, 2014
Lehotsky Á, Szilágyi L, Ferenci T, Kovács L, Pethes R, Wéber Gy, Haidegger T: Quantitative impact of direct, personal feedback on hand hygiene technique, Journal of Hospital Infection 91:81-84, 2015
Szilágyi SM, Szilágyi L: A fast hierarchical clustering algorithm for large-scale protein sequence data sets, Computers in Biology and Medicine 48:94-101, 2014
Szilágyi L: Lessons to learn from a mistaken optimization, Pattern Recognition Letters 36(1):29-35, 2014
Szilágyi L, Szilágyi SM: An efficient Markov clustering approach to protein sequence grouping, Journal of Pattern Recognition & Image Processing 3(1):263-272, ISSN: 2160-9454, 2013
Gosztolya G, Szilágyi L: Application of fuzzy and possibilistic c-means clustering models in blind speaker clustering, Acta Polytechinca Hungarica 12(7):41-56, 2015
Szilágyi L, Szilágyi SM: Efficient Markov clustering algorithm for protein sequence grouping, 35th Annual International Conference of IEEE Engineering in Medicine and Biology Society, Osaka, pp. 639-642, ISBN 978-1-4577-0214-3, 2013
Szilágyi SM, Szilágyi L, Hirsbrunner B: Simulation of arrhythmia using adaptive spatio-temporal resolution, Computers in Cardiology 40:(accepted paper, 4 pages), 2013
Szilágyi SM, Szilágyi L, Hirsbrunner B: Modeling the influence of high fibroblast level on arrhythmia development and obstructed depolarization spread, Computers in Cardiology 40:(accepted paper, 4 pages), 2013
Szilágyi L: Lessons to learn from a mistaken optimization, Pattern Recognition Letters 36(1):29-35, 2014
Szilágyi L, Szilágyi SM: An efficient Markov clustering approach to protein sequence grouping, Journal of Pattern Recognition & Image Processing 3(1):263-272, ISSN: 2160-9454, 2013
Szilágyi L, Szilágyi SM: Efficient Markov clustering algorithm for protein sequence grouping, 35th Annual International Conference of IEEE Engineering in Medicine and Biology Society, Osaka, pp. 639-642, ISBN 978-1-4577-0214-3, 2013
Szilágyi SM, Szilágyi L, Hirsbrunner B: Simulation of arrhythmia using adaptive spatio-temporal resolution, Computers in Cardiology 40:365-368, 2013
Szilágyi SM, Szilágyi L, Hirsbrunner B: Modeling the influence of high fibroblast level on arrhythmia development and obstructed depolarization spread, Computers in Cardiology 40:45-48, 2013
Szilágyi L, Szilágyi SM: Generalization rules for the suppressed fuzzy c-means clustering algorithm, Neurocomputing 139:298-309, 2014
Szilágyi SM, Szilágyi L: A fast hierarchical clustering algorithm for large-scale protein sequence data sets, Computers in Biology and Medicine 48:94-101, 2014
Szilágyi L, Dénesi G, Szilágyi SM: Fast color reduction using approximative c-means clustering models, IEEE International Conference on Fuzzy Systems (FUZZ-IEEE 2014, Beijing), pp. 194-201, ISBN: 978-1-4799-2073-0, 2014
Szilágyi L, Dénesi G, Kovács L, Szilágyi SM: Comparison of various improved-partition fuzzy c-means clustering algorithms in fast color reduction, 12th IEEE International Symposium on Intelligent Systems and Informatics (SISY 2014, Subotica), pp. 197-202, ISBN: 978-1-4799-5996-9, 2014
Szilágyi L, Szilágyi SM: Fast implementations of Markov clustering for protein sequence grouping, Modeling Decisions for Artificial Intelligence, LNCS vol. 8234, pp. 214-225 (MDAI 2013, Barcelona), ISBN: 978-3-642-41549-4, 2013
Szilágyi L, Varga ZsR, Szilágyi SM: Application of the fuzzy-possibilistic product partition in elliptic shell clustering, Modeling Decisions for Artificial Intelligence, LNCS vol. 8825, pp. 158-169 (MDAI 2014, Tokyo), 2014
Szilágyi L, Szilágyi SM, Hirsbrunner B: A fast and memory-efficient heirarchical graph clustering algorithm, International Conference on Neural Information Processing, LNCS vol. 8834, pp. 247-254 (ICONIP 2014, Kuching), 2014
Szilágyi L, Kovács L, Szilágyi SM: Synthetic test data generation for hierarchical graph clustering methods, International Conference on Neural Information Processing, LNCS vol. 8835, pp. 303-310 (ICONIP 2014, Kuching), 2014
Szalay P, Szilágyi L, Benyó Z, Kovács L: Sensor drift compensation using fuzzy interface system and sparse-grid quadrature filter in blood glucose control, International Conference on Neural Information Processing, LNCS vol. 8835, pp. 445-453 (ICONIP 2014, Kuching), 2014
Szilágyi L: A unified theory of fuzzy c-means clustering models with improved partition, Modeling Decisions for Artificial Intelligence, LNCS vol. 9321, pp. 129-140 (MDAI 2015, Skövde, Svédország), 2015
Szilágyi L, Nagy LL, Szilágyi SM: Recent advances in improving the memory efficiency of the TRIBE MCL algorithm, International Conference on Neural Information Processing, LNCS vol. 9490, pp. 28-35 (ICONIP 2015, Isztambul), 2015
Iclanzan D, Szilágyi L: Neural population coding of stimulus features, International Conference on Neural Information Processing, LNCS vol. 9492, pp. 263-270 (ICONIP 2015, Isztambul), 2015
Szilágyi L, Lefkovits L, Iantovics BL, Iclanzan D, Benyó B: Automatic brain tumor segmentation in multispectral MRI volumetric records, International Conference on Neural Information Processing, LNCS vol. 9492, pp. 174-181 (ICONIP 2015, Isztambul), 2015
Szilágyi L, Lefkovits L, Benyó B: Automatic brain tumor segmentation in multispectral MRI volumes using a fuzzy c-means cascade algorithm, 12th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD 2015, Zhangjiajie, Kína), pp. 310-316, ISBN 978-1-4673-7681-5, 2015
Szilágyi L: Random process simulation using Petri nets, 5th International Conference on Recent Achievements in Mechatronics, Automation, Computer Sciences and Robotics (MACRO 2015, Marosvásárhely), pp. 177-182, ISSN 2247-0948, 2015



Back »