Levenshtein distance, AKA "how to compute similarity between strings"

The Levenshtein distance is a useful distance metrics that you can use to state whether two strings are similar between each other. It computes the number of different characters of a pair of strings.
The Wikipedia page proposes two alternatives:

1. the first one is recursive
2. the second one is iterative

Although they are fully working, and the recursive one is elegant to be read, when I found myself in implementing it in JavaScript to compare pairs of tweet texts, the recursive one wouldn't come to a result. It took ages and did not finish the computation for the pair of provided strings!

Thus, I found this nice test case which compares the two versions (in JavaScript):

http://jsperf.com/levenshtein-distance-2

[Oh, well, why JavaScript? Tweets are collected in JSON format and stored in MongoDB, and when you are required to analyze in a quick-and-dirty manner your dataset, you can JavaScript functions directly via the MongoDB console]

Classification of imbalanced datasets

How to overcome these binary text classification problems?
1) Highly imbalanced dataset (less than 10% positive samples)
2) Positive class subjectivity

To overcome problem 1, one could use more refined classification systems (boosting, bagging, e.g., AdaBoost for starters), although a very large dataset (even if imbalanced) could help ease the problem. This complicates the situation "a little bit": to collect enough positive samples one has to annotate tons of instances.

To overcome problem 2, one could find a god to pray.

Sorting algorithms in C++ - A small introduction for newbies and wannabe programmers

Today I finished the preparation of my set of slides on sorting algorithms.
This presentation is meant to introduce sorting algorithms to the ones that:

• do not know what a sorting algorithm is
• want to know more details about bubble sort algorithm (less interesting...) and merge sort algorithm (...definitely interesting!)
• want to know how to implement such algorithms in C++
• are a little bit rusty on the sorting process

So, drink up!

A crash course in Python - Lesson 7: Functional programming

In this post, I don't want to discuss functional programming at all, but I would like to list some of the functional tools I encountered while using Python.

Curry functions

From Wikipedia:
"Currying is the technique of translating the evaluation of a function that takes multiple arguments (or a tuple of arguments) into evaluating a sequence of functions, each with a single argument"

Suppose we have the following function:

def exp(base, power):
    return base ** power

If we want to create the function two_to_the with a single input (which is the power) and fixed base (which is 2), we may do it by simply doing the following:

def two_to_the(power):
    return exp(2, power)

The same thing can be done as follows:

from functools import partial

two_to_the = partial(exp,2)  # is a function of one variable
print two_to_the(3)  # 8

square_of = partial(exp, power=2)
print square_of(3)  # 9

Map, Filter and Reduce

We occasionally use map, reduce and filter, which provide functional alternatives to list comprehension.

Map

The map function can be used with multiple-argument function if you provide multiple lists:

def multiply(x, y):
    return x * y

products = map(multiply, [1,2], [4,5])
# [1*4, 2*5] = [4, 10]

Filter

The filter function does the work of a list-comprehension if:

def isEven(x):
    return x % 2 == 0

xs = [1,2,3,4]
x_evens = [x for x in xs if isEven(x)]  # [2,4]
x_evens = filter(isEven, xs)  # same as above
list_evener = partial(filter, isEven)  # function that filters a list
x_evens = list_evener(xs)  # again [2,4]

Reduce

The reduce function combines the first two elements of a list, then that result with the third, that result with the fourth, and so on.

xProduct = reduce(multiply, xs)  # = 1*2*3*4 = 24
listProduct = partial(reduce, multiply)  # function that reduces a list
xProduct = listProduct(xs)  # again = 24

A crash course in Python - Lesson 6: Object-oriented programming

Python allows the programmer to define classes that encapsulate:

• attributes (i.e., data that describe the status of the instantiated object)
• methods (i.e., functions that describe the behavior of the instantiated object)

