# An Improved Apriori Algorithm Based on an Evolution-Communication Tissue-Like P System with Promoters and Inhibitors

Authors: Xiyu Liu; Yuzhen Zhao; Minghe Sun
Journal: Discrete Dynamics in Nature and Society
 (2017)

---

## Abstract

Apriori algorithm, as a typical frequent itemsets mining method, can help researchers and practitioners discover implicit associations from large amounts of data. In this work, a fast Apriori algorithm, called ECTPPI-Apriori, for processing large datasets, is proposed, which is based on an evolution-communication tissue-like P system with promoters and inhibitors. The structure of the ECTPPI-Apriori algorithm is tissue-like and the evolution rules of the algorithm are object rewriting rules. The time complexity of ECTPPI-Apriori is substantially improved from that of the conventional Apriori algorithms. The results give some hints to improve conventional algorithms by using membrane computing models.


---

## Body

## 1. Introduction

Frequent itemsets mining, as a subfield of data mining, aims at discovering itemsets with high frequency from huge amounts of data. Interesting implicit associations between items then can be extracted from these data, which can help researchers and practitioners make informed decisions. One famous example is “beer and diapers” [1]. The supermarket management discovered a significant correlation between the purchases of beer and diapers which had nothing to do with each other ostensibly through frequent itemsets mining. Consequently, they put diapers next to beer. Through this layout adjustment, sales of both beer and diapers increased.The Apriori algorithm is a typical frequent itemsets mining algorithm, which is suitable for the discovery of frequent itemsets in transactional databases [2]. To process large datasets, many parallel improvements have been made to improve the computational efficiency of the Apriori algorithm [3–6]. How to implement the Apriori algorithm in parallel to improve its computational efficiency is still an on-going research topic. Given the extremity of the technology and theory of the silicon-based computing, new non-silicon-based computing devices P systems are used in this study.P systems are new bioinspired computing models of membrane computing, which focus on abstracting computing ideas from the study of biological cells, particularly of cellular membranes [7, 8]. This study uses an evolution-communication tissue-like P system with promoters and inhibitors (ECPI tissue-like P systems) for computation. P systems are powerful distributed and parallel bioinspired computing devices, being able to do what Turing machines can do [9–11], and have been applied to many fields. The applications of P systems are based on two types of membrane algorithms, the coupled membrane algorithm and the direct membrane algorithm. The coupled membrane algorithm combines the traditional algorithm with some structural characters of P systems, such as dividing the whole system into several relatively independent computing units, where the computing units can communicate with each other, the computing units can be dynamically rebuilt, and rules can be executed in parallel [12–16]. The direct membrane algorithm designs the algorithm based on the structure, the objects, and the rules of P systems directly [17–21]. The final goal of membrane computing is to build biocomputers and the direct membrane algorithm can be transplanted to the biocomputers directly, which is more meaningful from this perspective. However, the direct membrane algorithm needs to transform the whole traditional algorithm into P system, which is complex and difficult. Up to date, a few simple studies on the direct membrane algorithm focus on the arithmetic operations, the logic operations, the generation of graphic language, and clustering [17–21].In this study, a novel improved Apriori algorithm based on an ECPI tissue-like P system (ECTPPI-Apriori) is proposed using the parallel mechanism in P systems. The information communication between different computing units in ECTPPI-Apriori is implemented through the exchange of materials between membranes. Specifically, all itemsets are searched in parallel, regulated by a set of promoters and inhibitors. For a database witht fields, t
+
2 cells are used in the algorithm, where 1 cell is used to enter the data in the database into the system, t cells are used to detect the frequent itemsets, and one specific cell, called output cell, is used to store the results. The time complexity of ECTPPI-Apriori is compared with those of other parallel Apriori algorithms to show that the proposed algorithm is time saving.The contributions of this study are twofold. From the viewpoint of data mining, new bioinspired techniques are introduced into frequent itemsets mining to improve the efficiency of the algorithms. P systems are natural distributed parallel computing devices which can improve the time efficiency in computation. Besides the hardware and software implementations, P systems can be implemented by biological methods. The computing resources needed are only several cells, which can decrease the computing resource requirements. From the viewpoint of P systems, the application areas of the new bioinspired devices P systems are extended to frequent itemset mining. The applications based on the direct membrane algorithms are limited. This study provides a new application of P systems in frequent itemsets mining, which expands the application areas of the direct membrane algorithms.The paper is organized as follows. Section2 introduces some preliminaries about the Apriori algorithm and about the ECPI tissue-like P systems. The ECTPPI-Apriori algorithm using the parallel mechanism of the ECPI tissue-like P system is developed in Section 3. In Section 4, one illustrative example is used to show how the proposed algorithm works. Computational experiments using two datasets to show the performance of the proposed algorithm in frequent itemsets mining are reported in Section 5. Conclusions are given in Section 6.


## 2. Preliminaries

In this section, some basic concepts and notions in Apriori algorithm [2] and ECPI tissue-like P system [7] are introduced.


### 2.1. The Apriori Algorithm

The Apriori algorithm is a typical frequent itemsets mining algorithm proposed by Agrawal and Srikant [2], which aims at discovering relationships between items in transactional databases.Definitions
(i)
Item: a field in a transactional database is called an item. If one record contains a certain item “1,” otherwise “0,” is placed in the corresponding field of the record in the transactional database.
(ii)
Itemset:a set of items is called an itemset. For notational convenience, an itemset with n items I
1
,
I
2
,
…, and I
n is represented by {
I
1
,
I
2
,
…
,
I
n
}.
(iii)
h-itemset:a set containing h items is called a h-itemset.
(iv)
Transaction: a record in a transactional database is called a transaction, and each transaction is a nonempty itemset.
(v)
Support count:the number of transactions containing a certain itemset is called the support count of the itemset. Support count is also called the frequency or count of the itemset.
(vi)
Frequent itemset:if the support count of an itemset is equal to or larger than the given minimum support count threshold k, this itemset is called a frequent itemset.The general procedure of Apriori from Han et al. [1] is as follows.Input. The database contains D transactions and the support count threshold k.Step 1.
Scan the database to compute the support count of each item, and obtain the frequent 1-itemsetsL
1. Let h
=
2.Step 2.
Obtain the candidate frequenth-itemsets C
h by joining two frequent (h
-
1)-itemsets with only one item different.Step 3.
Prune those itemsets which have infrequent subset of length (h
-
1) from the candidate frequent h-itemsets.Step 4.
Scan the database to compute the support count of each candidate frequenth-itemset. Delete those itemsets which do not meet the support count threshold k and obtain the frequent h-itemsets L
h.Step 5.
Leth
=
h
+
1. Repeat Steps 2 to 4 until no itemset meets the support count threshold k.Output. The collection of all frequent itemsets is represented by L.


### 2.2. Evolution-Communication Tissue-Like P Systems with Promoters and Inhibitors

Membrane computing is a new branch of natural computing, which abstracts computing ideas from the construct and the functions of cells or tissues. In the nature, each organelle membrane or cell membrane works as a relatively independent computing unit. The amount and the types of materials in each organelle or cell change through chemical reactions. Materials can flow between different organelle or cell membranes to transport information. Reactions in different organelles or cells take place in parallel, while reactions in the same organelle or cell take place also in parallel. These biological processes are abstracted as the computing processes of membrane computing. The internal parallel feature makes membrane computing a powerful computing method which has been proven to be equivalent to Turing machines [7–11].The ECPI tissue-like P system, composed of a network of cells linked by synapses (channels), is a typical membrane computing model. The whole P system is divided into separate regions through these cells, each forming one region. Each cell has two main components, multisets of objects (materials) and rules, also called evolution rules (chemical reactions). Objects, as information carriers, are represented by characters.Rules regulate the ways objects evolve to new objects and the ways objects in different cells communicate through synapses. Rules are executed in nondeterministic flat maximally parallel in each cell. That is, at any step, if more than one rule can be executed but the objects in the cell can only support some of them, then a maximal number of rules will be executed, and each rule can be executed for only once [22].The computation halts if no rule can be executed in the whole system. The computational results are represented by the types and numbers of specified objects in a specified cell. Because objects in a P system evolve in flat maximally parallel, regulated by promoters and inhibitors, the systems compute very efficiently [10, 22]. Păun [7] provided more details about P systems.A formal description of the ECPI tissue-like P system is as follows.An ECPI tissue-like P system of degreem is of the form(1)
Π
=
O
,
σ
1
,
σ
2
,
…
,
σ
m
,
s
y
n
,
ρ
,
i
o
u
t
,where (1) O represents the alphabets including all objects of the system. (2) s
y
n
⊆
{
1,2
,
…
,
m
}
×
{
1,2
,
…
,
m
} represents all synapses between the cells. (3) ρ defines the partial ordering relationship of the rules; that is, rules with higher orders are executed with higher priority. (4) i
o
u
t represents the subscript of the output cell where the computation results are placed. (5) σ
1
,
…
,
σ
m represent the m cells. Each cell is of the form(2)
σ
h
=
w
h
,
0
,
R
h
,
f
o
r
1
≤
h
≤
m
.In (2), w
h
,
0 represents the initial objects in cell h. A w
h
,
0
=
λ means that there is no object in cell h. If a represents an object, a
n represents the multiplicity of n copies of such objects. R
h in (2) represents a set of rules in cell h with the form of w
z
→
x
y
g
o, where w is the multiset of objects consumed by the rule, z in the subscript is the promoter or the inhibitor of the form z
=
z
′ or z
=
¬
z
′, and x and y are the multisets of objects generated by the rule. A rule can be executed only when all objects in the promoter appear and cannot be executed when any objects in the inhibitor appear. Multiset of objects x stay in the current cell, and multiset of objects y go to the cells which have synapses connected from the current cell. The qth subset of rules in cell h having similar functions is represented by r
h
q, and the rules in the same subset are connected by ∪.


## 2.1. The Apriori Algorithm

The Apriori algorithm is a typical frequent itemsets mining algorithm proposed by Agrawal and Srikant [2], which aims at discovering relationships between items in transactional databases.Definitions
(i)
Item: a field in a transactional database is called an item. If one record contains a certain item “1,” otherwise “0,” is placed in the corresponding field of the record in the transactional database.
(ii)
Itemset:a set of items is called an itemset. For notational convenience, an itemset with n items I
1
,
I
2
,
…, and I
n is represented by {
I
1
,
I
2
,
…
,
I
n
}.
(iii)
h-itemset:a set containing h items is called a h-itemset.
(iv)
Transaction: a record in a transactional database is called a transaction, and each transaction is a nonempty itemset.
(v)
Support count:the number of transactions containing a certain itemset is called the support count of the itemset. Support count is also called the frequency or count of the itemset.
(vi)
Frequent itemset:if the support count of an itemset is equal to or larger than the given minimum support count threshold k, this itemset is called a frequent itemset.The general procedure of Apriori from Han et al. [1] is as follows.Input. The database contains D transactions and the support count threshold k.Step 1.
Scan the database to compute the support count of each item, and obtain the frequent 1-itemsetsL
1. Let h
=
2.Step 2.
Obtain the candidate frequenth-itemsets C
h by joining two frequent (h
-
1)-itemsets with only one item different.Step 3.
Prune those itemsets which have infrequent subset of length (h
-
1) from the candidate frequent h-itemsets.Step 4.
Scan the database to compute the support count of each candidate frequenth-itemset. Delete those itemsets which do not meet the support count threshold k and obtain the frequent h-itemsets L
h.Step 5.
Leth
=
h
+
1. Repeat Steps 2 to 4 until no itemset meets the support count threshold k.Output. The collection of all frequent itemsets is represented by L.


