Click here to Skip to main content
Click here to Skip to main content

Visualizing Search Results in 3D (Hybrid Smart Client)

, 18 May 2009 CPOL
Rate this:
Please Sign up or sign in to vote.
Uses latent semantic analysis to cluster and visualize search results in 3D.

Introduction

The 3D capabilities of WPF are used here to show semantic "proximity" between search results. Singular Value Decomposition (SVD) - the principal technique behind Latent Semantic Analysis (LSA) - is used to reduce a multi-dimensional dataset down to three dimensions (while still preserving the key characteristics of that multi-dimensional space). The results are then plotted in a 3D scene that can be navigated by dragging the mouse. This reduced dimensional matrix is then scaled back, and a simple clustering algorithm is run over the data to show related search results and give them (and the corresponding 3D cubes) the same color.

This technique of reducing dimensions and then using this lower rank matrix to approximate the higher dimensional space (LSA) is a fairly cool trick that can give good results, although interestingly, it is not always known exactly why or how the new matrix approximation is better! Google is rumored to use it in their search ranking algorithm, teams chasing Netflix's $1M prize to improve recommendations are reportedly using it, and as can be seen in the demo project, search results from the modified matrix are indeed grouped in a fairly coherent way.

The chief idea is that the lost data is the least significant - the noisy, forgettable, and aberrant - and so, by focusing on the strongest trends, the new matrix is a better representation of the "concepts" than the data was in the first place. In this case, since we see objects in a maximum of three dimensions, reducing higher-dimensional data to three dimensions is a means to visualize that higher dimensional space.

Background

Please see my previous CodeProject article for a brief introduction to vector space model techniques. The main takeaway is that they revolve around the count of each term per document, which are normalized relative to each term's inverse document frequency and then stored in a matrix. The columns or rows that represent the documents can then be compared for similarity using vector multiplication.

For an overview of LSA, the Wikipedia article is a good starter. The hard part of LSA is in computing the SVD. One way SVD has been described is as follows: Suppose you have thousands of tropical fish swimming around in a large fish tank. You want to take a photograph of a fish that shows the full variety of fish in the tank, while preserving the relative distance between fishes. SVD will be able to tell you, at any given moment, the best place and angle to position the camera to take that "optimum" photo.

Paul Selormey's CodeProject matrix library is included here to perform the actual SVD computations. Note that there may be errors in this library! Some values in the least significant rows are wrong; however, as these are the rows that are discarded, all is still well.

You should notice that the 3D scene is draggable with the mouse. If you hold down the left button and drag over the 3D scene, you can "move the model" around. If you hold down the right button, you can make it smaller and larger. This trackball code was lifted from here.

Building the First Matrix

When a search is executed, the application fires off a query to a web service that is provided by Dog Blue Software. This web service in turn queries Microsoft Live Search for the list of search results. Next, the web service does word sense disambiguation on each result, and stores the count and text of each noun and adjective with the result.

The rationale for using nouns and adjectives rather than all the words in the text is that these might represent less ambiguous signals as to the meaning of each search result. A plurality of prepositions, adverbs - even of verbs - are not necessarily beneficial to the LSA algorithm, which is notoriously sensitive. (Although nouns better represent the "anchors of discourse", this in no way solves the problem of entailment ("the president was assassinated" == "the president is dead")).

Anyway, it is here that the present application gets down to work. It parses the XML, and uses the TermDocumentModel class to create documents and to add terms to those documents. In this case, we want a matrix with terms along the y-axis and documents along the x-axis. This is created in normalized form with the following code:

int numDocs = _documentList.Count;
int numTerms = _termToIndex.Count;
double nd = numDocs;
GeneralMatrix ret = new GeneralMatrix(numTerms, numDocs);
int x = 0;
foreach (Document doc in _documentList)
{
    double docTermCount = doc.totalTermCount;
    foreach (KeyValuePair<int, uint> item in doc.termCount)
    {
        int termIndex = item.Key;
        double count = item.Value;
        double termFrequency = count / docTermCount;
        double inverseDocumentFrequency = 
          Math.Log(nd / _keywordDocumentOccurence[termIndex].Count);
        double weight = inverseDocumentFrequency * termFrequency;
        ret.SetElement(termIndex, x, weight);
    }
    ++x;
}

