SSIS Junkie : fuzzy

Fuzzyness

jamie.thomson — Wed, 21 May 2008 06:57:00 GMT

SQL Server 2008 is introducing some interesting querying and storage enhancements such as the introduction of spatial data and the FILESTREAM attribute on VARBINARY(MAX) columns and my thoughts have recently turned to what querying enhancements we are going to see in future versions. I was chatting to Rob Farley recently and we started to wonder aloud about whether the database engine might one day support fuzzy querying methods in the engine (Rob spoke about it here).

What do we mean by fuzzy querying? Well I'll try to put this as close to lay terms as possible. Fuzzy querying allows us to compare two things that aren't the same but are a little bit the same. Are you any the wiser? Perhaps an example might suffice.

Take the following list of values:

Brian Smith

Bryan Smith

Brian Smyth

Bryan Smyth

Brian Smythe

Now as far as SQL Server 2008 is concerned those five names are all different, that's just how SQL works. Something either is true or it isn't. Yay or nay. Zero or one. Clearly though we as humans can see there is some sort of similarity between those five names and that is important information to know; its not hard to imagine a class of applications that could make use of this ability to know that things are similar as opposed to being the same. For example, perhaps I am maintaining a customer database for which different telesales operators have the ability to enter data. Its not inconceivable that different people may enter data for the same customer except with slightly different spellings and I am going to want to know about that. Fuzzy querying would allow us to check for these anomalies.

Those of you that have used SSIS 2005 will know that Fuzzy Querying exists in that product as provided by the Fuzzy Lookup and Fuzzy Grouping components however I personally don't want to have to call out to a SSIS package to process data that is already in my database. Rob posted a submission to Connect requesting fuzzy querying behaviour in the database engine so if you think this is an important feature go here and vote for it.

Following on from the basic ability to query on similarity, I wonder if indexing on similarity could be possible? Take the example above. Placing an index on those five values today wouldn't result in them appearing contiguously in the index however if we indexed on similarity...perhaps they would. Something to think about.

OK, so that covers off fuzzy querying of textual values. Looking even further into the future I wonder if there are even more complex scenarios that could leverage this inate ability to know that two things are similar. Here's a scenario to consider:

I use a free tool called Windows Live Photo Gallery (WLPG) to manage my personal photo library and one of the features of this tool is the ability to tag photos (WLPG uses SQL Server CE under the covers by the way to manage all of the photo data). For example, I might tag all of the photos in which my fiance, Helen, appears.

Its occurred to me before that a really great feature of WLPG would be auto-tagging. That is, the ability to compare a batch of new photos with all my existing photos and then discover that Helen appears in some of my new photos and tag them appropriately.

Here again we are comparing things (images rather than text this time) based on similarity. It may seem a bit far-fetched based on our pre-conceptions of what a RDBMS does but I see no reason why the ability to compare images to discover whether a person appears in both of them shouldn't be a function of the database rather than a standalone tool. Its clear in SQL Server 2008 that Microsoft are taking the product beyond what we traditionally think a RDBMS should do so the capabilities I'm talking about here seem, to me, to be a logical extension.

What do you think?

-Jamie

P.S. My colleague Peter Hanlon has an interesting perspective on fuzzy querying where he considers the impact that it could have on house buying. Read it here.

SSIS: Regular Expressions & Fuzzy Matching

jamie.thomson — Sun, 03 Apr 2005 11:40:00 GMT

A few days ago I posted a blog entry discussing some experiences of using fuzzy matching in SSIS. In it I talked of a problem I was having resolving 50 different records with the word "google" in them down to a single record "www.google.com".

Another problem I was having was that fuzzy matching doesn't allow much control over what these 50 records may resolve to. I want them all to resolve to "www.google.com" but they may easily all resolve to "images.google.jp" which is not good.

Nils Erik Ihlen read the article and wrote to me suggesting that regular expressions may be able to help solve my problem. He told me he had implemented regular expressions in SSIS using the script component transformation and was kind enough to share his work with me. This was tremendously helpful to me because I am in no way a conventional .Net developer and I don't really know what the .Net Framework provides so I learnt alot from this.