## 2.2. Evolution-Communication Tissue-Like P Systems with Promoters and Inhibitors

Membrane computing is a new branch of natural computing, which abstracts computing ideas from the construct and the functions of cells or tissues. In the nature, each organelle membrane or cell membrane works as a relatively independent computing unit. The amount and the types of materials in each organelle or cell change through chemical reactions. Materials can flow between different organelle or cell membranes to transport information. Reactions in different organelles or cells take place in parallel, while reactions in the same organelle or cell take place also in parallel. These biological processes are abstracted as the computing processes of membrane computing. The internal parallel feature makes membrane computing a powerful computing method which has been proven to be equivalent to Turing machines [7–11].The ECPI tissue-like P system, composed of a network of cells linked by synapses (channels), is a typical membrane computing model. The whole P system is divided into separate regions through these cells, each forming one region. Each cell has two main components, multisets of objects (materials) and rules, also called evolution rules (chemical reactions). Objects, as information carriers, are represented by characters.Rules regulate the ways objects evolve to new objects and the ways objects in different cells communicate through synapses. Rules are executed in nondeterministic flat maximally parallel in each cell. That is, at any step, if more than one rule can be executed but the objects in the cell can only support some of them, then a maximal number of rules will be executed, and each rule can be executed for only once [22].The computation halts if no rule can be executed in the whole system. The computational results are represented by the types and numbers of specified objects in a specified cell. Because objects in a P system evolve in flat maximally parallel, regulated by promoters and inhibitors, the systems compute very efficiently [10, 22]. Păun [7] provided more details about P systems.A formal description of the ECPI tissue-like P system is as follows.An ECPI tissue-like P system of degreem is of the form(1)
Π
=
O
,
σ
1
,
σ
2
,
…
,
σ
m
,
s
y
n
,
ρ
,
i
o
u
t
,where (1) O represents the alphabets including all objects of the system. (2) s
y
n
⊆
{
1,2
,
…
,
m
}
×
{
1,2
,
…
,
m
} represents all synapses between the cells. (3) ρ defines the partial ordering relationship of the rules; that is, rules with higher orders are executed with higher priority. (4) i
o
u
t represents the subscript of the output cell where the computation results are placed. (5) σ
1
,
…
,
σ
m represent the m cells. Each cell is of the form(2)
σ
h
=
w
h
,
0
,
R
h
,
f
o
r
1
≤
h
≤
m
.In (2), w
h
,
0 represents the initial objects in cell h. A w
h
,
0
=
λ means that there is no object in cell h. If a represents an object, a
n represents the multiplicity of n copies of such objects. R
h in (2) represents a set of rules in cell h with the form of w
z
→
x
y
g
o, where w is the multiset of objects consumed by the rule, z in the subscript is the promoter or the inhibitor of the form z
=
z
′ or z
=
¬
z
′, and x and y are the multisets of objects generated by the rule. A rule can be executed only when all objects in the promoter appear and cannot be executed when any objects in the inhibitor appear. Multiset of objects x stay in the current cell, and multiset of objects y go to the cells which have synapses connected from the current cell. The qth subset of rules in cell h having similar functions is represented by r
h
q, and the rules in the same subset are connected by ∪.


## 3. The ECTPPI-Apriori Algorithm

In this section, the structure of the P system used in the ECTPPI-Apriori algorithm is presented first, the computational processes in different cells are then discussed in detail, a pseudocode summarizing the operations is presented, and an analysis of the algorithm complexity is provided.


### 3.1. Algorithm and Rules

Assume a transactional database containsD records and t fields. An object a
i
j is generated only if the ith transaction contains the jth item I
j (i.e., there is a 1 in the corresponding field in the transactional database). In this way, the database is transformed into objects, a form that the P system can recognize. The support count threshold is set to k. A cell structure with t
+
2 cells, labeled by 0,1
,
…
,
t
+
1, as shown in Figure 1, is used as the framework for ECTPPI-Apriori. The evolution rules are not shown in this figure due to their length. Transactional databases are usually sparse. Therefore, the number of objects, represented by a
i
j, to be processed in this algorithm is much smaller than D
t.Figure 1
Cell structure for the ECTPPI-Apriori algorithm.When computation begins, objectsa
i
j encoded from the transactional database and object θ
k representing the support count threshold k are entered into cell 0. Objects a
i
j and θ
k are passed to cells 1,2
,
…
,
t in parallel, using a parallel evolution mechanism in tissue-like P systems. The auxiliary objects β
j
k are generated in cell 1. Next, the frequent 1-itemsets are produced and objects representing frequent 1-itemsets are generated in cell 1 by executing the evolution rules in parallel. The objects representing the frequent 1-itemsets are passed to cells 2 and t
+
1. Cell t
+
1 is used to store the computational results. The frequent 2-itemsets and the objects representing the frequent 2-itemsets are produced in cell 2 by executing the evolution rules in parallel. The objects representing the frequent 2-itemsets are passed to cells 3 and t
+
1. This process continues until all frequent itemsets have been produced. As compared with that of the conventional Apriori algorithm, the computational time needed by ECTPPI-Apriori to generate the candidate frequent h-itemsets C
h and to compute the support count of each candidate frequent h-itemset can be substantially reduced.The ECPI tissue-like P system for ECTPPI-Apriori is as follows.(3)
Π
A
p
r
i
o
r
i
=
O
,
σ
0
,
σ
1
,
…
,
σ
t
+
1
,
s
y
n
,
ρ
,
i
o
u
t
,where (1) O
=
a
i
j
,
β
j
,
β
j
1
j
2
,
…
,
β
j
1
⋯
j
t
,
δ
j
,
δ
j
1
j
2
,
…
,
δ
j
1
⋯
j
t
,
α
j
,
α
j
1
j
2
,
…
,
α
j
1
⋯
j
t for 1
≤
i
≤
D
,
1
≤
j
,
j
1
,
…
,
j
t
≤
t; (2) s
y
n
=
{
{
0,1
}
,
{
0,2
}
,
…
,
{
0
,
t
}; {
1
,
t
+
1
}
,
{
2
,
t
+
1
}
,
…
,
{
t
,
t
+
1
}; {
1,2
}
,
{
2,3
}
,
…
,
{
t
-
1
,
t
}
}; (3) ρ
=
{
r
i
>
r
j
∣
i
<
j
}; (4) σ
0
=
(
w
0,0
,
R
0
), σ
1
=
(
w
1,0
,
R
1
), σ
2
=
(
w
2,0
,
R
2
)
,
…
,
σ
t
=
(
w
t
,
0
,
R
t
); (5) i
o
u
t
=
t
+
1. Inσ
0
=
(
w
0,0
,
R
0
), w
0,0
=
λ and
R
0:
r
01
=
a
i
j
→
a
i
j
,
g
o
∪
{
θ
k
→
θ
g
o
k
}
for1
≤
i
≤
D and 1
≤
j
≤
t.
⁡
Inσ
1
=
(
w
1,0
,
R
1
)
,
w
1,0
=
λ and
R
1:
r
11
=
{
θ
k
→
β
1
k
⋯
β
t
k
}.
r
12
=
δ
j
p
β
j
k
-
p
→
λ
∪
{
(
δ
j
k
)
¬
β
j
→
α
j
,
g
o
}
for1
≤
j
≤
t and 1
≤
p
≤
k.
r
13
=
{
a
i
j
β
j
→
δ
j
}
for1
≤
i
≤
D and 1
≤
j
≤
t.
⁡
Inσ
2
=
(
w
2,0
,
R
2
)
,
w
2,0
=
λ and
R
2:
r
21
=
{
(
)
α
j
1
α
j
2
θ
k
¬
β
j
1
j
2
k
→
β
j
1
j
2
k
}
for1
≤
j
1
<
j
2
≤
t.
r
22
=
{
α
j
→
λ
}
(
1
≤
j
≤
t
).
r
23
=
δ
j
1
j
2
p
β
j
1
j
2
k
-
p
→
λ
∪
{
(
δ
j
1
j
2
k
)
¬
β
j
1
j
2
→
α
j
1
j
2
,
g
o
}
for1
≤
j
1
<
j
2
≤
t and 1
≤
p
≤
k.
r
24
=
{
(
β
j
1
j
2
)
a
i
j
1
a
i
j
2
→
δ
j
1
j
2
}
for1
≤
i
≤
D and 1
≤
j
1
<
j
2
≤
t.
⁡
⋮
⁡
Inσ
h
=
(
w
h
,
0
,
R
h
)
,
w
h
,
0
=
λ and
R
h:
r
h
1
=
{
(
)
α
j
1
⋯
j
h
-
2
j
h
1
α
j
1
⋯
j
h
-
2
j
h
2
θ
k
¬
β
j
1
⋯
j
h
-
2
j
h
1
j
h
2
k
→
β
j
1
⋯
j
h
-
2
j
h
1
j
h
2
k
}
for1
≤
j
1
<
⋯
<
j
h
-
2
≤
t and 1
≤
j
h
1
,
j
h
2
≤
t.
r
h
2
=
{
α
j
1
⋯
j
h
-
1
→
λ
}
for1
≤
j
1
<
⋯
<
j
h
-
1
≤
t.
r
h
3
=
δ
j
1
⋯
j
h
-
2
j
h
1
j
h
2
p
β
j
1
⋯
j
h
-
2
j
h
1
j
h
2
k
-
p
→
λ
∪
{
(
δ
j
1
⋯
j
h
-
2
j
h
1
j
h
2
k
)
¬
β
j
1
⋯
j
h
-
2
j
h
1
j
h
2
→
α
j
1
⋯
j
h
-
2
j
h
1
j
h
2
,
g
o
}
for1
≤
j
1
<
⋯
<
j
h
-
2
≤
t
,
1
≤
j
h
1
,
j
h
2
≤
t and 1
≤
p
≤
k.
r
h
4
=
{
(
β
j
1
⋯
j
h
-
2
j
h
1
j
h
2
)
a
i
j
1
⋯
a
i
j
h
-
2
j
h
1
j
h
2
→
δ
j
1
⋯
j
h
-
2
j
h
1
j
h
2
}
for1
≤
i
≤
D
,
1
≤
j
1
<
⋯
<
j
h
-
2
≤
t and 1
≤
j
h
1
,
j
h
2
≤
t.
⁡
⋮
⁡
Inσ
t
=
(
w
t
,
0
,
R
t
)
,
w
t
,
0
=
λ and
R
t:
r
t
1
=
{
(
)
α
j
1
⋯
j
t
-
2
j
t
1
α
j
1
⋯
j
t
-
2
j
t
2
θ
k
¬
β
j
1
⋯
j
t
-
2
j
t
1
j
t
2
k
→
β
j
1
⋯
j
t
-
2
j
t
1
j
t
2
k
}
for1
≤
j
1
<
⋯
<
j
t
-
2
≤
t and 1
≤
j
t
1
,
j
t
2
≤
t.
r
t
2
=
{
α
j
1
⋯
j
t
-
1
→
λ
}
for1
≤
j
1
<
⋯
<
j
t
-
1
≤
t.
r
t
3
=
δ
j
1
⋯
j
t
-
2
j
t
1
j
t
2
p
β
j
1
⋯
j
t
-
2
j
t
1
j
t
2
k
-
p
→
λ
∪
{
(
δ
j
1
⋯
j
t
-
2
j
t
1
j
t
2
k
)
¬
β
j
1
⋯
j
t
-
2
j
t
1
j
t
2
→
α
j
1
⋯
j
t
-
2
j
t
1
j
t
2
,
g
o
}
for1
≤
j
1
<
⋯
<
j
t
-
2
≤
t, 1
≤
j
t
1
,
j
t
2
≤
t and 1
≤
p
≤
k.
r
t
4
=
{
(
β
j
1
⋯
j
t
-
2
j
t
1
j
t
2
)
a
i
j
1
⋯
a
i
j
t
-
2
j
t
1
j
t
2
→
δ
j
1
⋯
j
t
-
2
j
t
1
j
t
2
}
for1
≤
i
≤
D, 1
≤
j
1
<
⋯
<
j
t
-
2
≤
t and 1
≤
j
t
1
,
j
t
2
≤
t.
⁡
Inσ
t
+
1
=
(
w
t
+
1,0
,
R
t
+
1
), w
t
+
1,0
=
λ and R
t
+
1
=
⌀.The auxiliary objectsβ
j
k and δ
j, for 1
≤
j
≤
t, are used to detect the frequent 1-itemsets. The auxiliary objects β
j
k store the items in the candidate frequent 1-itemsets using their subscripts. For example, object β
1
k means the itemset {
I
1
} is a candidate frequent 1-itemset. The auxiliary objects δ
j are used to identify the frequent 1-itemsets. The k copies of β
j initially in cell 1 indicate that the jth item needs to appear in at least k records to make the itemset {
I
j
} a frequent 1-itemset. One object β
j is removed from, and one object δ
j is generated in cell 1 when one more of the jth item is detected in a record. Therefore, if there is no object β
j left and k objects δ
j have been generated in cell 1, at least k records have been found to contain the jth item. The functions of β
j
1
j
2
k in cells 2, β
j
1
j
2
j
3
k in cell 3
,
…, and β
j
1
⋯
j
t
k in cell t are similar to that of β
j
k in cell 1. The functions of δ
j
1
j
2 in cell 2, δ
j
1
j
2
j
3 in cell 3
,
…, and δ
j
1
⋯
j
t in cell t are similar to that of δ
j in cell 1. The objects α
j, for 1
≤
j
≤
t, are used to store the items in the frequent 1-itemsets using their subscript. For example, α
1 means the itemset {
I
1
} is a frequent 1-itemset. The functions of α
j
1
j
2 in cell 2, α
j
1
j
2
j
3 in cell 3
,
…, and α
j
1
·
·
·
j
t in cell t are similar to that of α
j in cell 1.The evolution rules are object rewriting rules similar to chemical reactions. They take objects, transform them into other objects, and may transport them to other cells.


