On the Application of Bio-Inspired Optimization Algorithms to Fuzzy C-Means Clustering of Time Series

(1)

(2)

ICPRAM 2015

Proceedings of the

International Conference on

Pattern Recognition Applications and Methods

Volume 1

Lisbon, Portugal 10 - 12 January, 2015

Copyright © 2015 SCITEPRESS – Science and Technology Publications All rights reserved

Edited by Maria De Marsico, Mário Figueiredo and Ana Fred

Printed in Portugal ISBN: 978-989-758-076-5 Depósito Legal: 385616/14

http://www.icpram.org

icpram.secretariat@insticc.org

(4)

2QWKH$SSOLFDWLRQRI%LR,QVSLUHG2SWLPL]DWLRQ$OJRULWKPVWR)X]]\

C0HDQV&OXVWHULQJRI7LPH6HULHV

0XKDPPDG0DUZDQ0XKDPPDG)XDG

Forskningsparken 3, Institutt for kjemi, NorStruct

The University of Tromsø - The Arctic University of Norway, NO-9037 Tromsø, Norway marwan.fuad@uit.no

.H\ZRUGV 'DWD 0LQLQJ 'LIIHUHQWLDO (YROXWLRQ 'LVWDQFH 0HWULFV )X]]\C0HDQV &OXVWHULQJ *HQHWLF $OJRULWKPV 2YHUILWWLQJ3DUWLFOH6ZDUP2SWLPL]DWLRQ7LPH6HULHV

$EVWUDFW )X]]\cPHDQVFOXVWHULQJ)&0LVDFOXVWHULQJPHWKRGZKLFKLVEDVHGRQWKHSDUWLDOPHPEHUVKLSFRQFHSW

$V ZLWK WKH RWKHU FOXVWHULQJ PHWKRGV )&0 DSSOLHV D GLVWDQFH WR FOXVWHU WKH GDWD :KLOH WKH (XFOLGHDQ GLVWDQFHLVZLGHO\XVHGWRSHUIRUPWKHFOXVWHULQJWDVNRWKHUGLVWDQFHVKDYHEHHQVXJJHVWHGLQWKHOLWHUDWXUH ,QWKLVSDSHUZHVWXG\WKHXVHRIDZHLJKWHGFRPELQDWLRQRIPHWULFVLQ)&0FOXVWHULQJRIWLPHVHULHVZKHUH WKH ZHLJKWV LQ WKH FRPELQDWLRQ DUH WKH RXWFRPH RI DQ RSWLPL]DWLRQ SURFHVV XVLQJ GLIIHUHQWLDO HYROXWLRQ JHQHWLF DOJRULWKPV DQG SDUWLFOH VZDUP RSWLPL]DWLRQ DV RSWLPL]HUV :H VKRZ KRZ WKH RYHUILWWLQJ SKHQRPHQRQLQWHUIHUHVLQWKHRSWLPL]DWLRQSURFHVVWKDWWKHRSWLPDOUHVXOWVREWDLQHGGXULQJWKHWUDLQLQJVWDJH GHJUDGHGXULQJWKHWHVWLQJVWDJHDVDUHVXOWRIRYHUILWWLQJ

,1752'8&7,21

$ time series LV DQ RUGHUHG FROOHFWLRQ RI REVHUYDWLRQV DW LQWHUYDOV RI WLPH SRLQWV 7KHVH REVHUYDWLRQV DUH UHDOYDOXHG PHDVXUHPHQWV RI D SDUWLFXODUSKHQRPHQRQ

7LPH VHULHV DULVH LQ GLVFLSOLQHV UDQJLQJ IURP PHGLFLQH DQG ILQDQFH WR PHWHRURORJ\ DQG HQJLQHHULQJ WR QDPH D IHZ )RU WKLV UHDVRQ WLPH VHULHVGDWDPLQLQJKDVUHFHLYHGLQFUHDVLQJDWWHQWLRQ RYHUWKHODVWWZRGHFDGHV

7LPH VHULHV GDWD PLQLQJ KDQGOHV VHYHUDO WDVNV VXFK DV FODVVLILFDWLRQ FOXVWHULQJ VLPLODULW\ VHDUFK PRWLI GLVFRYHU\ DQRPDO\ GHWHFWLRQ DQGRWKHUV$OO WKHVH WDVNV DUH EDVHG RQ WKH FRQFHSW RI VLPLODULW\

ZKLFK LV PHDVXUHG XVLQJ Dsimilarity measure RU D distance metric

Bio-inspired Optimization DOVR FDOOHGnature- inspired Optimization LV D EUDQFK RI RSWLPL]DWLRQ ZKLFK DV WKH QDPH VXJJHVWV LV LQVSLUHG E\ QDWXUDO SKHQRPHQD ,W KDV GLYHUVH DSSOLFDWLRQV LQ HQJLQHHULQJILQDQFHHFRQRPLFVDQGRWKHUGRPDLQV ,Q FRPSXWHU VFLHQFH ELRLQVSLUHG RSWLPL]DWLRQ KDV EHHQ DSSOLHG LQ VHYHUDO ILHOGV VXFK DV QHWZRUNLQJ GDWDPLQLQJDQGVRIWZDUHHQJLQHHULQJ

