Re: [computer-go] Fuzzy pattern matching

[Richard Brown <rbrown@xxxxxxxx>]

Gian-Carlo Pascutto wrote:
> Hello,
Hi.

> does anyone have any resources related to fuzzy
> pattern matching? I'm trying to determine when
> two bitmaps (or tritmaps or two bitmaps) are 'almost'
> the same, or when no exact match is found, which other
> bitmaps represent closest matches.
I hope I won't come to regret this, but...

If you Google [and I know I do!] for "k-nearest neighbor",
"Delauney triangulation", and "convex hulls" you may find
something useful.

If you can represent each bitmap as a vector of real numbers,
then you can use these sorts of algorithms.

In k-nearest neighbor searching, when a novel vector doesn't match
exactly the data you've already collected, you can find its k
most-similar vectors in the data.

The appropriate value for k can be determined experimentally.
Odd numbers seem to work best.

Dimensionality doesn't matter too much; but of course, as always,
feature selection -- what you choose to represent -- is the most
difficult part.

> Bonus points for the method being very fast :)
Hmmm.  When we first implemented this, we had to search through
almost the entire dataset to find the k nearest neighbors, and that
was s-l-o-w.  A partitioning scheme that already lumps similar
vectors together has increased the speed around a thousandfold.

> Anybody using this in a go program?
Yeah.

--
Richard L. Brown            Office of Information Services
Senior Unix Sysadmin        University of Wisconsin System
                           780 Regent St., Rm. 246
rbrown@xxxxxxxxxxxxxxxxx             Madison, WI  53715

_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://computer-go.org/mailman/listinfo/computer-go