TRENDS 2 - Clustering

Clustering

Clustering is one of the methods that serves for data classification. It is traditionally used as algorithm beyond the information retrieval process as the assessment documents relevance. The innovation which could be brought by this approach is the projection of this algorithm in the presentational level of the information retrieval system.

Cluster

Cluster is defined as number of similar items – things, persons or groups - grouped closely together. The difference between clusters and thesaurus classes is the unsupervised classification – clusters are not predefined. The initiative which activates the clustering process is the user’s need expressed by user’s information retrieval query. Clusters could show the natural grouping or structure in data set. There are several clusters as resulting forms that are exploited in different clustering methods and models (Zaïane, 1999):

• Exclusive Clustering – definite cluster with strict data

• Overlapping Clustering – fuzzy sets to cluster data, each data has different degree of membership, each cluster belongs to two or more clusters
• Hierarchical Clustering – union between two nearest clusters
• Probabilistic Clustering – completely probabilistic approach
  

Distance-based clustering

We could divide clusters in different groups according to the algorithm that defines different grouping. In the case of the first picture, we easily identify 4 clusters into which the data can be divided; the similarity criterion is distance: two or more objects belong to the same cluster if they are “close” according to a given distance. This is called distance-based clustering (Zaïane, 1999) – items in the group share almost the same characteristics expressed by their position in the information space; items are depicted in the 2D or 3D space – in our case 2D - according to their options that establishes their uniform position.

Conceptual clustering

Another kind of clustering is conceptual - two or more objects belong to the same cluster if each one is defined by common concept to all that objects. Conceptual clustering is not based on perfect match and similarity between objects, but rather conceptual likeness (Tutorial, 2000). Categories and features that determinate the similarity of the group are fuzzy and more open than in the previous distance model, they cold be defined as overlapping clusters – items in the group have at least one “same” character.

The example of conceptual approach is Latent Semantic Indexing (LSI, see Deerwester et al., 1990). A query with one term (such as “pigs”) could have a high similarity with a document that has a related term (“hogs”). Rather than expanding queries based only a small set of term relations, LSI considers all terms potentially related to each other, and all documents to be similarly related (Newby, 2002).

Model-based clustering

Another of the conceptual clustering approaches is the model-based clustering methods. It is based on fit between two different data sets the data set and model. It emerges from the nonlinear m-dimensional inputs in data set. Which position is based on closeness. Thus the data set is selfcorrecting according to the changeable mental model. This theory is in connection with the SOM – self organizing model - theory from 1981 proposed by Kohen.

The further development in clustering theories is based on the likeness with human information acquisition. According to this approach precede the clustering theory the learning, statistic and probabilistic theories.

Cognitive aspects

The advantage of the clustering is the close similarity to the human way of thinking. It responses to the theory of inner mental modelling according to Wittgenstein and the theory of term and conceptual thinking, that enables people to deal with large data sets and easier to classify their long term memory (Loukotová, 2009). Clustering method though reflects the higher mental activities and is sufficient for information retrieval. Other important advantage is its relation to the changeable context of the real world. The structure of clusters is not fixed and it is reflecting the changes of the inner mental model depending on the reality.

The clustering method on the representative level could then bring a tool for easier understanding of the data set’s environment and deeper understanding of the relations in between the terms and objects and not to say the reality.

Problems

The exploitation of clustering method in the Web environment brings problem as each method that is based on similarity to the human thinking. There emerge a lot of different unknown and changeable facts that have to be taken in account. As bigger data set as more unknown facts. Other problem is the changeability of data set itself. In the web environment is the change of the amount and kind of data high and fast.

All kinds of clustering models are basically founded on sort of “distance” between terms and thus the right identification of the cluster is based on their representation in the information space. In follows the problem of filtering clusters is primarily consequent on the position of the clusters in the information space.

Conclusion

Nowadays clustering methods are highly exploited in the form of hidden algorithm. However their exploitation is not fully utilized. The potential is in the cognitive aspects of the method. As will be presented later, this approach is closest to the cognitive perception and ways of human thinking. That could in connection with search engines serve as the perfect information retrieval and learning tool.

Examples

Solitary applications: Carrot2Workbench

Web search engines: clusty.com

References

BORGMAN, Christine L. (1989). All Users of Information Retrieval Systems are Not Created Equal: An Exploration into Individual Differences. Information Processing and Management, vol. 25, no.3, pp. 237–251.