$V ZLWK RWKHU ILHOGV RI FRPSXWHU VFLHQFH GLIIHUHQWSDSHUVKDYHSURSRVHGDSSO\LQJELRLQVSLUHG

RSWLPL]DWLRQWRGDWDPLQLQJWDVNV0XKDPPDG)XDG DED

,Q WKLV ZRUN ZH VWXG\ WKH DSSOLFDWLRQ RI WKUHH ZHOONQRZQ ELRLQVSLUHG RSWLPL]DWLRQ DOJRULWKPV GLIIHUHQWLDO HYROXWLRQ JHQHWLF DOJRULWKPV DQG SDUWLFOH VZDUP RSWLPL]DWLRQ WR WKH WDVN RI )&0 FOXVWHULQJRIWLPHVHULHVZKHUHWKHVHRSWLPL]HUVDUH XVHG WR REWDLQ WKH RSWLPDO YDOXHV RI WKH ZHLJKWV DVVLJQHG WR WKH GLVWDQFHV WKDW FRQVWLWXWH D FRPELQDWLRQ RI PHWULFV XVHG LQ WKH )&0 FOXVWHULQJ WDVN

7KHUHVWRIWKHSDSHULVRUJDQL]HGDVIROORZVLQ 6HFWLRQ ZH SUHVHQW EDFNJURXQG RQ WLPH VHULHV FOXVWHULQJ VLPLODULW\ PHDVXUHV DQG RYHUILWWLQJ ,Q 6HFWLRQZHLQWURGXFHWKHSURSRVHGPHWKRGZKLFK ZHWHVWLQ6HFWLRQ7KHUHVXOWVRIWKHH[SHULPHQWV DUH GLVFXVVHG LQ 6HFWLRQ :H FRQFOXGH WKLV SDSHU ZLWK6HFWLRQ

**%$&.*5281'**

$ WLPH VHULHV LV DQ RUGHUHG FROOHFWLRQ RI REVHUYHG GDWD)RUPDOO\DWLPHVHULHVSRIOHQJWKnLVGHILQHG DV S s vt s vt s_n v_nt_n 7KHVH YDOXHV FDQ EH UHDO QXPEHUV RU PXOWL GLPHQVLRQDOYHFWRUV

348

(5)

'DWDPLQLQJLVWKHDQDO\VLVRIGDWDZLWKWKHJRDO RIXQFRYHULQJKLGGHQNQRZOHGJHLQLW'DWDPLQLQJ LQFOXGHV VHYHUDO WDVNV VXFK DV FODVVLILFDWLRQ FOXVWHULQJ DQRPDO\ GHWHFWLRQ DQG RWKHUV 3URFHVVLQJ WKHVH GLIIHUHQW WDVNV XVXDOO\ UHTXLUHV H[WHQVLYHFRPSXWLQJ

Clustering LV D IXQGDPHQWDO GDWD PLQLQJ WDVN

&OXVWHULQJ VHHNV IRU WKH JURXSLQJ WHQGHQFLHV RI WKH GDWD &OXVWHULQJ FDQ EH GHILQHG DV WKH SURFHVV RI ILQGLQJ QDWXUDO JURXSV FDOOHGclusters LQ D GDWDVHW 7KH REMHFWLYH RI WKH FOXVWHULQJ WDVN LV WR ILQG WKH PRVW KRPRJHQHRXV FOXVWHUV WKDW DUH DV GLVWLQFW DV SRVVLEOH IURP RWKHU FOXVWHUV 7KLV JURXSLQJ VKRXOG PD[LPL]H LQWHUFOXVWHU YDULDQFH ZKLOH PLQLPL]LQJ LQWUDFOXVWHU YDULDQFH (VOLQJ DQG $JRQ 7KHUH DUH VHYHUDO EDVLF FOXVWHULQJ PHWKRGV WKRVH ZKLFK FRQFHUQ WLPH VHULHV GDWD DUHPartition-based Clustering, Hierarchical-based Clustering, and Model-based Clustering /LDR )LJXUH VKRZV WKH JHQHUDO VFKHPH RI WKH SDUWLWLRQEDVHG FOXVWHULQJDOJRULWKP

Fuzzy c-means Clustering )&0LVDSDUWLWLRQ EDVHG FOXVWHULQJ PHWKRG )&0 LV EDVHG RQ WKH FRQFHSWRIPartial MembershipZKHUHWKHDOORFDWLRQ RIWKHGDWDSRLQWWRWKHFHQWHUVEHFRPHVDPDWWHURI GHJUHH ± WKH KLJKHU WKH PHPEHUVKLS YDOXH WKH VWURQJHU LWV ERQG WR WKH FOXVWHU .U]\V]WRIet al

7KHREMHFWLYHRI)&0FOXVWHULQJLVWRPLQLPL]H WKHPHDVXUH

p i

c

p n

i m pi

m u d z x

E

¦¦

:KHUHu LV WKH IX]]\ PHPEHUVKLS DQGm LV IX]]\