Suppose we want to create a class that describes a set of elements (although, as we saw in a previous lesson, Set is already a built-in Python data structure.

The behavior that we may apply on such class is as follows:

• adding items
• removing items from it
• check whether it contains a certain value

Here is a possible implementation of such class:

class Set:
    def __init__(self, values=None):  # constructor
        self.dict = {}
        if values is not None:
            for value in values:
                self.add(value)

    def __repr__(self):  # toString() method
        return "Set: " + str(self.dict.keys())

    def add(self, value):
        self.dict[value] = True

    def contains(self, value):
        return value in self.dict

    def remove(self, value):
        del self.dict[value]

Then we can use such class as follows:

s = Set([1,2,3])

s.add(4)
print s.contains(4)  # True

s.remove(3)
print s..contains(3)  # False

A crash course in Python - Lesson 5: some extra functionalities

Generators

A huge problem with lists is that they can grow really big. By using the following instruction:

L = range(1000000)

we actually create a list containing one million elements! If you only need to deal with one of them at a time, this results in a very inefficient code (supposing that you are able to fit the list in memory... if not, you are in trouble).

To overcome this problem, one can use generators. A generator is something that you can iterate over (e.g., by using a for loop) so that values are produced in a lazy manner, i.e., only when needed.

The creation of a generator resembles the creation of a list, with the only difference that elements are not materialized: we only suggest to the generator how to create the next elements when one need to use them.
To create a generator, one can use the following method:

def lazy_range(N):
    i = 0
    while i < N
        yield i
        i += 1

In this way, the yielded values are consumed one at a time, until none are left. The iteration over the generator is identical to the one we use over lists:

for i in lazy_range(10):
    do_something(i)

Actually, Python comes with a "lazy range function" as the one reported above, called xrange. Moreover, in Python 3 the function range is lazy itself.

By using generators, one could create even an infinite sequence! See the following:

def natural_numbers():
    n = 1
    while True:
        yield n
        n += 1

Note: the flip side of laziness is that you can only iterate through a generator once! If you need to iterate through something multiple times:

• either you recreate the generator
• or you use a list

Another way of creating a generator is by using list comprehension (see Lesson 2):

lazy_evens_below_20 = (i for i in lazy_range(20) if i % 2 == 0)

Randomness

The Python random module allows us to draw random numbers in the interval [0,1].
To draw a random number we do as follows:

import random
aRandomNumber = random.random()

Reproducibility

As usual, the random generator produces pseudorandom numbers (i.e., deterministic) based on an internal state. Such state can be initialize with random.seed. It is suggested to apply such approach, since you may want to get reproducible results in your experiments!
Every time you reset the seed to a specific value, the extraction of random numbers restarts, and redraws the same values it drew the first time you reset the seed to that value.

mySeed = 10

random.seed(mySeed)
print random.random()  # 0.5714

random.seed(mySeed)
print random.random()  # again 0.5714

Extracting values from a range

You can use random.randrange(), which takes:

• a single arguments B, when you want to extract numbers from the range [0, 1, ..., B-1]
• two arguments A and B, when you want to extract numbers from the range [A, A+1, ..., B-1]

Lists vs. random

The random module can be used to randomize the order of list elements, too. This is done via the random.shuffle() function:

upToTen = range(10)
random.shuffle(upToTen)
print upToTen
# [2,5,1,9,7,3,8,6,4,0]

With a similar mechanism, it is possible to pick up a random element from the list.

myBestFriend = random.choice(["Alice","Bob","Charlie"])  # 'Bob'

If you need to draw a sample of elements without replacement (i.e., without duplicates):

lotteryNumbers = range(60)
winningNumbers = random.sample(lotteryNumbers, 6)
# [16, 36, 10, 6, 25, 9]

To choose a sample of elements with replacement (i.e., with duplicates):

fourWithReplacement = [random.choice(range(10))
                          for _ in range(4)]

Regular expressions

Regular expressions provide a way of searching text.
The Python module that allows one to apply regular expressions to text is re.
We are not going to discuss regular expressions syntax in this article! Feel free to read some documentation.

args and kwargs

Python allows the programmer to declare function whose parameters are not specified. By using args and kwargs, one is able to read:

• the parameter values (via args)
• the parameter names (via kwargs)

def magic(*args, **kwargs):
    print "unnamed args: ", args
    print "keyword args:", kwargs

magic(1, 2, key="word", key2="word2")

# prints:
#   unnamed args: (1,2)
#   keyword args: {'key2': 'word2', 'key': 'word'}

A crash course in Python - Lesson 4: other data structures

Tuple

A tuple is an immutable list. Technically, you can do on/with tuples whatever you can do on a list that does not involve modifying it.

A tuple can be specified by using parentheses (or nothing) instead of square brackets:

my_tuple = (1, 2)
other_tuple = 3, 4

try:
    my_tuple[1] = 3
except TypeError:
    print "cannot modify a tuple"

A tuple is a convenient way of returning multiple values from functions:

def sum_and_product(x, y):
    return (x + y), (x * y)

sp = sum_and_product(2, 3)  # equals (5,6)
s, p = sum_and_product(5, 10) # s = 15, p = 50

Consequently, tuples can be used for multiple assignments too:

x, y = 1, 2  # x = 1, y = 2
x, y = y, x  # swap: x = 2, y = 1

Set

A set represents a collection of distinct elements. It can be declared, modified and manipulated as follows:

s = set()
s.add(1)  # s = {1}
s.add(2)  # s = {1, 2}
s.add(2)  # s = {1, 2}
x = len(s)  # x = 2
y = 2 in s  # y = True
z = 3 in s  # z = False

Sets perform very well when one has to check if they contain a specific value: in is a very fast operation! So, if we have a large collection of items that we want to use for a membership test, a set is more appropriate than a list.
Moreover, if one builds a set starting from a list, what he obtains is the set of distinct values in that list:

my_list = [1, 2, 3, 2, 1, 3]
item_set = set(my_list)  # {1, 2, 3}
distinct_elements = list(item_set) # [1, 2, 3]