CARD, Stuart K., Mackinlay, Jock D., and Shneiderman, Ben. (1999). Readings in Information Visualization : Using Vision to Think. San Francisco: Morgan-Kaufman.

CEJPEK, J. (1998) Informace, komunikace a myšlení. Karolinum, Praha. 178

HULL, David A. (1999). The TREC-7 Filtering Track: Description and Analysis. In Voorhees, Ellen and Harman, Donna (Eds.), Proceedings of the 7th Text REtrieval Conference (TREC-7), Gaithersburg. Maryland: National Institute of Science and Technology

INGWERSEN, P. (1996). Cognitive Perspectives in Information Retrieval Interaction: Elements of a Cognitive IR Theory. J. Documentation, vol. 52, no. 1, pp. 3–50.

LOUKOTOVÁ, K. (2009) Úvod do problematiky uživatelského rozhraní. In Červenková, A. & Hořava, M. (Eds.), Uživatelsky přívětivá rozhraní. Horava &Associates, Praha.

NEWBY, G. B. (2002) Empirical Study of a 3D Visualization for Information Retrieval Tasks. Journal of Intelligent Information Systems, vol. 18, pp. 31–53.

SABOL, V. et al. (2002) Applications of a Lightweight, Web-Based Retrieval, Clustering, and Visualization Framework. In D. Karagiannis and U. Reimer (Eds.): PAKM 2002, LNAI 2569, pp. 359–368, 2002.

SHNEIDERMAN, Ben. (1996). The Eyes Have It: User Interfaces for Information Visualization. Technical Report No. CS-TR-3665, Human Computer Interface Laboratory. University of Maryland at College Park. Available at http://www.cs.umd.edu/TRs/groups/HCIL-no-abs.html

SCHAMBER, Linda, Eisenberg, Michael, and Nilan, Michael. (1991). Towards a Dynamic, Situational Definition of Relevance. Information Processing and Management, vol. 26, no. 2, pp. 755–776.

TUTORIAL on Clustering Algorithms (2000) Politecnico di Milano. Available at: http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/

ZAÏANE, Osmar R. (1999) Principles of Knowledge Discovery in Databases - Chapter 8: Data Clustering. University of Alberta. Available on : http://www.cs.ualberta.ca/~zaiane/courses/cmput690/slides/Chapter8/index.html

True Knowledge - let see

What is that ?

Is new search engine which should help to find easily knowledges contented on web. The goal as they say should be providing consumers with instant answers to complex questions, with a single click.True Knowledge structures data in a way that enables computers to work and think like humans do. Its ambitions are to be a search engine-like consumer site which can answer questions, be used to add knowledge and also be used just like a conventional search engine. The whole True Knowledge would be presented during 2008. Nowadays work True Knowledge as beta version and for access is necessary registration. In other case you are not alowed to see whats going on at all.

How it works?

Technically the system use the knowledge stored in format which it could understand and after decoding the question it´s able to find and code the answer back in natural language. Because the majority of people is nowadays used to write query in short keyword version is also part of this system possibility to use this clasical style of searching, when the system is able to look for two or three keywords and show results or show the short conclusion on the top of the side.

Difference between normal search engine even between natural language search engine is that True Knowledge enables you also to add yor own knowledges. The difference between wiki is that the format of knowledges is in the format understandable for sysetm, not in the natural language as an wiki article, user is forced to add knowledge in forprepared blank. Nowadays is possible to add all real kinds of information, from some reason is not possible to add knowledge about fantastics things as mystical animals and others. The quality of facts is secured by assessing, which is not described in accesible information.But actually this could be the most interesting point of this platform. Because they actually make absolutely new database of knowledges, which probably should be way to assess the content, but on my opinion it´s really huge goal nowadays in competition of web environment...
But if they really would be able to make assessed knowledge database with some relevant garant or institution in background, then it would be really important search tool.

Conclusion
Nowadays is available beta version. And its really hard to get some information from that, because it usually doesnt have answer and ask you for adding information. Which means that there is really a lot of work to fill the database and link it throught.
As a conclusion I could say that it has potential at least the structure of the searching with the use of natural language and the answer which is formulated in natural language as much as its possible.

Powerset - small miracle

What´s that?
Powerset is one of the modern search engines which tries to facilitates the retrieval in Internet as much as is possible. This search engine arose in San Francisco in 2005 and was founded by Foundation Capital, Founders Fund, Paperboy Ventures and other investors. In 2008 was Powerset acquired by Microsoft.
The whole engine is applied on Wikipedia and Freebase that means that the among of information is limited by among of information consist in these databases. This product was launched in May 2008, thus that means that it´s really young, but in my opinion very succesful.