### 3.2. Computing Process

Input. Cell 0 is the input cell. The objects a
i
j encoded from the transactional database and objects θ
k representing the support count threshold k are entered into cell 0 to activate the computation process. Rule r
01 is executed to put copies of a
i
j and θ
k to cells 1,2
,
…
,
t.Frequent 1-Itemsets Generation. Frequent 1-itemsets are generated in cell 1. Rule r
11 is executed to generate β
j
k for 1
≤
j
≤
t. Rule r
13 is executed to detect all frequent 1-itemsets using the internal flat maximally parallel mechanism in the P system. Rule r
12 cannot be executed because no object δ
j is in cell 1 at this time. The detection process of the candidate frequent 1-itemset {
I
1
} is taken as an example. The detection processes of other candidate frequent 1-itemsets are performed in the same way. Rule r
13 is actually composed of multiple subrules working on objects with different subscripts. If object a
i
1 is in cell 1  which means the ith record contains the first item, the subrule {
a
i
1
β
1
→
δ
1
} meets the execution condition and can be executed. If object a
i
1 is not in cell 1 which means the ith record does not contain the first item, the subrule {
a
i
1
β
1
→
δ
1
} does not meet the execution condition and cannot be executed. Initially, k copies of β
1 are in cell 1 indicating that the first item needs to appear in at least k records for the itemset {
I
1
} to be a frequent 1-itemset. Each execution of a subrule consumes one β
1. Therefore, at most k subrules of the form {
a
i
1
β
1
→
δ
1
} can be executed in nondeterministic flat maximally parallel. The checking process continues until all objects a
i
j have been checked or all of the k copies of β
1 have been consumed. If all of the k copies of β
1 have been consumed, the first item appeared in at least k records and the itemset {
I
1
} is a frequent 1-itemset. If some copies of β
1 are still in this cell after all objects a
i
j have been checked, the itemset {
I
1
} is not a frequent 1-itemset.Ruler
12 is then executed to process the results obtained by rule r
13. The 1-itemset {
I
1
} is again taken as an example. If p copies of β
1 have been consumed by rule r
13, and k
-
p copies of β
1 are still in this cell, subrule {
δ
1
p
β
1
k
-
p
→
λ
} is executed to delete the objects δ
1
p and β
1
k
-
p. If all of the k copies of β
1 have been consumed, subrule {
(
δ
1
k
)
¬
β
1
→
α
1
,
g
o
} is executed to put an object α
1 to cells 2 and t
+
1 to indicate that the itemset {
I
1
} is a frequent 1-itemset and to activate the computation in cell 2. If no 1-itemset is a frequent 1-itemset, the computation halts.Frequent 2-Itemsets Generation. The frequent 2-itemsets are generated in cell 2. Rule r
21 is executed to obtain all candidate frequent 2-itemsets using the internal flat maximally parallel mechanism in the P system. The pair of empty parentheses in this subrule indicates that no objects are consumed when this rule is executed. The detection process of the candidate frequent 2-itemset {
I
1
,
I
2
} is taken as an example. The detection processes of the other candidate frequent 2-itemsets are performed in the same way. Rule r
21 is actually composed of multiple subrules working on objects with different subscripts. If objects α
1 and α
2 are in cell 2, which means itemsets {
I
1
} and {
I
2
} are frequent 1-itemsets, subrule {
(
)
α
1
α
2
θ
k
¬
β
12
k
→
β
12
k
} is executed to generate β
12
k. The presence of β
12
k means the 2-itemset {
I
1
,
I
2
} is a candidate frequent 2-itemset.Ruler
22 is executed to delete the redundant objects α
j that were used by rule r
21 but are not needed anymore.Ruler
24 is executed to detect all frequent 2-itemsets using the internal flat maximally parallel mechanism in the P system. Rule r
23 cannot be executed because no object δ
j
1
j
2 is in cell 2 at this time. The detection process of the frequent 2-itemset {
I
1
,
I
2
} is taken as an example. Rule r
24 is actually composed of multiple subrules working on objects with different subscripts. If objects a
i
1 and a
i
2 are in cell 2 which means the ith record contains the first and the second items, subrule {
(
β
12
)
a
i
1
a
i
2
→
δ
12
} meets the execution condition and can be executed. If objects a
i
1 and a
i
2 are not both in cell 2 which means the ith record does not contain both the first and the second items, subrule {
(
β
12
)
a
i
1
a
i
2
→
δ
12
} does not meet the execution condition and cannot be executed. Initially, k copies of β
12 are in cell 2 indicating that both the first and the second items need to appear together in at least k records for the itemset {
I
1
,
I
2
} to be a frequent 2-itemset. Each execution of these subrules consumes one β
12. Therefore, at most k subrules of the form {
(
β
12
)
a
i
1
a
i
2
→
δ
12
} can be executed in nondeterministic flat maximally parallel. The checking process continues until all objects a
i
j have been checked or all of the k copies of β
12 have been consumed. If all of the k copies of β
12 have been consumed, the first and the second items appeared together in at least k records and the itemset {
I
1
,
I
2
} is a frequent 2-itemset. If some copies of β
12 are still in this cell after rule r
24 is executed, the itemset {
I
1
,
I
2
} is not a frequent 2-itemset.Ruler
23 is executed to process the results obtained by rule r
24. The 2-itemset {
I
1
,
I
2
} is again taken as an example. If p copies of β
12 have been consumed by rule r
24, and k
-
p copies of objects β
12 are still in this cell, subrule {
δ
12
p
β
12
k
-
p
→
λ
} is executed to delete the objects δ
12
p and β
12
k
-
p. If all of the k copies of β
12 have been consumed, subrule {
(
δ
12
k
)
¬
β
12
→
α
12
,
g
o
} is executed to put an object α
12 to cells 3 and t
+
1 to indicate that the itemset {
I
1
,
I
2
} is a frequent 2-itemset and to activate the computation in cell 3. If no 2-itemset is a frequent 2-itemset, the computation halts.Each cellj for 3
≤
j
≤
t has 4 rules which are similar to those in cell 2. Each cell j performs similar functions as cell 2 does but for frequent j-itemsets.After the computation halts, all the results, that is, objects representing the identified frequent itemsets, are stored in cellt
+
1.


### 3.3. Algorithm Flow

The conventional Apriori algorithm executes sequentially. ECTPPI-Apriori uses the parallel mechanism of the ECPI tissue-like P system to execute in parallel. A pseudocode of ECTPPI-Apriori is shown as in Algorithm1.Algorithm 1:ECTP-Apriori algorithm.
Input:
The objectsa
i
j encoded from the transactional database and objects θ
k representing the support count
thresholdk.
Ruler
01:
Copy alla
i
j and θ
k to cells 1 to t
+
1.
Method:
Ruler
11:
Generateβ
j
k for 1
≤
j
≤
t to form the candidate frequent 1-itemsets C
1.
Ruler
13:
Scan each objecta
i
j in cell 1 to count the frequency of each item. If a
i
j is in cell 1, consume one β
j and
generate oneδ
j. Continue until all k copies of β
j have been consumed or all objects a
i
j have been scanned.
Ruler
12:
If allk copies of β
j have been consumed, generate an object α
j to add {
I
j
} to L
1 as a frequent 1-itemset
and passα
j to cells 2 and t
+
1. Delete all remaining copies of β
j and delete all copies of δ
j.
For (2
≤
h
≤
t and L
h
-
1
≠
⌀) do the following in cell h:
Ruler
h
1:
Scan the objectsα
j
1
⋯
j
h
-
1 representing the frequent (h
-
1)-itemsets L
h
-
1 to generate the objects β
j
1
⋯
j
h
k
representing the candidate frequenth-itemsets C
h.
Ruler
h
2:
Delete all objectsα
j
1
⋯
j
h
-
1 after they have been used by rule r
h
1.
Ruler
h
4:
Scan the objectsa
i
j representing the database to count the frequency of each candidate frequent h-itemset
C
h. If the objects a
i
,
j
1
,
…
,
a
i
,
j
h
-
1 and a
i
,
j
h are all in cell h, consume one β
j
1
⋯
j
h and generate one δ
j
1
⋯
j
h.
Continue until all copies ofβ
j
1
⋯
j
h have been consumed or all objects a
i
j have been scanned.
Ruler
h
3:
If allk copies of β
j
1
⋯
j
h have been consumed, generate α
j
1
⋯
j
h to add {
I
j
1
,
…
,
I
j
h
} to L
h as a frequent
h-itemset and put α
j
1
⋯
j
h in cells h
+
1 and t
+
1. Delete all remaining copies of β
j
1
⋯
j
h and delete all copies
ofδ
j
1
⋯
j
h.
Leth
=
h
+
1.
Output:
The collection of all frequent itemsetsL encoded by objects α
j
,
α
j
1
j
2
,
…
,
α
j
1
⋯
j
n.


