# Nick Grattan's Blog

About Microsoft SharePoint, .NET, Natural Language Processing and Machine Learning

## Summary – Document and String Similarity/Distances Measures in C#

This post summarizes a number of recent posts on this blog showing how to calculate similarity and distance measures in C# for documents and strings.

First, documents can be represented by a “Bag of Words” (a list of the unique words in a document) or a “Frequency Distribution” (a list of the unique words in a document together with the occurrence frequency).

Bag of Words and Frequency Distributions in C#

The simplest similarity measure covered in this series is the Jaccard Similarity measure. This uses a bag of words and compares the number of common words between two documents with the overall number of words. This does not take into account the relative frequency nor the order of the words in the two documents.

Jaccard Similarity Index for measuring Document Similarity

Three measures using Frequency Distributions are described. In all these cases a n-dimensional space is created from the Frequency Distribution with a dimension for each word in the documents being compared. They are:

1. Euclidean Distance – The shortest distance between two documents in the Frequency Distribution space.
2. Manhattan Distance – The sum of all the sides in the hyper rectangle formed around two documents in the Frequency Distribution Space.
3. Cosine Distance – The cosine of the angle subtended at the origin between two documents in the Frequency Distribution Space.

These measures take into account the word frequency, but Cosine Distance cannot distinguish between documents where the relative frequency of words is the same (rather than the absolute frequency). They do not take into account the order of the words in the documents.

Euclidean, Manhattan and Cosine Distance Measures in C#

The final measure is the Levenshtein Minimum Edit Distance. This measure aligns two documents and calculates the number of inserts, deletes or substitutions that are required to change the first document into the second document, which may not necessarily be the same length. This measure takes into account the words, the frequency of words and the order of words in the document.

Levenshtein Minimum Edit Distance in C#

By using MinHash and Locality Sensitivity Hashing, similar documents can be identified very, very efficiently – these techniques are related to the Jaccard Similarity Index.

MinHash for Document Fingerprinting in C#

Locality Sensitivity Hashing for finding similar documents in C#

Written by Nick Grattan

July 10, 2014 at 6:21 pm

## Levenshtein Minimum Edit Distance in C#

with one comment

From Lesk[1] p.254 – “The Levenstein, or edit distance , defined between two strings of not necessarily equal length, is the minimum number of ‘edit operations’ required to change one string into the other. An edit operation is a deletion, insertion or alteration [substitution] of a single character in either sequence “. Thus the edit distance between two strings or documents takes into account not only the relative frequency of characters/words but the position as well. Strings can be aligned too. For example, here’s an alignment of two nucleotide sequences where ‘-‘ represents an insertion:

ag-tcc
cgctca

For these two strings the edit distance is 3 (2 substitutions and 1 insertion/deletion).  In the case above the substitutions and inserts/deletes (“indels”) have the same weight. Often, substitutions are given a weight of 2 and indels 1 resulting in an edit distance of 5 for these strings. Substitutions are really an insert with a delete, hence the double weight.

The edit distance calculation uses Dynamic Programming. The algorithm is well described in Jurafsky & Martin[2] p.107. and summarized in these PowerPoint slides.  This class implements the edit distance algorithm and text alignment in C#:

/// <summary>
/// Calculates the minimum edit distance (Levenshtein) between two lists of items
/// </summary>
/// <typeparam name="T">Type of item (e.g. characters or string)</typeparam>
public class MinEditDistance<T>
{
public MinEditDistance(List<T> list1, List<T> list2)
{
InsCost = 1;
DelCost = 1;
SubCost = 2;
List1 = list1;
List2 = list2;
}

List<T> List1;
List<T> List2;

Distance[,] D;

// The costs of inserts, deletes, substitutions. Normally run SubCost with 2, others at 1
public int InsCost { get; set; }
public int DelCost { get; set; }
public int SubCost { get; set; }

/// <summary>
/// Calculates the minimum edit distance using weights in InsCost etc.
/// </summary>
/// <returns></returns>
public int CalcMinEditDistance()
{
if (List1 == null || List2 == null)
{
throw new ArgumentNullException();
}
if (List1.Count == 0 || List2.Count == 0)
{
throw new ArgumentException("Zero length list");
}
// prepend dummy value
List1.Insert(0, default(T));
List2.Insert(0, default(T));

int lenList1 = List1.Count;
int lenList2 = List2.Count;
D = new Distance[lenList1, lenList2];
for (int i = 0; i < lenList1; i++)
{
D[i, 0].val = DelCost * i;
D[i, 0].backTrace = Direction.Left;
}
for (int j = 0; j < lenList2; j++)
{
D[0, j].val = InsCost * j;
D[0, j].backTrace = Direction.Up;
}
for (int i = 1; i < lenList1; i++)
for (int j = 1; j < lenList2; j++)
{
int d1 = D[i - 1, j].val + DelCost;
int d2 = D[i, j - 1].val + InsCost;
int d3 = (EqualityComparer<T>.Default.Equals(List1[i], List2[j])) ? D[i - 1, j - 1].val : D[i - 1, j - 1].val + SubCost;
D[i, j].val = Math.Min(d1, Math.Min(d2, d3));
// back trace
if (D[i, j].val == d1)
{
D[i, j].backTrace |= Direction.Left;
}
if (D[i, j].val == d2)
{
D[i, j].backTrace |= Direction.Up;
}
if (D[i, j].val == d3)
{
D[i, j].backTrace |= Direction.Diag;
}
}
return D[lenList1 - 1, lenList2 - 1].val;
}

/// <summary>
/// Returns alignment strings. The default value for T indicates an insertion or deletion in the appropriate string. align1 and align2 will
/// have the same length padded with default(T) regardless of the input string lengths.
/// </summary>
/// <param name="align1">First string alignment</param>
/// <param name="align2">Second string alignment</param>
public void Alignment(out List<T> align1, out List<T> align2)
{
if (D == null)
{
throw new Exception("Distance matrix is null");
}
int i = List1.Count - 1;
int j = List2.Count - 1;

align1 = new List<T>();
align2 = new List<T>();
while (i > 0 || j > 0)
{
Direction dir = D[i, j].backTrace;
int dVal, dDiag = int.MaxValue, dLeft = int.MaxValue, dUp = int.MaxValue;
if ((dir & Direction.Diag) == Direction.Diag)
{
// always favour diagonal as this is a match on items
dDiag = -1;
}
if ((dir & Direction.Up) == Direction.Up)
{
dUp = D[i, j - 1].val;
}
if ((dir & Direction.Left) == Direction.Left)
{
dLeft = D[i - 1, j].val;
}
dVal = Math.Min(dDiag, Math.Min(dLeft, dUp));
if (dVal == dDiag)
{
i--;
j--;
}
else if (dVal == dUp)
{
j--;
}
else if (dVal == dLeft)
{
i--;
}
}
align1.Reverse();
align2.Reverse();
}

/// <summary>
/// Writes out the "D" matrix showing the edit distances and the back tracing directions
/// </summary>
public void Write()
{
int lenList1 = List1.Count;
int lenList2 = List2.Count;
Console.Write("      ");
for (int i = 0; i < lenList1; i++)
{
if (i == 0)
Console.Write(string.Format("{0, 6}", "*"));
else
Console.Write(string.Format("{0, 6}", List1[i]));
}
Console.WriteLine();
for (int j = 0; j < lenList2; j++)
{
if (j == 0)
Console.Write(string.Format("{0, 6}", "*"));
else
Console.Write(string.Format("{0, 6}", List2[j]));
for (int i = 0; i < lenList1; i++)
{
Console.Write(string.Format("{0,6:###}", D[i, j].val));
}
Console.WriteLine();
Console.Write("      ");
for (int i = 0; i < lenList1; i++)
{
WriteBackTrace(D[i, j].backTrace);
}
Console.WriteLine();
Console.WriteLine();
}
}

/// <summary>
/// Writes out one backtrace item
/// </summary>
/// <param name="d"></param>
void WriteBackTrace(Direction d)
{
string s = string.Empty;
s += ((d & Direction.Diag) == Direction.Diag) ? "\u2196" : "";
s += ((d & Direction.Up) == Direction.Up) ? "\u2191" : "";
s += ((d & Direction.Left) == Direction.Left) ? "\u2190" : "";
Console.Write(string.Format("{0,6}", s));
}

/// <summary>
/// Represents one cell in the 'D' matrix
/// </summary>
public struct Distance
{
public int val;
public Direction backTrace;
}

/// <summary>
/// Direction(s) for one cell in the 'D' matrix.
/// </summary>
[FlagsAttribute]
public enum Direction
{
None = 0,
Diag = 1,
Left = 2,
Up = 4
}
}