H[SRQHQW ,Q WKH IROORZLQJ ZH SUHVHQW D EULHI GHVFULSWLRQRI)&00DXOLNet al)&0VWDUWV ZLWK UDQGRP c LQLWLDO FOXVWHU FHQWHUV ,Q WKH IROORZLQJVWHSDQGDWHYHU\LWHUDWLRQWKHDOJRULWKP ILQGV WKH IX]]\ PHPEHUVKLS RI HDFK GDWD REMHFW WR HYHU\FOXVWHUXVLQJWKHIROORZLQJHTXDWLRQ

¦

_¸^¸

¹

·

¨¨

©

§ ^m

c

j j i

i p pi

x z d

u

IRUpcin.

$OJRULWKP&OXVWHULQJ

Require c the number of clusters, n data objects.

1.(Randomly) initialize the cluster centers.

2.For each data object, and for each center, compute the distance between this data object and the cluster center, assign the data object to the closest center.

3.Update the cluster centers.

4.Repeat steps 2-3 until convergence.

)LJXUH7KHSDUWLWLRQEDVHGFOXVWHULQJDOJRULWKP

%DVHGRQWKHPHPEHUVKLSYDOXHVWKHFOXVWHUFHQWHUV DUHUHFRPSXWHGXVLQJWKHIROORZLQJHTXDWLRQ

¦

n

i

m pi

i n

i

m pi p

u x u z

pc

7KH DOJRULWKP FRQWLQXHV XQWLO D VWRSSLQJ FRQGLWLRQ WHUPLQDWHVLW

2YHUILWWLQJ

2QH RI WKH IUHTXHQW SUREOHPV HQFRXQWHUHG ZKHQ JHQHUDWLQJ D GDWD PLQLQJ PRGHO LV overfitting 2YHUILWWLQJUHVXOWVZKHQWKHSURYLVLRQDOPRGHOWULHV WRDFFRXQWIRUHYHU\SRVVLEOHWUHQGRUVWUXFWXUHLQWKH WUDLQLQJ VHW ,Q RYHUILWWLQJ WKH DOJRULWKP PHPRUL]HV WKHWUDLQLQJVHWDWWKHH[SHQVHRIJHQHUDOL]DELOLW\WR WKH YDOLGDWLRQ VHW /DURVH 7KHUH DUH VHYHUDO UHDVRQV IRU RYHUILWWLQJ DQG RYHUILWWLQJDYRLGDQFH LV DQ LPSRUWDQW UHVHDUFK WRSLF LQ GDWD PLQLQJ 7KH TXHVWLRQ RI RYHUILWWLQJ LV SDUWLFXODUO\ LPSRUWDQW ZKHQ DSSO\LQJ ELRLQVSLUHG DOJRULWKPV WR SHUIRUP GDWDPLQLQJWDVNV0XKDPPDG)XDGE 6LPLODULW\0HDVXUHV

0HDVXULQJWKHVLPLODULW\EHWZHHQWZRWLPHVHULHVRQ ZKLFK FOXVWHULQJ DQG RWKHU GDWD PLQLQJ WDVNV DUH EDVHGLVQRWDWULYLDOWDVN7KHUHKDYHEHHQVHYHUDO GLVWDQFHPHWULFVDQGVLPLODULW\PHDVXUHVSURSRVHGLQ On the Application of Bio-Inspired Optimization Algorithms to Fuzzy C-Means Clustering of Time Series

349

(6)

WKH OLWHUDWXUH 7KH PRVW FRPPRQ GLVWDQFH PHWULF KRZHYHU LV WKH Minkowski distance ZKLFK LV GHILQHGEHWZHHQWZRWLPHVHULHV SDQGTDV

p n

i

p i i

p S T s t

L

¦

,Ip WKHGLVWDQFHLVFDOOHGWKHManhattan distance RU WKHcity block GLVWDQFH ,Ip LW LV FDOOHG WKH infinity distanceRUWKHchessboard distanceDQGLIp ZH JHW WKH ZLGHO\NQRZQEuclidean distance

$SSO\LQJDQ\RIWKHVHGLVWDQFHVWDNHVOLQHDUWLPHLQ WKHOHQJWKRIWKHVHULHV

**$33/<,1*$&20%,1$7,21 2)',67$1&(672)&0**

&/867(5,1*

7KH LGHD RI DSSO\LQJ D FRPELQDWLRQ RI GLVWDQFH PHWULFVRUVLPLODULW\PHDVXUHVWRKDQGOHGDWDPLQLQJ WDVNVKDVEHHQSURSRVHGE\GLIIHUHQWUHVHDUFKHUV,Q

%XVWRVDQG6NRSDOWKHDXWKRUVSURSRVHXVLQJ DZHLJKWHGFRPELQDWLRQRIVHYHUDOPHWULFVWRKDQGOH WKH VLPLODULW\ VHDUFK SUREOHP 7KH QRYHOW\ RI RXU ZRUN LV WKDW ZH DGGUHVV WKLV DV DQ RSWLPL]DWLRQ SUREOHP 0RUH IRUPDOO\ ZH )&0 FOXVWHU WKH WLPH XVLQJ D ZHLJKWHG FRPELQDWLRQ RI GLVWDQFH PHWULFV GHILQHGDV