### 3.4. Time Complexity

The time complexity of ECTPPI-Apriori in the worst case is analyzed. Initially, 1 computational step is needed to put copies ofa
i
j and θ
k to cells 1,2
,
…
,
t.Generating the frequent 1-itemsets needs 3 computational steps. Generating the candidate frequent 1-itemsetsC
1 needs 1 computational step. Finding the support counts of the candidate frequent 1-itemsets needs 1 computational step. All candidate frequent 1-itemsets in the database are checked in the flat maximally parallel. Passing the results of the frequent 1-itemsets to cells 2 and t
+
1 needs 1 computational step.Generating the frequenth-itemsets (1
<
h
≤
t) needs 4 computational steps. Generating the candidate frequent h-itemsets C
h needs 1 computational step. Cleaning the memory used by the objects needs 1 computational step. Finding the support counts of the candidate frequent h-itemsets needs 1 computational step. All candidate frequent h-itemsets in the database are checked in flat maximally parallel. Passing the results of the frequent h-itemsets to cells h
+
1 and t
+
1 needs 1 computational step.Therefore, the time complexity of ECTPPI-Apriori is1
+
3
+
4
(
t
-
1
)
=
4
t, which gives O
(
t
). Note that O is used traditionally to indicate the time complexity of an algorithm and the O used here has a different meaning from that used earlier when ECTPPI-Apriori is described.Some comparison results between ECTPPI-Apriori and the original as well as some other improved parallel Apriori algorithms are shown in Table1, where C
k is the number of candidate frequent k-itemsets and L
k
-
1 is the number of frequent k
-
1-itemsets.Table 1
Time complexities of some Apriori algorithms.
Algorithm
Time complexity
Apriori [2]
O
D
t
C
k
+
t
L
k
-
1
L
k
-
1
Apriori based on the boolean matrix and Hadoop [3]
O
(
D
t
)
Multi-GPU-based Apriori [4]
O
(
t
|
L
k
-
1
|
|
L
k
-
1
|
)
PApriori [5]
O
(
D
t
|
C
k
|
+
t
|
L
k
-
1
|
|
L
k
-
1
|
)
Parallel Apriori algorithm on Hadoop cluster [6]
O
(
D
t
|
C
k
|
+
t
|
L
k
-
1
|
|
L
k
-
1
|
)
ECTPPI-Apriori
O
(
t
)


## 3.1. Algorithm and Rules

Assume a transactional database containsD records and t fields. An object a
i
j is generated only if the ith transaction contains the jth item I
j (i.e., there is a 1 in the corresponding field in the transactional database). In this way, the database is transformed into objects, a form that the P system can recognize. The support count threshold is set to k. A cell structure with t
+
2 cells, labeled by 0,1
,
…
,
t
+
1, as shown in Figure 1, is used as the framework for ECTPPI-Apriori. The evolution rules are not shown in this figure due to their length. Transactional databases are usually sparse. Therefore, the number of objects, represented by a
i
j, to be processed in this algorithm is much smaller than D
t.Figure 1
Cell structure for the ECTPPI-Apriori algorithm.When computation begins, objectsa
i
j encoded from the transactional database and object θ
k representing the support count threshold k are entered into cell 0. Objects a
i
j and θ
k are passed to cells 1,2
,
…
,
t in parallel, using a parallel evolution mechanism in tissue-like P systems. The auxiliary objects β
j
k are generated in cell 1. Next, the frequent 1-itemsets are produced and objects representing frequent 1-itemsets are generated in cell 1 by executing the evolution rules in parallel. The objects representing the frequent 1-itemsets are passed to cells 2 and t
+
1. Cell t
+
1 is used to store the computational results. The frequent 2-itemsets and the objects representing the frequent 2-itemsets are produced in cell 2 by executing the evolution rules in parallel. The objects representing the frequent 2-itemsets are passed to cells 3 and t
+
1. This process continues until all frequent itemsets have been produced. As compared with that of the conventional Apriori algorithm, the computational time needed by ECTPPI-Apriori to generate the candidate frequent h-itemsets C
h and to compute the support count of each candidate frequent h-itemset can be substantially reduced.The ECPI tissue-like P system for ECTPPI-Apriori is as follows.(3)
Π
A
p
r
i
o
r
i
=
O
,
σ
0
,
σ
1
,
…
,
σ
t
+
1
,
s
y
n
,
ρ
,
i
o
u
t
,where (1) O
=
a
i
j
,
β
j
,
β
j
1
j
2
,
…
,
β
j
1
⋯
j
t
,
δ
j
,
δ
j
1
j
2
,
…
,
δ
j
1
⋯
j
t
,
α
j
,
α
j
1
j
2
,
…
,
α
j
1
⋯
j
t for 1
≤
i
≤
D
,
1
≤
j
,
j
1
,
…
,
j
t
≤
t; (2) s
y
n
=
{
{
0,1
}
,
{
0,2
}
,
…
,
{
0
,
t
}; {
1
,
t
+
1
}
,
{
2
,
t
+
1
}
,
…
,
{
t
,
t
+
1
}; {
1,2
}
,
{
2,3
}
,
…
,
{
t
-
1
,
t
}
}; (3) ρ
=
{
r
i
>
r
j
∣
i
<
j
}; (4) σ
0
=
(
w
0,0
,
R
0
), σ
1
=
(
w
1,0
,
R
1
), σ
2
=
(
w
2,0
,
R
2
)
,
…
,
σ
t
=
(
w
t
,
0
,
R
t
); (5) i
o
u
t
=
t
+
1. Inσ
0
=
(
w
0,0
,
R
0
), w
0,0
=
λ and
R
0:
r
01
=
a
i
j
→
a
i
j
,
g
o
∪
{
θ
k
→
θ
g
o
k
}
for1
≤
i
≤
D and 1
≤
j
≤
t.
⁡
Inσ
1
=
(
w
1,0
,
R
1
)
,
w
1,0
=
λ and
R
1:
r
11
=
{
θ
k
→
β
1
k
⋯
β
t
k
}.
r
12
=
δ
j
p
β
j
k
-
p
→
λ
∪
{
(
δ
j
k
)
¬
β
j
→
α
j
,
g
o
}
for1
≤
j
≤
t and 1
≤
p
≤
k.
r
13
=
{
a
i
j
β
j
→
δ
j
}
for1
≤
i
≤
D and 1
≤
j
≤
t.
⁡
Inσ
2
=
(
w
2,0
,
R
2
)
,
w
2,0
=
λ and
R
2:
r
21
=
{
(
)
α
j
1
α
j
2
θ
k
¬
β
j
1
j
2
k
→
β
j
1
j
2
k
}
for1
≤
j
1
<
j
2
≤
t.
r
22
=
{
α
j
→
λ
}
(
1
≤
j
≤
t
).
r
23
=
δ
j
1
j
2
p
β
j
1
j
2
k
-
p
→
λ
∪
{
(
δ
j
1
j
2
k
)
¬
β
j
1
j
2
→
α
j
1
j
2
,
g
o
}
for1
≤
j
1
<
j
2
≤
t and 1
≤
p
≤
k.
r
24
=
{
(
β
j
1
j
2
)
a
i
j
1
a
i
j
2
→
δ
j
1
j
2
}
for1
≤
i
≤
D and 1
≤
j
1
<
j
2
≤
t.
⁡
⋮
⁡
Inσ
h
=
(
w
h
,
0
,
R
h
)
,
w
h
,
0
=
λ and
R
h:
r
h
1
=
{
(
)
α
j
1
⋯
j
h
-
2
j
h
1
α
j
1
⋯
j
h
-
2
j
h
2
θ
k
¬
β
j
1
⋯
j
h
-
2
j
h
1
j
h
2
k
→
β
j
1
⋯
j
h
-
2
j
h
1
j
h
2
k
}
for1
≤
j
1
<
⋯
<
j
h
-
2
≤
t and 1
≤
j
h
1
,
j
h
2
≤
t.
r
h
2
=
{
α
j
1
⋯
j
h
-
1
→
λ
}
for1
≤
j
1
<
⋯
<
j
h
-
1
≤
t.
r
h
3
=
δ
j
1
⋯
j
h
-
2
j
h
1
j
h
2
p
β
j
1
⋯
j
h
-
2
j
h
1
j
h
2
k
-
p
→
λ
∪
{
(
δ
j
1
⋯
j
h
-
2
j
h
1
j
h
2
k
)
¬
β
j
1
⋯
j
h
-
2
j
h
1
j
h
2
→
α
j
1
⋯
j
h
-
2
j
h
1
j
h
2
,
g
o
}
for1
≤
j
1
<
⋯
<
j
h
-
2
≤
t
,
1
≤
j
h
1
,
j
h
2
≤
t and 1
≤
p
≤
k.
r
h
4
=
{
(
β
j
1
⋯
j
h
-
2
j
h
1
j
h
2
)
a
i
j
1
⋯
a
i
j
h
-
2
j
h
1
j
h
2
→
δ
j
1
⋯
j
h
-
2
j
h
1
j
h
2
}
for1
≤
i
≤
D
,
1
≤
j
1
<
⋯
<
j
h
-
2
≤
t and 1
≤
j
h
1
,
j
h
2
≤
t.
⁡
⋮
⁡
Inσ
t
=
(
w
t
,
0
,
R
t
)
,
w
t
,
0
=
λ and
R
t:
r
t
1
=
{
(
)
α
j
1
⋯
j
t
-
2
j
t
1
α
j
1
⋯
j
t
-
2
j
t
2
θ
k
¬
β
j
1
⋯
j
t
-
2
j
t
1
j
t
2
k
→
β
j
1
⋯
j
t
-
2
j
t
1
j
t
2
k
}
for1
≤
j
1
<
⋯
<
j
t
-
2
≤
t and 1
≤
j
t
1
,
j
t
2
≤
t.
r
t
2
=
{
α
j
1
⋯
j
t
-
1
→
λ
}
for1
≤
j
1
<
⋯
<
j
t
-
1
≤
t.
r
t
3
=
δ
j
1
⋯
j
t
-
2
j
t
1
j
t
2
p
β
j
1
⋯
j
t
-
2
j
t
1
j
t
2
k
-
p
→
λ
∪
{
(
δ
j
1
⋯
j
t
-
2
j
t
1
j
t
2
k
)
¬
β
j
1
⋯
j
t
-
2
j
t
1
j
t
2
→
α
j
1
⋯
j
t
-
2
j
t
1
j
t
2
,
g
o
}
for1
≤
j
1
<
⋯
<
j
t
-
2
≤
t, 1
≤
j
t
1
,
j
t
2
≤
t and 1
≤
p
≤
k.
r
t
4
=
{
(
β
j
1
⋯
j
t
-
2
j
t
1
j
t
2
)
a
i
j
1
⋯
a
i
j
t
-
2
j
t
1
j
t
2
→
δ
j
1
⋯
j
t
-
2
j
t
1
j
t
2
}
for1
≤
i
≤
D, 1
≤
j
1
<
⋯
<
j
t
-
2
≤
t and 1
≤
j
t
1
,
j
t
2
≤
t.
⁡
Inσ
t
+
1
=
(
w
t
+
1,0
,
R
t
+
1
), w
t
+
1,0
=
λ and R
t
+
1
=
⌀.The auxiliary objectsβ
j
k and δ
j, for 1
≤
j
≤
t, are used to detect the frequent 1-itemsets. The auxiliary objects β
j
k store the items in the candidate frequent 1-itemsets using their subscripts. For example, object β
1
k means the itemset {
I
1
} is a candidate frequent 1-itemset. The auxiliary objects δ
j are used to identify the frequent 1-itemsets. The k copies of β
j initially in cell 1 indicate that the jth item needs to appear in at least k records to make the itemset {
I
j
} a frequent 1-itemset. One object β
j is removed from, and one object δ
j is generated in cell 1 when one more of the jth item is detected in a record. Therefore, if there is no object β
j left and k objects δ
j have been generated in cell 1, at least k records have been found to contain the jth item. The functions of β
j
1
j
2
k in cells 2, β
j
1
j
2
j
3
k in cell 3
,
…, and β
j
1
⋯
j
t
k in cell t are similar to that of β
j
k in cell 1. The functions of δ
j
1
j
2 in cell 2, δ
j
1
j
2
j
3 in cell 3
,
…, and δ
j
1
⋯
j
t in cell t are similar to that of δ
j in cell 1. The objects α
j, for 1
≤
j
≤
t, are used to store the items in the frequent 1-itemsets using their subscript. For example, α
1 means the itemset {
I
1
} is a frequent 1-itemset. The functions of α
j
1
j
2 in cell 2, α
j
1
j
2
j
3 in cell 3
,
…, and α
j
1
·
·
·
j
t in cell t are similar to that of α
j in cell 1.The evolution rules are object rewriting rules similar to chemical reactions. They take objects, transform them into other objects, and may transport them to other cells.


