Making my own similarity measures module

I wanted to have a number of functions for determining set similarity: the overlap coefficient, the Jaccard similarity, the Dice-Sørensen coefficient, the cosine similarity, the simple matching coefficient, and the hamming coefficient. Of course, the first question is, “Why bother?” since there are already libraries out there that contain functions for this. Well, I did a round of searching for them, but nothing worked well with sets or a single value. scikit-learn has two functions: jaccard_score¹ and cosine_similarity², and neither accept a set or return a single value, let alone a value that matches the examples I found. scipy has three functions: jaccard³ and dice⁴ only work on boolean arrays, and cosine⁵ only works for equally sized arrays/lists. py_stringmatching has the most functions with four: being overlap⁶, jaccard⁷, dice⁸, and cosine⁹. However, the only work on strings and are (a bit) cumbersome because you have to instantiate an object for each method. Also, the Hamming coefficient is a metric I deviced based of the Hamming distance. So, like Bender from Futurama, I decided “Yeah, well, I’m gonna go build my own module.”

Created with imgflip.com

Let me take you through what I wanted out of this module, how I did it, and what I learned from it. In this story I’ll focus on the implementation in Python of the measures. In another article I’ll go into detail on the working of these set similarity measures.

Outline

For my own module, I drafted the following requirements, some functional and some more as a personal training goal:

• Validate the input for every function by
• checking if all inputs are sets;
• checking if both sets are not empty;
• for certain functions, checking if at least one set is non-empty because some measures can’t provide a sensible outcome if one set is empty;
• checking if all the elements of the sets are of the same type;
• and, check if the optional total range is a superset of the other two sets.
• Use a decorator for the validation function to get better at constructing these.
• Create a function each for similarity measure that is
• the overlap coefficient;
• the Jaccard similarity;
• the Dice-Sørensen coefficient;
• the cosine similarity;
• and the simple matching coefficient.
• Use Python set operations as the default, i.e. &|-^, for the calculations as a way to better understand their use.
• Make all the functions with a similar signature to allow easier looping with
• Write tests using pytest to better learn to test code and use that library as it integrates well with VS Code.

Implementation

Input validation

In order to reduce duplicate code and still have uniform validation, I choose to use a decorator. A set of guard clauses in each function would be against the DRY principle¹⁰, and using one (private) function for validation was something I already knew. The decorator function had to be able to accept an optional parameter as to check if at least one set is non-empty.

To create such a decorator, you can use the following boilerplate code as seen below. The innermost function wrapper handles providing the positional and keyword arguments to the decorated function. The actual decorator inner passes the function to be decorated to wrapper and the decorator factory takes the (optional) parameters for the decorator. For further reference, see these articles¹¹.

def decorator(parameters=None):
    # action based on parameters
    def inner(func):
        # action based on parameters
        def wrapper(*args, **kwargs):
            # action based on parameters
            # actions before calling function
            func(*args, **kwargs)
            # actions after calling function
        return wrapper
    return inner

In the snapshot below, you can see how each function calls the next one. The decorator gets put onto the stack together with the decorated function. Next the decorator adds the inner function, which in turn calls the wrapper.

Snapshot taken from https://pythontutor.com

The decorator I created has the following elements:

• The decorator factory validate_input takes an optional parameter option and validates it. Otherwise, a ValueError is raised. It returns the decorator decorator_validate_input.
• The decorator decorator_validate_input decorates the wrapper wrapper_validate_input using the functools.wrap decorator and returns it. This wraps decorator makes the decorator mirror the decorated function by copying attributes such as __name__, and __doc__ (the docstring).¹²
• The wrapper does the actual validation of the input for the decorated function.
• First, a check is done whether all arguments are sets. Otherwise, a TypeError is raised.
• Second, if the option "one" is provided, a check is done whether one set is empty. If so, a warning is given and None returned without calling the decorated function. I moved this up in contrast to my outline because this would result in an earlier exit from the function. This embraces the ‘fail-fast principle’ of guard clauses.¹³
• Third, a check is done if both sets are empty. If so, a warning is given and 0 returned without calling the decorated function.
• Fourth, a check is done whether all the elements in the sets are of the same type. To allow integers and floats to be used mixed, I used the number.Number class as it is the root of the numbers hierarchy in Python.¹⁴ Otherwise, a TypeError is raised.
• Finally, check if the provided total range is a superset of the other two sets. If this is not the case, remove it from the arguments. The check for a superset is done with >= and the union of a set found using the | operator.

