Zeno was a Greek philosopher who lived circa 490 to 430 BC. Zeno’s paradoxes paradoxes have puzzled us for more than 2500 years now; three of them are presented here for you to ponder upon.

1. Achilles and the tortoise: In a race, the quickest runner can never overtake the slowest, since the pursuer must first reach the point whence the pursued started, so that the slower must always hold a lead.

2. Dichotomy paradox: That which is in locomotion must arrive at the half-way stage before it arrives at the goal.  

3. Arrow paradox: If everything when it occupies an equal space is at rest, and if that which is in locomotion is always occupying such a space at any moment, the flying arrow is therefore motionless.

Let’s think!

How credit card numbers work? It is interesting to see how quickly payment gateway web page can check whether given card number is valid. There is a pattern that every card number adheres to. Such patterns can be matched using JavaScript. A credit card number is made-up of four different components: MII (digit 1), IIN (digits 1-6), IAI (digits 7-15) and a check digit (last digit). Let’s see how credit card numbers work with the help of an example.

MII: In the above example, 6 is MII or Major Industry Identifier. This one digit identifier tells us which industry the card belongs to. Following table lists MIIs and industries they represent:

IIN/BIN: Digits 1 to 6 make up IIN or Issuer Identification Number. This six digit number includes the first digit of MII. IIN tells you which bank has issued the card. It is sometimes also referred to as BIN (Bank Identifier Number). The website Binlists is an organized collection of BINs for credit cards as well as debit cards.

IAI: 7 to 15 digits represent Individual Account Identifier. This number is used to identify the customer account associated with the card.

Check Digit: The last digit is a check digit calculated by Luhn algorithm. In our example card number, check digit is 5.

6069 9832 3412 3455

Luhn test is at the heart of the question how credit card numbers work! Luhn test is the frontline defence against fraud. If you are a programmer, you may want to take a look at Rosettacode.org where this algorithm is implemented in 98 different programming languages.

References

1. Patterns in Card Numbers
2. Binlists.com
3. Find Digital Root of a Number
4. Rosettacode.org

This post discusses Apache log visualization with Matplotlib library. First, download the data file used in this example from here.

We will require numpy and matplotlib

In [1]:

import numpy as np
import matplotlib.pyplot as plt

numpy.loadtext() can directly load a text file in an array requests-idevji.txt contains only hour on which request was made, this is achieved by pre-prcoessing the Apache log.

In [2]:

data = np.loadtxt (‘requests-idevji.txt’)

We need 24 bins because we have 24 hours’ data. For other attributes of hist() see references.

In [3]:

