2016 3rd International Conference on Soft Computing & Machine Intelligence

A Novice approach for web document clustering using FP Growth based Fuzzy
Particle Swarm Optimization

Raja Varma Pamba Dr Elizabeth Sherly

Research Scholar Professor & Head, VRCLC
School of Computer Sciences, M.G. University IIITMK
Kottayam, India Trivandrum, India
pambaraj@[Link] sherly@[Link]

Abstract—The success of any Information Retrieval system of similar nature. The algorithm of FPGrowth helps find
relies upon extracting relevant pages of similar knowledge frequent sets which are indirectly a hint for the set of classes
matching the requirements of the user. The traditional best of to which documents has to be clustered. Second prime
all statistical methodologies fails in conquering the issues of reason to hire the concept of Fuzzy Particle swarm
relevancy and redundancy of web pages retrieved. In this optimization was to help optimize the resultant item sets
paper we propose a novel architecture, FP Growth based which in this algorithm is presumed as the swarm/particle for
Fuzzy Particle swarm optimization which captures the the rest of the algorithm for clustering. The usage of
dynamicity and fuzziness of web documents. With FPGrowth FuzzyPSO clearly outlaw the FCM performance with its
we attain a much lesser but frequent sets recurring repeatedly.
global and local search mechanism. The position matrix in
Indirectly the FPGrowth reduce the redundancy of the search
space. These reduced frequent sets are optimized efficiently
FuzzyPSO is same as Membership matrix in FCM. So is the
with evolutionary nature inspired PSO algorithm. This case of objective function in FCM used is the very same as
scenario of divide and conquer strategy of FP Growth to fitness function .
reduce the list of transactions to frequent items and being Documents in the FuzzyPSO are strongly correlated due to
optimised using FuzzyPSO is extended to web document its local and global search mechanism however traditional
[Link] major contribution in this paper is the FuzzyPSO clustering are sensitive to the initialization of
generation of number of clusters and frequent item swarm and initial number of clusters and center. The
sets(particles) achieved via FP Growth which in rest of all proposed approach has a smooth dive over these issues by
algorithms are user given and better optimized accuracy in concatenating the benefits of FPGrowth and FuzzyPSO to
retrieval using FuzzyPSO avoiding the limitation of local resolve all those issues discussed. However, to the best of
minima of FCM completely with the global and local search
[Link] evaluation reveals an optimised results for the
the authors knowledge, FPgrowth based fuzzyPSO has not
proposed hybrid approach. been used to cluster text documents. In this research, an
efficient clustering algorithm based on FPGrowth based
Keywords-frequent pattern; swarm; fuzzy particle swarm FuzzyPSO is studied and results observed are highlighted.
optimisation.
II. PROBLEM DESCRIPTION
I. INTRODUCTION Taking into account above facts the Problem statement
can be defined as follows:
All information retrieval system that exploit the
Given a set of documents
redundancy of data on the web has to first identify relevant
similarly matching sets of documents catering to the needs of 1. D= {d1, d2, d3…dn}
the user. This grouping of relevant sets of similar attributes
to a group is known as clustering[4][12].This paper presents 2. Number of clusters and frequent items sets (particle)
a hybrid model fusing in the concepts of FP Growth for computed using FPGrowth.
finding frequent item sets with FuzzyPSO. The traditional
3. Optimizing the resultant reduced transaction sets
PSO is primarily omitted from the study as it doesn’t capture
with FuzzyPSO .
the dynamicity of the web in totality. The choice of
FPGrowth is due to its innate nature of divide and conquer 4. A fitness function that evaluates the cluster quality
strategy to help reduce a list of huge transaction to a small based upon Euclidean Distance.
bunch of conditional frequent patterns, which are indeed
easy to handle. Extending this concept to clustering ,the 5. Evaluation of clustering .
initial focus was on reducing the transactions (or in terms of
web parlance sets of documents retrieved as part of
search).The FPGrowth help find set of frequent documents

978-1-5090-3696-7/16 $31.00 © 2016 IEEE 90

