 Open Access
 Total Downloads : 13
 Authors : Akshay A. Bandivadekar , Harshal D. Gadhia , V.Mukhilan
 Paper ID : IJERTCONV2IS04033
 Volume & Issue : ICONET – 2014 (Volume 2 – Issue 04)
 Published (First Online): 30072018
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Comparison of Clustering Algorithm in Automated Inventory System
Comparison of Clustering Algorithm in Automated Inventory System
Akshay A. Bandivadekar , Harshal D. Gadhia ,V.Mukhilan,
Abstract Patterns and classification of stock or inventory data is very important for decision making and business support. In proposed system an algorithm for mining patterns of huge stock data to predict factors affecting the sale of products, Identification of sales patterns from inventory data indicate the market trends which can further be used for forecasting, decision making and strategic planning. The objective is to get better decision making for improving sales, services and quality as to identify the reasons for dead stock, slow moving and fast moving stock. The system proposes two phases in which first phase includes initial clustering which is performed on the database with the help of a clustering algorithm. In the second phase the system uses most frequent pattern, MFP algorithm to find the frequencies of property values of the items. The existing system uses kmeans clustering algorithm along with MFP for mining patterns. In order to improve the execution time the proposed system uses efficient methods for clustering which includes Partitioning Around Medoids, PAM and Balanced Iterative Reducing and Clustering using Hierarchies BIRCH along with MFP.The most efficient iterative clustering approach called as PAM is used for initial clustering and is then combined with frequent pattern mining algorithm. In order to meet the memory requirements, an incremental clustering algorithm BIRCH is also used for mining frequent patterns. So, the evaluation of these clustering algorithms along with MFP is made with respect to the execution times.
Keywords: Data mining, Clustering, Kmeans, PAM, MFP, computational complexity

INTRODUCTION
Cluster analysis or clustering is the task of grouping a set of objects in such a way that objects in the same group (called a cluster) are more similar (in some sense or another) to each other than to those in other groups (clusters). It is a main task of exploratory data mining, and a common technique for statistical data analysis, used in many fields, including machine learning, pattern recognition, image analysis, information retrieval, and bioinformatics
Association algorithms are designed to operate on databases containing transactions. As is common in association rule mining, given a set of item sets, the algorithm attempts to find subsets which are common to at least a minimum number C of the item sets. Apriori uses a "bottom up" approach, where frequent subsets are extended one item at a time (a step known as candidate generation), and groups of candidates are tested
against the data. The algorithm terminates when no further successful extensions are found.
The relationship among the large amount of biological data has become a hot research topic. It is desirable to have clustering methods to group similar data together so that, when a lot of data is needed, all data are easily found in close proximity to some search result.
Clustering techniques have a wide use and importance nowadays. This importance tends to increase as the amount of data grows and the processing power of the computers increases. Clustering applications are used extensively in various fields such as artificial intelligence, pattern recognition, economics, ecology, psychiatry and marketing.
The main purpose of clustering techniques is to partitionate a set of entities into different groups, called clusters. These groups may be consistent in terms of similarity of its members. As the name suggests, the representativebased clustering techniques uses some form of representation for each cluster. Thus, every group has a member that represents it. The motivation to use such clustering techniques is the fact that, besides reducing the cost of the algorithm, the use of representatives makes the process easier to understand. There are many decisions that have to be made in order to use the strategy of representativebased clustering. For example, there is an obvious tradeoff between the number of clusters and the internal cohesion of them. If there are few clusters, the internal cohesion tends to be small. Otherwise, a large number of clusters makes them very close, so that there is little difference between adjacent groups. Another decision is whether the clusters should be mutually exclusive or not, that is, if an entity can coexist in more than one cluster at the same time.

