I am trying to implement Particle Swarm Optimization for document clustering. I have gone through lots of reserach papers. Going through them, I could only figure out that each particle will be represented as K number of cluster centroids.
So a particle is equal to (C1,C2,....CK)
But what about velocity and position? What do they represent? How do we initialize them? Can anybody suggest me regarding this?
Kauser Ahmed P First a fall, thank you for your comment.
I checked out yarpiz.com as you suggested...It has done pso clustering. The initial data is loaded from a seperate file.I want to know how do we initialize velocity and position? I didn't find that portion in the code. Also as mentioned in the post, I know that a particle represents centroids. But what do velocity and postion represent? Like do they represent certain part of centroid? Can you please elaborate? It will be highly helpful
In general, when we say Particle (in PSO algorithm) , it means a single Solution. These solutions are trying to find the best solutions (or variables inside the solution) in the searching space. Searching Space means all possible solutions (good or bad), so usually we represent the variables of the solutions by ( X ). Therefore, each Xi in Xd ( where D represents the size of the problem ), represents the position of the solution in search space. If the position is very close to the optimal solution, then, this is the best solution so far.
The values of all Xs in the solution are generated randomly, this is the core idea behind the stochastic metaheurisitics. Usually, we use the uniform distribution equation to generate them, or some researchers use chaotic maps.. it depends. At the same time, the velocities for each particle - or solution - are generated by the same equation you used for generating the positions.
Most of the researchers do not mention the how to initialize both (Xi and Vi), unless they have contributed something in this stage.
So, in coding part, you need to initilize the values of X for all particles within the search space ( LB
Thank you Sinan Salih for the detailed explanation.....so in case of document clustering, suppose the document is of dimension 5464 X 1.
1. So, now the dimension of X (position) and Velocity(v) is also 5464 X 1 right?
2. You mentioned uniform distribution equation to generate X. Can you point me to the link of those equations? It will be very helpful
You are welcome,
1- Correct , both have the exact same size. But you have to make sure how many dimensions should the particles have.
2- Uniform distribution, it is a topic in mathematics. If you want to study it you can find so many articles in the Internet. But in our case, each particle - or solution - is generated randomly based on a simple equation :
Xi = (UB - LB) * Rand + LB
where: UB - The upper bound, LB - Lower Bound, Rand - a value in the range [0,1].
This equation generate values in the range [LB,UB], so there is no Xi out side the search space.
Regards..
Sinan Salih Thank you for your answer.. I have few questions. Could you please go through them and answer them?
1." How many dimensions should the particles have"----Every particle will contain K cluster centers. So you mean how many cluster centers do we assign to each particle, right?
2. So if Xi and Vi both are randomly generated then, what is the use of document vector that we have generated through word gram or TF_IDF? What do we use that for?
3. How do you determine Upper Bound(UB) and Lower Bound(LB) value for the equation?
Lastly, Did you refer to any specific book while studying meta heuristics? Your answer seems to be so much in detail. I am a beginner in meta heuristics. Could you refer a good book regarding PSO to me? I would be really grateful
If you are a Postgraduate student, and have time, I suggest for you to do the following :
1- Try to read some Articles/books for Optimization, Metaheuristics..
2- Try to understand the theory behind the swarm intelligence in general, and PSO in particular.
2- Write a code for solving a simple benchmark test function (such as Sphere, or so ) by using PSO.
From the above points, you will get a good knowledge, then you can start with the following:
1- Start reading about the data clustering problem in general, then the main algorithms used for clustering such as K-means..
2- There is an easy bio-inspired metaheuristic has been published several years ago for data clustering, read it and try to code it ( Black Hole Algorithm ) .
3- Now, you just need to change what have you learn into what you need.
Back to your questions, I am not sure if my answers will be correct 100%, I will try my best :
1- Each particle in the swarm should represents a candidate clustering solution, for the documents. So the size of each particle/ (d) is equal to the number of clusters, which you already know from the dataset.
2- PSO clustering algorithm searches for the proper centroids of clusters which minimize the intra-cluster distance, and maximize the distance between the clusters.
3- They are problem dependent variables, there is no method to calculate them. They represent the borders of the search space, some problems LB = 0, UB = 1, other problems LB = -100, UB = +100.
1 - Try to read this paper, I think it will give you a clear vision on the topic. To be honest, it is exactly your work.
Conference Paper Document clustering using particle swarm optimization
Then you might read :
2- Article Black hole: A new heuristic optimization approach for data clustering
3- https://ieeexplore.ieee.org/document/5190037
4- METAHEURISTICS From Design to Implementation, Talbi El-Gazali (2009). A book explains the basics of optimization and metaheuristics.
5 - Article Clustering using firefly algorithm: Performance study
6 - In Yarpiz Project, they have implement most of the important algorithm , it may helps you ( yarpiz.com )
Hope this helps,
Regards..
- Badges
- Science topic
- Similar topics
- Papers