¦

ⁿ

1 i

i id S,T T

, S

d Z

ZKHUHZi

> @

⁰^,¹

,Q RUGHU WR SHUIRUP WKLV RSWLPL]DWLRQ SURFHVV DQGIRUFRPSDULVRQUHDVRQVZHFKRRVHWRXVHWKUHH RI WKH PRVW SRZHUIXO ELRLQVSLUHG RSWLPL]DWLRQ DOJRULWKPVZKLFKDUHDifferential EvolutionParticle Swam OptimizationDQGGenetic Algorithms 'LIIHUHQWLDO(YROXWLRQ

'LIIHUHQWLDO (YROXWLRQ '( LV DQ HYROXWLRQDU\

RSWLPL]DWLRQDOJRULWKPZKLFKLVSDUWLFXODUO\DGDSWHG WRVROYHFRQWLQXRXVRSWLPL]DWLRQSUREOHPV

'( VWDUWV ZLWK D SRSXODWLRQ RIPopSize YHFWRUV HDFKRIZKLFKLVRInbpGLPHQVLRQVZKHUHnbp LVWKH QXPEHU RI SDUDPHWHUV LQ RXU SUREOHPnbp LV WKH QXPEHU RI GLVWDQFHV LQ WKH FRPELQDWLRQ JLYHQ E\

HTXDWLRQ,QWKHQH[WVWHSIRUHDFKLQGLYLGXDOT_i G FDOOHG WKHtarget vector RI WKH SRSXODWLRQ WKUHH PXWXDOO\ GLVWLQFW LQGLYLGXDOVVG_r₁

VG_r₂ VG_r₃

DQG

GLIIHUHQW IURP TG_i

DUH FKRVHQ UDQGRPO\ IURP WKH SRSXODWLRQ 7KH donor vectorDG

LV IRUPHG DV D ZHLJKWHG GLIIHUHQFH RI WZR RIV_r₁

G V_r₂ G V_r₃

G DGGHG WRWKHWKLUGLHDG VGr1 F

VGr2 VGr3

FLVFDOOHG

WKHmutation factor.

7KHtrial vector R

GLV IRUPHG IURP HOHPHQWV RI WKH WDUJHW YHFWRU T_i

GDQG HOHPHQWV RI WKH GRQRU YHFWRUDG

DFFRUGLQJ WR GLIIHUHQW VFKHPHV ,Q WKLV SDSHUZHFKRRVHWKHFURVVRYHUVFKHPHSUHVHQWHGLQ )HRNWLVWRY,QWKLVVFKHPHDQLQWHJHURndLV FKRVHQ UDQGRPO\ DPRQJ WKH GLPHQVLRQV

>

^,^nbp

@

7KHQWKHWULDOYHFWRUR

GLVIRUPHGDVIROORZV

> >

°¯

°®

otherwise t

i Rnd C , rand if t t F t t

j , i

r j , i r

, i r , i r , i i

ZKHUHi ,...,nbpC_rLVWKHcrossover constant,Q WKHQH[WVWHS'(VHOHFWVZKLFKRIWKHWULDOYHFWRUDQG WKHWDUJHWYHFWRUZLOOVXUYLYHLQWKHQH[WJHQHUDWLRQ DQG ZKLFK ZLOO GLH RXW 7KLV VHOHFWLRQ LV EDVHG RQ ZKLFKRITG_i

DQGR

G\LHOGVDEHWWHUYDOXHRIWKHILWQHVV IXQFWLRQ'(FRQWLQXHVIRUDQXPEHURIJHQHUDWLRQV NrGen

7KH*HQHWLF$OJRULWKP

7KHGenetic Algorithm *$ LV DQRWKHU PHPEHU RI WKH HYROXWLRQDU\ DOJRULWKPV IDPLO\ *$ KDV WKH IROORZLQJ HOHPHQWV D SRSXODWLRQ RI LQGLYLGXDOV VHOHFWLRQ DFFRUGLQJ WR ILWQHVV FURVVRYHU WR SURGXFH QHZ RIIVSULQJ DQG UDQGRP PXWDWLRQ RI WKH QHZ RIIVSULQJ0LWFKHOO

7KH ILUVW VWHS RI *$ LV GHILQLQJ WKH SUREOHP YDULDEOHV DQG WKH ILWQHVV IXQFWLRQ $ SDUWLFXODU FRQILJXUDWLRQ RI YDULDEOHV SURGXFHV D FHUWDLQ YDOXH RIWKHILWQHVVIXQFWLRQDQGWKHREMHFWLYHRI*$LVWR ILQG WKH YDOXHV RI WKH SDUDPHWHUV WKDW RSWLPL]H WKH ILWQHVV IXQFWLRQ $V ZLWK '( *$ VWDUWV ZLWK D SRSXODWLRQ RI PopSize YHFWRUV DOVR FDOOHG chromosomesHDFKRIZKLFKLVRInbpGLPHQVLRQV (DFK FKURPRVRPH UHSUHVHQWV D SRVVLEOH VROXWLRQ WR WKH SUREOHP DW KDQG 7KH ILWQHVV IXQFWLRQ RI HDFK FKURPRVRPHLVHYDOXDWHG7KHQH[WVWHSLVselection 7KH SXUSRVH RI WKLV SURFHVV LV WR GHWHUPLQH ZKLFK FKURPRVRPHVDUHILWHQRXJKWRVXUYLYHDQGSRVVLEO\

SURGXFH RIIVSULQJ DQG ZKLFK ZLOO GLH RXW 7KLV LV GHFLGHG DFFRUGLQJ WR WKH ILWQHVV IXQFWLRQ RI HDFK FKURPRVRPH 7KH SHUFHQWDJH RI FKURPRVRPHV VHOHFWHGIRUPDWLQJLVGHQRWHGE\sRateCrossoverLV WKH QH[W VWHS LQ ZKLFK RIIVSULQJ RI WZR SDUHQWV DUH SURGXFHGWRHQULFKWKHSRSXODWLRQZLWKILWWHU ICPRAM 2015 - International Conference on Pattern Recognition Applications and Methods

350

(7)

7DEOH 7KH )&0 FOXVWHULQJ HUURUV RQ WKH WUDLQLQJ VHWV DQG WHVWLQJ VHWV IRU '( 362 DQG *$ WRJHWKHU ZLWK WKH )&0 FOXVWHULQJHUURUVIRU///

'DWDVHW / / / '( 362 *$

(WUDLQ (WHVW (WUDLQ (WHVW (WUDLQ (WHVW

%HHI

&%)

&LQ&B(&*BWRUVR

&RIIHH

(&*

(&*)LYH'D\V

)DFH)RXU

),6+

*XQB3RLQW

/LJKWLQJ

0HGLFDO,PDJHV 0RWH6WUDLQ

2OLYH2LO

268/HDI

6RQ\$,%25RERW6XUIDFH,, 6ZHGLVK/HDI

6\PEROV

V\QWKHWLFBFRQWURO

7UDFH

7ZR/HDG(&*

\RJD

FKURPRVRPHV *$ DOVR DSSOLHV D PHFKDQLVP FDOOHG mutation WKURXJK ZKLFK D SHUFHQWDJHmRate RI JHQHV LV UDQGRPO\ DOWHUHG 7KH DERYH VWHSV UHSHDW IRUNrGenJHQHUDWLRQV

3DUWLFOH6ZDUP2SWLPL]DWLRQ Particle Swarm Optimization362LVDPHPEHURI D IDPLO\ RI QDWXUDOO\LQVSLUHG RSWLPL]DWLRQ DOJRULWKPV FDOOHGSwarm Intelligence 6, 362 LV LQVSLUHG E\ WKH VRFLDO EHKDYLRU RI VRPH DQLPDOV VXFK DV ELUG IORFNLQJ RU ILVK VFKRROLQJ +DXSW DQG +DXSW,Q362LQGLYLGXDOVFDOOHGparticles IROORZWKUHHUXOHVDSeparation: HDFKSDUWLFOHDYRLGV JHWWLQJWRRFORVHWRLWVQHLJKERUVEAlignment:HDFK SDUWLFOH VWHHUV WRZDUGV WKH JHQHUDO KHDGLQJ RI LWV QHLJKERUV DQG FCohesion: HDFK SDUWLFOH PRYHV WRZDUGVWKHDYHUDJHSRVLWLRQRILWVQHLJKERUV

362 VWDUWV E\ LQLWLDOL]LQJ D VZDUP RIPopSize SDUWLFOHV DW UDQGRP SRVLWLRQV X_i

G DQG YHORFLWLHV

VGi

ZKHUH i

^

PopSize

`

,Q WKH QH[W VWHS WKH ILWQHVV IXQFWLRQ RI HDFK SRVLWLRQ DQG IRU HDFK LWHUDWLRQ LV HYDOXDWHG 7KH SRVLWLRQV XG_i^k

DQG YHORFLWLHV VG_i^k

DUH XSGDWHG DW WLPH VWHS k DFFRUGLQJWRWKHIROORZLQJIRUPXODH

i^k

k i L k i k G k i k

i .V G X L X

VG G G G G G

Z M M

k i k i k

i X V

X

G G

G

ZKHUH M_G r_Ga_GM_L r_La_L r_Gr_LoU R

G

L a

a

Z _L^G^k_i LV WKH EHVW SRVLWLRQ IRXQG E\

SDUWLFOH iG^k

G LVWKHJOREDOEHVWSRVLWLRQIRXQGE\WKH ZKROH VZDUP

Z

LV FDOOHG WKHinertia a_LLV FDOOHG WKHlocal acceleration DQGa_GLV FDOOHG WKHglobal acceleration7KHDOJRULWKPFRQWLQXHVIRUDQXPEHU RILWHUDWLRQV

(;3(5,0(176

7KH REMHFWLYH RI RXU H[SHULPHQWV LV WR VHH LI D ZHLJKWHGFRPELQDWLRQRIWKH(XFOLGHDQGLVWDQFHWKH 0DQKDWWDQ GLVWDQFH DQG WKH LQILQLW\ GLVWDQFH ZLOO JLYHEHWWHU)&0FOXVWHULQJUHVXOWVWKDQZKHQHDFKRI WKHVH GLVWDQFHV LV XVHG DV D VWDQGDORQH GLVWDQFH 0RUH IRUPDOO\ ZH )&0 FOXVWHU WKH GDWD XVLQJ WKH IROORZLQJFRPELQDWLRQ

T , S L T , S L T , S L T , S

d Z₁ ₁ Z₂ ₂ Z₃ _f

$V LQGLFDWHG HDUOLHU WKH ZHLJKWV

Z

_iDUH REWDLQHG On the Application of Bio-Inspired Optimization Algorithms to Fuzzy C-Means Clustering of Time Series

351

(8)

WKURXJK DQ RSWLPL]DWLRQ SURFHVV WKDW PLQLPL]HV WKH )&0FOXWWHULQJHUURUDVJLYHQE\HTXDWLRQ

:HWHVWHGRXUPHWKRGRQDYDULHW\RIWLPHVHULHV GDWDVHWVIURPWKH8&5DUFKLYH.HRJK et al :H PHDQW WR FKRRVH GDWDVHWV RI GLIIHUHQW VL]HV DQG OHQJWKVWRJHWXQELDVHGUHVXOWV

,Q RXU H[SHULPHQWV ZH FRPSDUHG WKH WKUHH RSWLPL]HUV SUHVHQWHG LQ 6HFWLRQ LQ WHUPV RI )&0 FOXVWHULQJHUURU

:H XVHG WKH VDPH FRQWURO SDUDPHWHUV IRU WKH WKUHHRSWLPL]HUVH[FHSW IRUWKRVH ZKLFK DUH SURSHU WRWKDWFHUWDLQRSWLPL]HUPopSizeZDVVHWWRDQG NrGenZDVVHWWR

)RU HDFK GDWDVHW DQG IRU HDFK RSWLPL]HU WKH H[SHULPHQWFRQVLVWVRIWZRVWDJHVWKHWUDLQLQJVWDJH DQG WKH WHVWLQJ VWDJH ,Q WKH WUDLQLQJ VWDJH ZH SHUIRUP DQ RSWLPL]DWLRQ SURFHVV ZKHUH WKH SDUDPHWHUV RI WKH RSWLPL]DWLRQ SUREOHP DUH WKH ZHLJKWVZ_ii

^ `

7KH RXWFRPH RI WKLV RSWLPL]DWLRQ SUREOHP LV WKH ZHLJKWVȦiZKLFK \LHOG WKH PLQLPXP )&0 FOXVWHULQJ HUURU 7KHVH RSWLPDO YDOXHVDUHWKHQDSSOLHGWRWKHWHVWLQJVHWV,Q7DEOH ZHSUHVHQWWKHUHVXOWVRIRXUH[SHULPHQWV

7DNLQJLQWRDFFRXQWWKDWWKHRSWLPL]DWLRQSURFHVV ZDVDSSOLHGWRWKHWUDLQLQJGDWDVHWVZHVHHWKDWWKH WKUHHRSWLPL]HUVGLGLPSURYHWKH)&0FOXVWHULQJDV WKH)&0FOXVWHULQJHUURUVRIWKHWUDLQLQJGDWDVHWVIRU DOOWKHGDWDVHWVDQGZKDWHYHURSWLPL]HULVXVHGDUH VPDOOHU WKDQ WKH HUURUV UHVXOWLQJ IURP XVLQJ / / RU / DV VWDQGDORQH GLVWDQFHV +RZHYHU ZKHQ FRPSDULQJWKH)&0FOXVWHULQJHUURUVRQWKHWHVWLQJ GDWDVHWVZHVHHWKDWWKHVHHUURUVDUHODUJHUWKDQWKRVH REWDLQHG ZKHQ XVLQJ / / RU / DV VWDQGDORQH GLVWDQFHV

,Q RUGHU WR XQGHUVWDQG WKLV SKHQRPHQRQ ZH LQYHVWLJDWH ZKHWKHU WKH OHDUQLQJ SURFHVV KDV XQGHUJRQHRYHUILWWLQJ

7KHUH DUH VHYHUDO PHDVXUHV LQ WKH OLWHUDWXUH WR PHDVXUH RYHUILWWLQJ :H RSWHG IRU WKH IROORZLQJ VLPSOHPHDVXUH

test

train E

E

OF

:KHUHEtrain EtestDUHWKH)&0FOXVWHULQJHUURUVRQ WKHWUDLQLQJVHWDQGWKHWHVWLQJVHWUHVSHFWLYHO\OF LVWKHRYHUILWWLQJYDOXH

,Q7DEOHZHUHSRUWWKHRYHUILWWLQJPHDVXUHVRI WKHWKUHHRSWLPL]HUVDQGIRUDOOWKHGDWDVHWVRQZKLFK ZH FRQGXFWHG RXU H[SHULPHQWV 7KH UHVXOWV VKRZ WKDW WKHUH H[LWV HYLGHQFH RI RYHUILWWLQJ KDSSHQLQJ GXULQJ WKH OHDUQLQJ SURFHVV 2I WKH WKUHH FRPSDUHG RSWLPL]HUV *$ VHHPV WR KDYH VXIIHUHG WKH OHDVW IURPRYHUILWWLQJZKHUHDV'(KDVVXIIHUHGWKHPRVW :HKDYHWRSRLQWRXWKRZHYHUWKDWIRUHDFKGDWDVHW

7DEOH7KHRYHUILWWLQJYDOXHVRI'(362DQG*$

'DWDVHW '( 362 *$

%HHI

&%)

&LQ&B(&*BWRUVR

&RIIHH

(&*

(&*)LYH'D\V

)DFH)RXU

),6+