The following screenshot shows how Nils used regular expressions in the script component to search for records containing the word "google".

Basically what the code does is to search the incoming record for the string "google" and if it is found output the string "http://www.google.com" and "" otherwise. And there you have it....exactly what I wanted...everything coming out as google.

Now, let's try and apply this to my practical example. I can add this regular expression to my package that currently uses fuzzy matching but we still have problems with it. Every string that I wanted to search for would require its own regular expression. There may be literally hundreds of these strings (e.g. microsoft, msn, yahoo, askjeeves, conchango) and building a regular expression for every one of them is going to become unwieldy. I still need the fuzzy matching component to deal with all the records that my regular expressions cannot resolve.

What I'm really saying is that on their own, regular exressions and fuzzy matching have alot of uses but combining them together gives me a powerful mechanism for dealing with irregular data.

I have posted an example package demonstrating the use of regular expressions here (apologies that its not a .dtsx file, our blogging engine doesn't seem to like them for some reason). Feel free to download it and have a play...it doesn't require any configuration, just download it, run it, and see what regular expressions can do for you. For help with regular expressions, try this link.

Many thanks to Nils for the help and advice he has provided me with.

I have been discussing what Conchango's approach to using fuzzy matching should be with my colleague Mick Horne. Mick did alot of work using SSIS's fuzzy components way back in summer 2004. His overall conclusion was that if you want fuzzy matching/lookups to do exactly what you want then there has to be some form of human element involved. His suggestion was that the outputs from fuzzy matching can be sent to a lookup table which can then be used on future executions, prior to the fuzzy matching, to ensure that repeated occurences are always mapped to the same value. To make this truly useful and intuitive we would need to periodically check over the lookup table and decide whether a mapping is satisfactory. For example if fuzzy matching says "images.google.com" always maps to "www.google.jp" that might not be what we want, so we want to get rid of that mapping from the lookup table. It wouldn't be hard to knock up a sinple interface that allowed you to do this.

[Warning, "stating the bleeding obvious" coming up!!] Fuzzy logic in SSIS isn't an exact science. SSIS's architecture allows you many methods of refining fuzzy computation to make it work for you. Explore these methods before you start to implement fuzzy computation en masse. Be sure you know what you're getting into. That sounds very cautionary, and it is. But it doesn't mean to say with the correct approach fuzzy matching/lookups can't be a powerful tool in your SSIS armoury for dealing with inexact data.

-Jamie

SSIS: Adventures with Fuzzy Matching

jamie.thomson — Wed, 30 Mar 2005 19:48:00 GMT

I have been doing some work with the Fuzzy Matching transformation and as anyone that has done any form of fuzzy logic before will know, it is far from being an exact science.

Fuzzy logic for those that don't know can be defined in many ways:
"The process of reaching conclusions based on information and facts that are not 100 percent certain." - www.stanford.edu/~buc/SPHINcsX/bkhm15.htm
"A way of dealing with uncertain information and variables that do not permit simple yes/no categorisations (e.g. colour). Can also be used to make decisions where uncertainty occurs." - www.calresco.org/glossary.htm
"Fuzzy logic is applied to fuzzy sets where membership in a fuzzy set is a probability, not necessarily 0 or 1. Non-fuzzy logic manipulates outcomes that are either true or false. Fuzzy logic needs to be able to manipulate degrees of "maybe" in addition to true and false." - www.twocrows.com/glossary.htm

Or here's a back-of-the-***-packet description courtesy of yours truly:
"Fuzzy logic is a method used for approximating things that are not exact"

All of these descriptions are a bit fuzzy (pardon the extraordinarily bad pun) so lets apply a bit of context, namely some SSIS context.

SSIS provides 2 transformations that provide fuzzy computation, the Fuzzy lookup transform and the Fuzzy Matching transform. The Fuzzy Lookup transform allows you to match records in a dataset to records in a secondary set that are approximately the same. The Fuzzy Matching transform enables you to group records together that are approximately the same.

I have recently been using the fuzzy matching component a little and I thought it might be worth sharing my experiences.
I have been using fuzzy matching in a scenario of processing web server log files. I wanted to use fuzzy matching to say, for example, a referrer of http://www.google.com should be considered the same as http://www.google.co.uk which should be considerd the same as http://www.google.net etc... All I care about is that someone visited my site from Google.

The Fuzzy Matching algorithm attempts to match all records that are suitably similar according to a similarity "score". The algorithm requires that some temporary tables are created in SQL Server in order to determine this "score" and then to achieve the matching.

I had 154237 records flowing through my Fuzzy Matching transform and herein arose the first problem. There were many many identical records in my dataset. For example, the web server logs capture data from http://www.conchango.com and therefore we would expect that there would be many records with a referrer of "www.conchango.com", and indeed there were. Other sites also appeared many many times. The Fuzzy Matching algorithm attempts to group all records that suitably similar regardless of how many times a record may be considered familar to something else. Before you chew that statement over let me, more simply, tell you how it manifested itself. One of the temporary tables that I mentioned before had over 21million records in it when I pulled the plug. Goodness knows how big it would have grown if I hadn't. This resulted in approximately 10GB of hard disk being used by the database file and transaction file and up to that point had taken about 15 minutes to execute.

I needed to cut down the amount of data being processed by my Fuzzy Matching transform without losing any accuracy. My approach was to use a Multicast transform to seperate the data flow into 2 identical flows. I sent one of the flows to a sort transform to eliminate duplicates (my recordset was reduced from 154237 records to 236 records), sent that data through the fuzzy matching transformation and then join to the other flow using the original referrer value and insert the 154237 records into my destination table, complete with the "cleaned" referrer.

The screenshot here shows my data flow. The sort transformation prior to the join are required because the Merge Join transformation requires its inputs to be sorted.

This worked and it worked well. The whole data flow executed in seconds and it successful eliminated records such as http://www.google.com./ and replaced it with http://www.google.com

So, my first tip when using the fuzzy logic transforms in SSIS is to work with as small a data set as possible. You can use the technique I utilised here, that of eliminating duplicates, or any of a number of other possible techniques.

I wasn't satisfied with the results though. I still had 50 "cleaned" referrers that had the word "Google" in them. When you think that there are sites such as http://images.google.com, http://gmail.google.com as well as the obvious http://www.google.com and on top of that there are .com, .co.uk, .de, .fr, .es etc etc... (in fact most countries in the world) you start to see how problems can arise. I wanted those 50 referrers to appear as 1 single referrer - Google, and after all this is the functionality that the Fuzzy Matching component is meant to provide.

I mentioned earlier the existence of a each record being given a "score" to indicate how well it matches to another record. The score will be a number between 0 and 1. A score of 1 indicates an exact match. Any record with a score that is above a specified threshold is considered a satisfactory fuzzy match. Part of the skill of optimising the fuzzy matching process is to modify this threshold so as to achieve the desired results.

The screenshot below shows the dialog that is used to set the similarity threshold.

The default setting for this threshold is 0.8 and that is the value I was running with when I got the 50 different Google referrers. I wanted these 50 records to be considered suitably similar so I had to lower the similarity threshold.

A threshold of 0.6 resulted in 39 different occurences with the word "Google" in them. Interestingly "www.google.com.pk" and "www.google.com.ph" are not considered suitably close enough but "www.google.co.id" and "www.google.co.in" are. Weird!!

A threshold of 0.5 resulted in 29 different occurences containing the word "Google". Note that it thinks
"google", "www.google.com", "www.google.com.au" & "www.google.com.ar" are suitably similar but "www.google.com.ph" is not.

I gave up at this point. Clearly I could eventually lower the threshold to something that would allow everything with the word "google" in it to appear together, it just seems as though that threshold needs to be a lot lower than we would imagine. Setting the threshold too low increases the danger that records that have no real-world match could in fact be matched.

Clearly if you are going to be using fuzzy logic within SSIS you need to do it with caution. Test beforehand the settings that you apply and ensure that you have the optimum balance between matching those records that are indeed similar and eliminating those rogue values that look similar but in fact are not!

I plan to do more work with fuzzy components in the future so if I find out anything else that is worthy of sharing you can be sure I'll put it up here.

-Jamie