## 3.2. Computing Process

Input. Cell 0 is the input cell. The objects a
i
j encoded from the transactional database and objects θ
k representing the support count threshold k are entered into cell 0 to activate the computation process. Rule r
01 is executed to put copies of a
i
j and θ
k to cells 1,2
,
…
,
t.Frequent 1-Itemsets Generation. Frequent 1-itemsets are generated in cell 1. Rule r
11 is executed to generate β
j
k for 1
≤
j
≤
t. Rule r
13 is executed to detect all frequent 1-itemsets using the internal flat maximally parallel mechanism in the P system. Rule r
12 cannot be executed because no object δ
j is in cell 1 at this time. The detection process of the candidate frequent 1-itemset {
I
1
} is taken as an example. The detection processes of other candidate frequent 1-itemsets are performed in the same way. Rule r
13 is actually composed of multiple subrules working on objects with different subscripts. If object a
i
1 is in cell 1  which means the ith record contains the first item, the subrule {
a
i
1
β
1
→
δ
1
} meets the execution condition and can be executed. If object a
i
1 is not in cell 1 which means the ith record does not contain the first item, the subrule {
a
i
1
β
1
→
δ
1
} does not meet the execution condition and cannot be executed. Initially, k copies of β
1 are in cell 1 indicating that the first item needs to appear in at least k records for the itemset {
I
1
} to be a frequent 1-itemset. Each execution of a subrule consumes one β
1. Therefore, at most k subrules of the form {
a
i
1
β
1
→
δ
1
} can be executed in nondeterministic flat maximally parallel. The checking process continues until all objects a
i
j have been checked or all of the k copies of β
1 have been consumed. If all of the k copies of β
1 have been consumed, the first item appeared in at least k records and the itemset {
I
1
} is a frequent 1-itemset. If some copies of β
1 are still in this cell after all objects a
i
j have been checked, the itemset {
I
1
} is not a frequent 1-itemset.Ruler
12 is then executed to process the results obtained by rule r
13. The 1-itemset {
I
1
} is again taken as an example. If p copies of β
1 have been consumed by rule r
13, and k
-
p copies of β
1 are still in this cell, subrule {
δ
1
p
β
1
k
-
p
→
λ
} is executed to delete the objects δ
1
p and β
1
k
-
p. If all of the k copies of β
1 have been consumed, subrule {
(
δ
1
k
)
¬
β
1
→
α
1
,
g
o
} is executed to put an object α
1 to cells 2 and t
+
1 to indicate that the itemset {
I
1
} is a frequent 1-itemset and to activate the computation in cell 2. If no 1-itemset is a frequent 1-itemset, the computation halts.Frequent 2-Itemsets Generation. The frequent 2-itemsets are generated in cell 2. Rule r
21 is executed to obtain all candidate frequent 2-itemsets using the internal flat maximally parallel mechanism in the P system. The pair of empty parentheses in this subrule indicates that no objects are consumed when this rule is executed. The detection process of the candidate frequent 2-itemset {
I
1
,
I
2
} is taken as an example. The detection processes of the other candidate frequent 2-itemsets are performed in the same way. Rule r
21 is actually composed of multiple subrules working on objects with different subscripts. If objects α
1 and α
2 are in cell 2, which means itemsets {
I
1
} and {
I
2
} are frequent 1-itemsets, subrule {
(
)
α
1
α
2
θ
k
¬
β
12
k
→
β
12
k
} is executed to generate β
12
k. The presence of β
12
k means the 2-itemset {
I
1
,
I
2
} is a candidate frequent 2-itemset.Ruler
22 is executed to delete the redundant objects α
j that were used by rule r
21 but are not needed anymore.Ruler
24 is executed to detect all frequent 2-itemsets using the internal flat maximally parallel mechanism in the P system. Rule r
23 cannot be executed because no object δ
j
1
j
2 is in cell 2 at this time. The detection process of the frequent 2-itemset {
I
1
,
I
2
} is taken as an example. Rule r
24 is actually composed of multiple subrules working on objects with different subscripts. If objects a
i
1 and a
i
2 are in cell 2 which means the ith record contains the first and the second items, subrule {
(
β
12
)
a
i
1
a
i
2
→
δ
12
} meets the execution condition and can be executed. If objects a
i
1 and a
i
2 are not both in cell 2 which means the ith record does not contain both the first and the second items, subrule {
(
β
12
)
a
i
1
a
i
2
→
δ
12
} does not meet the execution condition and cannot be executed. Initially, k copies of β
12 are in cell 2 indicating that both the first and the second items need to appear together in at least k records for the itemset {
I
1
,
I
2
} to be a frequent 2-itemset. Each execution of these subrules consumes one β
12. Therefore, at most k subrules of the form {
(
β
12
)
a
i
1
a
i
2
→
δ
12
} can be executed in nondeterministic flat maximally parallel. The checking process continues until all objects a
i
j have been checked or all of the k copies of β
12 have been consumed. If all of the k copies of β
12 have been consumed, the first and the second items appeared together in at least k records and the itemset {
I
1
,
I
2
} is a frequent 2-itemset. If some copies of β
12 are still in this cell after rule r
24 is executed, the itemset {
I
1
,
I
2
} is not a frequent 2-itemset.Ruler
23 is executed to process the results obtained by rule r
24. The 2-itemset {
I
1
,
I
2
} is again taken as an example. If p copies of β
12 have been consumed by rule r
24, and k
-
p copies of objects β
12 are still in this cell, subrule {
δ
12
p
β
12
k
-
p
→
λ
} is executed to delete the objects δ
12
p and β
12
k
-
p. If all of the k copies of β
12 have been consumed, subrule {
(
δ
12
k
)
¬
β
12
→
α
12
,
g
o
} is executed to put an object α
12 to cells 3 and t
+
1 to indicate that the itemset {
I
1
,
I
2
} is a frequent 2-itemset and to activate the computation in cell 3. If no 2-itemset is a frequent 2-itemset, the computation halts.Each cellj for 3
≤
j
≤
t has 4 rules which are similar to those in cell 2. Each cell j performs similar functions as cell 2 does but for frequent j-itemsets.After the computation halts, all the results, that is, objects representing the identified frequent itemsets, are stored in cellt
+
1.


## 3.3. Algorithm Flow

The conventional Apriori algorithm executes sequentially. ECTPPI-Apriori uses the parallel mechanism of the ECPI tissue-like P system to execute in parallel. A pseudocode of ECTPPI-Apriori is shown as in Algorithm1.Algorithm 1:ECTP-Apriori algorithm.
Input:
The objectsa
i
j encoded from the transactional database and objects θ
k representing the support count
thresholdk.
Ruler
01:
Copy alla
i
j and θ
k to cells 1 to t
+
1.
Method:
Ruler
11:
Generateβ
j
k for 1
≤
j
≤
t to form the candidate frequent 1-itemsets C
1.
Ruler
13:
Scan each objecta
i
j in cell 1 to count the frequency of each item. If a
i
j is in cell 1, consume one β
j and
generate oneδ
j. Continue until all k copies of β
j have been consumed or all objects a
i
j have been scanned.
Ruler
12:
If allk copies of β
j have been consumed, generate an object α
j to add {
I
j
} to L
1 as a frequent 1-itemset
and passα
j to cells 2 and t
+
1. Delete all remaining copies of β
j and delete all copies of δ
j.
For (2
≤
h
≤
t and L
h
-
1
≠
⌀) do the following in cell h:
Ruler
h
1:
Scan the objectsα
j
1
⋯
j
h
-
1 representing the frequent (h
-
1)-itemsets L
h
-
1 to generate the objects β
j
1
⋯
j
h
k
representing the candidate frequenth-itemsets C
h.
Ruler
h
2:
Delete all objectsα
j
1
⋯
j
h
-
1 after they have been used by rule r
h
1.
Ruler
h
4:
Scan the objectsa
i
j representing the database to count the frequency of each candidate frequent h-itemset
C
h. If the objects a
i
,
j
1
,
…
,
a
i
,
j
h
-
1 and a
i
,
j
h are all in cell h, consume one β
j
1
⋯
j
h and generate one δ
j
1
⋯
j
h.
Continue until all copies ofβ
j
1
⋯
j
h have been consumed or all objects a
i
j have been scanned.
Ruler
h
3:
If allk copies of β
j
1
⋯
j
h have been consumed, generate α
j
1
⋯
j
h to add {
I
j
1
,
…
,
I
j
h
} to L
h as a frequent
h-itemset and put α
j
1
⋯
j
h in cells h
+
1 and t
+
1. Delete all remaining copies of β
j
1
⋯
j
h and delete all copies
ofδ
j
1
⋯
j
h.
Leth
=
h
+
1.
Output:
The collection of all frequent itemsetsL encoded by objects α
j
,
α
j
1
j
2
,
…
,
α
j
1
⋯
j
n.


## 3.4. Time Complexity