*XQB3RLQW

/LJKWLQJ

0HGLFDO,PDJHV 0RWH6WUDLQ

2OLYH2LO

268/HDI

6RQ\$,%25RERW6XUIDFH,, 6ZHGLVK/HDI

6\PEROV

V\QWKHWLFBFRQWURO

7UDFH

7ZR/HDG(&*

\RJD

WKH WKUHH RSWLPL]HUV KDYH VXIIHUHG IURP RYHUILWWLQJ LQ D VLPLODU ZD\ WR D FHUWDLQ GHJUHH VR WKH H[SODQDWLRQ RI WKH UHVXOWV SUHVHQWHG LQ 7DEOH FDQ ILQDOO\ EH DWWULEXWHG WR GLIIHUHQFHV EHWZHHQ WKH WUDLQLQJVHWVDQGWKHWHVWLQJVHWV

:H KDYH WR PHQWLRQ KHUH WKDW GXULQJ WKH H[SHULPHQWV ZH DOVR UHFRUGHG H[HFXWLRQ WLPH EXW ZHGLGQRWUHSRUWWKHVHUHVXOWVIRUVSDFHUHVWULFWLRQV 7KH H[HFXWLRQ WLPH ZDV FOHDUO\ LQ IDYRU RI 362 ZKHUHDV'(DQG*$UDQDWVLPLODUVSHHGV

',6&866,21

7KHUH DUH VHYHUDO FRXQWHU PHDVXUHV WR DYRLG RYHUILWWLQJ,Q:LWWHQDQG)UDQNWKHDXWKRUV VXJJHVW XVLQJ D VLPSOHVWILUVW VHDUFK DQG VWRSSLQJ ZKHQ D VXIILFLHQWO\ FRPSOH[ FRQFHSW GHVFULSWLRQ LV IRXQG ,Q WKH ODQJXDJH RI ELRLQVSLUHG RSWLPL]DWLRQ WKLVLVWUDQVODWHGDVWHUPLQDWLQJWKHVHDUFKDOJRULWKP HDUOLHU RU XVLQJ IHZHU SDUDPHWHUV $V IRU WKH ODWWHU LGHDWKHSDUDPHWHUVZHDUHXVLQJDUHLQWULQVLFWRWKH SUREOHP DQG WKHLU QXPEHU FDQQRW EH UHGXFHG

%HVLGHV WKH QXPEHU RI WKH SDUDPHWHUV LQ RXU SUREOHPLVDOUHDG\VPDOO$VIRUWKHIRUPHULGHD ZH GLG FRQGXFW H[SHULPHQWV ZKLFK ZH GLG QRW UHSRUW KHUH ZKHUHNrGen ZDV VHW WR DQG WR EXW ZH GLG QRW VHH D VLJQLILFDQW GLIIHUHQFH LQ ICPRAM 2015 - International Conference on Pattern Recognition Applications and Methods

352

(9)

SHUIRUPDQFH EHWZHHQ WKH UHVXOWV ZH REWDLQHG IRU WKHVHYDOXHVDQGWKRVHZHUHSRUWHGLQWKLVSDSHUIRU ZKLFKNrGenZDVVHWWR7KHUHDVRQVIRUWKH RYHUILWWLQJ RI WKH VROXWLRQV UHVXOWLQJ IURP WKH )&0 FOXVWHULQJ PLJKW EH WKH QDWXUH RI WKH DSSOLFDWLRQ LWVHOI0XKDPPDG)XDG

&21&/86,216

7KH DSSOLFDWLRQ RI ELRLQVSLUHG RSWLPL]DWLRQ DOJRULWKPV WR GDWD PLQLQJ WDVNV LV QRW WULYLDO JLYHQ WKH FRPSOH[LW\ RI WKHVH WDVNV DQG WKH VWRFKDVWLF EHKDYLRURIELRLQVSLUHGDOJRULWKPV,QWKLVSDSHUZH DSSOLHG WKUHH ZLGHO\XVHG ELRLQVSLUHG RSWLPL]DWLRQ DOJRULWKPV GLIIHUHQWLDO HYROXWLRQ JHQHWLF DOJRULWKPV DQG SDUWLFOH VZDUP RSWLPL]DWLRQ WR WKH WDVNRIIX]]\cPHDQVFOXVWHULQJRIWLPHVHULHVGDWD ZKHUH WKH DIRUHPHQWLRQHG RSWLPL]HUV ZHUH XVHG WR REWDLQWKHRSWLPDOYDOXHVRIWKHZHLJKWVDVVLJQHGWR D FRPELQDWLRQ RI GLVWDQFH PHWULFV WKDW ZDV XVHG LQ WKH)&0FOXVWHULQJRIWKHWLPHVHULHV:HVKRZHGLQ WKH H[SHULPHQWV ZH FRQGXFWHG KRZ ZKLOH DOO WKH RSWLPL]HUVPDQDJHGWRLPSURYHWKHSHUIRUPDQFHRQ WKHWUDLQLQJGDWDVHWVWKHLPSURYHPHQWGURSSHGZKHQ WKHRSWLPL]HGYDOXHVRIWKHZHLJKWVZHUHDSSOLHGWR WKH WHVWLQJ GDWDVHWV DV D UHVXOW RI WKH RYHUILWWLQJ SUREOHP ZKLFK DSSHDUHG GXULQJ WKH RSWLPL]DWLRQ SURFHVV