It really is important to normalize the matrix in a way similar to this. Doing so creates a balance so that longer search results don't outweigh shorter search results and the more frequent words in English don't assume an unwarranted (within the concept space) importance.

Building the second matrix

Next, the application uses LSA to create the approximated matrix.

SingularValueDecomposition svd = matrix.SVD();
GeneralMatrix v = svd.GetV();
GeneralMatrix u = svd.GetU();
GeneralMatrix s = svd.S;
int k = 2;
if(k >= u.ColumnDimension)
    k = (u.ColumnDimension - 1);
if(k >= v.RowDimension - 1)
    k = v.RowDimension - 1;
GeneralMatrix u2 = u.GetMatrix(0, u.RowDimension - 1, 0, k);
GeneralMatrix v2 = v.Inverse().GetMatrix(0, k, 0, v.ColumnDimension - 1);
GeneralMatrix x = u2.Multiply(s.GetMatrix(0, k, 0, k)).Multiply(v2);

The SingularValueDecomposition class finds the Eigenvalues and Eigenvectors of the first matrix and creates three matrices. Multiplying the first with the second with the inverse of the third perfectly recreates (apart from any rounding errors that may have been introduced) the first matrix. But since we are doing LSA, we want an approximation of this matrix, so we discard most of the data and keep just the first three rows or columns of each respective SVD matrix. (Note that if we want to find an "optimum" rank to reduce these matrixes by (as three is discarding a lot of the information), we can use the Frobenius norm.)

But three works perfectly for us, as we want to show the results in 3D.

double[] sVec = svd.SingularValues;
v = v.GetMatrix(0, 2, 0, v.ColumnDimension-1);
double s1 = sVec[0];
double s2 = sVec[1];
double s3 = sVec[2];
double maxX = double.MinValue, minX = double.MaxValue, 
       maxY = double.MinValue, minY = double.MaxValue, 
       maxZ = double.MinValue, minZ = double.MaxValue;
int numDocs = v.ColumnDimension;
List<Document> docList = new List<Document>();
for(int i = 0; i < numDocs; i++) {
    Document d = new Document(v.GetElement(0, i) * s1, 
      v.GetElement(1, i) * s2, v.GetElement(2, i) * s3, i);
    docList.Add(d);
    if(d.X > maxX)
        maxX = d.X;
    if(d.X < minX)
        minX = d.X;
    if(d.Y > maxY)
        maxY = d.Y;
    if(d.Y < minY)
        minY = d.Y;
    if(d.Z > maxZ)
        maxZ = d.Z;
    if(d.Z < minZ)
        minZ = d.Z;
}

// normalize each document in the three
// dimensions and position it accordingly
double rangeX = maxX - minX;
double rangeY = maxY - minY;
double rangeZ = maxZ - minZ;
foreach(Document d in docList) {
    d.Normalise(minX, rangeX, minY, rangeY, minZ, rangeZ);
    Dispatcher.Invoke(new UpdateSearchResultDelegate(
      _SetSearchResultPosition), d.Index, d.X, d.Y, d.Z);
}

This code plots each document into the three dimensions introduced by our simplified model of the data. The x, y, and z placement is normalized against the maximum values for each, and then the 3D cube is created and positioned with those values.

Finally, a simple clustering algorithm is run against the columns in the second matrix (the approximated version). This algorithm groups similar items together until the desired number of clusters is reached (ten in this case). The cubes and search results are updated accordingly.