The time complexity of ECTPPI-Apriori in the worst case is analyzed. Initially, 1 computational step is needed to put copies ofa
i
j and θ
k to cells 1,2
,
…
,
t.Generating the frequent 1-itemsets needs 3 computational steps. Generating the candidate frequent 1-itemsetsC
1 needs 1 computational step. Finding the support counts of the candidate frequent 1-itemsets needs 1 computational step. All candidate frequent 1-itemsets in the database are checked in the flat maximally parallel. Passing the results of the frequent 1-itemsets to cells 2 and t
+
1 needs 1 computational step.Generating the frequenth-itemsets (1
<
h
≤
t) needs 4 computational steps. Generating the candidate frequent h-itemsets C
h needs 1 computational step. Cleaning the memory used by the objects needs 1 computational step. Finding the support counts of the candidate frequent h-itemsets needs 1 computational step. All candidate frequent h-itemsets in the database are checked in flat maximally parallel. Passing the results of the frequent h-itemsets to cells h
+
1 and t
+
1 needs 1 computational step.Therefore, the time complexity of ECTPPI-Apriori is1
+
3
+
4
(
t
-
1
)
=
4
t, which gives O
(
t
). Note that O is used traditionally to indicate the time complexity of an algorithm and the O used here has a different meaning from that used earlier when ECTPPI-Apriori is described.Some comparison results between ECTPPI-Apriori and the original as well as some other improved parallel Apriori algorithms are shown in Table1, where C
k is the number of candidate frequent k-itemsets and L
k
-
1 is the number of frequent k
-
1-itemsets.Table 1
Time complexities of some Apriori algorithms.
Algorithm
Time complexity
Apriori [2]
O
D
t
C
k
+
t
L
k
-
1
L
k
-
1
Apriori based on the boolean matrix and Hadoop [3]
O
(
D
t
)
Multi-GPU-based Apriori [4]
O
(
t
|
L
k
-
1
|
|
L
k
-
1
|
)
PApriori [5]
O
(
D
t
|
C
k
|
+
t
|
L
k
-
1
|
|
L
k
-
1
|
)
Parallel Apriori algorithm on Hadoop cluster [6]
O
(
D
t
|
C
k
|
+
t
|
L
k
-
1
|
|
L
k
-
1
|
)
ECTPPI-Apriori
O
(
t
)


## 4. An Illustrative Example