If all checks are passed, the decorated function is returned.

def validate_input(option: typing.Optional[str] = None) -> typing.Callable:
    if option and option != "one":
        raise ValueError(
            "The provided option is incorrect; it can only be 'one'")

    def decorator_validate_input(func: typing.Callable) -> typing.Callable:
        # Preserves the metadata of the original function, such as name.
        @functools.wraps(func)
        def wrapper_validate_input(*args: tuple[typing.Set]) -> typing.Any:
            # Validate that all arguments are sets
            if not all(isinstance(s, set) for s in args):
                raise TypeError("All arguments must be sets!")
            # Ensure at least one set is non-empty if option is "one"
            if option == "one" and any(not s for s in args[:2]):
                warnings.warn("At least one of the sets must be non-empty.")
                return None
            # Return 0 if all sets are empty
            if all(not s for s in args[:2):
                warnings.warn("Both sets are empty!", UserWarning)
                return 0
            # Ensure all elements in the sets are of the same type
            if len({numbers.Number if isinstance(c, numbers.Number)
                    else type(c) for c in args[0] | args[1]}) != 1:
                raise TypeError(
                    "Elements in the sets must be of the same type.")
            # Ensure that the provided totalrange is a superset of the other
            # two sets, otherwise remove it from the arguments
            if len(args) == 3:
                set1, set2, total_range = args
                if not total_range >= (set1 | set2):
                    warnings.warn("The total range provided is not a superset of the other two sets",  # noqa E501
                                  UserWarning)
                    args = args[:2]
            return func(*args)
        return wrapper_validate_input
    return decorator_validate_input

Similarity measures

The first and easiest measure is the overlap coefficient. This is the size of the intersection of the two sets divided by the size of the smallest set. The intersection of two sets is found using the & operator.

@validate_input("one")
def overlap_coefficient(set1: set, set2: set) -> float:
    return len(set1 & set2) / min(len(set1), len(set2))

The second and also easy-to-implement measure is the jaccard coefficient. It is defined as the size of the intersection divided by the size of the union.

@validate_input()
def jaccard_similarity(set1: set, set2: set) -> float:
    return len(set1 & set2) / len(set1 | set2)

The Dice-Sørensen coefficient is twice the size of the intersection divided by the product of the size of both sets.

@validate_input()
def dice_sørensen_coefficient(set1: set, set2: set) -> float:
    return 2 * len(set1 & set2) / (len(set1) + len(set2))

The fourth measure is the cosine similarity, which is defined as the dot product divided by the product of their magnitude. The dot product is the sum of the product of every element in the vectors which are lists of the boolean values whether or not a value from the intersection is present in that set. The magnitude of a set is the sum of the square of each element.

@validate_input("one")
def cosine_similarity(set1: set, set2: set) -> float:
    intersection: set = set1 | set2
    vector1: list[int] = [1 if i in set1 else 0 for i in intersection]
    vector2: list[int] = [1 if i in set2 else 0 for i in intersection]
    dot_product: int = sum(a * b for a, b in zip(vector1, vector2))
    norm_a: float = math.sqrt(sum(a ** 2 for a in vector1))
    norm_b: float = math.sqrt(sum(b ** 2 for b in vector2))
    magnitude: float = norm_a * norm_b
    return dot_product / magnitude

The fifth measure is the Simple matching coefficient. Despite its name, there is a trick to calculating it. It is the fraction of all elements that appear in both sets and all elements that appear in neither set over all the elements in the entire range. Whereby the range could extend beyond the union of the two sets. Therefore, the extended set all_ is created either from a provided total range or otherwise from the union of the two sets.

The formula is (p+s)/(p+q+r+s) where p is the size of the intersection of the two sets, q is the size of the difference between set 1 and set 2, r is the size of the difference between set 2 and set 1, and s is the size of symmetric difference of the two sets against the total range. The operator for difference is - and the operator for symmetric difference is ^.

@validate_input("one")
def simple_matching_coefficient(set1: set,
                                set2: set,
                                total_range: typing.Optional[set] = None
                                ) -> float:
    all_ = set1 | set2 if not total_range else total_range
    p: int = len(set1 & set2)
    q: int = len(set1 - set2)
    r: int = len(set2 - set1)
    s: int = len((set1 ^ all_) & (set2 ^ all_))
    return (p + s) / (p + q + r + s)

The last measure is the Hamming coefficient. This is something I derived from the Hamming distance. Also, how in other metrics coefficient or similarity are related to distance, this is 1 minus the resulting measure. Furthermore, I included the total range to take into accounting elements not in either set. This is partially based on some other views as well.¹⁵’¹⁶

@validate_input()
def hamming_coefficient(set1: set,
                        set2: set,
                        total_range: typing.Optional[set] = None,
                        /) -> float:
    all_: set = set1 | set2 if not total_range else total_range
    return len(set1 ^ set2) / len(all_)

For all functions, I added the parameter total_range, which is only used for SMC and Hamming coefficient, to for a similar approach when using them in for loops or map functions. Also, I added a / to the function signature to enforce the use of only positional arguments.¹⁷

Testing

I ended up dividing the tests into two blocks: tests on the input validation, i.e. the decorator, and test each measure on the output. There are probably other and potentially better structures. I came onto this after a few iterations. The tests are grouped into six classes, one for the decorator and one for each measure.

Testing the decorator

All the aspects of the decorator related to how it works are tested in the TestInputValidation class. These are:

• Is a ValueError raised if an invalid option is provided;

def test_invalid_option(self):
    with pytest.raises(ValueError, match="The provided option is incorrect; it can only be 'one'"):
        @similarities.validate_input("two")
        def func():
            pass

• Is a TypeError raised if not all inputs are sets;

def test_invalid_input(self):
    @similarities.validate_input()
    def func():
        pass
    with pytest.raises(TypeError,
                       match="All arguments must be sets!"):
        func(1, 1)
    with pytest.raises(TypeError,
                       match="All arguments must be sets!"):
        func({1}, 1)

• If option is "one", is a warning issued when one set is empty. Otherwise, return 0;

def test_one_empty_sets(self):
    @similarities.validate_input()
    def func(*args):
        return 0
    result = func({1}, set())
    assert result == 0

    @similarities.validate_input("one")
    def func():
        pass
    with pytest.warns() as record:
        result = func({1}, set())
    assert result is None
    assert str(record[0].message) == "At least one of the sets must be non-empty."

• Is a warning issued if both sets are empty;

def test_two_empty_sets(self):
    @similarities.validate_input()
    def func():
        pass
    with pytest.warns() as record:
        result = func(set(), set())
    assert result == 0
    assert str(record[0].message) == "Both sets are empty!"

    @similarities.validate_input("one")
    def func():
        pass
    with pytest.warns() as record:
        result = func(set(), set())
    assert result is None
    assert str(record[0].message) == "At least one of the sets must be non-empty."

• Is a TypeError raised if the element types of the sets are not the same;

def test_uneven_types(self):
    @similarities.validate_input()
    def func(*args):
        return 0
    with pytest.raises(
            TypeError,
            match="Elements in the sets must be of the same type."):
        func({1, 2, 3}, {"f"})
    result = func({1, 2, 3}, {.5})
    assert result == 0

• Check if a warning is issued of the total range is not a superset of the other two sets.

def test_invalid_total_range(self):
    @similarities.validate_input()
    def func(*args) -> None:
        pass
    with pytest.warns() as record:
        result = func({1}, {2}, {3})
    assert result is None
    assert str(record[0].message) ==\
        "The total range provided is not a superset of the other two sets"

Testing the measure

For each measure, three tests were written. One to check for two sets that have no overlap, one to check for complete overlap, and one benchmark specific to each measure. This last one was done against examples found of these measures as described by others.

def _test_no_match(method):
    result = method(set(range(10)), set(range(10, 15)))
    assert result == 0

def _test_full_match(method):
    result = method(set(range(10)), set(range(10)))
    assert round(result) == 1

class TestSMC:

    def test_no_match(self):
        _test_no_match(similarities.simple_matching_coefficient)

    def test_full_match(self):
        _test_full_match(similarities.simple_matching_coefficient)

    def test_example_smc(self) -> None:
        """Test the simple matching coefficient with example sets.
        https://people.revoledu.com/kardi/tutorial/Similarity/SimpleMatching.html  # noqa: E501
        """
        # Example from Kardi Teknomo
        result = similarities.simple_matching_coefficient(
            {"a", "b", "c", "d"},
            {"b"})
        assert result == 0.25

What I learned

• First of all, I learned from taken the time to use set operators how they work, and what to use them for. This helped me move from using the set methods such as union, and also I learned a new operator being >= for superset.
• Second, and a personal gain, was learning how to create a parameterized decorator as well as learning how to create tests for that.
• Third, I got a deeper understanding of these similarity measures or at least how they work by coding them and then, in turn, testing that code against examples. It brought insight into how related these measures are to each other.
• Fourth, creating my own metric was a new high for me. Although it is probably not the most unique one, it was fun to derive a metric for set comparison based of the Hamming distance. One part was figuring out how to derive the distance between the two sets, and the other part was normalizing that result. It took a moment to figure this out and test it but it felt good to make it work.
• Finally, refactoring the pytest suite made me realize that testing the decorator separately is more meaningful, logical, and above all easier to separate the behavior from the decorated function than testing it with every measure.

Conclusion

Although there possibly might already be a suitable package out there, writing my own was a fun and valuable experience. It gave me inside in the similarity measures and is set the foundation for my follow-up story where I’ll dive deeper into these measures. Eventually, this will lead to a story on finding similar nodes in a network graph.

This story is my way to share my coding experience and the lessons I learned, and to document my solutions. All claps, comments, and highlights are appreciated, as well as sharing the story. For more code and my other links see: https://github.com/UnicornOnAzur/.

[1] https://scikit-learn.org/stable/modules/generated/sklearn.metrics.jaccard_score.html

[2] https://scikit-learn.org/stable/modules/generated/sklearn.metrics.pairwise.cosine_similarity.html

[3] https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.distance.jaccard.html

[4] https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.distance.dice.html

[5] https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.distance.cosine.html

[6] https://anhaidgroup.github.io/py_stringmatching/v0.4.x/OverlapCoefficient.html

[7] https://anhaidgroup.github.io/py_stringmatching/v0.4.x/Jaccard.html

[8] https://anhaidgroup.github.io/py_stringmatching/v0.4.x/Dice.html

[9] https://anhaidgroup.github.io/py_stringmatching/v0.4.x/Cosine.html

[10] See for example, https://www.geeksforgeeks.org/dont-repeat-yourselfdry-in-software-development/

[11] https://realpython.com/primer-on-python-decorators/, https://www.geeksforgeeks.org/decorators-with-parameters-in-python/

[12] https://docs.python.org/3/library/functools.html#functools.wraps

[13] https://dev.to/maximegel/guard-clauses-explained-13aa

[14] https://docs.python.org/3/library/numbers.html#numbers.Number

[15] https://cyber.bibl.u-szeged.hu/index.php/actcybern/article/view/3634/3618

[16] https://www.researchgate.net/post/How_to_calculate_the_Hamming_Distance_between_two_sets

[17] https://thepythoncodingbook.com/2022/12/11/positional-only-and-keyword-only-arguments-in-python/