BACKGROUND AND RELATED WORK
For the transportation industry hugely contributes to the economy of India.For transportation purpose, the development and management of highway is a must. So tries to cluster research objects (namely chosen hub city) using clustering analysis , and then sort them according to some rules in order to make sure different layers of highway transportation cities
sets[1]. Data is very important for every organization and
business. Data mining techniques like clustering and associations can be used to find meaningful patterns for future predictions. Clustering is used to generate groups of related patterns, while association provides a way to get generalized rules of dependent variables. The algorithms used are K means, MFP(Most Frequent Pattern), KMedoid, Birch
algorithm [13].To formulates, simulates and assess an improved data clustering algorithm for mining web documents with a view to preserving their conceptual similarities and eliminating problem of speed while increasing accuracy. The proposed algorithm was simulated using the fuzzy logic and statistical toolbox in Matlab7.0 [4] . To represent a data mining approach for inventory forecasting and planning a Bill of Materials in a highly competitive environment such as an Italian car racing team. By exploiting clustering algorithms and by using statistical techniques to identify the optimal number of clusters this work presents a method to optimally cluster a multiyear dataset containing the products used in car revision after each rally competition during a three year period
[9] .
Clustering Algorithm:

KMean algorithm.

K Medoids algorithm (PAM)

Birch Algorithm


Association Rule Mining Algorithm:

Most Frequent Pattern (MFP) algorithm.

Apriori Algorithm

Comparison will be done by using two parameters Number of Iterations and size of dataset handled by each algorithm.
Our aim is to find out which algorithm is best and time efficient among clustering algorithms and which algorithm works best with which association algorithm.
Stock market produces huge datasets that deals enormously complex and dynamic problems with data mining tool. Data mining is the emerging methodology used in stock market, finding efficient ways to summarize and visualize the stock market data to give individuals or institutions useful information about the market behavior for investment decision. [12] .To obtained the frequent patterns from the stock data. Hybrid clustering association mining approach is proposed to classify stock data and find compact form of associated patterns of sale . From the experimental results it is clear that proposed approach is very efficient for mining patterns of stock data with less computational time than the proposed approach .By these patterns we may predict the

METHODOLOGY 1)Clustering Algorithm:

KMean Algorithm

3 categories
/li>


DeadStock (DS).

SlowMoving (SM).

FastMoving (FM) .
Start
factors affecting the sales. In future we may try to implement the same process in document classification and may even try
to have better computational efficiency by efficient algorithms
[17].Number of cluster K

EXISTING STSTEM
In paper [17], an algorithm is used for mining patterns of huge stock data to predict factors affecting the sale of products. To achieve these goals, we need to fully exploit this data by extracting all the useful information from it.
The algorithms used are 1. KMean algorithm.

K Medoids algorithm (PAM)

Birch Algorithm

Most Frequent Pattern (MFP)
In this paper, for clustering KMean algorithm, K Medoids algorithm (PAM), Birch Algorithm are used and Association is done by using Most Frequent Pattern (MFP) algorithm.
In this paper, comparison done by using Number of Iteration
This paper shows that Birch with MFP algorithm shows best result as compared to KMean with MFP algorithm and KMedoids with MFP algorithm.


PROPOSED SYSTEM
Only through data mining it is possible to extract useful pattern and association from the stock data.
Algorithm are used:
Centroid
Distance object to Centroid
Grouping based on Minimum distance
Fig.KMean Algorithm
No object move
End
over all medoids
Steps for the KMean algorithm

Step 1: Place K points into the space represented by the objects that are being clustered. These points represent initial group centroids.

Step 2: Assign each object to the group that has the closest centroid.

Step 3: When all objects have been assigned, recalculate the positions of the K centroids.

Step 4: Repeat Steps 2 and 3 until the centroids no longer move.