How does it work?
The basic think, which brough me to this search engine is the use of natural language. It is possible to add query in short version, as we are used from classic search engines, as topic or key keyword. But then is here possibility to add normal question in natural language as for example "How many people were evacuated from new orleans during hurricane katrina?" or "How old is Barack Obama?".
System is able to decomposite this natural language structure on necessary keywords containing the meaning of the query and then use traditional fulltext search method. The result is not just the list of the articles in Wikipedia which consist the answer, but also the clear answer on question in the heading, if its possible. Which means if he hasn´t differently information.
Powerset than provides further searching in articles. Is able to extract thetable of contents which is helpful for further searching. Offers two different views on article and also the link to the original article.
The system is always improving. There are such small details as possibility to highlighte the important parts of text and send it to someone else, which means that he get the same text with the same marks in the text. Simply but very worthwile.

Conclusion
Powerset is one of my favourite search engines. You know how I am exacting...
The point is not in the use of natural language, although I was surprised how well it works. The main point and advantige of this search engine is in his sophisticated structure. Its easy, well aranged and with cosy design. It offers tools as table of contents which really helps and make faster the searching.
I am really curious how it will grow on.

Project - consideration

As I said in last artical, my topic for the final essay are searchengines and specially focus on natural language search engines.

First and second generation of search engines
Technologies should help people to make things easily and faster. After the first generation of search engines which were quite complicated and was quit necessary to have a help of the thirth side (librarian or information specialist), because of using special forced language. It was necessary to know how ... Came the second generation of search engines, which was based on the boolean logic and used graphic userfirendly interface. Thats actually search engine which we know from nowadays. I dont think that its necessary to give here an example, because everyone knows them, Google or Yahoo. They are for sure not the only but they are the biggest and the most famous. Nowadays could users quit easily use this kind of interface and most of users are able to work with boolean logic. That means use the basic operators as AND, OR, NOT and keywords. With combination of fulltext search which nowadays promote common search engines.

My own opinion is, that this is good way how to search information. That actually the process of thinking and searching for information is based on simple definitions of keywords and their combinations. Our brain is used to work with these basic forms, always when we create a sentence or other speech, we have to use at least two different ranges: vocabularies and grammar. How we use it depends on our language skills or communication skills. Actually the way of searching information reflect the way of thinking, but it is not process in brain, but the final proces of creating sentence takes place directly in the search engine. The interface of search engines makes this process easier. In the better search engines you could use for exmple suggestions, to see how other people use this or that keyword in which combination, which could help you to create exactly the query.
Conclusion for this is that this way of searching information is used at the begun of thinking and helps to create the right query or sentence directly in the process.

Thirth generation ... ?
Nowadays is very trendy and big tendency to develop new engines based on natural language searching. The idea is that user writes question in the natural language ( mostly in english) and the system decodes the keywords from this sentence and go throught the webpages and use these keywords to find the answer. Problem is that the decoding of the sentence could be quit defficult, because of the basic charakter of natural language which is asymetry. That means that there are different ways how to express the same thing. Then after is the system usually confused and doesnt give the right answer or any answer at all.

If we look at this problematic, we could see that the that here exist two ways of coding and decoding of information. First is in our brain when we have to think out how to create proper sentence which would be system able to answer, then the system decode this sentence back on the basic fundaments and find the answer. During the first coding process of making a sentence
in the brain we have to work just with our knowledges, because the search engines usually cant offer any suggestions. Well in this point I think is the searching much more exhausting than when you could use the clusters or other supports of common search engines.

What say libraries of it?
The use of natural language maybe could help them get older users, because they would feel more comfortable to use the natural language then to use the traditional boolean logic. It could remind more the traditional communication with the librarian. And contrary to the boolean logic search engines the system would speak as a normal human. But is that enought?

More interesting would be implementation of sth. like Trueknowledge which is search engine, which use the natural language, but uses its own knowledge database with the basic in Wikipedia database. I will speak about this engine more later...
Or the system Powerset which helps to scan and make abstract from the webpages and ofer briefly information about the article. Nowadays is oriented just on the Wikipedia articles, but the plan is to extend the focus. This is really nice engine ... and contrary to the others it works quit well ... I also will speak about it in special articel ...

Conclusion
This was just theoretical concideration about the use of natural language in search engines. Just a small theory...