The following code shows how this class can be used:

// example from Speach & Language Processing, Jurafsky & Martin P. 108, cites Krushkal (1983)
[TestMethod]
public void LevenshteinAltDistance()
{
string s1 = "EXECUTION";
string s2 = "INTENTION";
int m = Align(s1, s2, 2, 1, 1, "*EXECUTION", "INTE*NTION");
Assert.AreEqual(8, m);
}

private int Align(string s1, string s2, int subCost = 1, int delCost = 1, int insCost = 1, string alignment1 = null, string alignment2 = null)
{
List<char> l1 = s1.ToList();
List<char> l2 = s2.ToList();
MinEditDistance<char> med = new MinEditDistance<char>(l1, l2);
List<char> a1, a2;
med.SubCost = subCost;
med.DelCost = delCost;
med.InsCost = insCost;
int m = med.CalcMinEditDistance();
Console.WriteLine("Min edit distance: " + m);
med.Write();

med.Alignment(out a1, out a2);
foreach (char c in a1)
{
if (c == default(char))
Console.Write("*");
else
Console.Write(c);
}
Console.WriteLine();
foreach (char c in a2)
{
if (c == default(char))
Console.Write("*");
else
Console.Write(c);
}
Console.WriteLine();
if (alignment1 != null && alignment2 != null)
{
Assert.AreEqual(alignment1, new string(a1.ToArray()).Replace('\0', '*'));
Assert.AreEqual(alignment2, new string(a2.ToArray()).Replace('\0', '*'));
}
return m;
}

The output from this test reports the edit distance to be 8 and the alignment is:

*EXECUTION
INTE*NTION

The “D” matrix with backtrack information is also displayed:

Note that there may be several different possible alignments since backtracking allows multiple routes through the matrix. This web site http://odur.let.rug.nl/kleiweg/lev/ provides an online tool for calculating the edit distance.

[1] “Introduction to Bioinfomatics”, Arthur M. Lesk, 3rd Edition 2008, Oxford University Press

[2] “Speech and Language Processing” D.Jurafsky, J.Martin, 2nd Edition 2009, Prentice Hall

Written by Nick Grattan

June 21, 2014 at 8:10 am

## Microsoft Azure to offer Machine Learning Services – Preview July 2014

” Microsoft Azure Machine Learning combines power of comprehensive machine learning with benefits of cloud”

“Machine learning today is usually self-managed and on premises, requiring the training and expertise of data scientists. However, data scientists are in short supply, commercial software licenses can be expensive and popular programming languages for statistical computing have a steep learning curve. Even if a business could overcome these hurdles, deploying new machine learning models in production systems often requires months of engineering investment. Scaling, managing and monitoring these production systems requires the capabilities of a very sophisticated engineering organization, which few enterprises have today.

Microsoft Azure Machine Learning, a fully-managed cloud service for building predictive analytics solutions, helps overcome the challenges most businesses have in deploying and using machine learning. How? By delivering a comprehensive machine learning service that has all the benefits of the cloud. In mere hours, with Azure ML, customers and partners can build data-driven applications to predict, forecast and change future outcomes – a process that previously took weeks and months.”

See this blog post from: Joseph Sirosh, Corporate Vice President of Machine Learning at Microsoft

Written by Nick Grattan

June 20, 2014 at 3:22 pm

## Euclidean, Manhattan and Cosine Distance Measures in C#

with one comment

Euclidean, Manhattan and Cosine Distance Measures can be used for calculating document dissimilarity. Since similarity is the inverse of a dissimilarity measure, they can also be used to calculate document similarity. For document similarity the calculations are based on Frequency Distributions. See here for a comparison between Bag of Words and Frequency Distributions and here for using Jaccard Similarity with a Bag of Words.

The calculation starts with a frequency distribution for words in a number of documents. For example:

A n-dimensional space is then created, with a dimension for each of the words. In the above example a dimension will be created for “Cat”, “Mouse”, “Dog” and “Rat”, so it’s a four dimensioned space. Then, each document is plotted in this space. The following diagram shows the plot for just two of the four dimensions with the Euclidean Distance (the shortest distance between two points):

The Manhattan distance is the sum of the lengths of the rectangle formed by the two points:

Finally, the Cosine distance is the angle subtended at the origin between the two documents. A value of 0 degrees represents identical documents and 90 degrees dissimilar documents. Note that this distance is based on the relative frequency of words in a document. A document with, say, twice as many occurrences of all words compared to another document will be regarded as identical.

For a full description of these distance measures see [1], including details on their calculation.

The Euclidean and Manhattan distances are specific examples of a more general Lr-Norm distance measure. The ‘r’ refers to a power term, and for Manhattan this is 1 and for Euclidean it’s 2. Therefore a single class can be used to implement both:

public class LrNorm
{
/// <summary>
/// Returns Euclidean distance between frequency distributions of two lists
/// </summary>
/// <typeparam name="T">Type of the item, e.g. int or string</typeparam>
/// <param name="l1">First list of items</param>
/// <param name="l2">Second list of items</param>
/// <returns>Distance, 0 - identical</returns>
public static double Euclidean<T>(List<T> l1, List<T> l2)
{
return DoLrNorm(l1, l2, 2);
}

/// <summary>
/// Returns Manhattan distance between frequency distributions of two lists
/// </summary>
/// <typeparam name="T">Type of the item, e.g. int or string</typeparam>
/// <param name="l1">First list of items</param>
/// <param name="l2">Second list of items</param>
/// <returns>Distance, 0 - identical</returns>
public static double Manhattan<T>(List<T> l1, List<T> l2)
{
return DoLrNorm(l1, l2, 1);
}

/// <summary>
/// Returns LrNorm distance between frequency distributions of two lists
/// </summary>
/// <typeparam name="T">Type of the item, e.g. int or string</typeparam>
/// <param name="l1">First list of items</param>
/// <param name="l2">Second list of items</param>
/// <param name="r">Power to use 2 = Euclidean, 1 = Manhattan</param>
/// <returns>Distance, 0 - identical</returns>
public static double DoLrNorm<T>(List<T> l1, List<T> l2, int r)
{
// find distinct list of values from both lists.
List<T> dvs = FrequencyDist<T>.GetDistinctValues(l1, l2);

// create frequency distributions aligned to list of descrete values
FrequencyDist<T> fd1 = new FrequencyDist<T>(l1, dvs);
FrequencyDist<T> fd2 = new FrequencyDist<T>(l2, dvs);

if (fd1.ItemFreq.Count != fd2.ItemFreq.Count)
{
throw new Exception("Lists of different length for LrNorm calculation");
}
double sumsq = 0.0;
for (int i = 0; i < fd1.ItemFreq.Count; i++)
{
if (!EqualityComparer<T>.Default.Equals(fd1.ItemFreq.Values[i].value, fd2.ItemFreq.Values[i].value))
throw new Exception("Mismatched values in frequency distribution for LrNorm calculation");

if (r == 1)   // Manhattan optimization
{
sumsq += Math.Abs((fd1.ItemFreq.Values[i].count - fd2.ItemFreq.Values[i].count));
}
else
{
sumsq += Math.Pow((double)Math.Abs((fd1.ItemFreq.Values[i].count - fd2.ItemFreq.Values[i].count)), r);
}
}
if (r == 1)    // Manhattan optimization
{
return sumsq;
}
else
{
return Math.Pow(sumsq, 1.0 / r);
}
}
}

The following code shows how to use the methods in this class:

double LrNormUT(int r)
{
// Sample from Page 92 "Mining of Massive Datasets"
List l1 = new List();
List l2 = new List();

return LrNorm.DoLrNorm(l1, l2, r);
}
[TestMethod]
public void Euclidean1()
{
double dist = LrNormUT(2);
Assert.AreEqual(5, (int)dist);
Console.WriteLine("d:" + dist);
}

[TestMethod]
public void Manhattan()
{
double dist = LrNormUT(1);
Assert.AreEqual(7, (int)dist);
Console.WriteLine("d:" + dist);
}

