Set (union and intersection)

A set is an unordered collection of objects. Because it is not a sequence objects such as lists and tuples, its element cannot be indexed:

>>> s = set([1,2,3])
>>> s[1]
Traceback (most recent call last):
  File "", line 1, in 
TypeError: 'set' object does not support indexing

Sets cannot have duplicate members:

>>> set(["I", "was", "a", "child", "and", "she", "was", "a", "child"])
set(['a', 'and', 'I', 'she', 'child', 'was'])

We can make a set in two ways: set([]) or {[]}:

>>> s1 = set([1, 2.0, 'three', (4,5)])
>>> s2 = {1, 2.0, 'three', (4,5)}

>>> s1
set([(4, 5), 1, 2.0, 'three'])
>>> s2
set([(4, 5), 1, 2.0, 'three'])

However, we can not have dictionaries, lists, and other sets as a member of a set:

>>> set([ {'one':1} ])
Traceback (most recent call last):
  File "", line 1, in 
TypeError: unhashable type: 'dict'
>>> set([ [1,2,3] ])
Traceback (most recent call last):
  File "", line 1, in 
TypeError: unhashable type: 'list'
>>> set([ {1, 2, 3} ])
Traceback (most recent call last):
  File "", line 1, in 
TypeError: unhashable type: 'set'

One exception is the frozenset, and it can be a member of a set because it's immutable which means it has a hash value which never changes during its lifetime (so, it's hashable):

>>> f = frozenset([1,2,3])
>>> s = {f}

Note that dictionaries, lists, and sets are not hashable. Therefore, none of them cannot be a member of a set.

>>> hash(1)
1
>>> hash('was')
-4873397472080222404
>>> hash((1,2))
3713081631934410656
>>> hash([1,2])
Traceback (most recent call last):
  File "", line 1, in 
TypeError: unhashable type: 'list'
>>> hash({'one':1})
Traceback (most recent call last):
  File "", line 1, in 
TypeError: unhashable type: 'dict'
>>> hash({1,2})
Traceback (most recent call last):
  File "", line 1, in 
TypeError: unhashable type: 'set'

As we can see from the example above, all other types are hashable except dictionaries, lists, and sets!

hashable - from Python Glossary

An object is hashable if it has a hash value which never changes during its lifetime (it needs a __hash__() method), and can be compared to other objects (it needs an __eq__() or __cmp__() method). Hashable objects which compare equal must have the same hash value.

Hashability makes an object usable as a dictionary key and a set member, because these data structures use the hash value internally.

All of Python's immutable built-in objects are hashable, while no mutable containers (such as lists or dictionaries) are. Objects which are instances of user-defined classes are hashable by default; they all compare unequal (except with themselves), and their hash value is their id().

We can initialize a set using a list:

>>> L = [1,2,3]
>>> s = set(L)
>>> s
set([1, 2, 3])

We create an empty set:

>>> s1 = set()
>>> s1
set([])

We add a single member:

>>> s1.add("first")
>>> s1
set(['first'])

>>> s1.add("2nd")
>>> s1
set(['2nd', 'first'])

We can add several members at once using update():

>>> s1.update( ["3rd", "4th"] )
>>> s1
set(['4th', '2nd', '3rd', 'first'])

The following example shows how to get the union and intersection of sets. The two get*() function takes a set which has list elements, and calculate union and intersection, respectively.

def getUnion(s):
    """ return a union from a set of lists """  
    u = set()
    for x in s:
       u = u | set(x)
    return u

def getIntersection(s):
    """ return an intersection from a set of lists """  
    i = set(s[0])
    for x in s[1:]:
        i = i & set(x)
    return i

if __name__ == "__main__":
    s = [];
    s.append([1,2,3,4])
    s.append([2,3,5,7])
    s.append([2,4,6])    
    
    u = getUnion(s)
    i = getIntersection(s)

    print("input=%s") %(s)
    print("size of input=%s") %(len(s))

    print("union=%s size=%s") %(u, len(u))
    print("intersection=%s size=%s") %(i, len(i))

Output:

input=[[1, 2, 3, 4], [2, 3, 5, 7], [2, 4, 6]]
size of input=3
union=set([1, 2, 3, 4, 5, 6, 7]) size=7
intersection=set([2]) size=1

The Jaccard coefficient measures similarity between finite sample sets, and is defined as the size of the intersection divided by the size of the union of the sample sets:

The code below calculates the Jaccard coefficient in the jaccard() function. It takes two lists indexed by the list of tuples. The tuple indices are the result from the itertools.combinations() function:

from __future__ import division
import itertools

def jaccard(s1, s2):
    " takes two lists as input and returns Jaccard coefficient"
    st1=set(s1)
    st2=set(s2)
    u = set(st1).union(st2)
    i = set(st1).intersection(st2)
    return len(i)/len(u)


if __name__ == "__main__":
    s = [];
    s.append([1,2,3,4])
    s.append([2,3,5,7])
    s.append([2,4,6])  
    s.append([8,9,10,11,12])

    print("input set : %s") %(s)

    combinations = list( itertools.combinations([x for x in range(len(s))], 2) )
    print("combinations=%s") %(combinations)

    for c in combinations:
        i1 = c[0]
        i2 = c[1]
        jac = jaccard(s[i1], s[i2])
        print("%s : %s,%s : jaccard=%s") %(c, s[i1],s[i2],jac)

Output:

input set : [[1, 2, 3, 4], [2, 3, 5, 7], [2, 4, 6], [8, 9, 10, 11, 12]]
combinations=[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
(0, 1) : [1, 2, 3, 4],[2, 3, 5, 7] : jaccard=0.333333333333
(0, 2) : [1, 2, 3, 4],[2, 4, 6] : jaccard=0.4
(0, 3) : [1, 2, 3, 4],[8, 9, 10, 11, 12] : jaccard=0.0
(1, 2) : [2, 3, 5, 7],[2, 4, 6] : jaccard=0.166666666667
(1, 3) : [2, 3, 5, 7],[8, 9, 10, 11, 12] : jaccard=0.0
(2, 3) : [2, 4, 6],[8, 9, 10, 11, 12] : jaccard=0.0

"Suppose our document D is the string "abcdabd", and we pick k= 2. Then the set of 2-shingles for D is {ab,bc,cd,da,bd}. Note that the substring "ab" appears twice within D, but appears only once as a shingle."
- A. Rajaraman and J. Ullman (2010). "Mining of Massive Datasets".

The following code uses 3 documents, the first one is the original but the second one is the plagiarized the first one. The third one is an unrelated doc. When we look at the result (Jaccard coefficient), clearly doc[0] and doc[1] are similar:

(0, 1) : jaccard=0.141248720573
(0, 2) : jaccard=0.0141557128413
(1, 2) : jaccard=0.00681596884129

Here is the code:

from __future__ import division
import itertools

def jaccard_set(s1, s2):
    " takes two sets and returns Jaccard coefficient"
    u = s1.union(s2)
    i = s1.intersection(s2)
    return len(i)/len(u)

if __name__ == '__main__':
    documents = ["The legal system is made up of civil courts, criminal courts and specialty courts such as family law courts and bankruptcy court. Each court has its own jurisdiction, which refers to the cases that the court is allowed to hear. In some instances, a case can only be heard in one type of court. For example, a bankruptcy case must be heard in a bankruptcy court. In other instances, there may be several potential courts with jurisdiction. For example, a federal criminal court and a state criminal court would each have jurisdiction over a crime that is a federal drug offense but that is also an offense on the state level.",
      "The legal system is comprised of criminal and civil courts and specialty courts like bankruptcy and family law courts. Every one of the courts is vested with its own jurisdiction. Jurisdiction means the types of cases each court is permitted to rule on. Sometimes, only one type of court can hear a particular case. For instance, bankruptcy cases an be ruled on only in bankruptcy court. In other situations, it is possible for more than one court to have jurisdiction. For instance, both a state and federal criminal court could have authority over a criminal case that is illegal under federal and state drug laws.",
      "In many jurisdictions the judicial branch has the power to change laws through the process of judicial review. Courts with judicial review power may annul the laws and rules of the state when it finds them incompatible with a higher norm, such as primary legislation, the provisions of the constitution or international law. Judges constitute a critical force for interpretation and implementation of a constitution, thus de facto in common law countries creating the body of constitutional law."]

    # shingle size
    k = 9   
  
    shingles = []
    for doc in documents:
        sh = set()
        size = len(doc)
        for i in range(size-k):
            sh.add(doc[i:i+k])
        print("size=%s: %s") %(len(sh), sh)
        shingles.append(sh)

    # print("sets: shingles=%s") %(shingles)

    print("len(shingles)=%s") %(len(shingles))

    combinations = list( itertools.combinations([x for x in range(len(shingles))], 2) )
    print("combinations=%s") %(combinations)

    # combinations of shingles(=numbe of docs)
    for c in combinations:
        i1 = c[0]
        i2 = c[1]
        jac = jaccard_set(shingles[i1], shingles[i2])
        print("%s : jaccard=%s") %(c,jac)

Output:

size=542: set(['sdiction,', 'sdiction.', 'r a crime', 'se on the', ... 'ion, whic', 'e may be '])
size=573: set(['sdiction.', 'r a crimi', 'e for mor', 'sdiction ', ... 'is possib', ', it is p'])
size=461: set(['dy of con', 'e constit', 'of a cons', 'Courts wi', ... 'tion, the', 'ation and'])
len(shingles)=3
combinations=[(0, 1), (0, 2), (1, 2)]
(0, 1) : jaccard=0.141248720573
(0, 2) : jaccard=0.0141557128413
(1, 2) : jaccard=0.00681596884129

Selecting appropriate k is not easy. If we use k=5 instead of k=9, we get different result:

(0, 1) : jaccard=0.255405405405
(0, 2) : jaccard=0.0627352572146
(1, 2) : jaccard=0.0551558752998

If we use longer tokens (k=20):

(0, 1) : jaccard=0.0238907849829
(0, 2) : jaccard=0.0
(1, 2) : jaccard=0.0

In all the cases above, we can see the last document is not similar to the first two docs while the first and the second one appear to have some similarities.

This section is not much different from the previous section. The primary difference is the way of constructing tokens: we uses words instead of characters. For example, k-shingle means k words but not k characters.

So, when k=4. for the document D="It was many and many a year ago", we get:

{'It was many and', 'was many and many'...}

Instead of:

{'It w', 't wa', ' was', 'as m'...}

Here is the revised code:

from __future__ import division
import itertools
import re

# a shingle in this code is a string with K-words
K = 4

def jaccard_set(s1, s2):
    " takes two sets and returns Jaccard coefficient"
    u = s1.union(s2)
    i = s1.intersection(s2)
    return len(i)/len(u)

def make_a_set_of_tokens(doc):
    """makes a set of K-tokens"""

    # replace non-alphanumeric char with a space, and then split
    tokens = re.sub("[^\w]", " ",  doc).split()

    sh = set()
    for i in range(len(tokens)-K):
        t = tokens[i]
        for x in tokens[i+1:i+K]:
            t += ' ' + x 
        sh.add(t)
    return sh

if __name__ == '__main__':

    documents = ["The legal system is made up of civil courts, criminal courts and specialty courts such as family law courts and bankruptcy court. Each court has its own jurisdiction, which refers to the cases that the court is allowed to hear. In some instances, a case can only be heard in one type of court. For example, a bankruptcy case must be heard in a bankruptcy court. In other instances, there may be several potential courts with jurisdiction. For example, a federal criminal court and a state criminal court would each have jurisdiction over a crime that is a federal drug offense but that is also an offense on the state level.",
      "The legal system is comprised of criminal and civil courts and specialty courts like bankruptcy and family law courts. Every one of the courts is vested with its own jurisdiction. Jurisdiction means the types of cases each court is permitted to rule on. Sometimes, only one type of court can hear a particular case. For instance, bankruptcy cases an be ruled on only in bankruptcy court. In other situations, it is possible for more than one court to have jurisdiction. For instance, both a state and federal criminal court could have authority over a criminal case that is illegal under federal and state drug laws.",
      "In many jurisdictions the judicial branch has the power to change laws through the process of judicial review. Courts with judicial review power may annul the laws and rules of the state when it finds them incompatible with a higher norm, such as primary legislation, the provisions of the constitution or international law. Judges constitute a critical force for interpretation and implementation of a constitution, thus de facto in common law countries creating the body of constitutional law."]
  
    shingles = []
    # handle documents one by one
    # makes a list of sets which are compresized of a list of K words string
    for doc in documents:
        # makes a set of tokens
        # sh = set([' ', ..., ' '])
        sh = make_a_set_of_tokens(doc)

        # shingles : list of sets (sh)
        shingles.append(sh)

    # print("shingles=%s") %(shingles)
    
    combinations = list( itertools.combinations([x for x in range(len(shingles))], 2) )
    print("combinations=%s") %(combinations)

    # compare each pair in combinations tuple of shingles
    for c in combinations:
        i1 = c[0]
        i2 = c[1]
        jac = jaccard_set(shingles[i1], shingles[i2])
        print("%s : jaccard=%s") %(c,jac)

Output:

combinations=[(0, 1), (0, 2), (1, 2)]
(0, 1) : jaccard=0.0196078431373
(0, 2) : jaccard=0.0
(1, 2) : jaccard=0.0