The PAM Clustering Algorithm
Start
Number Of cluster center k and medoids k
Group objects to closest medoid
Swap each medoid and non medoid object
Select minimum cost
NO
No change
YES
end
Figure 1: Flowchart of PAM algorithm
PAM (Detail Algorithm given by Margaret H.Dunham): Arbitrarily select k medoids from D;
Repeat
for each th not a medoid do for each medoidt,do calculateTCih;
Find i,h where TCih is the smallest;
If TCih<0 then replacemedoidti with th; Until Tcih<=0;
for each ti belonging to D do
assignti to kj where dis(ti,tj) is smallest

BIRCH: An Efficient Data Clustering Method for Very Large Database
Introduction:
Definition of Data clustering
Given the desired number of clusters K and a distance based measurement function, we are asked to find a partition of the dataset that minimizes the value of the measurement function.databaseoriented constraint:
The amount of memory available is limited and we want to minimize the time required for I/O.
Insertion into a CF Tree
We now present the algorithm for inserting an entry into a CF tree.Given entry Ent, it proceeds as below:

Identifying the appropriate leaf: Starting from the root, according to a chosen distance metric D0 to D4 as defined before, it recursively descends the CF tree by choosing the closest child node .

Modifying the leaf: When it reaches a leaf node, it finds the closest leaf entry, and tests whether the node can absorb it without violating the threshold condition.

If so, the CF vector for the node is updated to reflect this.

If not, a new entry for it is added to the leaf.

If there is space on the leaf for this new entry, we are done.



Modifying the path to the leaf: After inserting Ent into a leaf, we must update the CF information for each nonleaf entry on the path to the leaf.

In the absence of a split, this simply involves adding CF vectors to reflect the additions of Ent.

A leaf split requires us to insert a new nonleaf entry into the parent node, to describe the newly created leaf.

If the parent has space for this entry, at all higher levels, we only need to update the CF vectors to reflect the addition of Ent.

Otherwise, we may have to split the parent as well, and so on up to the root.


Merging Refinement: In the presence of skewed data input order, split can affect the clustering quality, and also reduce space utilization. A simple additional merging often helps ameliorate these problems: suppose the propagation of one split stops at some nonleaf node Nj, i.e., Nj can accommodate the additional entry resulting from the split.

Scan Nj to find the two closest entries.

If they are not the pair corresponding to the split, merge them.

If there are more entries than one page can hold, split it again.

During the resplitting, one of the seeds attracts enough merged entries, the other receives the rest entries.
Data
Phase 1:Load into memory by building a CF tree
Initial CF Tree
Phase 2(Optional):Condense into desirable range by building a smaller CF tree
Phase 4(optional and offline):Clustering refinement
Phase 3:Global cluster
SmallerCF Tree Good Cluster
Better Cluster
Figure:Flowchart of Birch Algorithm
BIRCH Clustering Algorithm Phase 2,3 & 4

Phase 2: Condense into desirable range by building a smaller CF tree

To meet the need of the input size range of Phase 3


Phase 3: Global clustering

To solve the problem 1

Approach: recluster all subclusters by using the existing global or semiglobal clustering algorithms


Phase 4: Global clustering

To solve the problem 2

Approach: use the centroids of the cluster produced by phase 3 as seeds, and redistributes the data points to its closest seed to obtain a set of new clusters. This can use existing algorithm
BIRCH Clustering Phase1 Threshold Value Heuristic approach to increase the threshold
Try to choose new threshold value so that the number of data points that will be scanned under the new threshold value can double .
Approach 1: find the most crowded leaf node and the closest two entries on the leaf can be merged under new threshold.
Approach 2: Assuming that the volume occupied by the leaf clusters grows linearly with data points. a series of value pair: number of data point and volume new volume (a new data point, using least squares linear regression) new threshold
Using some heuristic methods to adjust the above two thresholds and choose one.
BIRCH Clustering Phase1 DelaySplit option
When we run out of memory. There may be more data points that can fit in the current CF tree. We can continue to read data point and write those data points that require to split a node to disk until the disk space is run out. The advantage of this approach is that more data points can fit in the tree before we have to rebuild.
Performance Studies