5()(5(1&(6

%XVWRV % DQG 6NRSDO 7 '\QDPLF VLPLODULW\

VHDUFKLQPXOWLPHWULFVSDFHVProceedings of the ACM Multimedia, MIR Workshop. $&0 3UHVV 1HZ <RUN 1<

(VOLQJ 3 DQG $JRQ & 7LPHVHULHV GDWD PLQLQJ ACM Comput. Surv

)HRNWLVWRY9Differential evolution: in search of solutions 6SULQJHU 2SWLPL]DWLRQ DQG ,WV

$SSOLFDWLRQV 6HFDXFXV 1- 86$ 6SULQJHU 9HUODJ 1HZ<RUN,QF

.U]\V]WRI -& 3HGU\F] : 6ZLQLDUVNL 5: .XUJDQ /$ Data mining: a knowledge discovery approach6SULQJHU9HUODJ1HZ<RUN,QF6HFDXFXV 1HZ-HUVH\

+DXSW 5/ +DXSW 6 ( Practical genetic algorithms with CD-ROM:LOH\,QWHUVFLHQFH .HRJK(=KX4+X%+DR<;L;:HL/

5DWDQDPDKDWDQD & $ 7KH 8&5 WLPH VHULHV FODVVLILFDWLRQFOXVWHULQJ KRPHSDJH ZZZFVXFUHGX aHDPRQQWLPHBVHULHVBGDWD

/DURVH ' Discovering knowledge in data: an introduction to data mining:LOH\+RERNHQ1- /LDR 7 &OXVWHULQJ RI WLPH VHULHV GDWD±D VXUYH\

Pattern Recognition

0DXOLN8%DQG\RSDGK\D\60XNKRSDGK\D\$

Multiobjective genetic algorithms for clustering:

applications in data mining and bioinformatics 6SULQJHU

0LWFKHOO0An introduction to genetic algorithms 0,73UHVV&DPEULGJH0$

0XKDPPDG )XDG 00 D $ V\QHUJ\ RI DUWLILFLDO EHH FRORQ\ DQG JHQHWLF DOJRULWKPV WR GHWHUPLQH WKH SDUDPHWHUV RI WKH Ȉ*UDP GLVWDQFHIn DEXA 2014, Munich, Germany/HFWXUH1RWHVLQ&RPSXWHU6FLHQFH 9ROXPHSS

0XKDPPDG )XDG 00 D 'LIIHUHQWLDO HYROXWLRQ YHUVXVJHQHWLFDOJRULWKPVWRZDUGVV\PEROLFDJJUHJDWH DSSUR[LPDWLRQ RI QRQQRUPDOL]HG WLPH VHULHV In IDEAS’12 , Prague, Czech Republic, 3XEOLVKHG E\

%\WH3UHVV$&0

0XKDPPDG )XDG 00 E 2QHVWHS RU WZRVWHS RSWLPL]DWLRQ DQG WKH RYHUILWWLQJ SKHQRPHQRQ D FDVH VWXG\RQWLPHVHULHVFODVVLILFDWLRQIn ICAART 2014 0XKDPPDG )XDG 00 E 8VLQJ GLIIHUHQWLDO

HYROXWLRQ WR VHW ZHLJKWV WR VHJPHQWV ZLWK GLIIHUHQW LQIRUPDWLRQ FRQWHQW LQ WKH SLHFHZLVH DJJUHJDWH DSSUR[LPDWLRQIn KES 2012, San Sebastian, Spain, )$,$,263UHVV

0XKDPPDG)XDG00P:KHQRSWLPL]DWLRQLVMXVW DQLOOXVLRQIn ADMA 2013, 3DUW,/1&6YRO SS±6SULQJHU+HLGHOEHUJ

:LWWHQ ,+ )UDQN ( Data mining practical machine learning tools and techniques, second edition(OVHYLHU

On the Application of Bio-Inspired Optimization Algorithms to Fuzzy C-Means Clustering of Time Series

353

(10)