An illustrative example is presented in this section to demonstrate how ECTPPI-Apriori works. Table2 shows the transactional database of one branch office of All Electronics [1]. There are 9 transactions and 5 fields in this database; that is, D
=
9 and t
=
5. Suppose the support count threshold is k
=
2. The computational processes are as follows.Table 2
The transactional database of the illustrative example.
T
I
D
Items
T
100
I
1, I
2, I
5
T
200
I
2, I
4
T
300
I
2, I
3
T
400
I
1, I
2, I
4
T
500
I
1, I
3
T
600
I
2, I
3
T
700
I
1, I
3
T
800
I
1, I
2, I
3, I
5
T
900
I
1, I
2, I
3Input. The database is transformed into objects a
11, a
12, a
15, a
22, a
24, a
32, a
33, a
41, a
42, a
44, a
51, a
53, a
62, a
63, a
71, a
73, a
81, a
82, a
83, a
85, a
91, a
92, and a
93, in a form that the P system can recognize. These objects and objects θ
2 representing the support count threshold k
=
2 are entered into cell 0 to activate the computation process. Rule r
01
=
a
i
j
→
a
i
j
,
g
o
∪
{
θ
k
→
θ
g
o
k
} is executed to put copies of a
11, a
12, a
15, a
22, a
24, a
32, a
33, a
41, a
42, a
44, a
51, a
53, a
62, a
63, a
71, a
73, a
81, a
82, a
83, a
85, a
91, a
92, a
93, and θ
2 to cells 1
⋯
5.Frequent 1-Itemsets Generation.Within cell 1, the auxiliary objects β
j
2, for 1
≤
j
≤
5, are created by rule r
11 to indicate that each item j needs to appear in at least k
=
2 records for it to be a frequent 1-itemset. Rule r
13 is executed to detect all frequent 1-itemsets in flat maximally parallel. The detection process of the candidate frequent 1-itemset {
I
1
} is taken as an example. Objects a
11, a
41, a
51, a
71, a
81, and a
91 are in cell 1 which means the first, the fourth, the fifth, the seventh, the eighth, and the ninth records contain I
1. The subrules {
a
11
β
1
→
δ
1
}, {
a
41
β
1
→
δ
1
}, {
a
51
β
1
→
δ
1
}, {
a
71
β
1
→
δ
1
}, {
a
81
β
1
→
δ
1
}, and {
a
91
β
1
→
δ
1
} meet the execution condition and can be executed. Objects a
21, a
31, and a
61 are not in cell 1, which means the second, the third, and the sixth records do not contain I
1. The subrules {
a
21
β
1
→
δ
1
}, {
a
31
β
1
→
δ
1
}, and {
a
61
β
1
→
δ
1
} do not meet the execution condition and cannot be executed. Initially, 2 copies of β
1 are in cell 1 indicating that the first item needs to appear in at least 2 records to make the itemset {
I
1
} a frequent 1-itemset. Each execution of a subrule consumes one β
1. Therefore, 2 of subrules among {
a
11
β
1
→
δ
1
}, {
a
41
β
1
→
δ
1
}, {
a
51
β
1
→
δ
1
}, {
a
71
β
1
→
δ
1
}, {
a
81
β
1
→
δ
1
}, and {
a
91
β
1
→
δ
1
} can be executed in nondeterministic flat maximally parallel. Through the execution of 2 such subrules, both of the 2 copies of β
1 are consumed and 2 copies of δ
1 are generated. The detection processes of other candidate frequent 1-itemsets are performed in the same way. After the detection processes, β
1
2, β
2
2, β
3
2, β
4
2, and β
5
2 are consumed, and δ
1
2, δ
2
2, δ
3
2, δ
4
2, and δ
5
2 are generated.Ruler
12 is then executed to process the results obtained by rule r
13. The 1-itemset {
I
1
} is again taken as an example. All of the 2 copies of β
1 have been consumed, subrule {
(
δ
1
2
)
¬
β
1
→
α
1
,
g
o
} is executed to put an object α
1 to cells 2 and 6 to indicate that the itemset {
I
1
} is a frequent 1-itemset and to activate the computation in cell 2. Subrules {
(
δ
2
2
)
¬
β
3
→
α
2
,
g
o
}, {
(
δ
3
2
)
¬
β
3
→
α
3
,
g
o
}, {
(
δ
4
2
)
¬
β
4
→
α
4
,
g
o
}, and {
(
δ
5
2
)
¬
β
5
→
α
5
,
g
o
} are also executed to put objects α
2, α
3, α
4, and α
5 to cells 2 and 6 to indicate that the itemsets {
I
2
}, {
I
3
}, {
I
4
}, and {
I
5
} are frequent 1-itemsets and to activate the computation in cell 2.Frequent 2-Itemsets Generation. Within cell 2, rule r
21 is executed to obtain all candidate frequent 2-itemsets. The detection process of the candidate frequent 2-itemset {
I
1
,
I
2
} is taken as an example. Objects α
1 and α
2 are in cell 2, which means itemsets {
I
1
} and {
I
2
} are frequent 1-itemsets. Subrule {
(
)
α
1
α
2
θ
2
¬
β
12
2
→
β
12
2
} is executed to generate β
12
2. The presence of β
12
2 means the 2-itemset {
I
1
,
I
2
} is a candidate frequent 2-itemset, and both I
1 and I
2 need to appear together in at least 2 records for the itemset {
I
1
,
I
2
} to be a frequent 2-itemset. The detection processes of the other candidate frequent 2-itemsets are performed in the same way. After the detection processes, objects β
12
2, β
13
2, β
14
2, β
15
2, β
23
2, β
24
2, β
25
2, β
34
2, β
35
2, and β
45
2 are generated.Ruler
22 is executed to delete the objects α
1, α
2, α
3, α
4, and α
5 that are not needed anymore.Ruler
24 is executed to detect all frequent 2-itemsets. Objects a
11 and a
12, a
41 and a
42, a
81 and a
82, and a
91 and a
92 are in cell 2, which means the first, the fourth, the eighth, and the ninth records contain both I
1 and I
2. The subrules {
(
β
12
)
a
11
a
12
→
δ
12
}, {
(
β
12
)
a
41
a
42
→
δ
12
}, {
(
β
12
)
a
81
a
82
→
δ
12
}, and {
(
β
12
)
a
91
a
92
→
δ
12
} meet the execution condition and can be executed. Objects a
21 and a
22, a
31 and a
32, a
51 and a
52, a
61 and a
62, or a
71 and a
72 are not both in cell 2, which means the second, the third, the fifth, the sixth, and the seventh records do not contain both I
1 and I
2. The subrules {
(
β
12
)
a
21
a
22
→
δ
12
}, {
(
β
12
)
a
31
a
32
→
δ
12
}, {
(
β
12
)
a
51
a
52
→
δ
12
}, {
(
β
12
)
a
61
a
62
→
δ
12
}, and {
(
β
12
)
a
71
a
72
→
δ
12
} do not meet the execution condition and cannot be executed. Initially, 2 copies of β
12 are in cell 2 indicating that both I
1 and I
2 need to appear together in at least 2 records for the itemset {
I
1
,
I
2
} to be a frequent 2-itemset. Each execution of these subrules consumes one β
12. Therefore, 2 subrules among {
(
β
12
)
a
11
a
12
→
δ
12
}, {
(
β
12
)
a
41
a
42
→
δ
12
}, {
(
β
12
)
a
81
a
82
→
δ
12
}, and {
(
β
12
)
a
91
a
92
→
δ
12
} can be executed. After the execution, 2 copies of β
12 are consumed and 2 copies of δ
12 are generated. The detection processes of other candidate frequent 2-itemsets are performed in the same way. After the detection processes, objects β
12
2, β
13
2, β
14, β
15
2, β
23
2, β
24
2, β
25
2, and β
35 are consumed, and objects δ
12
2, δ
13
2, δ
14, δ
15
2, δ
23
2, δ
24
2, δ
25
2, and δ
35 are generated.Ruler
23 is executed to process the results obtained by rule r
24. The 2-itemset {
I
1
,
I
2
} is again taken as an example. All of the 2 copies of β
12 have been consumed by rule r
24, subrule {
(
δ
12
2
)
¬
β
12
→
α
12
,
g
o
} is executed to put an object α
12 to cells 3 and 6 to indicate that the itemset {
I
1
,
I
2
} is a frequent 2-itemset and to activate the computation in cell 3. Subrules {
(
δ
13
2
)
¬
β
13
→
α
13
,
g
o
}, {
(
δ
15
2
)
¬
β
15
→
α
15
,
g
o
}, {
(
δ
23
2
)
¬
β
23
→
α
23
,
g
o
}, {
(
δ
24
2
)
¬
β
24
→
α
24
,
g
o
}, and {
(
δ
25
2
)
¬
β
25
→
α
25
,
g
o
} are also executed, which put objects α
13, α
15, α
23, α
24, and α
25 to cells 3 and 6 to indicate that the itemsets {
I
1
,
I
3
}, {
I
1
,
I
5
}, {
I
2
,
I
3
}, {
I
2
,
I
4
}, and {
I
2
,
I
5
} are frequent 2-itemsets and to activate the computation in cell 3.The 4 rules in each cellh for 3
≤
h
≤
5 are executed in ways similar to those in cell 2. The rules in these cells detect the frequent h-itemsets for 3
≤
h
≤
5. After the computation halts, the objects α
1, α
2, α
3, α
4, α
5, α
12, α
13, α
15, α
23, α
24, α
25, α
123, and α
125 are stored in cell 6, which means {
I
1
}
,
{
I
2
}
,
{
I
3
}
,
{
I
4
}
,
{
I
5
}
,
{
I
1
,
I
2
}
,
{
I
1
,
I
3
}
,
{
I
1
,
I
3
}
,
{
I
2
,
I
3
}
,
{
I
2
,
I
4
}, {
I
2
,
I
5
}
,
{
I
1
,
I
2
,
I
3
}, and {
I
1
,
I
2
,
I
5
} are all frequent itemsets in this database.The change of objects in the computation processes is listed in Tables3–6.Table 3
Generation of frequent 1-itemsets.
r
i
j
C
e
l
l
0
C
e
l
l
1
C
e
l
l
6
0
a
11
a
12
a
15
a
22
a
24
a
32
a
33
a
41
a
42
a
44
a
51
a
53
a
62
a
63
a
71
a
73
a
81
a
82
a
83
a
85
a
91
a
92
a
93
θ
2
1
a
11
a
12
a
15
a
22
a
24
a
32
a
33
a
41
a
42
(
r
01
)
a
44
a
51
a
53
a
62
a
63
a
71
a
73
a
81
a
82
a
83
a
85
a
91
a
92
a
93
θ
2
2
a
11
a
12
a
15
a
22
a
24
a
32
a
33
a
41
a
42
a
44
a
51
a
53
a
62
a
63
a
71
a
73
a
81
a
82
a
83
a
85
a
91
a
92
a
93
β
1
2
β
2
2
β
3
2
β
4
2
β
5
2
(
r
11
)
3
a
32
a
42
a
51
a
62
a
63
a
71
a
73
a
81
a
82
a
83
a
91
a
92
a
93
δ
1
2
δ
2
2
δ
3
2
δ
4
2
δ
5
2
(
r
13
)
4
a
32
a
42
a
51
a
62
a
63
a
71
a
73
a
81
a
82
α
1
α
2
α
3
α
4
α
5
a
83
a
91
a
92
a
93
(
r
12
)Table 4
Generation of frequent 2-itemsets.
r
i
j
Cell 2
Cell 6
4
α
1
α
2
α
3
α
4
α
5
θ
2
α
1
α
2
α
3
α
4
α
5
a
11
a
12
a
15
a
22
a
24
a
32
a
33
a
41
a
42
a
44
a
51
a
53
a
62
a
63
a
71
a
73
a
81
a
82
a
83
a
85
a
91
a
92
a
93
5
α
1
α
2
α
3
α
4
α
5
β
25
2
β
34
2
β
35
2
β
45
2
θ
2
α
1
α
2
α
3
α
4
α
5
a
11
a
12
a
15
a
22
a
24
a
32
a
33
a
41
a
42
a
44
a
51
a
53
a
62
a
63
a
71
a
73
a
81
a
82
a
83
a
85
a
91
a
92
a
93
r
21
6
β
12
2
β
13
2
β
14
2
β
15
2
β
23
2
β
24
2
β
25
2
β
34
2
β
35
2
β
45
2
θ
2
α
1
α
2
α
3
α
4
α
5
a
11
a
12
a
15
a
22
a
24
a
32
a
33
a
41
a
42
a
44
a
51
a
53
a
62
a
63
a
71
a
73
a
81
a
82
a
83
a
85
a
91
a
92
a
93
r
22
7
δ
12
2
δ
13
2
δ
14
β
14
δ
15
2
δ
23
2
δ
24
2
δ
25
2
β
34
2
δ
35
β
35
β
45
2
θ
2
α
1
α
2
α
3
α
4
α
5
a
11
a
12
a
15
a
22
a
24
a
32
a
33
a
41
a
42
a
44
a
51
a
53
a
62
a
63
a
71
a
73
a
81
a
82
a
83
a
85
a
91
a
92
a
93
r
24
8
θ
2
α
1
α
2
α
3
α
4
α
5
α
12
a
11
a
12
a
15
a
22
a
24
a
32
a
33
a
41
a
42
a
44
a
51
a
53
a
62
a
63
a
71
a
73
a
81
a
82
a
83
a
85
a
91
a
92
a
93
r
23
α
13
α
15
α
23
α
24
α
25Table 5
Generation of frequent 3-itemsets.
r
i
j
Cell 3
Cell 6
8
α
12
α
13
α
15
α
23
α
24
α
25
θ
2
α
1
α
2
α
3
α
4
α
5
α
12
a
11
a
12
a
15
a
22
a
24
a
32
a
33
a
41
a
42
a
44
a
51
a
53
a
62
a
63
a
71
a
73
a
81
a
82
a
83
a
85
a
91
a
92
a
93
α
13
α
15
α
23
α
24
α
25
9
α
12
α
13
α
15
α
23
α
24
α
25
β
123
2
β
125
2
β
135
2
β
234
2
β
235
2
β
245
2
θ
2
α
1
α
2
α
3
α
4
α
5
α
12
a
11
a
12
a
15
a
22
a
24
a
32
a
33
a
41
a
42
a
44
a
51
a
53
a
62
a
63
a
71
a
73
a
81
a
82
a
83
a
85
a
91
a
92
a
93
r
31
α
13
α
15
α
23
α
24
α
25
10
β
123
2
β
125
2
β
135
2
β
234
2
β
235
2
β
245
2
θ
2
α
1
α
2
α
3
α
4
α
5
α
12
a
11
a
12
a
15
a
22
a
24
a
32
a
33
a
41
a
42
a
44
a
51
a
53
a
62
a
63
a
71
a
73
a
81
a
82
a
83
a
85
a
91
a
92
a
93
r
32
α
13
α
15
α
23
α
24
α
25
11
δ
123
2
δ
125
2
δ
135
β
135
β
234
2
δ
235
β
235
β
245
2
θ
2
α
1
α
2
α
3
α
4
α
5
α
12
a
11
a
12
a
15
a
22
a
24
a
32
a
33
a
41
a
42
a
44
a
51
a
53
a
62
a
63
a
71
a
73
a
81
a
82
a
83
a
85
a
91
a
92
a
93
r
34
α
13
α
15
α
23
α
24
α
25
12
θ
2
α
1
α
2
α
3
α
4
α
5
α
12
a
11
a
12
a
15
a
22
a
24
a
32
a
33
a
41
a
42
a
44
a
51
a
53
a
62
a
63
a
71
a
73
a
81
a
82
a
83
a
85
a
91
a
92
a
93
r
33
α
13
α
15
α
23
α
24
α
25
α
123
α
125Table 6
Generation of frequent 4-itemsets.
r
i
j
Cell 4
Cell 6
12
α
123
α
125
θ
2
α
1
α
2
α
3
α
4
α
5
α
12
a
11
a
12
a
15
a
22
a
24
a
32
a
33
a
41
a
42
a
44
a
51
a
53
a
62
a
63
a
71
a
73
a
81
a
82
a
83
a
85
a
91
a
92
a
93
α
13
α
15
α
23
α
24
α
25
α
123
α
125
13
α
123
α
125
β
1235
2
θ
2
α
1
α
2
α
3
α
4
α
5
α
12
a
11
a
12
a
15
a
22
a
24
a
32
a
33
a
41
a
42
a
44
a
51
a
53
a
62
a
63
a
71
a
73
a
81
a
82
a
83
a
85
a
91
a
92
a
93
r
41
α
13
α
15
α
23
α
24
α
25
α
123
α
125
14
β
1235
2
θ
2
α
1
α
2
α
3
α
4
α
5
α
12
a
11
a
12
a
15
a
22
a
24
a
32
a
33
a
41
a
42
a
44
a
51
a
53
a
62
a
63
a
71
a
73
a
81
a
82
a
83
a
85
a
91
a
92
a
93
r
42
α
13
α
15
α
23
α
24
α
25
α
123
α
125
15
δ
1235
β
1235
θ
2
α
1
α
2
α
3
α
4
α
5
α
12
a
11
a
12
a
15
a
22
a
24
a
32
a
33
a
41
a
42
a
44
a
51
a
53
a
62
a
63
a
71
a
73
a
81
a
82
a
83
a
85
a
91
a
92
a
93
r
44
α
13
α
15
α
23
α
24
α
25
α
123
α
125
16
θ
2
α
1
α
2
α
3
α
4
α
5
α
12
a
11
a
12
a
15
a
22
a
24
a
32
a
33
a
41
a
42
a
44
a
51
a
53
a
62
a
63
a
71
a
73
a
81
a
82
a
83
a
85
a
91
a
92
a
93
r
43
α
13
α
15
α
23
α
24
α
25
α
123
α
125


## 5. Computational Experiments

Two databases from the UCI Machine Learning Repository [23] are used to conduct computational experiments. Computational results on these two databases are reported in this section.


### 5.1. Results on the Congressional Voting Records Database