Complexity Analysis

Experiment with Synthetic Datasets

Performance Comparisons of BIRCH and CLARANS with Synthetic Datasets

Experiment with Real Datasets

Association Algorithm:

MOST FREQUENT PATTERN MINING (MFPM) ALGORITHM
Association rule mining is one of the mostimportant and well defines technique for frequent pattern,associations in a dataset. Association rules [7] are widelyused in various areas such as market analysis, inventory[4] control, and stock data. Apriori algorithm for strongassociation amog the patterns is highly recommended. Inthis work we proposed a new algorithm MFP thatefficiently generates frequent patterns and strongassociation between them Let we have set X of N items ina Dataset having set Y of attributes. This algorithm countsmaximum of each attribute values for each item in thedataset.
The algorithm is as follows
Input: Datasets (DS)
Output:Matrix Most Frequent Pattern (MFP): MFP (DS)
Begin
For each item Xi in DS

for each attribute

count occurrences for Xi C=Count (Xi)

Find attribute name of C having maximum count Mi=Attribute (Ci)
Next [End of inner loop]


Find Most Frequent Pattern
i. MFP=Combine (Mi) Next [End of outer loop


APRIORI ALGORITHM
The candidategen function takes Fk1 and returns a superset (called the candidates) of the set of all frequent kitemsets. It has two steps

join step: Generate all possible candidate itemsetsCk of length k

prune step: Remove those candidates in Ck


that cannot be frequent.
Candidate gen function
Function candidategen(Fk1)
CkÂ¬Ã†;
forallf1, f2 ÃŽFk1
withf1 = {i1, , ik2, ik1}
andf2 = {i1, , ik2, ik1} andik1 <ik1 do
cÂ¬ {i1, , ik1, ik1}; // join f1 and f2 CkÂ¬CkÃˆ {c};
foreach (k1)subset s of cdo if(sÃFk1) then
deletec from Ck; // prune
returnCk;


EXPERIMENTS AND RESULTS
The data set we used includes data objects each one with seven attributes. Basing on one of the attributes the clustering technique is applied. The attribute for clustering

is decided accordingly. In our application of stock data [7], clustering is performed based on the attribute of quantity sold. The sample data is shown below.
TABLE I. DATA SET
We apply the clustering technique for the initial grouping of the whole data it then give three clusters of DS, SM and FM stock. So the process has two phases as given below
The evaluation of K means, PAM and BIRCH is done and the execution time is tabulated

Interaction Effects Study

The interaction effects study gives us the interaction between Execution time and the iterations. We take the interaction plot between the execution time and iterations. The following can be observed.

When Kmeans is considered there is a increase in the execution time with respect to the iterations

When KMedoids [15] is compared to k means there is decrease in the execution time which may improve the overall computational efficiency.
When Birch is compared to these algorithms there has been much improvement in the execution time.
Based on these effects the results are specified in a tabular form showing the iterations and the execution time in milliseconds for clustering algorithms kmeans, PAM and BIRCH in combination with MFP.A graph is then plotted basing on these tabulated values.
TABLE II. RESULTS OF ALGORITHMS
Iterations
MFP with K
Means
MFP with
PAM
MFP with
BIRCH
1
235
155
140
2
368
288
250
3
503
431
388
4
631
576
413
5
777
707
543
6
816
764
567
7
950
890
607
8
1094
937
630


CONCLUSION AND FUTURE WORK

By comparing Kmeans with MFP, PAM with MFP, Birch with MFP, Kmeans with Apriori, PAM with Apriori, Birch with Apriori where Kmeans, PAM and Birch are Clustering algorithms while Apriori and MFP are Association rule mining algorithms. We will achieve that which clustering algorithm is best and time efficient and which association algorithm is best and time efficient. Here the comparison parameter are – 1)Number Of Iteration 2)Size of dataset
REFERENCES