The following class calculates the Cosine Distance:

/// <summary>
/// Calculate cosine distance between two vectors
/// </summary>
public class Cosine
{
/// <summary>
/// Calculates the distance between frequency distributions calculated from lists of items
/// </summary>
/// <typeparam name="T">Type of the list item, e.g. int or string</typeparam>
/// <param name="l1">First list of items</param>
/// <param name="l2">Second list of items</param>
/// <returns>Distance in degrees. 90 is totally different, 0 exactly the same</returns>
public static double Distance<T>(List<T> l1, List<T> l2)
{
if (l1.Count() == 0 || l2.Count() == 0)
{
throw new Exception("Cosine Distance: lists cannot be zero length");
}

// find distinct list of items from two lists, used to align frequency distributions from two lists
List<T> dvs = FrequencyDist<T>.GetDistinctValues(l1, l2);
// calculate frequency distributions for each list.
FrequencyDist<T> fd1 = new FrequencyDist<T>(l1, dvs);
FrequencyDist<T> fd2 = new FrequencyDist<T>(l2, dvs);

if(fd1.ItemFreq.Count() != fd2.ItemFreq.Count)
{
throw new Exception("Cosine Distance: Frequency count vectors must be same length");
}
double dotProduct = 0.0;
double l2norm1 = 0.0;
double l2norm2 = 0.0;
for(int i = 0; i < fd1.ItemFreq.Values.Count(); i++)
{
if (!EqualityComparer<T>.Default.Equals(fd1.ItemFreq.Values[i].value, fd2.ItemFreq.Values[i].value))
throw new Exception("Mismatched values in frequency distribution for Cosine distance calculation");

dotProduct += fd1.ItemFreq.Values[i].count * fd2.ItemFreq.Values[i].count;
l2norm1 += fd1.ItemFreq.Values[i].count * fd1.ItemFreq.Values[i].count;
l2norm2 += fd2.ItemFreq.Values[i].count * fd2.ItemFreq.Values[i].count;
}
double cos = dotProduct / (Math.Sqrt(l2norm1) * Math.Sqrt(l2norm2));
// convert cosine value to radians then to degrees
return Math.Acos(cos) * 180.0 / Math.PI;
}
}

Here are some methods that show how to use this class:

double tol = 0.00001;

[TestMethod]
public void CosineSimple()
{
List<int> l1 = new List<int>();
List<int> l2 = new List<int>();

double dist = Cosine.Distance(l1, l2);
Console.WriteLine(dist);
Assert.AreEqual(40.3645365730974, dist, tol);
}

Reference: [1] “Mining of Massive Datasets” by A.Rajaraman, J. Leskovec, J.D. Ullman, Cambridge University Press. 2011.  P.90. See http://infolab.stanford.edu/~ullman/mmds.html

Written by Nick Grattan

June 10, 2014 at 7:45 am

## Bag of Words and Frequency Distributions in C#

The simplest way of representing a document is the “Bag of Words”. This is the list of unique words used in a document. It is therefore a simple present/not present indicator for all words in the vocabulary and does not take into account the occurrence frequency of these words nor the order of the words.

The Bag of Words is used by the Jaccard Similarity measure for document similarity. If two documents have the same set of words then they are deemed identical, and if they have no common words they are completely different. This similarity measure takes no account of the relative length of the two documents being compared.

In C# a Bag of Words can be represented by a generic List<>. The list type can either be a string (in which case it’s the actual word) or an integer (where the integer is a lookup into a dictionary). The latter is more efficient because the word is stored just once as a string and the integer lookup (4 bytes) is most likely to be shorter than the word itself. The C# in this blog post creates a dictionary, some Bag of Words and calculates the Jaccard index for documents.

Frequency Distributions record not only the words in a document but also the frequency with which they occur. However, like Bags of Words, no account is taken of the order of words in the document. These frequency distributions can be compared and used to assess the similarity between two or more documents.

These techniques generally calculate the distance between two documents. A distance measure is the inverse of similarity. Common techniques are Euclidean, Manhattan and Cosine distances.

The following C# class manages Frequency Distributions. It’s a generic class, and so can use strings (the words themselves) or integers (for lookups into a dictionary).