while (_docList.Count > numClusters)
{
    int count = _docList.Count;
    Document best1 = null, best2 = null;
    double bestScore = double.MinValue;
    for (int i = 0; i < count; i++)
    {
        Document doc1 = _docList[i];
        for (int j = 0; j < count; j++)
        {
            if (i != j)
            {
                Document doc2 = _docList[j];
                double score = doc1.vector.CosineSimilarity(doc2.vector);
                if (score > bestScore)
                {
                    bestScore = score;
                    best1 = doc1;
                    best2 = doc2;
                }
            }
        }
    }
    if (best1 != null && best2 != null)
    {
        best1.Merge(best2);
        _docList.Remove(best2);
    }
    else
        break;
}
return _docList;

Working with the 3D model

The 3D scene contains a directional light to give the cubes some extra depth, along with a PerspectiveCamera - the positions of which are both transformed by the trackball code in response to mouse input.

We can hit-test the 3D cubes with the following code:

Cube foundCube = null;
SearchResult correspondingSearchResult = null;
HitTestResult result = 
   VisualTreeHelper.HitTest(viewPort, e.GetPosition(viewPort));
RayHitTestResult rayResult = result as RayHitTestResult;
if(rayResult != null) {
    RayMeshGeometry3DHitTestResult rayMeshResult = 
            rayResult as RayMeshGeometry3DHitTestResult;
    if(rayMeshResult != null) {
        GeometryModel3D model = 
              rayMeshResult.ModelHit as GeometryModel3D;
        foreach(KeyValuePair<int,> item in _cubeLookup) {
            if(item.Value.Content == model && 
                      _searchResultLookup.TryGetValue(item.Key, 
                      out correspondingSearchResult)) {
                foundCube = item.Value;
                break;
            }
        }
    }
}

Then, the brushes on the selected/deselected cube and the corresponding search result can be updated accordingly.

The 3D scene can be positioned by holding down the left or right mouse buttons and dragging the mouse. The interesting thing about this trackball code is that the mouse events are fired on a transparent border that is superimposed over the 3D scene. This is because WPF's Viewport3D class doesn't fire mouse events unless the cursor is over a 3D model. The trackball code is basically a "black box" that can be attached to any 3D scene to implement visual manipulation of the scene. We attach it as follows (note that we are attaching to the super-imposed border):

ModelViewer.Trackball trackball = new ModelViewer.Trackball();
myPerspectiveCamera.Transform = trackball.Transform;
directionalLight.Transform = trackball.Transform;
...
trackball.EventSource = borderCapture;

Running the demo

The demo application is a Visual Studio 2005 application. For some reason, when building the application for the first time, you can see the message "cannot locate resource window1.xaml". The workaround is to clean or rebuild the solution and the error "goes away". If anyone knows of a better workaround, then please let me know!

Points of interest

(One) of the great things about WPF is that it makes it easy to present a 3D scene without worrying too much about all the pesky details. Visualizing in 3D is certainly a powerful technique, and one that we will surely see more of as time goes on.

Such a highly computational task on real-time data from the internet is the ideal realm of the Smart Client, and this article tries to show that the means are indeed at hand - visualizing a multi-dimensional "concept space" has never been so easy!

History

  • May 19, 2009: First version.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Jack_Dermody
Architect Dog Blue Software
Australia Australia
I graduated from The University of Sydney in 1998. Since then I have worked on large websites with c#/asp.net, built Windows software in c++, .net and WPF, and started my own company Ice Blue Digital that provides software consultancy and product design services.
 
I am currently working on Ask Bluey Visual Search - a new, free, innovative way to search.

Comments and Discussions

 
BugDemo doesn't work Pinmemberfarshidmaj14-Aug-12 6:07 
BugDemo doesn't seem to work PinmemberMember 83823317-Nov-11 6:29 
GeneralThe bit I don't follow is... PinmemberDave Cross19-May-09 1:49 
GeneralRe: The bit I don't follow is... PinmemberJack_Dermody19-May-09 11:44 
GeneralThis really looks interesting PinmemberDewey18-May-09 23:56 
GeneralRe: This really looks interesting PinmemberJack_Dermody19-May-09 11:47 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web04 | 2.8.141216.1 | Last Updated 18 May 2009
Article Copyright 2009 by Jack_Dermody
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid