TELKOM
NIKA
, Vol. 11, No. 4, April 2013, pp. 2050
~20
5
7
ISSN: 2302-4
046
2050
Re
cei
v
ed
Jan
uary 6, 2013;
Re
vised Feb
r
uar
y 22, 201
3
;
Accepte
d
March 4, 2013
The K-Medoids Clustering Algorithm with Membrane
Computing
Yuz
h
en Zhao*
1
, Xi
y
u
Liu
2
, Hua Zhang
3
1,2
School of Manag
ement Sci
e
nce an
d Eng
i
n
eeri
ng,
Sha
ndo
ng Norm
al Un
i
v
ersit
y
, Jin
an,
Chin
a
3
Yello
w
R
i
ver
Roa
d
Bridg
e
E
ngi
neer
in
g Co
mpan
y, Jin
an, Chin
a
*Corres
p
o
ndi
n
g
author, e-ma
i
l
: zhao
yuz
h
e
n
_
hap
p
y
@1
26.co
m
A
b
st
r
a
ct
The K-
m
e
doids clustering
algorithm
is r
eali
z
ed
by a
P system
in this paper. Because th
e
me
mbra
ne
sys
tem has gre
a
t para
lle
lis
m and
low
e
r
co
mput
atio
n
a
l ti
me co
mp
lexity, it
is s
u
itab
le for
solv
i
n
g
combi
natori
a
l
prob
le
ms lik
e the cluster
i
n
g
p
r
obl
em. A
P sy
stem w
i
th all t
he rul
e
s to sol
v
e the K-med
o
i
ds
algorithm
was constructed. The spec
ific P system
is ass
o
ciated with
the dissim
i
larity
m
a
trix between n
obj
ects. T
h
is s
ystem c
an
get
one
poss
i
bl
e
classificati
ons in
a no
n-det
ermi
nistic
w
a
y. T
h
roug
h
ex
a
m
ple
test, it is appro
p
riate for clust
e
r ana
lysis. Thi
s
is a
new
attempt i
n
ap
plic
ati
ons of me
mbr
a
ne syste
m
an
d
it
provi
des new
i
deas a
nd
meth
ods for cluster
ana
lysis.
Ke
y
w
ords
: Cl
usterin
g
alg
o
rit
h
m, the K-
me
d
o
ids cl
usterin
g
, Membr
a
n
e
co
mp
utin
g, P System
Copy
right
©
2013 Un
ive
r
sita
s Ah
mad
Dah
l
an
. All rig
h
t
s r
ese
rved
.
1. Introduc
tion
Clu
s
terin
g
is a very important probl
em
in
machine
learni
ng, stat
istics, biolog
y, data
mining an
d m
any other ma
ny fields. Through the p
r
o
c
e
ss of
clust
e
ring, data
set are pa
rtitioned
into clu
s
ters with intra-cl
uster d
a
ta si
milar
an
d inter-clu
s
ter d
a
ta dissimil
a
r.
From anoth
e
r
perspe
c
tive, the
clust
e
rin
g
probl
em i
s
a
c
tually a
comb
ination p
r
o
b
le
m of data,
wh
ich i
s
to fin
d
a
prog
ram that
meets the ab
ove con
d
ition
s
from all co
mbination
s
[1
].
Many fields l
i
ke combin
atorial proble
m
, fi
nite state
probl
em
s an
d grap
h theo
ry have
applie
d me
mbra
ne
com
puting. Fo
r
many comb
i
natorial
prob
lems memb
rane com
puti
ng
approa
che
s
are
very suit
able used on
acco
unt
of
the va
st pa
ral
l
elism. T
he ti
me
compl
e
xity
parall
e
lism
of
the
com
puting
will b
e
le
ssen
ed
so
it can me
et the
requi
re
m
ent of
improving the
pro
c
e
ssi
ng speed of the bi
g data [2, 3].
The k-med
o
i
d
s alg
o
rithm
is one of the
partiti
oning
algorith
m
s fo
r spatial d
a
ta
. It is th
e
combi
nato
r
ial
proble
m
so it
can be
solve
d
with memb
rane computin
g [4].
This p
ape
r
combine
s
the
s
e two a
bove t
o
solve th
e p
r
oble
m
of cl
u
s
terin
g
n o
b
je
cts to
k
clu
s
ters. It uses the sub
s
cript i of point
i
a
to rep
r
e
s
ent the i-th obj
ect
of the origin
al
object
s
and i
t
use
s
the
dissimilarity of an
y two ori
g
inal
obje
c
ts to
d
e
fine the di
st
ance of corre
s
po
ndin
g
poi
nts
a. Differe
nt cl
usters
are
re
pre
s
ente
d
by
different
m
e
mbra
ne
s. First, it rand
oml
y
assi
gn
s
ce
nter
points of the
k clu
s
ters, an
d the remaini
ng point
s entry into memb
rane
s with th
e nearest ce
nter
point. Secon
d
, it re-spe
cifi
es the
ce
nter point
of e
a
ch memb
ran
e
makin
g
the
summation
of the
dissimila
rity betwee
n
the center poi
nt and all
other
points in the membrane th
e sho
r
test. And
then it
redi
stri
butes the
re
mainin
g
poi
nts, an
d
so
on,
until all th
e
center point
s
n
o
lon
ger chan
ge.
In this
way, it gains
the c
l
us
ters
. Finally, it
puts the
inform
ation
out in th
e form of cha
r
a
c
ter
string
s into th
e output mem
b
ran
e
. This
strategy
is a ne
w appli
c
ation
of membra
ne
computin
g.
2. The K-M
e
doids Algori
t
hm
The K-me
doi
ds alg
o
rithm
whi
c
h is mo
re robu
st to o
u
tliers a
nd n
o
ise i
s
a one
of the
cla
ssi
cal p
a
rti
t
ioning algo
rit
h
m of clu
s
te
ri
ng improved
by the K-mea
n
s alg
o
rithm [
5
].
The data
set
12
{
,
,
...,
}
n
X
xx
x
with n obje
c
ts can be
cl
usters into
k clu
s
ters by it.
A
medoid
is o
ne o
b
je
ct of
a
clu
s
ter
wi
th the mini
m
a
l total di
sta
n
ce
to all
ot
her
obje
c
ts.
By
distrib
u
ting
al
l non
-med
oid
obje
c
ts to t
he n
earest
medoid
the
clusters
12
{
,
,...,
}
k
CC
C
C
are
gene
rated. T
hey have the followin
g
thre
e prop
ertie
s
:
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
The K-Me
doi
ds Cl
uste
ring
Algorithm
with Mem
b
rane
Com
puting (Y
uzh
en Zha
o
)
2051
1)
i
C
1
ik
;
2)
1
k
ii
CX
;
3)
,,
1
,
ij
CC
i
j
i
j
k
.
What’
s
mo
re,
obje
c
ts in th
e sam
e
cl
ust
e
r a
r
e
simila
r to each oth
e
r an
d obj
ect
s
from
distin
ct clu
s
te
rs a
r
e differe
nt from each
other.
The di
stan
ce nee
ds to be defined in orde
r to find
the sol
u
tion.
In the literatu
r
e vari
ou
s alt
e
rnativ
e
s
h
a
ve bee
n repo
rted to ap
pro
a
c
h thi
s
ta
sk.
It
can
cho
o
se o
ne acco
rdin
g to the reque
st
.
This p
ape
r u
s
es the
dissimi
l
arity to defin
e it. Fi
rst of al
l, it defines th
e dissimila
rity matrix
'
nn
D
betwee
n
any
two obje
c
ts a
s
follows:
11
1
2
1
21
22
2
12
''
.
.
'
''
.
.
'
'
...
''
.
.
'
n
n
nn
nn
n
n
ww
w
ww
w
D
ww
w
(1)
Whe
r
e,
'
ij
w
is the dissimilarity between the i-th
obje
c
t a
nd the j-th o
b
j
ect [6] . Specific
cal
c
ulatio
n method is
sele
cted depe
ndin
g
on the type of object.
Then, it
cha
nge
s the
ma
trix element
s
'
ij
w
into integer
ij
w
by rou
ndin
g
for mem
b
ran
e
comp
uting. By this, it gains the new matrix
nn
D
as
follows
[7]:
11
12
1
21
22
2
12
..
..
...
..
n
n
nn
nn
n
n
ww
w
ww
w
D
ww
w
(2)
The K-m
edoi
d algo
rithm
has
som
e
specifi
c
meth
ods. Partitio
ning a
r
ou
nd
medoid
s
(PAM) is a re
pre
s
entative
one.
The ste
p
s of the PAM are a
s
follows:
1
)
Se
le
c
t
k
o
b
j
ec
ts
as
me
do
id
s arbitra
r
ily from all the ob
je
cts as the initial k clusters.
2)
Distri
bute th
e remai
n
ing
object
s
to thei
r mo
st
si
milar cl
ust
e
r
wit
h
t
he sh
ort
e
st
distan
ce.
3)
Ran
domly sel
e
ct non
-me
d
o
i
d obje
c
t
O
.
4)
Comp
ute the distan
ce of
O
and all the oth
e
r obje
c
ts.
5) Set
O
as the ne
w medoi
d if the total dista
n
ce i
s
de
cre
a
s
ed.
6)
Rep
eat the st
eps 2 to 5 ab
ove until all medoid
s
do
n’t cha
nge a
n
ymore [8].
So given
arb
i
trary n
obj
e
c
ts, it
ca
n
cl
uster
them
i
n
to k
cluste
rs by
computi
ng thei
r
dissimilarity matrix
nn
D
and u
s
i
ng the K-med
i
ods al
gorith
m
to cluste
r.
3. The K-M
e
doids Clus
te
ring Algorith
m
w
i
th Mem
b
rane
Comp
uting
3.1. The P Sy
stem for the K-med
o
ids
Cluste
ring Metho
d
In this se
ctio
n, a P system for the K-medi
od
s alg
o
r
ithm is prop
ose
d
. Its stru
cture i
s
depi
cted in Fi
gure 1.
Figure 1. The
P System for the K-Medoi
ds Cl
uste
ring
Method
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NIKA
Vol. 11, No. 4, April 2013 : 2050 – 2
057
2052
It use
the
su
bscript
i of th
e poi
nts
i
a
to re
pre
s
ent
the i
-
th obje
c
t
of the o
r
igin
al
o
b
ject
s
and use
the
matrix
nn
D
to com
pare
the
simil
a
rity between
the
n
obj
ect
s
. The
sp
ecifi
c
algo
rithm i
s
followed:
Firs
t, it s
e
t the maximum data in the matrix
nn
D
Max, the
minimum dat
a in the matrix
nn
D
Min and set the ab
solute v
a
lue of these two Abs for
convenie
n
ce.
The P system
for clu
s
terin
g
is defined a
s
follows:
01
0
1
(
,
,
,
,...,
,
,
,
,...,
,
,
)
kn
k
n
O
M
M
MMR
R
R
R
(3)
Whe
r
e:
1)
O
=
{
,
,
.
..,
,
,
}
12
1
0
1
,,
n
aa
a
s
e
.
O
repre
s
e
n
ts the coll
ectio
n
of object
s
in the P system.
2)
=
[
[
]
[
]
[]
[]
]
01
1
2
2
0
...
kk
n
n
.
rep
r
e
s
ent
s the memb
ran
e
st
ru
cture of the P system.
3)
，
01
1
1
2
1
2
0
1
{
,
,
,...,
,
}
,
...
{
,
}
,
k
nk
n
Ma
a
a
e
M
M
M
s
M
. M re
presents th
e
colle
ction
of
initial obj
ect
s
in e
a
ch m
e
mbra
ne.is th
e outp
u
t me
mbra
ne
of th
is P
sy
st
em.
The rul
e
s in
0
R
[9,10]:
1i
1
{1
,
1
}
t
tt
i
t
i
i
n
t
ra
A
A
i
n
t
k
12
12
12
12
12
1
21
2
1
2
1
2
1
2
i1
k
12
1
2
1
2
1
{
A
A
.
.
.
A
A
A
.
..A
U
U
...U
|
1
i,j
,
,...,
n}
{
(
)
|
1
i
1
}
{
A
A
.
.
.
A
U
U
...U
|
1
j
,
,...,
n}
{
(
A
ij
ij
ij
k
kk
i
nj
nj
nj
k
k
ww
w
k
ii
j
j
k
j
i
j
j
k
j
i
i
i
k
k
kk
ia
ww
w
nn
j
j
k
j
n
n
n
n
k
k
k
nj
ra
a
j
j
n
aa
j
j
2
21
2
A
...A
)
|
1
j
,
,
.
..,
n
}
kn
jk
j
a
k
jj
12
12
31
2
1
12
{
U
U
...U
|
0
,
1
,
1
}
{
U
U
...U
|
0
,
1
}
k
j
k
j
tt
t
k
ii
i
i
k
i
i
n
i
j
tt
t
nn
n
n
k
i
i
n
j
r
a
a
t
in
jk
aa
t
j
k
12
1
2
11
1
41
2
1
2
{
U
U
...U
U
U
...U
|
1
,
1
,
1
}
kk
jj
j
j
j
j
ii
i
k
i
i
i
k
s
ri
n
j
M
a
x
s
k
(
12
12
5
{
(
(
)
()
.
.
.
()
|
1
,
0
)
}
{
(
)()
.
.
.
()
)
}
k
k
ij
in
in
in
k
in
in
in
re
i
n
k
*
6
={
(
)
w
A
{a
|
1
}
}
n
in
jt
p
rw
w
p
n
The rul
e
s in
i
(1
)
Ri
k
:
*
*
+1
'={(
)
|
1
i
n
,
w
A
{a
|
1
}
}
'={
(
,
)
w
A
{a
|
1
}
}
i
ii
a
j
t
p
nj
t
p
rw
w
a
p
n
r
w
w
out
p
n
+2
1
'={(
)
(
,
,
,
)
#
|
1
,
,1
}
i
nj
h
a
j
h
j
h
r
A
A
A
out
i
h
n
j
k
+3
+
1
'{
|
1
}
{
(
|
1
}
i
ni
i
i
i
i
i
a
ra
O
i
n
i
n
)
+4
'{
|
1
,
,
,
1
,
|
|
}
ij
p
j
nt
i
j
h
p
j
i
t
w
w
h
p
r
s
Oa
A
b
Os
A
i
j
p
n
h
k
t
n
A
b
s
+5
0
0
r'
{
|
0
,
1
,
1
,
}
{}
|
0
,
1
,
1
,
}
ni
j
p
h
j
h
p
ij
p
h
j
p
h
s
A
O
s
A
a
nAbs
i
j
k
p
h
n
sA
O
s
A
a
i
n
A
b
s
j
k
p
h
n
+6
'{
|
1
}
ni
i
rb
a
i
n
+7
1
'{
|
1
}
ni
i
ri
n
，
+8
+9
r'
{
(
,
)
|
1
0
}
{
(
(
,
)
)
|
1
,
}
'{
(
,
)
|
1
}
j
ij
i
n
ni
i
e
o
u
t
i
n
jn
o
u
t
i
jn
ra
a
o
u
t
i
n
1
+1
0
1
1
1
11
'{
(
,
)
#
|
1
,
1
}
{(
)
(
,
)
#
|
1
,
1
}
n
n
n
jp
jp
jp
jp
jp
jp
rA
A
o
u
t
A
j
k
p
n
AA
o
u
t
A
j
k
p
n
{
|
1
<
6}
{
'
'
|
1
<
n+
10}
ij
i
j
r
r
ij
r
r
ij
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
The K-Me
doi
ds Cl
uste
ring
Algorithm
with Mem
b
rane
Com
puting (Y
uzh
en Zha
o
)
2053
3.2. An Ov
er
v
i
e
w
of Computa
t
ions
The rule
1
r
is
execute
d
firstly
according
to t
he p
r
io
rity rel
a
tionship. It choo
se
s o
ne f
r
om all
the points
i
a
arbitrarily an
d put the point into membran
e
1 whi
c
h re
p
r
esents the fi
rst clu
s
te
r. At
the same tim
e
, it converts the chosen l
o
we
rcase letter
i
a
into co
rrespondi
ng ca
pital letter
ti
A
to
avoid putting
it into the o
t
her mem
b
ra
nes
and to
disting
u
ishing
the ce
nter
point an
d ot
her
comm
on d
a
ta point. T
he
sub
s
cript
s
of
ti
A
sh
ow
that
the ce
nter p
o
int of cl
uste
r t is th
e i-th
obje
c
t. Obje
ct
t
is used to
control the ti
me of execut
ion of rul
e
s
and the
se
ri
al numb
e
r of
membrane
w
h
ich it put the cente
r
poin
t
into. Accord
ing role
1
r
, it successfully ch
oose k cent
e
r
points a
r
bitra
r
ily from
all
the n
u
mb
ers
and
put th
em
into m
e
mb
ra
nes lab
e
led
from
1 to
k
w
h
ich
r
e
pr
es
e
n
t
th
e k
c
l
us
te
rs
.
Then it execu
t
es the rule
2
r
.Beginni
ng with
point
1
a
, the object
s
t
ij
U
are g
e
nerate
d
. The
corne
r
marks i, j and t show that the value of dissimil
arity betwee
n
point
i
a
and th
e cente
r
point
of clu
s
te
r j i
s
t. Then l
e
t all
the supe
rscri
p
t de
crea
se
a
t
the
same
time u
n
til on
e
of them i
s
0.T
h
is
mean poi
nt
1
a
is
the most simil
a
r to cente
r
p
o
int of
the correspon
ding
cl
uster.
Next it
puts poi
nt
1
a
into the co
rrespon
ding
membrane
while
1
increa
se
s, maki
ng it
begin to
cal
c
ulate th
e
dissimila
rity betwee
n
point
2
a
and all ce
nter points. If the
point
i
a
does not exist, meaning that
this poi
nt ha
s been
cho
s
e
n
to be
a
cen
t
er poi
nt, then
i
ad
d 1
dire
ctly and
goe
s into the n
e
xt
cycle. An
d so
on until
n
a
. If
n
a
e
x
ists, it gene
rates the
dissi
m
ilarity betw
een it an
d ea
ch
cente
r
point. Then l
e
t the A obj
ects i
n
0 me
mbra
ne di
sa
ppea
r an
d th
e su
perscript
of object
s
t
ij
U
decrea
s
e
at t
he
sam
e
tim
e
until
one
o
f
them i
s
0.
Next it p
u
t p
o
int
n
a
into the
correspon
ding
membrane. Obje
cts
t
ij
U
disa
ppea
r. If point
n
a
has b
een
sele
cted a
s
a cente
r
poin
t, it cannot
prod
uce the
obje
c
ts
t
ij
U
and t
he a
u
xiliary
point
n
and
A disapp
ear.
All points ent
er into
the
corre
s
p
ondin
g
mem
b
rane
at thi
s
time.
Clu
s
te
rs hav
e be
en
co
mp
leted the
first step:
it give
s
k
cente
r
poi
nts arbitra
r
ily, and divide
s
the remai
n
in
g points i
n
to k cl
uste
rs base
d
on t
he
dissimila
rity betwee
n
them
and the
ce
nt
er p
o
ints. At this time, the
r
e is
no p
o
int
i
a
in membr
a
ne
0. Beca
use t
here
is an
ob
ject e i
n
me
m
b
ran
e
0, it g
e
nerate
s
obje
c
t
into mem
b
rane
s lab
e
led
from 1 to
k b
y
rule
5
r
. Then rules i
n
mem
b
rane
s la
bele
d
from 1 to
k a
r
e trig
gered.
Rule
5
r
makes
the red
e
termi
nation of ce
n
t
er point
s go
es after all th
e points
i
a
are
divided into
k clu
s
te
rs. If
there a
r
e k
obje
c
ts
in membra
ne 0, this mean that
the center p
o
ints of the k memb
ran
e
s
labele
d
from
1 to k are n
o
t cha
nge
d.
Then, it exe
c
utes
rule
s i
n
membrane
s l
abele
d
from
1 to
k. If there is no
point
except th
e
cente
r
point i
n
on
e m
e
mb
rane, it u
s
e
s
the o
b
je
ct #
to sto
p
the
p
r
oce
s
s a
nd
pu
t an o
b
je
ct
to
sho
w
it. Othe
rwi
s
e it be
gin
s
to find the
best
cente
r
p
o
ints. It start
s
with
1
a
. If
the point doe
s not
exist,
1
add
s 1
and go
es i
n
to the next cycle directly. If the point exists, it is set
as the n
e
w
cente
r
p
o
int.
Then
cal
c
ul
ate the diffe
re
nce
betw
een
the di
ssi
mila
rity betwe
en
the ne
w
cent
er
point an
d the
rem
a
ining
p
o
int and
the
dissimila
rity betwe
en the
origin
al
cente
r
poi
nt an
d the
remai
n
ing
poi
nt and
ad
d th
e data
to the
sub
s
cript
of o
b
ject S. T
h
e
lowe
rcase
j
a
is repla
c
e
s
by
j
b
after the calculation to av
oid re
peating
calculation. I
f
the sub
s
cri
p
t of S is less than 0
after
cal
c
ulatin
g the di
ssimil
a
rity with all remai
n
ing
p
o
ints, the p
o
int
1
a
can reduce the total
con
s
um
ption.
So it is
set
as the
ne
w
center
point a
nd p
r
od
uce a
n
obje
c
t
to inform the new
cente
r
poi
nt
has
bee
n ge
nerate
d
. If the su
bscript o
f
S is greater than o
r
eq
u
a
l to 0, the n
e
w
cente
r
poi
nt can’t red
u
ce the total co
nsumption. Th
e
r
efore it main
tains the o
r
igi
nal ce
nter p
o
i
n
t,
rena
me obje
c
t
h
O
to
h
a
and
produ
ce
an
obje
c
t
to sho
w
it. T
h
e obj
ect
1
i
is
produ
ced
to
go
to
the next cy
cle
to com
p
a
r
e t
he obj
ect
2
a
and the
ce
nter poi
nt
and so on until
all
the o
b
ject
s
i
a
are
comp
ared. If
there i
s
any
in this mem
b
rane, it p
u
t an
obje
c
t e
out t
o
inform that
the data
nee
d
to be
re
cla
ssi
fied out
of th
e mem
b
ra
ne.
And p
u
t an
obje
c
t
out to i
n
form th
at th
e center poi
nt
this is memb
rane is not ch
ange
d. Then
i
a
are put out .
Last it resto
r
e
s
obje
c
ts in this memb
ra
n
e
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NIKA
Vol. 11, No. 4, April 2013 : 2050 – 2
057
2054
to initial
state
and
put th
e
informatio
n o
f
the cente
r
point o
u
t. It use
s
th
e o
b
j
e
ct
#
to stop the
comp
utation step
sendi
ng an
obje
c
t
1
out to show it.
Whe
n
re
sp
on
se
s in me
mb
rane
s la
bele
d
from 1 to
k are
com
p
let
ed, the mem
b
ran
e
0
inclu
d
e
s
trigg
e
ring
rul
e
an
d then the
proce
s
s of cl
ustering a
r
e
rep
eated u
n
til no
e in mem
b
ra
ne
0 showi
ng th
at ce
nter
poi
nts in
all
k
membrane
s
don’t chan
ge
and th
e
clu
s
tering
adju
s
t
m
ent
pro
c
e
s
s e
nd.
Then
mem
b
rane
s la
bele
d
from 1
to
k a
c
cept
an
obje
c
t
to exe
c
ute t
he
rule
s f
r
om
1
'
r
to
1
'
n
r
to output the re
sult of the cl
uste
r. Th
e re
sult
is in t
he form of
string. Finally, p
u
t these
string
s forme
d
above to the output mem
b
ran
e
n. One
comp
utation
pro
c
e
ss i
s
over.
3.3. Test and
Analy
s
is
To illustrate how the m
e
mbra
ne sy
stem sh
own in
Fig.1 run sp
ecifically, the following
simple
exam
ple is
con
s
id
e
r
ed: cl
uste
r 7
integral
point
s (1,3
), (1,4
),
(2,1),
(2,4),
(
3
,2), (4,1
), (4,
3
)
sho
w
n in Fi
g
u
re 2 into t
w
o
cla
sse
s. W
h
en ch
angi
ng t
he ce
nter p
o
i
n
t of each
clu
s
ter. Obvio
u
sly,
n=7, k=2.
Figure 2. The
7 Points Wai
t
ing for being
Clu
s
tere
d
First of all, it define
s
the di
ssimil
a
rity ma
trix
77
'
D
. In this example, it use
s
the squa
re
of
distan
ce
bet
wee
n
a
n
y tw
o poi
nts
as t
he di
ssimila
ri
ty. Because t
he p
o
ints are
integral p
o
in
ts,
matr
ix
77
D
is the same to matrix
77
'
D
:
77
77
01
5
2
5
1
3
9
1
0
10
1
8
18
1
0
51
0
0
9
2
4
8
'2
1
9
0
5
1
3
5
58
2
5
0
2
2
13
18
4
1
3
2
0
4
91
0
8
5
2
4
0
DD
(4)
The memb
ra
ne system cl
usteri
ng the
s
e sev
en num
bers into two
classe
s is show
n in
Figure 3:
2
11
1
2
7
,,
,
.
.
.
,
,
aa
a
e
，
01
,
s
01
,
s
Figure 3. The
P System Clusteri
ng Seve
n Numb
ers in
to Two Clu
s
te
rs
0
0.
5
1
1.
5
2
2.
5
3
3.
5
4
4.
5
5
0
0.
5
1
1.
5
2
2.
5
3
3.
5
4
4.
5
5
x
y
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
The K-Me
doi
ds Cl
uste
ring
Algorithm
with Mem
b
rane
Com
puting (Y
uzh
en Zha
o
)
2055
Steps of on
e
circulatio
n of
the clu
s
teri
n
g
are li
sted i
n
Table
1. Beca
use the
steps a
r
e
almost the
sa
me, only part
s
of them are
listed he
re.
Table 1. Step
s of the First
Circulatio
n of the Clu
s
terin
g
2
11
1
2
7
01
01
2
12
1
1
2
7
1
0
1
1
1
0
1
2
1
3
11
22
3
7
1
0
1
1
1
0
1
2
2
2
23
1
1
2
2
3
7
2
0
1
1
1
0
1
2
2
01
0
,
,
,
..
.,
,
,
,
1
,
,
,
.
..,
,
(
)
,
,
,
2
,
,
,
,.
..
,
,
(
)
,
,
,
,
3
,
,
,
,.
..
2
,
,
(
)
,,
,,
4
m
e
mb
r
a
n
e
me
mb
r
a
n
e
me
mb
r
a
n
e
aa
a
e
s
s
Aa
a
e
r
s
t
As
A
A
a
a
e
r
sA
sA
AA
a
a
e
r
s
A
s
A
，
，
，
，
2
3
3
11
22
3
7
2
0
1
1
1
0
1
2
2
51
0
3
1
1
2
2
3
7
3
1
3
2
2
01
1
1
01
2
2
49
31
1
2
2
3
7
3
1
3
2
4
0
1
1
1
0
1
2
2
05
31
1
2
2
3
7
3
1
3
2
4
,
,
,
,
..
.,
,
(
)
,
,
,
,
5
,
,
,
..
.,
,
,
U
,
U
(
)
,
,
,
,
6
,
,
,
..
.,
,
,
U
,
U
(
)
,
,
,
,
..
.
1
0
,
,
,.
..
,
,
,
U
,U
(
)
AA
a
a
e
r
s
A
s
A
A
A
a
a
e
r
sA
sA
AA
a
a
e
r
s
A
s
A
AA
a
a
e
r
，
，
，
，
01
1
1
0
1
2
2
2
4
3
11
22
4
7
3
0
1
1
1
3
0
1
22
33
0
1
1
1
35
67
0
1
2
2
4
35
0
1
1
1
35
67
0
1
2
2
4
30
2
1
1
3
5
6
7
1
0
0
2
,,
,
,
1
1
,
,
,
,
..
.,
,
(
)
,
,
,
,
,
..
.
4
7
(
)
,,
,
,
,
,
,,
,
48
(
)
,
,
,
,
,
,
,
,
,
,
,
49
,
,
,
,
,
,
,
(
'
)
,
sA
sA
AA
a
a
e
r
s
A
a
s
A
e
r
s
A
aaa
a
s
A
a
r
s
A
aaa
a
s
A
a
s
A
aaa
a
r
s
，
，
22
4
1
0
3
0
3
1
1
3
56
7
1
0
0
2
2
24
1
0
3
0
1
1
35
67
3
1
0
0
4
2
2
4
1
0
3
3
1
1
35
67
3
1
1
0
2
2
4
1
0
3
1
2
1
1
356
7
,,
,
(
'
)
5
0
,,
,
,
,
,
,
(
'
)
,,
,
,
(
'
)
51
,
,
,
,
,
,
,
(
'
)
,
,
,
,
(
'
)
5
2
,
,
,
,
,
,
,
(
')
,
,
,
(
')
5
3
,
,
,,,
,
,
Aa
r
s
A
aaa
a
r
s
A
a
r
sA
O
a
a
a
r
s
A
a
r
sA
O
b
a
a
r
s
A
O
r
sA
O
b
b
a
31
1
0
2
2
4
1
2
3
1
3
1
1
3
56
7
3
1
1
0
2
24
1
5
34
0
1
3
1
5
6
7
3
1
2
0
2
2
1
6
34
1
2
2
0
1
3
1
5
6
7
3
1
3
0
2
2
1
1
7
3
('
)
,
,
,
,
(
'
)
54
,
,
,
,
,
,
,
,
(
'
)
,
,
,
(
'
)
55
,
,
,
,
,
,
,
,
,
,
(
'
)
,
,
(
'
)
56
,
,
,
,
,
,
,
,
,
,
,
,
(
'
)
,
,
(
'
)
57
rs
A
a
r
s
A
O
bbb
r
s
A
a
r
as
A
a
b
b
b
r
s
A
r
aA
s
A
a
a
b
b
r
s
A
r
4
1
22
0
1
3
1
5
6
7
3
13
0
2
2
1
,,
,
,
,
,
,
,
,
,
,
,
(
'
)
,
,
aA
s
A
a
a
a
b
r
s
A
3
4
1
2
2
0
13
1
5
6
7
3
1
3
0
22
1
3
4
1
2
2
0
13
1
5
6
7
4
1
4
0
22
1
3
4
1
2
2
0
13
1
5
6
7
5
1
0
0
22
1
3
01
58
,
,
,
,
,
,
,
,
,
,
,
,
(
'
)
,
,
59
,
,
,
,
,
,
,
,
,
,
,
,
(
'
)
,
,
60
,
,
,
,
,
,
,
,
,
,
,
,
(
'
)
,
2
,
61
m
e
mb
r
a
n
e
me
mb
r
a
n
e
me
mb
r
a
n
e
aA
s
A
a
a
a
a
r
s
A
aA
s
A
a
a
a
a
r
s
A
aA
s
A
a
a
a
a
r
s
A
t
41
2
2
0
1
3
1
5
6
7
5
1
0
0
2
2
1
3
4
1
2
2
0
13
1
5
6
7
5
1
1
0
22
1
3
4
1
2
2
2
1
3
1
567
5
1
1
0
2
2
1
34
1
2
2
8
1
3
1
5
6
7
,,
,
,
,
,
,
,
,
,
,
,
(
'
)
,
,
62
,
,
,
,
,
,
,
,
,
,
,
,
(
'
)
,
,
63
,
,
,
,
,
,
,
,
,
,
,
,
(
'
)
,
,
64
,
,
,
,
,
,
,
,
,
aA
s
A
a
O
a
a
r
s
A
aA
s
A
b
O
a
a
r
s
A
aA
s
A
b
O
b
a
r
s
A
aA
s
A
b
O
b
b
51
1
0
2
2
1
2
3
4
1
2
2
0
15
1
3
6
7
5
1
2
0
22
1
2
3
4
1
2
2
0
1
5
1
367
5
1
3
0
2
2
1
2
3
4
1
2
2
0
15
1
3
6
7
5
1
3
0
22
1
3
,,
,
(
'
)
,
,
65
,
,
,
,
,
,
,
,
,
,
,
,
(
'
)
,
,
66
,
,
,
,
,
,
,
,
,
,
,
,
(
'
)
,
,
67
,
,
,
,
,
,
,
,
,
,
,
,
(
'
)
,
,
68
,
,
rs
A
aA
s
A
b
a
b
b
r
s
A
aA
s
A
a
a
b
b
r
s
A
aA
s
A
a
a
a
b
r
s
A
2
4
1
22
0
1
5
1
3
6
7
5
13
0
2
2
1
2
34
1
2
2
0
1
5
1
3
6
7
6
1
4
2
2
1
2
34
1
2
2
0
1
5
1
3
6
7
6
1
0
0
2
2
1
34
1
2
2
8
1
5
1
3
6
7
,,
,
,
,
,
,
,
,
,
(
'
)
,
,
69
,
,
,
,
,
,
,
,
,
,
,
,
(
'
)
,
,
70
,
,
,
,
,
,
,
,
,
,
,
,
(
'
)
,
,
71
,
,
,
,
,
,
,
,
,
,
,
aA
s
A
a
a
a
a
r
s
A
aA
s
A
a
a
a
a
r
s
A
aA
s
A
a
a
O
a
r
s
A
aA
s
A
b
a
O
a
2
61
1
0
2
2
1
2
34
1
2
2
1
0
1
5
1
3
6
7
6
1
1
0
2
2
1
2
34
1
2
2
1
2
1
5
1
3
6
7
6
1
1
0
2
2
1
2
34
1
2
2
0
1
5
1
3
6
7
6
1
2
0
2
2
1
3
,(
'
)
,
,
72
,
,
,
,
,
,
,
,
,
,
,
,
(
'
)
,
,
73
,
,
,
,
,
,
,
,
,
,
,
,
(
'
)
,
,
7
4
,,
,
,
,
,
,
,
,
,
,
,
,(
'
)
,
,
75
,
rs
A
aA
s
A
b
b
O
a
r
s
A
aA
s
A
b
b
O
b
r
s
A
aA
s
A
b
b
a
b
r
s
A
2
4
1
22
0
1
5
1
3
6
7
6
13
0
2
2
1
2
3
4
1
2
2
0
15
1
3
6
7
6
1
3
0
22
1
2
3
4
1
2
2
0
15
1
3
6
7
6
1
3
0
22
1
34
1
2
2
0
1
5
1
3
,,
,
,
,
,
,
,
,
,
,,
(
'
)
,
,
76
,
,
,
,
,
,
,
,
,
,
,
,
,
(
'
)
,
,
7
7
,,
,
,
,
,
,
,
,
,
,
,
,(
'
)
,
,
78
,
,
,
,
,
,
,
aA
s
A
a
b
a
b
r
s
A
aA
s
A
a
a
a
b
r
s
A
aA
s
A
a
a
a
a
r
s
A
aA
s
A
a
a
2
67
7
1
4
0
2
2
1
2
3
4
1
2
2
0
15
1
3
6
7
7
1
0
0
22
1
2
3
4
1
2
2
4
15
1
3
6
7
7
1
1
0
22
1
2
34
1
2
2
6
1
5
1
3
6
7
7
1
1
,,
,
,
,
,
(
'
)
,
,
79
,
,
,
,
,
,
,
,
,
,
,
,
,
(
'
)
,
,
8
0
,,
,
,
,
,
,
,
,
,
,
,
,(
'
)
,
,
8
1
,,
,
,
,
,
,
,
,
,
,
,
,(
'
)
aa
r
s
A
aA
s
A
a
a
a
O
r
s
A
aA
s
A
b
a
a
O
r
s
A
aA
s
A
b
b
a
O
r
s
02
2
1
2
3
4
1
2
2
8
15
1
3
6
7
7
1
1
0
22
1
2
3
4
1
2
2
0
15
1
3
6
7
7
1
2
0
22
1
2
3
4
1
2
2
0
15
1
3
6
7
7
1
3
0
22
1
34
1
2
,,
8
2
,
,
,
,
,
,
,,,
,
,
,
,
(
'
)
,
,
8
3
,
,
,
,
,
,
,,,
,
,
,
,
(
'
)
,
,
8
4
,
,
,
,
,
,
,,,
,
,
,
,
(
'
)
,
,
85
,
,
,
,
A
aA
s
A
b
b
b
O
r
s
A
aA
s
A
b
b
b
a
r
s
A
aA
s
A
a
b
b
a
r
s
A
aA
2
20
1
5
1
3
6
7
7
1
3
0
2
2
1
2
3
4
1
2
2
0
15
1
3
6
7
7
1
3
0
22
1
2
3
4
1
2
2
0
15
1
3
6
7
8
1
4
0
22
1
34
1
2
2
0
1
5
1
3
6
7
,,
,
,
,
,
,
,
,
(
'
)
,
,
86
,
,
,
,
,
,
,
,
,
,
,
,
,
(
'
)
,
,
8
7
,,
,
,
,
,
,
,
,
,
,
,
,(
'
)
,
,
88
,
,
,
,
,
,
,
,
,
,
,
sA
a
a
b
a
r
s
A
aA
s
A
a
a
a
a
r
s
A
aA
s
A
a
a
a
a
r
s
A
ae
A
s
A
a
a
a
a
81
5
0
2
2
1
3
1
4
1
2
2
0
1
53
67
8
1
6
0
2
2
1
3
1
3
4
1
2
2
0
15
6
7
8
1
6
0
22
1
31
3
4
6
1
2
2
0
1
5
7
8
1
6
0
2
2
1
31
3
,(
'
)
,
,
89
,
,
,
,
,
,
,
,
,
,
,
,
(
'
)
,
,
90
,
,
,
,
,
,
,
,
,
,
,
,
(
'
)
,
,
91
,
,
,
,
,
,
,
,
,
,
,
,
(
'
)
,
,
92
,
,
,
,
rs
A
a
a
e
A
sA
a
a
a
r
sA
ea
a
a
A
s
A
a
a
r
s
A
ea
a
a
a
A
s
A
a
r
s
A
ea
a
467
1
2
2
0
1
5
8
1
6
0
2
2
1
2
3
1
3
4
6
7
15
1
2
2
0
15
1
1
7
0
22
1
,,,
,
,
,
,
,
(
'
)
,
,
93
,
,
,
,
,
,
,
,
,
,
,
,
(
'
)
,
,
aa
a
A
s
A
r
s
A
e
a
a
a
aaA
A
s
A
r
s
A
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NIKA
Vol. 11, No. 4, April 2013 : 2050 – 2
057
2056
Figure 4. The
Result of the Cluste
r of these 7 Point
s
In the e
nd, th
ese
7 p
o
ints
are
clu
s
te
red
into tw
o cl
asse
s
sho
w
n i
n
Figu
re 4.
Th
e poi
nts
in the
sam
e
cla
s
ses are
close
r
to
ea
ch
other. S
o
th
e rig
h
t result of this m
e
tho
d
of
clu
s
terin
g
is
gaine
d.
4. Conclusio
n
This
pap
er
construct
s
a
P
system
to realiz
e the K
-
medoid
s
clu
s
tering
algo
rithm. Thi
s
algorith
m
is
suitabl
e for
cluster
analy
s
i
s
by ex
ampl
e test, but it need
s to be
further
studi
ed
wheth
e
r it is
suitabl
e for cl
uster
analysi
s
of la
rg
e am
ount of data. Speakin
g fro
m
a theoreti
c
al
point of vie
w
, the P sy
ste
m
ha
s g
r
e
a
t paralleli
sm.
So it ca
n
re
duce the
time complexity of
comp
uting a
n
d
increa
se
s the co
mputati
onal efficie
n
cy. The followi
ng re
se
arch
work
will focu
s on
the theo
retically analyze
of the alg
o
rit
h
m's time
co
mplexity. Additionally, me
mbra
ne
com
puting
is a ne
w biolo
g
ical
comp
uting method. N
o
w its t
heo
ret
i
cal re
se
arch
is mature, but its applicatio
n
is not pa
rticul
arly extensiv
e. A lot of applicatio
ns
will
emerg
e
in variou
s field
s
i
n
the future.
The
appli
c
ation in
cluste
r propo
sed in thi
s
pa
per is
one ex
ample. The
r
e
are many cl
u
s
terin
g
metho
d
and this pa
p
e
r only use t
he k-medoi
d
s
algo
rithm. Membrane
computing
ca
n be applie
d
to
a
variety of other clu
s
te
ring
method
s.
Ackn
o
w
l
e
dg
ments
The autho
rs thank the reviewe
r
s fo
r their su
gge
stio
ns. This p
r
oj
ect wa
s supp
orted by
the Natural Scien
c
e Fo
u
ndation of
Chin
a(No.61
1700
38), N
a
tural Scie
nce Found
atio
n of
Shando
ng Province, Chi
n
a (No.Z
R
20
1
1
FM00
1), Hu
manities a
n
d
Social Scie
nce
s
Proje
c
t
o
f
Ministry of
Education, Chi
na
(No.1
2
YJA63015
2)
, S
o
cial
Scie
nce
Fund
of Sh
a
ndon
g Province,
Chin
a (N
o.11
CGL
J
2
2
), Science-T
e
chno
logy Progr
a
m
of the Higher Edu
c
atio
n Institutions of
Shando
ng P
r
ovince, C
h
i
na (No.
J12
L
N
22
), Scie
n
c
e-Te
chn
o
log
y
Program
of the Hi
gh
er
Educatio
n Institutions of
Shandon
g
Province
,
Chin
a (N
o.J12L
N65
)
, Science-T
e
chno
logy
Program of t
he Hi
ghe
r Ed
ucatio
n Instit
utions
of Sha
ndon
g Provin
ce,
China
(N
o.J12
L
N
22),
and
Re
sea
r
ch Aw
ard F
oun
dati
on for O
u
tsta
nding Yo
ung
Scientist
s
of
Shando
ng P
r
ovince, Chi
n
a
(No.BS20
1
2
D
X041
).
Referen
ces
[1]
Z
hang HY. T
he research o
n
cl
usterin
g
alg
o
rit
h
m base
d
on D
N
A computi
ng.
PhD Thesis
. Ji
nan. De
pt.
Mana
geme
n
t Scienc
e an
d En
gin
eeri
ng, Sha
ndo
ng N
o
rmal
Univ., 201
1.
[2]
Che
n
H Z
.
Applicatio
n Res
ear
ch on Membr
a
ne Com
putin
g.
PhD Thesis
. C
hon
gqi
ng. De
pt. Computer
Scienc
e, Cho
n
gqi
ng Un
iv., 20
11.
[3]
Lia
ng H. Rese
arch on Memb
rane Com
puti
n
g Optimizatio
n
Methods.
PhD
T
hesis
. Hang
zhou. Dept.
Contro
l Scienc
e and En
gi
neer
ing, Z
hej
ian
g
U
n
iv., 2007.
[4]
Cha
ndras
hek
h
a
r AM, Raghuv
eer K. Performance ev
alu
a
tio
n
of data cluste
ring tech
niq
ues
using KD
D
Cup-
99 Intrusi
on detecti
on d
a
ta set.
Internationa
l Journ
a
l
of Informati
on and N
e
tw
ork Security.
2
0
12;
1(4): 294
–3
05.
0
0.
5
1
1.
5
2
2.
5
3
3.
5
4
4.
5
5
0
0.
5
1
1.
5
2
2.
5
3
3.
5
4
4.
5
5
x
y
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
The K-Me
doi
ds Cl
uste
ring
Algorithm
with Mem
b
rane
Com
puting (Y
uzh
en Zha
o
)
2057
[5]
Rema
ni NVJM
, Kurra RR. Efficient K-Me
ans Fuzz
y Cl
uster Rel
i
a
b
il
ity o
n
Ang
l
e O
r
iente
d
Fac
e
Reco
gniti
on.
I
n
ternati
o
n
a
l Jo
urna
l of Infor
m
at
ics an
d C
o
mmu
n
ic
ation T
e
chno
logy.
201
3; 2(1): 18
0
-
187.
[6]
Cardona M, Colom
e
r MA, P
é
rez-Jiménez
MJ.
Hierarc
hic
a
l cl
usteri
ng
with mem
b
ran
e
comp
uting.
Co
mp
uting a
n
d
informatics.
20
08; F
eb(3): 49
7–5
13.
[7]
Z
hang
HY,
Liu
XY. A C
L
IQU
E al
gorithm
us
ing
DNA
com
p
uting
tech
niq
u
e
s b
a
se
d o
n
c
l
ose
d
-circl
e
DNA seq
uenc
e
s
.
Biosystem
s
.
201
1; 105(
1): 73–8
2.
[8]
Han J, K
a
mbr
M.
Data Mi
nin
g
Co
nce
p
ts a
n
d
T
e
ch
niq
ues
.
2nd
ed.
USA:
Elsevi
er Press.
20
12; 3
83-
466.
[9]
Marc GA, Dan
i
el M, Alf
onso
RP, Petr SA
P. S
y
stem
an
d a c
onstructi
ve membr
a
n
e
-
i
nspir
ed
DN
A
alg
o
rithm for solvin
g the Ma
xi
mum Cliq
ue Pr
obl
em.
BioSystem
s.
2
007; 9
0
(
3
): 687–
69
7.
[10]
Hua
ng CY, Do
ng
XJ, Lon
g H
.
Solving S
o
rti
ng Prob
lem b
y
P S
y
stem.
Jo
urna
l of Sha
n
g
hai Ji
aoto
n
g
Univers
i
ty.
200
8; 42(2): 20
6–2
08.
Evaluation Warning : The document was created with Spire.PDF for Python.