/// <summary>
/// Manages Frequency Distributions for items of type T
/// </summary>
/// <typeparam name="T">Type for item</typeparam>
public class FrequencyDist<T>
{
/// <summary>
/// Construct Frequency Distribution for the given list of items
/// </summary>
/// <param name="li">List of items to calculate for</param>
public FrequencyDist(List<T> li)
{
CalcFreqDist(li);
}

/// <summary>
/// Construct Frequency Distribution for the given list of items, across all keys in itemValues
/// </summary>
/// <param name="li">List of items to calculate for</param>
/// <param name="itemValues">Entire list of itemValues to include in the frequency distribution</param>
public FrequencyDist(List<T> li, List<T> itemValues)
{
CalcFreqDist(li);
// add items to frequency distribution that are in itemValues but missing from the frequency distribution
foreach (var v in itemValues)
{
if(!ItemFreq.Keys.Contains(v))
{
ItemFreq.Add(v, new Item { value = v, count = 0 });
}
}
// check that all values in li are in the itemValues list
foreach(var v in li)
{
if (!itemValues.Contains(v))
throw new Exception(string.Format("FrequencyDist: Value in list for frequency distribution not in supplied list of values: '{0}'.", v));
}
}

/// <summary>
/// Calculate the frequency distribution for the values in list
/// </summary>
/// <param name="li">List of items to calculate for</param>
void CalcFreqDist(List<T> li)
{
itemFreq = new SortedList<T,Item>((from item in li
group item by item into theGroup
select new Item { value = theGroup.FirstOrDefault(), count = theGroup.Count() }).ToDictionary(q => q.value, q => q));
}
SortedList<T, Item> itemFreq = new SortedList<T, Item>();

/// <summary>
/// Getter for the Item Frequency list
/// </summary>
public SortedList<T, Item> ItemFreq { get { return itemFreq; } }

public int Freq(T value)
{
if(itemFreq.Keys.Contains(value))
{
return itemFreq[value].count;
}
else
{
return 0;
}
}

/// <summary>
/// Returns the list of distinct values between two lists
/// </summary>
/// <param name="l1"></param>
/// <param name="l2"></param>
/// <returns></returns>
public static List<T> GetDistinctValues(List<T> l1, List<T> l2)
{
return l1.Concat(l2).ToList().Distinct().ToList();
}

/// <summary>
/// Manages a count of items (int, string etc) for frequency counts
/// </summary>
/// <typeparam name="T">The type for item</typeparam>
public class Item
{
/// <summary>
/// The value of the item, e.g. int or string
/// </summary>
public T value { get; set; }
/// <summary>
/// The count of the item
/// </summary>
public int count { get; set; }
}
}

The following code shows how this class can be used:

List<string> li = new List<string>();
FrequencyDist<string> cs = new FrequencyDist<string>(li);
foreach (var v in cs.ItemFreq.Values)
{
Console.WriteLine(v.value + " : " + v.count);
}

The output from executing this code is:

One : 1
Three : 3
Two : 2

Written by Nick Grattan

June 9, 2014 at 6:51 pm

## Creating single server SharePoint 2013 trial for Windows Azure

with one comment

Creating virtual machines with Azure is a great way of standing up test servers, especially for SharePoint where the installation can be long.

You can create a SharePoint Server 2014 trial server from Azure by first selecting “From Gallery”:

And then select the “SharePoint Server 2013 Trial”

The problem with this is that SharePoint is already installed for a farm installation and therefore cannot be installed as a standalone server. As the description provided by Microsoft states, you will need to create another virtual machine for SQL Server and possibly another for a domain controller with Active Directory.

To circumvent this issue you can:

1. Create the VM using the gallery in Azure as shown above
2. Install SQL Server Express 2012 on the newly create VM
3. Create a new farm using the   New-SPConfigurationDatabase PowerShell command
4. Run the SharePoint Products Configurations Wizard and join the farm you’ve just created.

The last three steps are described in this excellent blog article: http://blogs.msdn.com/b/suhasaraos/archive/2013/04/06/installing-sharepoint-2013-on-a-single-server-without-a-domain-controller-and-using-sql-server-express.aspx

Written by Nick Grattan

April 22, 2014 at 1:00 am