plt.hist(data, bins=24)
plt.title(“Requests @ iDevji”)
plt.xlabel(“Hours”)
plt.ylabel(“# Requests”)

Out[3]:

Text(0,0.5,’# Requests’)

In [4]:

plt.show()


References:

1. numpy.loadtext(), Scipy.org
2. PyPlot API, Matplotlib.org

As a young adult nothing thrilled me more than Jeremy Brett’s performance as Sherlock Holmes. “You know my methods, apply them!” he would say. So let’s try to play Sherlock ourselves. We use Natural Language Tool Kit or NLTK to guess setting of a Sherlock story in terms of its geographic location. In this NLTK example, our approach is very naive: identify the most frequent place mentioned in the story. We use Named Entity Recognition (NRE) to identify geopolitical entities (GPE) and filter out the most frequent of them. This approach is very naive because there is no pre-processing on the text and GPEs may include other concepts apart from geographic locations such as nationalities. But we want to keep this really simple and fun. So here we go: Code :

#NLTK example
#This code reads one text file at a time

from nltk import word_tokenize, pos_tag, ne_chunk

read a text file

text = file (‘filepath/file.txt’)

replace \n with a spcae

data=text.read().replace(‘\n’, ‘ ‘)

chunked = ne_chunk (pos_tag ( word_tokenize (data) ))

extract GPEs

extracted = []
for chunk in chunked:
if hasattr (chunk, ‘label’):
if chunk.label() == ‘GPE’:
extracted.append (‘’.join (c[0] for c in chunk))

extract most frequent GPE

from collections import Counter
count = Counter(extracted)
count.most_common(1)

Results:

Sr.

Story

Extracted Location

Actual Setting

Result

The Adventure of the Dancing Men

[(‘Norfolk’, 14)]

Norfolk

Success

The Adventure of the Solitary Cyclist

[(‘Farnham’, 6)]

Farnham

Success

A Scandal in Bohemia

[(‘Bohemia’, 6)]

Bohemia

Success

The Red-Headed League

[(‘London’, 7)]

London

Success

The Final Problem

[(‘London’, 8)]

London

Success

The Greek Interpreter

[(‘Greek’, 15)]

Greece

Fail

We got 5/6 predictions correct! These are not discouraging results and we may think of using this code somewhere in a more serious application. References:

1. Sherlock Holmes Stories in Plain Text
2. NLTK Documentation

In this tutorial I’ll show you building a movie recommendation service with Apache Spark. Two users are alike if they rated a product similarly. For example, if Alice rated a book 3/5 and Bob also rated the same book 3.3/5 they are very much alike. Now if Bob buys another book and rates it 4/5 we should suggest that book to Alice, that’s what a recommender system does. See references if you want to know more about how recommender systems work. We are going to use Alternating Least Squares method from MLLib, and MovieLens 100K dataset which is only 5 MB in size. Download the dataset from https://grouplens.org/datasets/movielens/. Code :

from pyspark.mllib.recommendation import ALS,MatrixFactorizationModel, Rating
from pyspark import SparkContext

sc = SparkContext ()

#Replace filepath with appropriate data
movielens = sc.textFile(“filepath/u.data”)

movielens.first() #u’196\t242\t3\t881250949’
movielens.count() #100000

#Clean up the data by splitting it,
#movielens readme says the data is split by tabs and
#is user product rating timestamp
clean_data = movielens.map(lambda x:x.split(‘\t’))

#We’ll need to map the movielens data to a Ratings object
#A Ratings object is made up of (user, item, rating)
mls = movielens.map(lambda l: l.split(‘\t’))
ratings = mls.map(lambda x: Rating(int(x[0]),\
int(x[1]), float(x[2])))

#Setting up the parameters for ALS
rank = 5 # Latent Factors to be made
numIterations = 10 # Times to repeat process

#Need a training and test set, test set is not used in this example.
train, test = ratings.randomSplit([0.7,0.3],7856)

#Create the model on the training data
model = ALS.train(train, rank, numIterations)

For Product X, Find N Users to Sell To

model.recommendUsers(242,100)

For User Y Find N Products to Promote

model.recommendProducts(196,10)

#Predict Single Product for Single User
model.predict(196, 242)

References:

1. Building a Recommender System in Spark with ALS, LearnByMarketing.com
2. MovieLens
3. Video : Collaborative Filtering, Stanford University
4. Matrix Factorisation and Dimensionality Reduction, Thierry Silbermann
5. Building a Recommendation Engine with Spark, Nick Pentreath, Packt

In this post, GraphFrames PySpark example is discussed with shortest path problem. GraphFrames is a Spark package that allows DataFrame-based graphs in Saprk. Spark version 1.6.2 is considered for all examples. Including the package with PySaprk shell :

pyspark –packages graphframes:graphframes:0.1.0-spark1.6

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

from pyspark import SparkContext
from pyspark.sql import SQLContext
sc = SparkContext ()
sqlContext = SQLContext(sc)

# create vertex DataFrame for users with id and name attributes
v = sqlContext.createDataFrame([
  ("a", "Alice"),
  ("b", "Bob"),
  ("c", "Charlie"),
], ["id", "name"])

# create edge DataFrame with "src" and "dst" attributes
e = sqlContext.createDataFrame([
  ("a", "b", "friends"),
  ("b", "c", "follow"),
  ("c", "b", "follow"),
], ["src", "dst", "relationship"])

# create a GraphFrame with v, e
from graphframes import *
g = GraphFrame(v, e)

# example : getting in-degrees of each vertex
g.inDegrees.show()

Output:

example : getting “follow” relationships in the graph

1

g.edges.filter("relationship = 'follow'").count()

Output:

2

getting shortest paths to “a” from each vertex

1
2

results = g.shortestPaths(landmarks=\["a"\])
results.select("id", "distances").show()

Feel free to ask your questions in the comments section!

Logistic regression with Spark is achieved using MLlib. Logistic regression returns binary class labels that is “0” or “1”. In this example, we consider a data set that consists only one variable “study hours” and class label is whether the student passed (1) or not passed (0).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

from pyspark import SparkContext
from pyspark import SparkContext
import numpy as np
from numpy import array
from pyspark.mllib.regression import LabeledPoint
from pyspark.mllib.classification import LogisticRegressionWithLBFGS

sc = SparkContext ()

def createLabeledPoints(label, points):
    return LabeledPoint(label, points)

studyHours = [
 [ 0, [0.5]],
 [ 0, [0.75]],
 [ 0, [1.0]],
 [ 0, [1.25]],
 [ 0, [1.5]],
 [ 0, [1.75]],
 [ 1, [1.75]],
 [ 0, [2.0]],
 [ 1, [2.25]],
 [ 0, [2.5]],
 [ 1, [2.75]],
 [ 0, [3.0]],
 [ 1, [3.25]],
 [ 0, [3.5]],
 [ 1, [4.0]],
 [ 1, [4.25]],
 [ 1, [4.5]],
 [ 1, [4.75]],
 [ 1, [5.0]],
 [ 1, [5.5]]
]

data = []

for x, y in studyHours:
data.append(createLabeledPoints(x, y))

model = LogisticRegressionWithLBFGS.train( sc.parallelize(data) )

print (model)

print (model.predict([1]))

Output:

1
2
3

spark-submit regression-mllib.py
(weights=[0.215546777333], intercept=0.0)
1

References:

1. Logistic Regression - Wikipedia.org
2. See other posts in Learn Data Science

k-Means clustering with Spark is easy to understand. MLlib comes bundled with k-Means implementation (KMeans) which can be imported from pyspark.mllib.clustering package. Here is a very simple example of clustering data with height and weight attributes.

Arguments to KMeans.train:

1. k is the number of desired clusters
2. maxIterations is the maximum number of iterations to run.
3. runs is the number of times to run the k-means algorithm
4. initializationMode can be either ‘random’or ‘k-meansII’

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

   from pyspark import SparkContext from pyspark.mllib.clustering import KMeans from numpy import array sc = SparkContext() sc.setLogLevel ("ERROR") #12 records with height, weight data data = array([185,72, 170,56, 168,60, 179,68, 182,72, 188,77, 180,71, 180,70, 183,84, 180,88, 180,67, 177,76]).reshape(12,2) #Generate Kmeans model = KMeans.train(sc.parallelize(data), 2, runs=50, initializationMode="random") #Print out the cluster of each data point print (model.predict(array([185, 71]))) print (model.predict(array([170, 56]))) print (model.predict(array([168, 60]))) print (model.predict(array([179, 68]))) print (model.predict(array([182, 72]))) print (model.predict(array([188, 77]))) print (model.predict(array([180, 71]))) print (model.predict(array([180, 70]))) print (model.predict(array([183, 84]))) print (model.predict(array([180, 88]))) print (model.predict(array([180, 67]))) print (model.predict(array([177, 76])))

Output
0
1
1
0
0
0
0
0
0
0
0
0
(10 items go to cluster 0, where as 2 items go to cluster 2)

Above is a very naive example in which we use training dataset as input data too. In real world we will train a model, save it and later use it for predicting clusters of input data. So here is how you can save a trained model and later load it for prediction.

Training and Storing the Model

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

from pyspark import SparkContext
from pyspark.mllib.clustering import KMeans
from numpy import array

sc = SparkContext()

#12 records with height, weight data
data = array([185,72, 170,56, 168,60, 179,68, 182,72, 188,77, 180,71, 180,70, 183,84, 180,88, 180,67, 177,76]).reshape(12,2)

#Generate Kmeans
model = KMeans.train(sc.parallelize(data), 2, runs=50, initializationMode="random")

model.save(sc, "savedModelDir")

This will create a directory, _savedModelDir_ with two subdirectories _data_ and _metadata_ where the model is stored. **Using Already Trained Model for Predicting Clusters** Now, let's use trained model by loading it. We need to import KMeansModel in order to use it for loading the model from file.

from pyspark import SparkContext
from pyspark.mllib.clustering import KMeans, KMeansModel
from numpy import array

sc = SparkContext()

#Generate Kmeans
model = KMeansModel.load(sc, "savedModelDir")

#Print out the cluster of each data point
print (model.predict(array([185, 71])))
print (model.predict(array([170, 56])))
print (model.predict(array([168, 60])))
print (model.predict(array([179, 68])))
print (model.predict(array([182, 72])))
print (model.predict(array([188, 77])))
print (model.predict(array([180, 71])))
print (model.predict(array([180, 70])))
print (model.predict(array([183, 84])))
print (model.predict(array([180, 88])))
print (model.predict(array([180, 67])))
print (model.predict(array([177, 76])))

References:

1. Clustering and Feature Extraction in MLlib, UCLA
2. k-Means Clustering Algorithm Explained, DnI Institute
3. k-Means Clustering with Python, iDevji

Apriori Algorithm is used in finding frequent itemsets. Identifying associations between items in a dataset of transactions can be useful in various data mining tasks. For example, a supermarket can make better shelf arrangement if they know which items are purchased together frequently. The challenge is that given a dataset D having T transactions each with n number of attributes, how to find itemsets that appear frequently in D? This can be trivially solved by generating all possible itemsets (and checking each of the candidate itemset against support threshold.) which is computationally expensive. Apriori algorithm effectively eliminates majority of itemsets without counting their support value. Non-frequent itemsets are known prior to calculation of support count, thus the name Apriori alogrithm. It works on the following principle which is also known as apriori property:  

If an itemset is frequent, then all of its subsets must also be frequent.

  Suppose{c, d, e}is a frequent itemset. Clearly, any transaction that contains {c, d, e} must also contain its subsets, {c, d}, {c, e}, {d, e}, {c}, {d}, and {e}. As a result, if {c, d, e} is frequent, then all subsets of {c, d, e} must also be frequent. The algorithm works on bottom-up approach, that is generate 1-itemsets, eliminate those below support threshold then generate 2-itemsets, eliminate … and so on. This way only frequent _k_-itemsets are used to generate _k+1_-itemsets significantly reducing number of candidates. Let’s see an example: Our dataset contains four transactions with following particulars:

TID

Items

100

1, 3, 4

200

2, 3, 5

300

1, 2, 3, 5

400

2, 5

Support value is calculated as support (a -> b) = Number of transactions a and b appear in / total transactions. But for the sake of simplicity we use support value as number of times each transaction appears. We also assume support threshold = 2. Step 1 : Generate 1-itemsets, calculate support for each and mark itemsets below support threshold

Itemset

Support

{1}

2

{2}

3

{3}

3

{4}

1

{5}

3

Now, mark itemsets where support is below threshold

Itemset

Support

{1}

2

{2}

3

{3}

3

{4}

1

{5}

3

Step 1 : Generate 2-itemsets, calculate support for each and mark itemsets below support threshold. Remember for generating 2-itemsets we do not consider eliminated 1-itemsets.

Itemset

Support

{1, 2}

1

{1, 3}

2

{1, 5}

1

{2, 3}

2

{2, 5}

3

{3, 5}

2

Marking 2-itemsets below support threshold

Itemset

Support

{1, 2}

1

{1, 3}

2

{1, 5}

1

{2, 3}

2

{2, 5}

3

{3, 5}

2

Step 3 : Generate 3-itemsets, calculate support for each and mark itemsets below support threshold

Itemset

Support

{2, 3, 5}

2

  Stop: We stop here because 4-itemsets cannot be generated as there are only three items left! Following are the frequent itemsets that we have generated and which are above support threshold: {1}, {2}, {3}, {5}, {1, 3}, {2, 3}, {2, 5}, {3, 5} and {2, 3, 5}. Itemsets generated but not qualified are : {4}, {1, 2} and {1, 5}. If we do not use Apriori and instead rely on brute-force approach then number of candidate itemsets generated will be much larger! Feel free to ask your questions in comments section below!

Functional programming in Python is possible with the use of lambda map reduce and filter functions. This article briefly describe use of each these functions.

Lambda : Lambda specifies an anonymous function. It is used to declare a function with no name; When you want to use function only once. But why would you declare a function if you don’t want to reuse the code? Read on you’ll see. Syntax: lambda arg1, arg2 : expression

lambda x : x*x

This lambda expression with just one argument x which returns square of x.

Map : It takes two arguments, the first argument is name of a function and second argument is a sequence. map() applies function f to all elements in the sequence and returns a new sequence. Syntax: map (func, sequence)

1
2
3
4

list = [1, 2, 3]
map (lambda x : x*x, list)

#output: [1, 4, 9]

This code also demonstrates use of lambda. Instead writing a square function we substituted it with a lambda expression. map() applies it to all elements in the list and returns a new list with each element square of original element.

Reduce: reduce() continuously applies a function to a sequence and returns one value. In the following example we sum all elements in the original list. Syntax: reduce (func, sequence)

1

#output: 6

Filter: It filters all values in a sequence for which given function returns True. Syntax: filter (booleanFunc, sequence)

1
2

filter (lambda x : x%2, list)
#output: [1, 3]

Above example returns all odd integers in the list. Remember 2%2=0 is treated as boolean value False.