TELKOM NIKA , Vol.14, No .2, June 20 16 , pp. 638~6 4 6   ISSN: 1693-6 930,  accredited  A  by DIKTI, De cree No: 58/DIK T I/Kep/2013   DOI :  10.12928/TELKOMNIKA.v14i1.2751    638      Re cei v ed  De cem ber 2 0 , 2015; Re vi sed  March 18, 20 15; Accepted  April 8, 2016   Semi-supervised Online Multiple Kernel Learning  Algorithm for Bi g Data      Ning Liu 1 *, Jianhua Zh ao 2   1 School of ec o nomics a nd ma nag ement, Sha ngl uo Un iversit y , Sha ngl uo 7 2 600 0, Chi n a   2 School of mat hematics a nd c o mputer a p p lic ations , Sha n g l uo Un iversit y , Shan glu o  72 60 00, Chi n a   *Corres p o ndi n g  author, e-ma i l : liuni ng 20 122 014 @al i y un.c o m      A b st r a ct   In order to i m prove the  perf o rmanc e of machi ne  le arn i n g  in bi g dat a, onli ne  mu ltipl e  kerne l   lear nin g  al gorit hms  are pr opo sed in th is pa p e r. F i rst,  a supervise d onl in e mu ltipl e  kern el  lear nin g  al gorit h m   for big data (S OMK_bd) is pr opos ed to red u ce the co m p u t ationa l w o rklo ad duri ng ker n el modific a tio n . In   SOMK_bd, the  tradition al ker nel l earn i n g  al gorith m  is  i m pr oved a nd ker n el inte gratio n is  only carri ed o u t in  the co nstructe d kern el s ubs e t. Next, an u n s uperv i sed  on lin e  multi p le  kern el l earn i n g  a l g o rith m for  big  d a ta  (UOMK_bd) is  prop osed. In U O MK_bd, the traditi ona l kern el  learni ng a l gor i t hm is i m pr ove d  to adapt to the  onli ne  envir on me nt an d data  replac e m e n t strategy is use d  to mo dify the  kerne l  functio n  in uns up ervis e d   ma nn er. T hen,  a se mi-su per vised  on lin e  multipl e  k e rn e l  l earn i ng  al gor ithm for b i g  dat a (SSOMK_b d )  is   prop osed. Bas ed on i n cre m e n tal le arni ng, SSOMK_bd mak e s full use of the ab und ant  in formati on of lar g e   scale i n co mp le te labe le d dat a, and us es S O MK_bd  a nd  UOMK_bd to  upd ate the cur r ent read in g d a ta.  F i nally,  exp e ri me nts ar e c o n ducted  o n  U C I  data s e t a n d   th e res u lts s how   that the  pro pos ed  alg o rith ms   are  effective.    Ke y w ords : Se mi-s uperv i se d Classific a tio n , Onlin e Le arni n g , Multipl e  Ker nel, Big D a ta     Copy right  ©  2016 Un ive r sita s Ah mad  Dah l an . All rig h t s r ese rved .       1. Introduc tion  In rece nt years, with the ra pid develop m ent of  the Internet, clo ud computing, Internet o f   things, soci al  media a nd ot her info rmatio n techn o logy,  data from all  walks of life  are  sho w in g an  explosive g r owth tre nd [1]. We have  entere d   the  era of big  data, whi c h  has b e come  an  importa nt st rategic re so urce  of the  co untry,  the  m anag ement a nd  a nalysi s  of  big data ha s  become a hot  topic of aca d e mic an d ind u strial attenti on [2, 3].  The purpo se of  data coll ection,  data sto r age,  data  tra n smi ssi on  an d data  ma na gemen t   is to use big  data effective l y, where m a chin e lear nin g  techn o logy  is esse ntial [4, 5]. In rece nt  years, m a chi ne lea r nin g  in  big data  bein g  one  of  the hotsp ots  h a s attracte d extensive attentio n,  and ne w a c hi evements  are eme r ging [ 7 , 8]. For exam ple, Klein e r et al., [9] put forward a  ne w  data  sam p lin g meth od  of BLB b a se d  Baggi ng   l earni ng th ou ght, to  solve  the  bottlen eck  probl em s of cal c ulatio n in big dat a Bootstra p; Go nzal ez et al. ,  [10] presen ted  distribut ed   machi ne l e a r ning f r ame w o r k graph  to  realize the   la rge-scale  ma chine l earning;  Gao  et  al., [11]  prop osed the  idea of "one  pass learnin g " lear nin g , trying to only sca n again  the data usin g  con s tant  storage to sto r e i n terme d iate result s,  whi c h  achi eved go o d  re sults in A UC o p timization   su ch a compl e x learnin g  task.   However, there are  still many probl ems to  be solved in machine l earni ng for bi g data  due to it’s complexity [6, 7]. From the view of  the algorithm,  it mainly exists the follo wing  probl em s in  machi ne l earning a nd th e  analysi s   of  big data  mini ng. Becau s e  of the hu ge  data   size, it is not within the  accepta b le time to  get results. So putting forwa r d  a new ma chi n e   learni ng algo rithm to meet  the deman d of high  data pro c e ssi ng a nd larg e data  is one of the hot  r e sear ch points  in mach ine learning [3, 7].    On this i s sue,  the resea r ch ers  gen erally  solve the p r o b lem of big d a ta machine l earni ng  throug h two  method s. A method is to  modify ex isting machi ne le arnin g  algo rithm and tra n sform   it to be concurrent\parallel  computin g versi on[6,10]; the other me thod is to design a onlin e   learni ng versi on of  existing machi ne le arnin g  and d a t a mining alg o rithm [6, 7].  Becau s e th e online le arni n g  doe sn't ne e d  to store  sa mples  of earl y  data, or onl y needs  to save the early data from a sam p le  of a sufficie n t statistic, it is very suitable for big data  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  1693-6 930       Sem i -supe rvi s ed O n line M u ltiple Kern el Learning Alg o rithm  for Big Data (Ning Li u)  639 analysi s  ap pli c ation  scena rios. Fo r very l a rge  dat a  set s , online l earning get s dat a in a sequ en tial  manne r and  synchro nou s  update lea r ni ng; for hi gh speed dat a streams, onli ne  learni ng can  be  carrie d out while data is i nputting. And  the lear nin g  model can reflect a re ce nt period  of time  input data  rul e  and  ma ke  effective pred iction [12,  1 3 ]. In rece nt years, some  rese arche r s p u t  online lea r ni n g  into the field of machin e  lear nin g  and  produ ce d be tter benefits. For exampl e,  Shalev-Sh w a r tz S [1 4] p r o posed  gra d ie nt asce nt  (d e s cent)  metho d  ba se d o n  t he id ea  of on line  learni ng to impleme n t a large - scale m odel of fa st learni ng; Yan g  [15] prop osed an in cre m ental   optimizatio n fast de cisi on tree alg o rithm  for data with  noise. Comp ared  with the  traditional bi g   data mini ng  deci s io n tre e  algo rithm, th e main  adv a n tage of thi s  algo rithm  was  with real -time   mining capa b ilities, which coul d  store the com p lete  data for tr aini ng de cisio n  model when  the  mobile data  stream was inf i nite.  As a kin d  of importa nt onli ne lea r ning  method,  onli n e multiple kernel lea r ning  h a s be en   widely used  in different application fields [16-19 ]. Ho wever, du e to the indirect influe nce of  kernel l earni ng p r obl em  on target an alysis, o n line   multiple ke rnel  lea r nin g  has not  b een   fully  resea r ched in  the field of big data analy s is and mini ng  [7].  In orde r to improve the p e rforman c e of  machi ne lea r ning in big d a t a environm e n t, semi- sup e rvised l e arnin g  a nd  o n line m u ltiple  ke rnel  lea r ni ng a r e i n tro d u ce d into  the  field of  big  d a ta   machi ne lea r ning in this p aper. Fi rst ， a  supe rvise d  o n line multiple  kernel lea r ni ng algo rithm  for  big d a ta  (SO M K_bd) i s  p r opo sed   to  re duce th e  co mputational  worklo ad du ri ng  o n line   lea r ning   kernel mo dification. Next,  an un sup e rvi s ed o n line  m u ltiple ke rnel  learni ng alg o rithm (UO M K_ bd)  is p r op osed  to adapt   to  the onli ne l earni ng  environment. T h e n , an  semi -supervi sed  on line   multiple  ke rn el lea r nin g  al gorithm  for  bi g dat a  (SSO MK_bd) is p r opo sed. Ba sed o n  the  onl ine  learni ng fra m ewo r k of increme n tal lear ni ng, SSOMK_bd ma ke s full use  of the abundant   informatio n o f  large scale  labele d  and  unlab el ed dat a, and uses t he SOMK_bd  algorithm an d  UOMK_ bd  al gorithm  to u pdate th e  cu rre nt re adin g  data  se para t ely. Finally, experim ents  are  con d u c ted on  the benchma r k  UCI data  set to verify  th e effectivene ss of the p r op ose d  algo rith m.  The  stru cture  of this pap e r  is a s  follo ws:  th e   part  I is th e introdu ction; the  part II   introduces the  propo sed algorithms: SOMK_bd, UOMK_bd  and SSOMK_bd; the part III is the  experim ent a nd analy s is; the part IV is the co ncl u si on ; the part V is the ackno w le dgeme n ts.       2. Proposed  Algorithms   In this p ape r, we  pro p o s e  three  kin d s  o f  algorithm s i n  big  data e n v ironme n t, there  are   sup e rvised o n line multiple  kernel lea r n i ng al go rithm  for big data  (SOMK_bd ),  unsu pervi se d  online m u ltipl e  ke rnel l earning alg o rith m for big d a ta (UOMK_b d )  and  semi -supervi sed  onl ine  multiple ke rn el learni ng al gorithm for bi g data  (SSO MK_bd). Th e three alg o rith ms are de scri bed   in the followin g  part of the pape r.    2.1. Supervi sed Online  Multiple Kernel L earning  Algorithm for Big Da ta (SOMK_ bd)  The m a in p u rpose of m u ltiple kernel le a r ning  is t o  stu d y ke rnel  fun c tion  with p a rametri c   or se mi-p ara m etric di re ctly from  the training data,  whi c h contai n the informa t ion reflectin g  the   data di strib u tion. We ta ke i t  as  given  a  set of traini ng  data  D L = { (  x i ， y i )|i = 1 ，， ， ， 2 … n} wh ere   x i  is feature  set, y i ∈－ ， ， { 1 +1} i s  th e cl a s s label  K m = { k j (· ，Ｒ ， ， ， ， ·)  : X ×  X →   j  =  1 2 … m }  i s   given a set contai ning m  basi c  kernel  function s ， u =  {  u 1 ， u 2 ， …u m ,  ∑ u i = 1 }  is a  set of no n   negative wei ghts ， mini mizing the  cla ssi fication e r ror  of t he ke rnel  learni ng ma chine o n  the t e st   set. Beca use  of non ne gat ive weight s, convex com b i nation  kernel  function i s   still a valid ke rn el  function. The  probl em can  be formali z e d  as the formul a(1 ) :                                                                                     2 ii 1 mi n (f(x ) , y ) k k n fH H i fC l                                                                                                      (1)     For the formu l a (1), it is difficult to dire ctl y  compute th e optimal val ue ,even it is basi c ally   impossibl e  wi thin a c cepta b le time  to fi nd the  o p timal solution,  e s pe cially  und er th e bi g  da ta  environ ment .  In general, online multiple  kern el learni ng  will tran sf orm the opti m ization p r o b lem of  formula  (1) in to the followi ng problem: first, find out the optimal fu nction f i  of e a ch  ke rnel K i  in  their resp ecti ve Hilbe r t sp ace  H ki  ; then,  look fo r a set of weight s u i ,  which ma ke s the f i  to be the  Evaluation Warning : The document was created with Spire.PDF for Python.
                             ISSN: 16 93-6 930   TELKOM NIKA   Vol. 14, No. 2, June 20 16 :  638 – 64 6   640 best  co mbin a t ion, and  u p d a te weight s  u i  and  f i   synchronou sly in  th e p r o c e s s of  sea r ching  for  the  optimal value .     Whe n   the co mbination of kernel  fu nctio n   is  lin ea r, the onli ne m u ltiple ke rnel  l earni ng  probl em can  be solved by the  followi ng three step s: i n  the first  ste p , train  a  classifier f i  usi ng  t he  basi s  of the t r aining  set for  each kern el functio n .  The  se con d  ste p  i s  to pe rform  online l earnin g .  After readi ng  a trainin g  sa mple, differe n t  strategi e s  a r e ado pted to  modify the ke rnel  weig ht a n d   the cl assifier  according  to  different p r e d i ction  re sults.  In the thi r d   step, ite r ative  until it m eet s   certai n  con d ition, the o p timal kern el fu nction i s   a weighted  co mb ination of  ea ch ke rn el fun c tion  with the o p timal wei ght. Duri ng the  seco nd  step  and the thi r d step,  kern el wei ghts a n d   cla ssifie r s’  up dating  strate g y  is a s  follo ws: firs t  rea d  a  training  sam p le, then d e termin e wheth e r  the predictio n of the  sam p le is  co rrect .  If corr ect, d o  not pe rform any up dati ng a c tion; if  not,  update the  co rre sp ondi ng kernel  weig ht and cl assifier.   Ho wever, the r e is a p a rticu l arly larg e nu mber  of kern el function s in  the pro c e ss  of online  multiple  ke rn el lea r nin g .  Whe n  e a ch  sample i s  i npu t, all ke rnel  fu nction  are u s ed to  pre d ict  and  weig ht; once  the fore ca st  is not  co nsi s tent with  t h e co rrect la b e l, the wei g ht of all kernel  function s a r e  neede d to cha nge a nd  modify. This   will be a  wa ste of co mp uting re so urces,  esp e ci ally in big data environment,  it s ef f i cien cy  is v e r y  low.   In orde r to improve the op erating effici e n cy  of online  multiple ke rn el learni ng un der th e   environ ment  of big d a ta a nd redu ce it s com put ation a l re so urce  d u ring  modifyi ng weight  an d  cla ssifie r , we improve the traditional onli n e multip le ke rnel learning a l gorithm , and  put forward a  sup e rvised o n line multiple  kernel lea r nin g  algor ith m  for big data whi c h is n a med  as SOMK_ b d .   In the integ r a t ion process  of online  mul t iple ke rnel  le arnin g , SOM K _bd u s e s  B e rno u lli  sampli ng  to do  a random sampling. Only   the  samp l e   whose  sel e cti on probability is 1 is sel e ct ed  to be con s tru c ted a s  a  su bset of  kerne l  function  and  only the one  in the sub s e t  is to ca rry o u t   function p r edi ction, wei ghte d  combi natio n, kern el  wei ght and cl assi fier updatin g, redu cin g  ke rn el   cal c ulatio n workl oad.     Algorithm 1. The Algorith m  Description  of SOMK_bd   Inpu t :   – kernel functi on set ：   K m = {  k 1 ， k 2 ，， …k m }   –  T he  t -th labe led sam p le ：（ x t  ,y t ）    – Initializ ed cl assifier ：  F = {  f 1 (t) ， f 2 (t ) ，， …f m (t)}    – W e ight ：  u i (t)=1 , i=1,. ..,m    – Discount factor ：∈ β (0,1)   – Smoothin g  p a rameter ：∈ δ (0 ,1 )   Outp ut ： kernel w e ig ht  u i (t+ 1 ) and cl assifier  f i  (t+1),  i=1,. ..,m   Proc e dure ：   1 ）  q i(t) =u i (t)/[max 1 ≤ j ≤ m u j (t)], i=1, ... , m                 /*Kernel  w e i ght prob ab ilit y  q i (t)*/  2 ）  p i (t)=(1 −δ )q i (t)+ δ /m, i=1,. ..,m                 /*Kernel se le ction pro b a b il ity p i (t)*/   3 ）  for i=1,2,.. ., m do  4 ）    Sample s i (t)= Bernoul li_S a mpli ng( p i )    /*s i (t)= 1 represents i-th kerne l  is selected, th e one  w h er e s i (t)= 1construct a  subset*/   5 ）  end for   6 ） * 1 ( ) ( ( t ) (t ) s i g n ( ( t ))) m ii i i yt s i g n s q f    /*W e ightin g in  the subset  a n d  predict the la b e l of x t */   7 ）  for i=1,2,.. ., m do  8 ）     if  y * (t)= y t  then    /*correct, not update * /  9 ）         z i (t ) = 0  10 ）   else                /*not correct, upad e*/   11 ）      z i (t)=1      12 ）   end if   13 ）   Update u i (t+1)=u i (t) β z i  ( t ) m i( t)                                  /* w e i ght up datin g  w h ere z i (t)= 1 and m i  (t)=1*/  14 ）   Update f i (t+1)= f i (t)  + z i  (t )  m i (t) y t  k i (x t  ,•)           /*classifer u pdati ng  w h ere  z i (t)= 1 and m i  (t)=1*/  15 ） en d for   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  1693-6 930       Sem i -supe rvi s ed O n line M u ltiple Kern el Learning Alg o rithm  for Big Data (Ning Li u)  641 The d e tailed  pro c ed ure of  the alg o rith m SOMK_bd  is  sho w n i n  Algorithm  1. For th e   input labele d  sampl e s (x t  ,y t ), in step 1)  the  weighted probability  q i (t) is cal c ulate d ; in step 2) the  i-th  kernel sele ction probability p i  (t) is calcul ated. He re, p i (t) add s the smo o thing  paramete r   δ  to  ensure that each  kernel is  se lected  with the probabilit y of  δ /m, and avoid that the proba bility p i (t)  is con c entrated on  a few  kernel fun c tio n ; By step 4) Berno u lli sa mpling i s  carried o u t and  th e   probability s i (t) is  cal c ulate d . The o ne  where  s i   (t)  = 1  rep r e s ent s t hat the i-th  kernel  is  sel e cted  whe n  the  t-th  sampl e  i s  i n p u t. Then, th e  all kernel fu n c tion  sel e cte d  by Be rnoulli   sampli ng (s i  (t )  =  1)  c o ns titute  a s u bset; In the s t ep 6), the k e rnel  is  we ighted in th e  sub s et a nd th e predict ed la bel   of X is calcul ated; Step 13) and  step  14) is th e up dating proce dure of the  kernel  weig ht and  kernel  cla ssifi er. He re, the  updatin g only  focu s on t h e  sub s et of o n l i ne multiple  kernel l earning ,  whe r e s i (t )=1; That i s  to  sa y that we  onl y update  th e kernel wei ght   and cla s sifie r   where z i (t) = 1  and m i (t)=1 in  SOMK_bd al gorithm.     2.2.  Unsuper v ised Online Multiple Kernel  Lear ning Algorith m  for Big Da ta (UOM K_b d )  Traditio nal kernel le arni n g  method b a se d on da ta depend en ce is a co mmonly    unsupe rvise d  ke rnel l e a r n i ng meth od,  only co nsi d e r ing th e de n s ity of data  distrib u tion. I n   essen c e, it is to modify the ke rnel fu nction in  the tra i ning  set. It can modify an y existing kern e l   function b a se d on the ob served d a ta sample s , the essen c e i s  to  modify the inner  pro d u c t on  the Hilbe r t sp ace in du ced  by the kernel  function.  In gene ral, the  kernel fun c tio n  is modifie d  by  the formula (2), whi c h ma ke s the dist ribut ion of the D in the data  set.                     1 ( a , b ) ( a, b) ( I ) T Da D b Kk k M KM K                                                                                                 (2)      Whe r e D = {x 1 ,x 2 ,…,x n }; K is kernel fun c tion ， k xi =( k(x i ,x 1 ),k(x i ,x 2 ),…, k(x i ,x n )) ), K rep r e s ent s th e   Gram mat r ix of k about D ； a and b are  2 training sa mples; W ij =RBF( x i ,x j ), Where x i  and x j  are   the element s on the D , rep r esents  a sy mmet r ic dist a n ce  mat r ix .   The cal c ul ation of formula  (2) nee ds to  be  in the off-line bat ch, and the com p utational   time com p lex i ty is high. At the sa me ti me,  the kern el functio n ’s  updatin g of a  and b  nee d  to  comp ute K a  a nd  K b  in  the   data  sam p le s. For large  d a ta st ream s,  M an d K D   i s  in chan ging, a nd  not ea sy to  calcul ate. In  a ddition, di re ct  cal c ul ating t he  whol e d a ta set M  an d  K D  is  not real istic  in comp uting  resou r ces.   In order to m a ke the data  depe nd on kernel le arni n g  method suitable for onli ne ke rnel   modificatio n  in big data  environ ment.  We pr ovide  an unsupe rvised onli n e  multiple ke rnel  learni ng alg o rithm for big d a ta, which is  named a s  UOMK_bd.       Algorithm 2. The Algorith m  Description  of UOMK_bd   Input ：    –D= { x 1 ,x 2 ,…,x n }   –Curre nt input  sample ： x t    –Gram matrix  and d i stanc e matrix ：   K ,  M   Output ： Updat ed kern el matri x :  K   proce dure ：    1 ） Initializati o n   K x0    2 ） K xi =( k (x i ,x 1 ), k (x i ,x 2 ),…,  k (x i ,x n )))   3 ） for j= 1,…,N  do    4 ）     K 2 = K (j, •)     5 ）      1 11 2 (I ) t T x Kk k M KM K    6 ） end for    7 ） Using  K xt  to update matri x   K in the last ro w   a nd the l a st colum n         /*FI FO displacement*/   8)  return  K       The al gorith m  de scription  of UOMK_b d is  sh own in  Algorithm  2.  UOMK_ bd fo cu se s  o n   the onli ne u p dating  of M a nd K D . In order to facilitate the  cal c ulati on of M  and  K D , the si ze  o f  the  M and K D  a r e  re stricte d  to  be fixed N* N.  In orde r to m a ke full  use o f  information  of all of the d a ta  sampl e s to p e rform  ke rnel  learnin g , the sample d a ta  repla c em ent  strategy in D is de sign e d  to  Evaluation Warning : The document was created with Spire.PDF for Python.
                             ISSN: 16 93-6 930   TELKOM NIKA   Vol. 14, No. 2, June 20 16 :  638 – 64 6   642 ensure that th e other  sampl e s can be co me the el eme n t of D. Beca use the d a ta gene ration  rul e s  of big  data  m a y ch ang e  wit h  the  chan ge  of time, we  l e arn   from the  operating sy stem “first in first  out” (FIFO )  p age re pla c e m ent policy t o  repla c e th e  data sam p le s in D. He re,  the timeliness of  data is con s id ered.     In UOMK_b d ,  it maintains  a wo rking  set  of M whi c h  can be  used a s  a  ca che to   reflect   data di strib u tion in  a pe rio d  time. The  wo rkin g  set lim iti ng st rategy h a s a  cert ain  l o cality, but it i s   comp romi se d  unde r the limited com put ation and m e mory  re so urces. In the re a lization of FI FO   strategy, ne w entrants to the sam p le are put at the down w a r d an d  t he right colu mn in matrix M,  and the elem ents of the first ro w and first colu mn are  removed.      2.3. Semi-superv ised Online Multiple Ker n e l  Learning  Algorithm  for Big  Data   (SSOMK_bd)  Und e r th e e n v ironme n t of  big d a ta, lab e led  data lo ss i s  very  co m m on a nd th e  big d a ta  set i s  a mixe d data  set in cluding l abel e d  data  and  u n label ed d a ta . If you only u s ed l abel ed  d a ta   to learn by  a  sup e rvised l e arnin g  m e tho d , then  a  sup e rvise d  le arni ng mo del  doe s n o t have  go od   gene rali zatio n   ability  a n d  it  can  cau s e  large  waste  of  unla bele d  data;  If  you only  u s e a  l a rge  amount  of un labele d  data  with impli ed i n formatio n to  learn by u n supervi sed  lea r ning  metho d ,   the unsupervi sed learning  will ig nore the value of labeled data.  S e mi-supervised learni ng i s   a  new m a chine  learni ng met hod bet wee n  the tradition al sup e rvi s ed  learni ng an d  unsu p e r vise d  learni ng, its p u rpo s e i s  to  make full  use  of a large  nu mber  of unla beled  sam p le s to ma ke up  for  the lack of labeled  sampl e s and  imp r ov e the learni ng  performan ce  effectively.      Figure 1.  Semi-supe rvise d  Cla ssifi cati on Flow  Cha r t      Algorithm 3.  The Algorith m   Descri ptio n of SSOMK_bd   Inpu t ：  –D= { x 1 ,x 2 ,…,x n }   –Sampl e ：（ x t  ,y t ）   Outp ut ： Updated kern el matri x  K   Proc e dure ：   1)  Initializ ation   K   2)  Learn K fro m  D 0   3)  for each (x t ,y t ) in D  4)     if   y t  is not  NULL the n   5)             call SOMK_bd to car r y  out u pdati n g   6 ）    else  7 ）           call UOMK_bd to carr y out upd ating   8 ）    end if  9 ） end for     Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  1693-6 930       Sem i -supe rvi s ed O n line M u ltiple Kern el Learning Alg o rithm  for Big Data (Ning Li u)  643 Here, we pro posed a sem i -su p e r vise d online   multipl e   kernel  l earning algo rith m  for  bi g   data whi c h i s  nam ed a s  SSOMK_bd,  makin g  full use of  samp le  labeling i n formatio n a n d   unlab eled  sa mples with  i m plicit info rm ation to  ge n e r ate effe ctive  ke rnel  fun c tions an d effe ctive  cla ssifie r . Specifically, wh en re ading  a sam p le, o n line lea r nin g  method i s  base d  on t he  increme n tal learni ng to pe rform. First it deter mine s  wheth e r the sampl e  is ma rke d . If marked,  SSOMK_bd use s  su pervi sed   onlin e multiple ke rn el  lea r nin g   a l gorithm   SO MK_bd pre s ented   above in  part  2.1 to ca rry  out ke rnel  m odificatio n ; otherwise, it uses the  on -lin e un sup e rvised   multiple ke rn el learni ng al gorithm  UOM K _bd pr esent ed above in  part 2.2 to carry out kern el  modificatio n s.  Iterative until  they meet certain  con d ition. Finally it  gene rate s th e optimal  ke rnel  function to form a cla ssifie r  and  the test is ca rri ed out  on the test da ta.    Among the m , online  multiple ke rnel lear ning  and se mi-sup ervised classificatio n   algorith m  a r e  sh own in  Fi gure  1,  uppe r p a rt  within t he d a shed  b o x rep r e s e n ts o n line  multi p le   kernel le arni ng an d the  followin g  pa rt within the  dashed b o x rep r e s ent s semi-sup ervised   cla ssifi cation  pro c e ss. At the end of the  online mu ltip le kernel lea r ning, it generates an o p timal  kernel fun c tio n  for semi -su pervised cl as s i fic a tion to cons truc t the  class i fier.   The de scripti on of algorit hm SSOMK_bd is sh own  in Algorithm  3, where th e kernel  function i s  up dated in ste p  5) and 7 ) .       3.  Experiment and Analy s is  The experi m ents are ca rri ed out on UCI data se ts  and the pro p o se d algo rith ms in the   pape r are  co mpared with  the existing online mult iple ke rnel le arnin g  algo rithm  and batch   pro c e ssi ng of  multiple ke rn el learni ng al gorithm to ma ke the effecti v eness a s sessment.   In the exp e ri ment, SVM i s  used  as a  ke rnel   fun c tion.  RBF  ke rnel  a nd p o lynomia l ke rn el  , whose para m eters are  selecte d  ran d o m ly, are us ed  to  c o ns tr uct k e r n e l  fun c ti on [23, 24]. And   0-1 lo ss fun c t i on is u s ed to  evaluate the error rate.   In orde r to  cancel the o r d e rs of mag n it ude differen c e between th e dimen s io ns of data   and avoi d large predi ction  error  ca used  by diffe ren c es in i nput a nd outp u t, da ta norm a lization   function  is u s ed h e re. As shown in  form ula  (3),  the  i n put featu r e v a lue i s  no rma lized  to [-1, 1]  by  data normali zation functio n .      m in k m ax () / ( x x ) kk xx x                                                                                                   (3)    Whe r e x min    rep r e s ent s the minimum value in data seq uen ce, x max  repre s ent s the maximum  value in data  seq uen ce.       Table 1.  The  Dateset1 of Experiment   Index Dataset  Size   Dimensions  D1 Breast  683  9  D2 Splice   1000   60  D3 Dorothea   1150   100000   D4 Spambase  4601   57  D5 Mushrooms  8124   112          Table 2.  The  Dateset2 of Experiment   Index Dataset  Size   Dimensions  D6 Forest  Cove rT yp e  581012   54  D7 Poker-Hand   10 7  11  D8  Localization   Data for Pe rson  Activity   164860  8      Such  a s  Ta bl e 1  and  Ta bl e 2, 8  ki nd s  of  UCI data   sets a r e  use d  in th e exp e rime nt.  Table 1 is u s ed to verify the validity of the SOMK _bd  algorithm a n d  Table 2 is u s ed to verify the  validity of the  SSOMK_bd a l gorithm.   For the  samp le sele cted in  Table 2, the  prop or tio n  of the trainin g  set and the te st set i s   set to 1:1. The trainin g  set divided into l abeled a n d  unlabel ed  sampl e s. Th ree types of semi- sup e rvised  cl assificatio n  e x perime n tal d a ta sets a r e  con s tru c ted  a c cordi ng to t he p r op ortion  of   Evaluation Warning : The document was created with Spire.PDF for Python.
                             ISSN: 16 93-6 930   TELKOM NIKA   Vol. 14, No. 2, June 20 16 :  638 – 64 6   644 labele d  samp les to th e nu mber  of traini ng set sampl e s. In first cl a ss, the r e  are  labele d  samp les  accou n ted fo r 5% of the  sampl e s i n  the traini ng set; in the se con d  cla s s, there  are l a b e led   sampl e s a ccounted for 1 0 % of the sample s in the  training  set ;  in the third class, there  are  labele d  sam p les a cco unte d  for 15% of the sample s in the training set. We ca lculate the to tal  cla ssifi cation  rate by cal c ul ating the average  of the 3 kinds of cl assif i cation rates.    At the same t i me, the data  in Table  2 is divided into  30 pa rts, whi c h a r e to p u t in 4 file s  sep a rately, a nd the  data i n  the  seq uen tial rea d  file i s  trai ned  and  tested  on th e onlin e multi p le   kernel lea r ni n g . All these d a ta are u s e d  to  evaluate the rel a tionshi p betwe en th e data set si ze  and the CP U pro c e ssi ng time.      Table 3. The  Experiment Result     OM-2   SOMK_bd   mistake(%)  time(s)  mistake(%)  time(s)  D1 34.30±2.80   0.270±0.015   24.25±3.10   0.245±0.013   D2 30.80±1.41   0.420±0.005   25.56±1.21   0.380±0.020   D3 10.70±0.72   0.435±0.013   8.20±0.52   0.426±0.041   D4 58.16±1.50   5.184±0.239   23.30±1.10   3.30±0.68   D5 0.37±0.03   8.691±0.070   0.34±0.02   2.560±0.02       Table 4.  The  Corre c t Cla s sifi c a tion Rat e  Comparis on (%)    Algorithm 1  Algorithm 2  SSOMK_bd   D6 72.5±1.80   74.25±2.10   77.0±2.43   D7 78.7±2.01   78.18±1.15   81.70±1.37   D8 61.02±0.24   67.55±1.33   75.46±1.65           Figure 2.  CPU Ru n Time  Comp ari s ion       The first exp e rime nt is ca rrie d  out to  compa r e the  prop osed SO MK_bd with  existing   online m u ltiple ke rnel le arning alg o rith m om-2 [2 0]  to verify its  effec t ivenes s  in reduc i ng  the  comp utationa l wo rklo ad  du ring  ke rnel  m odificatio n . As sho w n in  T able 3, the  ex perim ent results  sho w  th at SO MK_bd  ha s e ffectiveness t o  re du ce  ke rnel  scale, ma inly in sho r te ning th e lea r n i ng  time and red u cin g  the error rate. The  rea s on i s  tha t  SOMK_bd redu ce s cal c u l ation wo rkl o ad  durin g ke rn el modificatio n  and sele cts some re pre s e n tative kern el  to update.  The  se co nd  e x perime n t is   carrie d o u t to  co mpa r e  the  propo se d  se mi-supe rvise d  onli n e   multiple kern el learni ng al gorithm SSO MK_bd with  t he existing  su pervised onli ne multiple  kerne l   learni ng  algo rithm1 [21] a n d  alg o rithm2   [22] to ve rif y  it s    ef f e ct iv en es s  in  improving the  co rre c t  cla ssifi cation.  As sho w n in  Table  4, we  c an  kn ow th at the propo sed  SSOMK_ bd ha s hi ghe r  corre c t cla s si fication rate  than the existing alg o rith m1 [21] and  algorithm 2 [22]. Espe cial ly,  SSOMK_bd i s  effe ctive in  dealin g with  l a rge  scal e in compl e te la b e led  data. Th e re ason i s  t hat   SSOMK_bd  make s full u s e of the tag i n formatio n of  labele d  sam p les  and  abu ndant info rm ation  of unlab eled  sam p le s to  train effe ctive cla ssifie r ,  whi c h  can   improve th e  perfo rma n ce of  learni ng.   0 5 10 15 20 25 30 0 5 10 15 20 25 Run t i m e  v a r i at i o n   di ag ram T h e s c al e   of   da t a  s e t ( * 1 0 6 ) T he run t i m e  of  C P U / s  (* 10 2 )     Al g o r i t h m  1 Al g o r i t h m  2 SS O M K b d Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  1693-6 930       Sem i -supe rvi s ed O n line M u ltiple Kern el Learning Alg o rithm  for Big Data (Ning Li u)  645 The data in T able 2 was di vided into 30  par ts to eval uate the rel a tionship bet ween the   data set si ze  and the  CPU  pro c e ssi ng ti me. As sho w n in Figu re  2, we  can  se e  SSOMK_bd  has  a goo d lin ear relatio n ship  betwe en the   gro w th  rate o f  the ru nnin g  time an d dat a set si ze. T h e   experim ent result in dicate s that SSOM K _bd is  with  good  scalabili ty and co uld  be u s ed in  m o re   regul ation s  d a ta analysi s   and ap plication. T he rea s on is that S S OMK_bd u s e s  increm e n tal  learni ng f r am ewo r k to im p r ove the  cl assificatio n  p e rf orma nce a n d  it is  effective  in the  big  da ta   environ ment.       4. Conclusio n   In this pa per,  the online  mu ltiple ke rnel l e ar nin g  alg o rit h m und er bi g  data environ ment is  studie d  deepl y, and the semi-supe rvise d  learni ng is  i n trodu ce d into the field of  big data ma chin e   learni ng. Th e  tradition al kernel  lea r nin g  algo rithm s  is imp r oved  to red u ce t he comp utational   worklo ad du ri ng ke rnel mo dification. Th e increme n tal learnin g  fra m ewo r k is used to improve  the   cla ssifi cation  perfo rman ce  in big data e n vironm ent. Based o n  the  current readi ng of larg e d a ta  fragme n ts i n   an o n line  wa y, the algo rith m ma ke s full  use  of the  ri ch information  of lab e led  d a ta  and unl abel e d  data to a c hieve ke rn el  updating  an d  co nstruct  efficient kern el function.  The  experim ent is condu cted  on the be n c hma r k UCI  large  data set, the results show th at th e   prop osed  alg o rithm s  a r e e ffective in sh ortenin g  the l earni ng time   and  red u ci ng  the erro r rate.  Also the prop ose d  algo rith ms could be  use d  in big d a ta analysi s  a nd appli c atio n.       Ackno w l e d g ements   The Proje c t Suppo rted  by Natural Sci e n c e Ba si c Research Pla n  in  Shaanxi Pro v ince o f   Chin a  (Prog r am  No.20 1 5 J M63 4 7 ) ; Th e Proj ect  Su pporte d  by  Scien c e  Te chnolo g y Plan  in  Shanglu o  Cit y  of China (Program No. SK2014- 0 1 -15); The Project Supp orted by Scien c e   Research Plan of Shangluo Univ ersity (Program No.14SKY026).      Ref e ren c e   [1]  LI W u jun, Z h o u  Z h ihu a . Lear nin g  to hash fo r big d a ta: Current status a nd future tren ds.  Chin ese   Scienc e Bull eti n . 2015; 6 0 (5-6 ): 485-49 0.  [2]  Ma yer-Sch önb erger V, Cuki e r  K. Big Data:  A  Revol u tion T hat Will T r ansform Ho w  We Live, Work,   and T h ink.  America n  Journ a l  of Epide m iol o g y . 2014; 17( 1): 181- 183.   [3]  Li Z h i jie,  Li  Y uan xian g, W a ng F e ng, et  al . Onlin e L earn i ng  Alg o rithms  for Big  Dat a   Anal ytics: A   Survey .  Journ a l  of Computer  Rese arch an d  Devel o p m ent . 201 5; 52(8): 17 07-1 721.   [4]  Z hou Z H , Cha w l a  NV, Ji n Y, et al. Big Dat a  Opportu nitie s  and C hal le n ges: Discuss io ns from Dat a   Analy t ics Pers pectives.  IEEE Co mp utation a l  Intelli genc e Ma ga z i n e . 20 14; 9(4): 62-7 4 .  [5]  T an M,  T s ang IW , W ang L. T o w a rds  Ultrah i g h  Dim ensi o n a l  F eature S e lecti on for B i g  Data .  Journa l o f   Machi ne Le arn i ng R e searc h . 201 4; 15(2): 13 71-1 429.   [6]  Yoo C, Ram i re z L, Liuzzi J. Bi g data a n a l ysis   using m oder n  statistical an d  machi ne l earn i ng meth ods  i n  me di ci ne .  Internati ona l Ne u r ourol ogy Jo ur nal . 20 14; 18( 2 ) : 50-57.   [7]  HE Qing, LI N i ng, L U O W e n - Juan, et  al. A  Surv e y  of Ma chin e Le arn i ng  Algor ithms for  Big D a ta.   Pattern Reco g n itio n & Ar tificial Intelligence .  201 4; 27(4): 32 7-33 6.   [8]  Hans en T J ,  Maho ne y M W .   Semi-su pervis ed Eig env ector s  for Large-sc ale L o cal l y -bi a sed Le arni ng.   Journ a l of Mac h in e Le arni ng  Rese arch . 20 1 4 ;15(1 1 ): 369 1 - 373 4.  [9]  Klei ner A, T a l w alkar A, S a rkar  P, et al.  T h e b i g d a ta  bootstr a p . Proc eed in g s  of the  29th  In ternatio nal   Confer ence  on  Machin e Le arnin g  (ICML). Edin burg h . 201 2 :  1759-1 7 6 6 .  [10]  Gonzal ez JE,  Lo w  Y, Gu  H, et al.  Pow e r G raph: Distri b uted gr ap h-par alle l co mputati on o n  n a tura l   grap hs . Proc eed ings  of t he  10th  US ENIX S y m pos ium  on O per ating  S y stem s Des i gn an d   Impleme n tatio n  (OSDI). Holl yw o o d . 201 2: 17-30.    [11]  Gao W ,  Jin R ,  Z hu S, et al.  One-pass AUC opti m i z at io n . Proceed ing s  of the 30th Internatio na l   Confer ence  on  Machin e Le arnin g (ICM L). Atlanta. 20 13: 90 6-91 4.   [12]  Hoi S CH, W a ng J, Z h a o  P. LIBOL: A Libr ar y  f o r  Onli ne Lear nin g   Al gor ithms.  Journ a l  of Machi n e   Lear nin g  Res e arch . 201 4; 15( 1): 495-4 99.   [13]  Yang   Ha ifen g, Liu  Y u a n , Xie  Z henp ing,  et a l . Efficientl y  T r ainin g  B a ll  Vect or Mach in e i n   Onlin e W a y.  Journ a l of Co mputer Res earc h  and D e ve lop m e n t . 2013; 5 0 ( 9): 1836- 18 42 .  [14]  Shal ev-Sh w a r tz S, Z hang T .   Acceler a ted pr oxi m al stoc has tic dual  c oord i nate asc ent for  regul ari z e d   loss minimi z a tion . Procee di n g s of the 31st  Internation a l  Confer ence  on  Machin e Le ar nin g  (ICML).  Beiji ng. 20 14:  64-7 2 .  Evaluation Warning : The document was created with Spire.PDF for Python.
                             ISSN: 16 93-6 930   TELKOM NIKA   Vol. 14, No. 2, June 20 16 :  638 – 64 6   646 [15]  Yang  H, F o ng  S.  In crem en tal l y  op tim i z e d   de ci si on  tree  for n o i sy bi g   d a t a . Proce edi ng s of the  1st   Internatio na l W o rkshop o n  Big Data, Streams an d H e terog e n eous  Source Mi nin g :  Algorithms,   S y stems, Prog ramming Mo de ls and Ap plic ati ons. ACM. 201 2.  [16]  Motai Y. K e rn el Ass o ciati o n   for Cl assificati on  an d Pre d ict i on: A  Surv e y .   IEEE  Trans  Neur al Netw  Lear n Syst . 2014; 26(2): 2 08- 223.   [17]  Z heng  H, Ye  Q, Jin Z .  A Novel Multi p l e  Ke rnel  S parse  Re prese n tatio n  b a sed  Class ifica t ion for F a ce   Reco gniti on.  K s ii T r ansacti on s on Internet & Information Sy stems . 20 14; 8 ( 4): 1463- 14 80 .  [18]  Shrivastav a A,  Pill ai JK,  Pat e l VM. Mu ltipl e  ke r nel- base d  dictio nar y  le ar nin g  for  w e ak l y  s u p e rvise d   classification.  Pattern  Reco g n itio n . 201 5; 48: 2667- 26 75.   [19]  Liu K H , L i n  YY, Che n  CS . Lin ear S pec tral  Mi xture  A nal ysis  vi a M u ltipl e -Ker nel   Lear nin g  for   H y pers pectral  Image  C l ass i fi cation.  IEEE T r ansactions  on Geo science  & Rem o t e  Sensing . 20 15;  53(4): 22 54- 22 69.   [20]  Luo  J, Orab on a F ,  F o rno n i  M, et al.  OM-2 : An Onl i ne  M u lti-class  Multi- kerne l  L ear nin g  Al gorith m .  Procee din g  of CVPR 20 10. 2 010: 43- 50.   [21]  Orabon a F ,  L uo J, C a p u to  B. Multi K e r nel  Le arni ng  w i t h  o n li ne- bat ch o p timizati o n .  Jour nal  of  Machi ne Le arn i ng R e searc h . 201 2; 13(1): 22 7-25 3.  [22]  Jin R,  Ho i SC H, Yan g  T .  Online  Mu ltipl e   K e rne l  L ear nin g : Alg o rithms  an d Mistak e Bo u nds.  Le ctu r e  Notes in C o mp uter Scienc e . 2 010; 63 31( 4): 390-4 04.   [23]  Z hang  W ,  Guo  Z ,  Z hang  L,  et al. A d a p tive  Co ntrol f o r R obotic  Man i p u l a tors b a se  on   RBF  Ne ura l   Net w ork.  TEL K OMNIKA Teleco mmu n icati o n Co mp utin g  Electron ics an d Co ntrol . 20 1 3 ; 8(3): 49 7- 502.   [24] Pan LJ, Ji n  W ,  W u  J. A Novel I n trusi on D e tectio n Appro a ch  usin g Multi-K e rne l  F unctions.   T E LKOMNIKA T e leco mmunic a tion C o mputi n g Electron ics a nd Co ntrol . 20 14; 12(4): 1 088 -109 5.   Evaluation Warning : The document was created with Spire.PDF for Python.