Yan Meng ,Xiyu Liu . Application of Kmeans Algorithm Based on Ant Clustering Algorithm in Macroscopic Planning of Highway Transportation Hub ,published in Â©2007 IEEE 1424413850/07.

ChenChia Chuang ,JinTsongJeng ,ChihWen Li . Fuzzy CMeans Clustering Algorithm with Unknown Number of Clusters for Symbolic Interval Data ,SICE Annual Conference 2008 .August 2022, 2008, The University ElectroCommunications, Japan .

ShengYi Jiang , Xia Li . A Hybrid Clustering Algorithm ,2009 Sixth International Conference on Fuzzy Systems and Knowledge Discovery.

Odukoya, O.H, Aderounmu G.A. And Adagunedo, E.R. An Improved Data Clustering Algorithm for Mining Web Documents,published in
Â©2010 IEEE 9781424453924/10/

FuhengQu ,Yating Hu ,Shuangzi Sun ,A New Possibilistic Clustering Algorithm with Its Application to Fault Diagnosis ,published in Â©2011 IEEE 9781424498574/11 /

WangChunhong,Nan Lili,Ren YaoPeng,Research on th Text Clustering Algorithm based on Latent Semantic Analysis and optimization,published in Â©2011 IEEE 9781424487288/11 /

Huiying Wang ,Xiangwei Liu ,Study on Frequent Term Setbased Hierarchical Clustering Algorithm ,2011 Eighth International Conference on Fuzzy Systems and Knowledge Discovery (FSKD) .

Li Liu ,Yun Shao ,Fengli Zhang ,Xu Lu ,The Discrepancies Caused By Different Cluster Merging Algorithms In Fully Polarimetric SAR Classification,published in Â©2012 IEEE 9781467311595/12/

Francesco Maiorana ,Angelo Mongioj ,A data mining approach for bill of materials for motor revision ,published in Â©2012 IEEE 97883 60810484/

NeethiNarayanan ,J.E.Judith, Dr.J.Jayakumari ,Enhanced Distributed Document Clustering Algorithm Using Different Similarity Measures ,Proceedings of 2013 IEEE Conference on Information and Communication Technologies (ICT 2013).

XuDegang, Zhao Panlei, GuiWeihua, Yang Chunhua, XieYongfang
,Research on Spectral Clustering Algorithms Based on Building Different Affinity Matrix,published in Â©2010 IEEE 978146735534 6/13/

Sachinkambrey, R. S. Thakur,ShaileshJalori,Application of Data Mining Technique in Stock Market : An Analysis, International Journal of Computer & Communication Technology (IJCCT) ISSN (Online): 2231 – 0371 ISSN (Print): 0975 7449 Vol3, Iss3, 2012

M.Rajeswari ,Y.Ramu,Frequent Patterns Mining Of Stock Data Using Hybrid Clustering Association ,International Journal of Systems,Algortihm and application Volume 1, Issue 1, December 2011 .

Aurangzeb Khan, BaharumBaharudin, Khairullah Khan, Mining Customer Data For Decision Making Using New Hybrid Classification Algorithm,publication of Little LionScientificR&D,IslamabadPakistan,Journal of Theroteicaland applied Information Technology,15th May 2011.Vol.27 No.1.

Sunil Joshi ,Dr. R. S . Jadon ,Dr. R. C. Jain ,An Implementation of Frequent Pattern Mining Algorithm using Dynamic Function ,International Journal of Computer Applications (0975 8887) Volume 9 No.9, November 2010

M.SureshBabu ,Dr. N.Geethanjali, Prof B.Satyanarayana ,Clustering Approach to Stock Market Prediction ,Int. J. Advanced Networking and Applications Volume: 03, Issue: 04, Pages:12811291 (2012) .

D.V.S. Shalini ,M.Shashi, A.M.Sowjanya , Mining Frequent Patterns of Stock Data UsingHybrid Clustering (2010) .