The Congressional Voting Records database [23] is used to test the performance of ECTPPI-Apriori. This database contains 435 records and 17 attributes (fields). The first attribute is the party that the voter voted for and the 2nd to the 17th attributes are sixteen characteristics of each voter identified by the Congressional Quarterly Almanac. The first attribute has two values, Democrats or Republican, and each of the 2nd to the 17th attributes has 3 values: yea, nay, and unknown disposition. The frequent itemsets of these attribute values need to be identified; that is, the problem is to find the attribute values which always appear together.Initially, the database is preprocessed. Each attribute value is taken as a new attribute. In this way, each new attribute has only two values: yes or no. After preprocessing, each record in the database has2
×
1
+
3
×
(
17
-
1
)
=
50 attributes. ECTPPI-Apriori then can be used to discover the frequent itemsets. In this experiment, one itemset is called a frequent itemset if it appeared in more than 40% of all records; that is, the support count threshold is k
=
174 (435
×
40
%). The frequent itemsets obtained by ECTPPI-Apriori are listed in Table 7.Table 7
The frequent itemsets identified by ECTPPI-Apriori for the Congressional Voting Records database.
Size of frequent itemset
The corresponding frequent itemsets
1
{
2
}
;
{
3
}
;
{
5
}
;
{
6
}
;
{
8
}
;
{
9
}
;
{
12
}
;
{
14
}
;
{
15
}
;
{
17
}
;
{
18
}
;
{
21
}
;
{
23
};
{
24
}
;
{
26
}
;
{
27
}
;
{
29
}
;
{
30
}
;
{
32
}
;
{
35
}
;
{
38
}
;
{
39
}
;
{
41
}
;
{
42
}
;
{
45
};
{
47
}
;
{
48
}
2
{
2,9
}
;
{
2,14
}
;
{
2,17
}
;
{
2,21
}
;
{
2,24
}
;
{
2,27
}
;
{
2,38
}
;
{
2,41
};
{
5,18
}
;
{
9,14
}
;
{
9,17
}
;
{
9,21
}
;
{
9,24
}
;
{
9,27
}
;
{
9,38
}
;
{
14,17
};
{
14,21
}
;
{
14,24
}
;
{
14,27
}
;
{
14,38
}
;
{
14,41
}
;
{
15,18
}
;
{
15,29
};
{
15,42
}
;
{
17,21
}
;
{
17,24
}
;
{
17,27
}
;
{
17,38
}
;
{
18,29
}
;
{
18,39
};
{
18,42
}
;
{
18,47
}
;
{
21,24
}
;
{
21,27
}
;
{
21,38
}
;
{
24,27
}
;
{
24,38
};
{
24,41
}
;
{
29,42
}
;
{
39,42
}
;
{
42,47
}
3
{
2,9
,
14
}
;
{
2,9
,
17
}
;
{
2,9
,
21
}
;
{
2,9
,
24
}
;
{
2,9
,
38
}
;
{
2,14,17
};
{
2,14,21
}
;
{
2,14,24
}
;
{
2,14,27
}
;
{
2,14,38
}
;
{
2,14,41
};
{
2,17,21
}
;
{
2,17,24
}
;
{
2,21,24
}
;
{
2,24,27
}
;
{
2,24,38
}
;
{
9,14,17
};
{
9,14,21
}
;
{
9,14,24
}
;
{
9,14,38
}
;
{
9,17,24
}
;
{
9,21,24
}
;
{
9,24,38
};
{
14,17,21
}
;
{
14,17,24
}
;
{
14,21,24
}
;
{
14,24,27
}
;
{
14,24,38
};
{
15,18,29
}
;
{
15,18,42
}
;
{
17,21,24
}
;
{
17,24,27
}
;
{
17,24,38
}
4
{
2,9
,
14,17
}
;
{
2,9
,
14,21
}
;
{
2,9
,
14,24
}
;
{
2,9
,
14,38
}
;
{
2,9
,
17,24
};
{
2,9
,
21,24
}
;
{
2,14,17,21
}
;
{
2,14,17,24
}
;
{
2,14,21,24
};
{
2,14,24,38
}
;
{
2,17,21,24
}
;
{
9,14,17,24
}
;
{
9,14,21,24
};
{
14,17,21,24
}
;
{
2,9
,
14,17,24
}
;
{
2,9
,
14,21,24
}
5
{
2,14,17,21,24
}
6
⌀


### 5.2. Results on the Mushroom Database

The Mushroom database [23] is also used to test ECTPPI-Apriori. This database contains 8124 records. The 8124 records are numbered orderly from 1 to 8124. Each record represents one mushroom and has 23 attributes (fields). The first attribute is the poisonousness of the mushroom and the 2nd to the 23rd attributes are 22 characteristics of the mushrooms. Each of the attributes has 2 to 12 values. The frequent itemsets of these attribute values need to be found; that is, the problem is to find the attribute values which always appear together.Initially, the database is preprocessed. Each attribute value is taken as a new attribute. In this way, each new attribute has only two values, yes or no. After preprocessing, each record has 118 attributes. ECTPPI-Apriori then can be used to discover the frequent itemsets. In this experiment, one itemset is a frequent itemset if it appears in more than 40 percent of all records; that is, the support count threshold isk
=
3250 (8124
×
40
%). The frequent itemsets obtained by ECTPPI-Apriori are listed in Table 8.Table 8
The frequent itemsets identified by ECTPPI-Apriori for the Mushroom database.
Size of frequent itemset
The corresponding frequent itemsets
1
{
1
}
;
{
2
}
;
{
3
}
;
{
4
}
;
{
5
}
2
{
1,2
}
;
{
1,3
}
;
{
1,4
}
;
{
1,5
}
;
{
2,3
}
;
{
2,4
}
;
{
2,5
}
;
{
3,4
};
{
3,5
}
;
{
4,5
}
3
{
1,2
,
3
}
;
{
1,2
,
5
}
;
{
1,3
,
5
}
;
{
2,3
,
4
}
;
{
2,3
,
5
}
4
{
1,2
,
3,5
}
5
⌀


## 5.1. Results on the Congressional Voting Records Database

The Congressional Voting Records database [23] is used to test the performance of ECTPPI-Apriori. This database contains 435 records and 17 attributes (fields). The first attribute is the party that the voter voted for and the 2nd to the 17th attributes are sixteen characteristics of each voter identified by the Congressional Quarterly Almanac. The first attribute has two values, Democrats or Republican, and each of the 2nd to the 17th attributes has 3 values: yea, nay, and unknown disposition. The frequent itemsets of these attribute values need to be identified; that is, the problem is to find the attribute values which always appear together.Initially, the database is preprocessed. Each attribute value is taken as a new attribute. In this way, each new attribute has only two values: yes or no. After preprocessing, each record in the database has2
×
1
+
3
×
(
17
-
1
)
=
50 attributes. ECTPPI-Apriori then can be used to discover the frequent itemsets. In this experiment, one itemset is called a frequent itemset if it appeared in more than 40% of all records; that is, the support count threshold is k
=
174 (435
×
40
%). The frequent itemsets obtained by ECTPPI-Apriori are listed in Table 7.Table 7
The frequent itemsets identified by ECTPPI-Apriori for the Congressional Voting Records database.
Size of frequent itemset
The corresponding frequent itemsets
1
{
2
}
;
{
3
}
;
{
5
}
;
{
6
}
;
{
8
}
;
{
9
}
;
{
12
}
;
{
14
}
;
{
15
}
;
{
17
}
;
{
18
}
;
{
21
}
;
{
23
};
{
24
}
;
{
26
}
;
{
27
}
;
{
29
}
;
{
30
}
;
{
32
}
;
{
35
}
;
{
38
}
;
{
39
}
;
{
41
}
;
{
42
}
;
{
45
};
{
47
}
;
{
48
}
2
{
2,9
}
;
{
2,14
}
;
{
2,17
}
;
{
2,21
}
;
{
2,24
}
;
{
2,27
}
;
{
2,38
}
;
{
2,41
};
{
5,18
}
;
{
9,14
}
;
{
9,17
}
;
{
9,21
}
;
{
9,24
}
;
{
9,27
}
;
{
9,38
}
;
{
14,17
};
{
14,21
}
;
{
14,24
}
;
{
14,27
}
;
{
14,38
}
;
{
14,41
}
;
{
15,18
}
;
{
15,29
};
{
15,42
}
;
{
17,21
}
;
{
17,24
}
;
{
17,27
}
;
{
17,38
}
;
{
18,29
}
;
{
18,39
};
{
18,42
}
;
{
18,47
}
;
{
21,24
}
;
{
21,27
}
;
{
21,38
}
;
{
24,27
}
;
{
24,38
};
{
24,41
}
;
{
29,42
}
;
{
39,42
}
;
{
42,47
}
3
{
2,9
,
14
}
;
{
2,9
,
17
}
;
{
2,9
,
21
}
;
{
2,9
,
24
}
;
{
2,9
,
38
}
;
{
2,14,17
};
{
2,14,21
}
;
{
2,14,24
}
;
{
2,14,27
}
;
{
2,14,38
}
;
{
2,14,41
};
{
2,17,21
}
;
{
2,17,24
}
;
{
2,21,24
}
;
{
2,24,27
}
;
{
2,24,38
}
;
{
9,14,17
};
{
9,14,21
}
;
{
9,14,24
}
;
{
9,14,38
}
;
{
9,17,24
}
;
{
9,21,24
}
;
{
9,24,38
};
{
14,17,21
}
;
{
14,17,24
}
;
{
14,21,24
}
;
{
14,24,27
}
;
{
14,24,38
};
{
15,18,29
}
;
{
15,18,42
}
;
{
17,21,24
}
;
{
17,24,27
}
;
{
17,24,38
}
4
{
2,9
,
14,17
}
;
{
2,9
,
14,21
}
;
{
2,9
,
14,24
}
;
{
2,9
,
14,38
}
;
{
2,9
,
17,24
};
{
2,9
,
21,24
}
;
{
2,14,17,21
}
;
{
2,14,17,24
}
;
{
2,14,21,24
};
{
2,14,24,38
}
;
{
2,17,21,24
}
;
{
9,14,17,24
}
;
{
9,14,21,24
};
{
14,17,21,24
}
;
{
2,9
,
14,17,24
}
;
{
2,9
,
14,21,24
}
5
{
2,14,17,21,24
}
6
⌀


## 5.2. Results on the Mushroom Database

The Mushroom database [23] is also used to test ECTPPI-Apriori. This database contains 8124 records. The 8124 records are numbered orderly from 1 to 8124. Each record represents one mushroom and has 23 attributes (fields). The first attribute is the poisonousness of the mushroom and the 2nd to the 23rd attributes are 22 characteristics of the mushrooms. Each of the attributes has 2 to 12 values. The frequent itemsets of these attribute values need to be found; that is, the problem is to find the attribute values which always appear together.Initially, the database is preprocessed. Each attribute value is taken as a new attribute. In this way, each new attribute has only two values, yes or no. After preprocessing, each record has 118 attributes. ECTPPI-Apriori then can be used to discover the frequent itemsets. In this experiment, one itemset is a frequent itemset if it appears in more than 40 percent of all records; that is, the support count threshold isk
=
3250 (8124
×
40
%). The frequent itemsets obtained by ECTPPI-Apriori are listed in Table 8.Table 8
The frequent itemsets identified by ECTPPI-Apriori for the Mushroom database.
Size of frequent itemset
The corresponding frequent itemsets
1
{
1
}
;
{
2
}
;
{
3
}
;
{
4
}
;
{
5
}
2
{
1,2
}
;
{
1,3
}
;
{
1,4
}
;
{
1,5
}
;
{
2,3
}
;
{
2,4
}
;
{
2,5
}
;
{
3,4
};
{
3,5
}
;
{
4,5
}
3
{
1,2
,
3
}
;
{
1,2
,
5
}
;
{
1,3
,
5
}
;
{
2,3
,
4
}
;
{
2,3
,
5
}
4
{
1,2
,
3,5
}
5
⌀


## 6. Conclusions

An improved Apriori algorithm, called ECTPPI-Apriori, is proposed for frequent itemsets mining. The algorithm uses a parallel mechanism in the ECPI tissue-like P system. The time complexity of ECTPPI-Apriori is improved toO
(
t
) compared to other parallel Apriori algorithms. Experimental results, using the Congressional Voting Records database and the Mushroom database, show that ECTPPI-Apriori performs well in frequent itemsets mining. The results give some hints to improve conventional algorithms by using the parallel mechanism of membrane computing models.For further research, it is of interests to use some other interesting neural-like membrane computing models, such as the spiking neural P systems (SN P systems) [8], to improve the Apriori algorithm. SN P systems are inspired by the mechanism of the neurons that communicate by transmitting spikes. The cells in SN P systems are neurons that have only one type of objects called spikes. Zhang et al. [24, 25], Song et al. [26], and Zeng et al. [27] provided good examples. Also, some other data mining algorithms can be improved by using parallel evolution mechanisms and graph membrane structures, such as spectral clustering, support vector machines, and genetic algorithms [1].



---

*Source: 6978146-2017-02-19.xml*