DOI 10.1109/ISCMI.2016.36
wants to assign the given documents to the relevant clusters Clustering and P be the remaining list of particles in
efficiently i.e. either maximizing or minimizing the Fitness the population or the search space. Call
function. inserttree([p|P],T), which is performed as follows.
III. PROPOSED METHODOLOGY If T has a child N such that
[Link]name=[Link]namethenincrementNby1;else
A. FP GROWTH ALGORITHM[1] create a new node N,with a value =1,its parent link
Data mining technique called association analysis, which linked to T,and its node link linked to the nodes with
is useful for discovering interesting relationship hidden in same [Link] P is nonempty,call
large data set also useful for clustering. There are two broad inserttree(P,N)recursively.
principles use for association analysis [1].One is Apriori and
another is Frequent Pattern(FP) growth principle. FP-growth C. FP GROWTH ALGORITHM ,Mining frequent patterns
is a divide and conquer strategy that mines a complete set of with FP tree by pattern fragment growth[1]
frequent item sets without candidate generation. FP-growth Input:A database D, represented by FP tree constructed
outperform Apriori because Apriori incurs considerable I/O according to Algorithm 1 and minimum support
overhead since it requires making several passes over the threshold,
transaction data set. For finding number of clusters and Output:Set of Frequent Patterns
initial cluster centers which are the major limitations of FCM
and FuzzyPSO, FP-growth algorithm for finding frequent Method:call FP-growth(FP-tree,null)
item-sets has been used. The frequent sets generated are of
frequency greater than the minimum support supplied by the 1. if Tree T contains a single prefix path
user. In the generated frequent sets of documents, the terms
2. then {
are taken to be the transactions and the documents are the
items of the transactions. In this way the frequent sets 3. let P be the single prefix path part of tree
generated are the ones which have particular set of terms in
common and hence are closely related. This helps by 4. let Q be the multipath part with the top branching
deciding the number of clusters and also the centers of these node replaced by a null root
clusters which is simply the centroid of the respective
frequent item-set- to generate frequent item sets ,it needs to 5. for each combination of the nodes in the path P do
undergo two stages, as follows:
6. generate pattern Ґ with support=minimum
B. FP TREE CONSTRUCTION[1] support of nodes in 
Let be a set of items and a transaction database is a
transaction which contains a set of items in I. This is 7. let fpset(P) be the set of pattens so generated }
assumed equivalent to term document matrix. In this
Transactions are considered equivalent to Documents and 8. else let Q be tree
items equivalent to keywords or terms as extracted. FPTREE
algorithm is as follows: 9. for each item in Q do {
Input: A Term Document Matrix( considered as Transaction 10. generate pattern
database) and a minimum support threshold in this
proposed approach. =ai U  (1)
Output: frequent pattern tree with support=.support construct  conditional pattern
base and then conditional FP Tree
Method:
11. let fpset(Q) be the set of patterns so generated } .
1. Two main scanning. First scanning of the Term
Document Matrix or Transaction database. Collect D. FUZZY PARTICLE SWARM
the set of frequent items (F) and their support counts. OPTIMISATION(FPSO)[2]
Sort F according to descending support count as Flist,
the list of frequent items. The base version Particle swarm optimization[2][3][4]is
a stochastic population based optimization tool inspired by
2. Create the root of an FP-tree,T, and label it as null . bird flocking and fish schooling introduced by Kennedy and
For each document considered as transaction ITran in [Link] technique is based on iterations till the
D do the following, conditions are met and when values are saturated with
iterations.
Select and sort the frequent items in ITran according The fuzzy clustering of objects is described by a fuzzy
to the order of Flist, . Let the sorted frequent list in matrix  with n rows and c columns in which n is the number
ITran be p[P] , where p is the first particle as per the of data objects and c is the number of clusters. The element
nomenclature used in Fuzzy Particle Swarm in the ith row and jth column , indicates the degree of

91
association or membership function of the ith object with the
jth cluster. The characters of  are as follows: (7)

Based upon the fitness function evaluated ,the particle

with least fitness function can be eliminated to help improve
the search space. Finally the FpFPSO Clustering is executed
upon the resultant set to fine tune the elements for clustering.
Figure 1 summarizes the whole of the methodology briefly

in which, m (m > 1) is a scalar termed the weighting

exponent and controls the fuzziness of the resulting clusters
and dij is the Euclidian distance from object oi to the cluster
center zj. The zj, centroid of the jth cluster, is obtained using
Eq. (6).

Pang [Link] proposed a modified [5]The algorithmic flow

in FuzzyPSO[5][6][7][8][9] starts with a population of
particles and initial number of clusters which are the Figure 1. Proposed Methodology
outcomes of FP growth algorithm[1] whose positions
represent the potential solutions for the studied problems and IV. EXPERIMENTAL RESULTS
velocities are randomly initialized in the search space. The
position matrix X is redefined in this proposed algorithm, A. PARAMETER SETTINGS
represent the fuzzy relation(membership function) between
the frequent items sets(particles) in columns and cluster In order to optimize the performance of the
center as rows. The position matrix is given below : FPSO[9][10][11] , fine tuning has been performed and best
values for their parameters are selected. Based on
experimental results these algorithms perform best under the
following settings: c1 = c2 = 2.0,P = 50, w = [Link] FPSO
terminating condition in Algorithm 2 is the maximum when
the algorithm cannot improve the gbest in 1000 consecutive
iterations, the FPSO terminating condition in Algorithm 3 is
the maximum number of iterations 1000 or no changes in
gbest in 200 consecutive iterations, and the FCM terminating
condition in Algorithm 3 is the number of iterations 5. Also
the FpFPSO terminating condition in Algorithm 3 is when
In each of its iteration ,the search for optimal solution is the algorithm cannot improve the gbest in 2 consecutive
executed by updating the particle velocities and its position. iterations. In all of algorithms m, the weighting exponent, is
The fitness value of each frequent item sets(particles or set to 2. For m=1.5 and m=2 the values are the same.
swarm) is determined using a fitness function based on
Euclidean Distance measure. The velocity of each particle is
updated using two best position , Individual best position B. EXPERIMENTAL RESULTS
and social best solution .The individual best position is the Few documents split from the articles of data retrieval
best position that particle has visited so far and is the best and information retrieval where given as [Link] standard
position the swarm has visited so far. A particle velocity and
position are updated as follows:

