Google Maps

This is a cool application of clustering. It uses the application of javascript to solve problem of over-crowdedness of markers on the google earth and maps. To relieve the problem ,we apply hard, near-neighbour clustering . the javascript library has the name: MarkerCluster, and its effect can be seen as :

It's easy to use - just add your markers to an array, pass that and your map into the MarkerClusterer, and it'll take care of the rest. Check out the simple example and code snippet below:

var markers = [];

for (var i = 0; i < 100; ++i)
{
var latlng = new GLatLng(data.photos[i].latitude, data.photos[i].longitude);
var marker = new GMarker(latlng);
markers.push(marker);
}
var markerCluster = new MarkerClusterer(map, markers);

Here the latlng is for the latitude and longitude application ,the two parameters that are taken are coordinates
of the point where the marjers are to be specified. We push the new marker to the set of markers and enable
clustering yet again. The  MarkerClusterer function

To use a marker clusterer, create a MarkerClusterer object. In the simplest case, just pass a map to it.

var map = new GMap2(document.getElementById("map"));
map.setCenter(new GLatLng(37.4419, -122.1419), 13);
var mc = new MarkerClusterer(map);

You may also specify a number of options to fine-tune the marker manager's performance. These options are passed via a MarkerClustererOptions object. The MarkerClustererOptions object is an object literal, so you simply declare the object without a constructor:

var map = new GMap2(document.getElementById("map"));
map.setCenter(new GLatLng(37.4419, -122.1419), 13);
var mcOptions = {gridSize: 50, maxZoom: 15};
var mc = new MarkerClusterer(map, [], mcOptions);

Once you create a marker cluster, you will want to add markers to it. MarkerClusterer supports adding markers using the addMarkers() method or by providing a array of markers to the constructor:

var map = new GMap2(document.getElementById("map"));
map.setCenter(new GLatLng(37.4419, -122.1419), 13);
var mcOptions = { gridSize: 50, maxZoom: 15};
var markers = [...]; // Create the markers you want to add and collect them into a array.
var mc = new MarkerClusterer(map, markers, mcOptions);

A Simple MarkerClusterer Example:

This example will show 100 markers on map.

  if(GBrowserIsCompatible()) {
   map = new GMap2($('map'));
   map.setCenter(new GLatLng(39.91, 116.38), 2);
   map.addControl(new GLargeMapControl());

   var markers = [];
   for (var i = 0; i < 100; ++i) {
     var latlng = new GLatLng(data.photos[i].latitude, data.photos[i].longitude);
     var marker = new GMarker(latlng);
     markers.push(marker);
   }
   var markerCluster = new MarkerClusterer(map, markers);

K-Means: algo to cluster

K-means is most important flat clustering algo. There has lots of research on K-means in recenpast and still leaves a lot of room for research. Before understanding what a K-means is , one should know why and when it is done.

Why: When we have a problem statement that specifies us to create a set of documents {d1,d2....dN}that has to be clustered and a desired number of cluster =K along with an objective function to minimize the average squared Euclidean distance of documents from their cluster center . So what we have is N set of documents ... can be N webpages , with already specified K number of clusters to be made out of them ,we also have an objective that would lead us to clusters having documents with least dissimilarity (or distance). Now to establish the center of our cluster from where we take take distance. It can simply be defined by equation:

where we have vector μ as the centroid and have documents as length normalized vectors. For vector normalizing visit:http://www.fundza.com/vectors/normalize/index.html,

Now ever creating a cluster by K-means one should remember that we should test the measure of how well centroid is for the particular cluster . This can easily be found by RSS (Residual Sum of Squares), the squared distance of each vector from its centroid.

Now the real algorithm to cluster the documents can be presented

The arguments supplied to the function are K: the number of clusters to be made and the set of documents . The first step involves randomly selected seeds(an area of debate and discussion),a set of K documents from N. Then we actually move the cluster's center in order to minimize RSS(Residual Sum of Squares) . There is a while loop which runs until stopping criterion has been met(discussed later). Merging of clusters is done according to a defined (arg min) step(8-9) , whose computation is based on distance between the document and the centroid. Each time the merge is done re-computation of centroid is done. step(10-11).

Now we need to consider stopping criteria :Well as normal fix a number of iteration , or keep doing until you find centroids are not changing.. A hybrid can help as is former we may unnecessarily be doing computations even if we have already found out the value and on the later we could have been calculating the value for an infinite time or to a level that we don't afford , A sensible approach could be to fix a threshold RSS which gets us to fix a standard .

Ways of clustering

This post is more of informative than tutorial... it will introduce the different methods applied in clustering.

The clustering methods are usually divided into two broad categories: Flat clustering and Hierarchical clustering. Flat clustering is fast but requires a earlier knowledge of approximate number of clusters to be make and also it is unstructured. Hierarchical clustering is slower, at least quadratic in time but has a structure of hierarchy which is very helpful as mentioned earlier, also it doesn't require the knowledge of number of clustered to be made.

Flat clustering is usually done by K-means and Expectation-Maximization Algorithm maximization algorithm or EM algorithm.

Hierarchical clustering is usually done by HAC or hierarchy agglomerative clustering:a bottom-up clustering algorithm ,usually done with different measures :single-link,complete-link,group-average,centroid,etc. Other approach for Hierarchical clustering can be top-down or divisive clustering clustering.

Clustering :Similarity to make a difference

I would try to explain step by step what clustering is(discussed only with contest to web) without going into cruel mathematics behind it

1)What is clustering? :In web clustering ,pages of similar categories are grouped togther.Not clear? go on reading