92
IR metrics to access the quality was used to evaluate our that it avoids initial particle selection and initialization of
[Link] algorithms are implemented using R clusters by users.
[Link] for each document the preprocessing has
been done,and tfidf matrix is [Link] the FPGrowth
with the support specified by user is given to divide and ACKNOWLEDGMENT
conquer the transaction database(term document To my guide Dr Elizabeth Sherly for her all time support
matrix)finally to obtain the relevant frequent [Link] and guidance in the work. And my sincere thanks to all
frequent sets are used for FPTree representation of the found valuable comments by the reviewers to help improvise my
frequent sets and they are considered as initial clusters for research to its next level.
FuzzyPSO,ie how many frequent sets found are equivalent to
the initial number of [Link] is used on the sets
which act as particles,in this case with 23 clusters and REFERENCES
according to the fuzzy nature gives back seven clusters after
fitness value evaluation and [Link] fitness value used [1] Jiawei Han,Jian Pei,Yiwen Yin, Mining Frequent Patterns without
for FPSO clustering is given as [10][11].Here we have Candidate Generation:A Frequent-Pattern Tree Approach, Data
chosen K,constriction factor as 1 and equation is redefined as Mining and Knowledge Discovery, 8,53-87, 2004
,where is the objective function as given in Eqn 4 . [2] [Link],[Link] swarm optimization,in:,Proceedings of
IEEE International Conference on Neural
Networks,vol.4,IEEE,pp.1942-1948,1995.
[3] Shafiq Alam,Gillian Dobbie,Yun Sing Koh,Patricia Riddle,Saeed ur
RehmanResearch on particle swarm optimization based clustering:A
systematic review of literature and techniques,Swarm and
Evolutionary Computation,17,pp 1-13,[Link]. 2. Oxford:
Clarendon, 1892, pp.68–73.
[4] [Link] and [Link],†Web document clustering: A feasibility
Figure 2. Final Cluster outcomes of FPGrowth and FuzzyPSO demonstration†,in Proceeding of 19th International ACM SIGIR
Conference on Research and Development in Information Retrieval,
Figure 2 shows the outcomes of FPGrowthFuzzyPSO June (1998).
optimization .The last column shows after FpFPSO [5] Pang,W.,Wang.K.,Zhou.C.,Dong,L,Fuzzy discrete particle swarm
optimisation for solving travelling salesman problem InProceedings
optimization the clustering of all documents to two clusters 1 of the fourth international conference on computer and information
and 2 effectively. Out of all 12 documents given as input its technology,pp.796-800,IEEE CSPress 2004.
shown in the 1that 7 documents belongs to cluster 2 and rest [6] L. Li, X. Liu, M. Xu, A Novel Fuzzy Clustering Based on Particle
5 belongs to cluster 1. Swarm Optimization, First IEEE International Symposium on
Next we calculate the performance of FpFuzzyPSO to Information Technologies and Applications in Education, pp. 88-90,
evaluate the documents in clusters shown in Fig 2. (2007).
[7] T. A. Runkler, C. Katz, Fuzzy Clustering by Particle Swarm
Optimization, 2006 IEEE International Conference on Fuzzy
Systems, Canada, pp. 601-608, (2006).
[8] F. Yang, T. Sun, C. Zhang, An efficient hybrid data clustering
method based on K-harmonic means, and Particle Swarm
Optimization, Expert Systems with Applications (36), pp.
9847–9852, (2009).
[9] E. Mehdizeded, S. Sadinezhad, R. Tavakkolimoghaddam,
Figure 3. Performance Evaluation of FpFPSO for 100 iteration. Optimization of Fuzzy Criteria by a Hybrid PSO and Fuzzy C-Means
Clustering Algorithm, Iranian Journal of Fuzzy Systems, pp. 1-14,
(2008)Electronic Publication: Digital Object Identifiers (DOIs):
V . CONCLUSION
[10] Hesam Izakian, Ajith Abraham,Fuzzy Clustering Using Hybrid Fuzzy
In our proposed approach we have tried to find an c-means and Fuzzy Particle Swarm Optimization,World Congress on
efficient methodology for clustering of documents using FP Nature and Biologically Inspired Computing,pp.1690-1694,(2009).
Growth based FuzzyPSO clustering algorithm. The output [11] Hesam Izakian,Ajith Abraham,Fuzzy C-means and fuzzy swarm for
shows the modelled system is stable, clustering documents to fuzzy clustering problem,Expert Systems with
Applications,38,pp.1835-1838,(2011).
groups efficiently and effectively. This research shows that
the FpFPSO document clustering algorithm can efficiently [12] Berkhin, P., Survey of clustering data mining techniques. Accrue
Software Research Paper.( 2002). Everitt, B. Cluster Analysis. 2nd
converge on the optimal solution or near optimal solution. Edition. Halsted Press, New York. 1980
The major contribution of this research holds to be the fact

93