2)How is it useful:Easiest way to understand this is by looking at clustered information.

Like if you search "Agglomerative" on google, you would obtain something like:

Searches related to: agglomerative

agglomerative cluster analysis agglomerative hierarchical agglomerative algorithm agglomeration thesaurus

agglomeration wikipedia

Now these related searches are hyperlinks and when you click at a specific link you would obtain

a more specific result for seach related to entered query, thus helping you to "drill down" on a specific topic!

Now that really looks helpful, isn't it ;)

Clustering is also helpful in data analysis,social networking and datamining(how ,will be discussed in later post).

3)How is clustering done? :Clustering is the most common form of unsupervised learning(i.e.almost none intervention from human is required).

Classification(will be discussed later) is different from clustering in that classification requires supervised learning.

Anyways I must make out this that clustering and classification (simultaneously)is best implemented by manual construction e.g.http://dmoz.org/ and also Yahoo Directory.

Clustering is done by various algorithms, but before going through them lets look at few terms:

1)Flat Clustering: Creates a fat set of clusters without sny explicit structure that would relate clusters to each other.

Now lets understand what it means:Go to the search: agglomerative

Click n the first cluster ,i.e. agglomerative cluster analysis (subject to change :P)

Now on clicking the hyperlink you get the query page such that it contains the clusters of form:agglomerative cluster analysis

hierarchical agglomerative cluster analysis euclidean distance cluster analysis cluster analysis dendrogram multivariate cluster analysis

cluster analysis algorithms cluster analysis matlab

If google had been using flat cluster we wouldn't have got this sub-cluster(a structure), therefore wat we r looking at is hierarical cluster :),not flat.

2)Hard Cluster:Each document is a member of exactly one cluster.

3)Soft cluster:Document may have fractional membership in several clusters

4)Non-Exaustive cluster may assignno cluster to a particular document.

Pagerank-The Multibillion Idea

Pagerank was the idea developed by Larry Page,thus the name.. accompanied by Sergey Brin --the owners of Google. They got this idea while doing a college project in Stanford. Now what was the idea that got them such large money?

Pagerank determines the quality of any page. Based on "Random Surfer Model", Pagerank is a probablity distribution used to represent likelyhood that a person clicking on links will arrive at a particular page.

Before Pagerank was introduced the method used for returning queries by search engines was vertor space model,which was quite good for content matching. But need for good pages to be returned as a result to query was felt. Then link matching was introduced in pagerank . Now we all know what hyperlink is... it connects one page to another.

Its a good way to understand pagerank with the idea that web is directed graph, where a site linking to other sites shows a directed link from it to the page being linked. The pages are like nodes and hyperlinks are the links of the directed graph.

We can, for now, say that , more the link pointed to a page by hyperlinks of other pages.. better it is .The links given to a page are called backlinks to that page. Accepting this we say that hyperlinks are like votes in democracy ,if you vote someone (by linking your page to his page) ,you actually increase his page's quality. But unlike democracy , you can vote more than once condition being more you vote.. fewer is the value of your vote.

So we say

PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))

where, d is termed to be the damping factor. ,

,PR(T1) represents pagerank of the page T1,

,C(T1) represents the number of outgoing links for the page T1

,d:damping factor is used to stop having to much influence ,this total vote is damped down to a value by d. the damping factor is usually taken to be 0.85

JQuery- The Javascript Library

We all have probably done coding ,and are more comfortable in understanding any new language with the help of previously learnt language . So I would take such an approach to exlain JQuery library of javascript . Almost all of us have done programming in C++. We always use strrev and don't go on for reversing a string in a loop. This is because it "reduces work". Same is the concept of JQuery . Its like using STL(standard template library of C++). Someone has written long library codes in javascript for you :) . You just have to pick up one that suits you and make beautiful site.

For using it you will have to put the famous and essential file "jquery.js" file in same folder where you put your library of JQuery (e.g. jquery.fancybox-1.2.1.pack.js file).

Now just embed the javascript file(e.g. jquery.fancybox-1.2.1.pack.js) in your webpage. Further is just a play. Make new designs with photoshop, attach it with the your webpage to give new look to the library or change the parameters of .js file according to your wish. Types of parameters vary with the library member that you use. I suggest the use of dream-weaver for ease.