Fuzzy Mathematics with FuzzPy (Part 1)

Posted on October 17, 2010 by Xavier

FuzzPy is a python library that exposes specialized datatypes to deal with a wide range of fuzzy number types, fuzzy sets, and fuzzy graphs. Binary operations against each type, such as set unions and intersections, can be performed using some of python’s native binary operators (|, &, ==), or specialized methods if you wish to deviate from the default functions for these computations.

FuzzPy also provides several helper methods such as kernel and neighbors isolation, alpha-cuts, cardinality testing, shortest-path computation, and minimum spanning trees. A powerful visualization framework also allows you to quickly create and save visualizations for your data.

In this post, we will examine fuzzy sets and fuzzy graphs, and see how one can use FuzzPy to work with these types, providing examples for each. In the next post of this series, we will examine the different types of fuzzy numbers, generate visualizations, and explore advanced concepts such as automatic fuzzification, and importing graph data from fuzzy adjacency matrices.

Fuzzy Sets

A fuzzy set is simply a set in which each element has an associated degree of membership into the set. This membership value is called $\mu$ -value of the element. A $\mu$ -value of zero indicates that the element does not belong to the set, while any value between zero (exclusive) and one (inclusive), indicates that the element is, to a certain degree, a set member.

Creating a fuzzy set with FuzzPy is just a matter of creating a new FuzzySet object, then either calling the add(FuzzyElement(value, mu)) method for each element to import, or using the update(elements) method, providing it with a list of FuzzyElement(value, -value) tuples for bulk import.

from fuzz import FuzzySet, FuzzyElement
 
# Create two lists of FuzzyElements
elements_a = [(1, 0.3), (2, 0.5), (3, 0.7), (4, 0.9)]
elements_b = [(3, 0.8), (6, 0.6), (1, 0.4), (8, 0.2)]
 
elements_a = [FuzzyElement(x[0], x[1]) for x in elements_a]
elements_b = [FuzzyElement(x[0], x[1]) for x in elements_b]
 
# Create two fuzzy sets
set_a = FuzzySet()
set_b = FuzzySet()
 
set_a.update(elements_a)
set_b.update(elements_b)

We’ve just created a couple fuzzy sets with four elements each. Notice that two of the elements are common to both set_a and set_b (albeit with different $\mu$ -values). We can now perform several operations against these sample sets. Save the code above in a file called example.py and fire up the python interpreter to test fuzzy set functionality against our sets:

>>> from example import *
>>> # Set Difference
...
>>> set_a - set_b
FuzzySet([FuzzyElement(2, 0.500000), FuzzyElement(4, 0.900000)])
>>> set_b - set_a
FuzzySet([FuzzyElement(8, 0.200000), FuzzyElement(6, 0.600000)])
# Set Union
...
>>> set_a | set_b
FuzzySet([FuzzyElement(1, 0.400000), FuzzyElement(2, 0.500000), FuzzyElement(3, 0.800000), FuzzyElement(4, 0.900000), FuzzyElement(6, 0.600000), FuzzyElement(8, 0.200000)])
# Set Intersection
...
>>> set_a & set_b
FuzzySet([FuzzyElement(1, 0.300000), FuzzyElement(3, 0.700000)])

Fuzzy graphs

In a fuzzy graph or digraph, each vertice and each edge can be associated with a $\mu$ -value. The $\mu$ -value of a vertice indicates the vertice’s degree of membership into the graph, while an edge or arc’s $\mu$ -value indicates the degree of connectivity between the head and tail vertices.

The creation of fuzzy graphs is also pretty straightforward: create a set or fuzzy set (see above), then feed that set to the fuzz.Graph constructor, along with the directed boolean value to specify whether you’d like to create a graph or a digraph. You can then use the fuzz.Graph.connect(head, tail, mu) method to add edges to the graph:

import fuzz
 
# Create two sets of vertices
set_a = set([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
set_b = set([11, 12, 13, 14, 15, 16, 17, 18, 19, 20])
 
# Create our graph objects
graph_a = fuzz.FuzzyGraph(viter=set_a, directed=False)
graph_b = fuzz.FuzzyGraph(viter=set_b, directed=True)
 
# Create some arcs in graph_a
graph_a.connect(1, 3, 0.5)
graph_a.connect(3, 6, 0.06)
graph_a.connect(2, 8, 0.2)
graph_a.connect(4, 1, 0.9)
 
# And some in graph_b
graph_b.connect(11, 19, 0.9)
graph_b.connect(14, 12, 0.3)
graph_b.connect(15, 14, 0.5)

Save the code above in a file named graphs.py and fire up your python interpreter so we can experiment with graph operations:

>>> from graphs import *
>>> # Retrieve the mu value of the edge between 1 and 3
... 
>>> graph_a.mu(3, 1)
0.5
>>> # Retrieve an alpha-cut of graph_b against mu-value of 0.5
... 
>>> graph_b.alpha(0.5)
Graph(viter = set([11, 12, 13, 14, 15, 16, 17, 18, 19, 20]), eiter = set([(15, 14), (11, 19)]), directed = True)
>>> # Is graph_a a subgraph of graph_b? (no)
... graph_a.issubgraph(graph_b)
False
>>> # Detect adjacent (connected) vertices
...
>>> graph_a.adjacent(1, 2)
False
>>> graph_a.adjacent(1, 3)
True
>>> # Find all the neighbours of the vertex with value 3
... 
>>> graph_a.neighbors(3)
set([1, 6])
>>> # Find the shortest path to all vertices using 6 as origin
... 
>>> graph_a.dijkstra(6)
{1: 3, 2: None, 3: 6, 4: 1, 5: None, 6: None, 7: None, 8: None, 9: None, 10: None}
>>> # Find the minimum spanning tree of graph_a
... 
>>> graph_a.minimum_spanning_tree()
Graph(viter = set([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]), eiter = set([(2, 8), (1, 3), (4, 1), (3, 6)]), directed = False)

There are a few more operations available for both crisp and fuzzy graphs/digraphs. You should consult the API doc for a comprehensive list.

You should also consult the examples provided as part of the module on GitHub to see FuzzPy in action.

Algorithms in Python: Binary exponentiation

Posted on August 7, 2010 by Xavier

The typical approach to exponentiation of a base b by an exponent n is to repeatedly multiply the base by itself, as such: $b^n = \prod_{i=1}^{n} b$

This is easy to compute for small values but quickly chokes with very large values.

A faster approach involves converting the exponent into base 2, then multiplying the running total and squaring the base each time a 1-bit is encountered. The python implementation looks like this:

def binary_exponent(base, exponent):
    """\
    Binary Exponentiation
 
    Instead of computing the exponentiation in the traditional way,
    convert the exponent to its reverse binary representation.
 
    Each time a 1-bit is encountered, we multiply the running total by
    the base, then square the base.
    """
    # Convert n to base 2, then reverse it.
    exponent = bin(exponent)[2:][::-1]
 
    result = 1
    for i in range(0, len(exponent)):
        if exponent[i] == '1':
            result *= base
        base *= base
    return result

Similarly, the same approach can be taken to perform modular exponentiation against very large exponents:

def modular_exponent(base, exponent, mod):
    """\
    Modular exponentiation through binary decomposition.
 
    We use the same technique as for the binary exponentiation above in
    order to find the modulo of our very large exponent and an arbitrary
    integer mod.
    """
    exponent = bin(exponent)[2:][::-1]
 
    x = 1
    power = base % mod
    for i in range(0, len(exponent)):
        if exponent[i] == '1':
            x = (x * power) % mod
        power = (power ** 2) % mod
    return x

The optimization is especially visible for the modulo operation, since we are working on smaller numbers with each iteration, whereas for simple exponentiation, the CPython interpreter can already optimize the operation.
The speedup for modular exponentiation on my system was in the order of 72x the speed of a simple $(a^n) \mod{m}$ whereas the the computation of the exponentiation took about the same time in both cases.

Algorithms in Python: Binary Operations

Posted on July 17, 2010 by Xavier

Today I’d like to demonstrate a simple implementation of Kenneth Rosen‘s binary addition and multiplication algorithms as outlined in "Discrete Mathematics and its Applications". Both algorithms are very simple and work the same way we’ve all learned to do decimal additions and multiplications by hand in grade-school.

As usual, I’ve also provided a unit-test suite for each algorithm.

Please note: This is only intended to demonstrate the algorithms. If you are actually trying to do some real work with binary numbers in Python, note that the language itself provides a highly optimized implementation of binary numbers and related operations. Here are a few examples:

# Decimal to binary conversion:
>>> bin(15)
'0b1111'
 
# Binary to decimal conversion:
>>> str(0b1111)
'15'
 
# Binary addition:
>>> bin(0b1111 + 0b10011)
'0b100010'
 
# Binary multiplication:
>>> bin(0b1111 * 0b10011)
'0b100011101'

Binary Addition

We will use strings in this example to represent sequences of bits. The algorithm operates right-to-left, maintaining a carry each time it adds two 1-valued bits.

Code:

"""Simple binary operation algorithm."""
 
import math
 
# a and b should be string representation of the binary components
# You could easily extend this to overload the + operator for binaries,
# but this is already built into python.
def binary_addition(bin_a, bin_b):
    """Performs a binary addition against two provided binary numbers"""
 
    # Pad the components so they are of equal length
    max_length = max(len(bin_a), len(bin_b))
    bin_a, bin_b = bin_a.zfill(max_length), bin_b.zfill(max_length)
 
 
    carry = 0
    result = ''
 
    # Note that we work from right to left
    for i in range(0, max_length)[::-1]:
        tmp = int(math.floor((int(bin_a[i]) + int(bin_b[i]) + carry)/2))
        res = str(int(bin_a[i]) + int(bin_b[i]) + carry - 2*tmp)
        result += res
        carry = tmp
 
    result = (result + str(carry))[::-1]
    try:
        return result[result.index('1'):]
    except ValueError, ex:
        return '0'

Unit Test:

"""Unit test for binary_addition.py"""
 
import unittest
from binary_addition import binary_addition
 
class TestBinaryAddition(unittest.TestCase):
 
    """Comparing python binary addition against our own"""
 
    def test_add_same_length(self):
 
        """Adding 2 binary numbers of the same length"""
 
        bin_a = '001001101'
        bin_b = '011011010'
 
        self._compare_additions(bin_a, bin_b)
 
    def test_add_b_larger(self):
 
        """ B has more digits than A """
 
        bin_a = '01000101'
        bin_b = '1110010110101011101101011101000101'
 
        self._compare_additions(bin_a, bin_b)
 
    def test_add_b_smaller(self):
 
        """B has less digits than A"""
 
 
        bin_a = '1110001001001001001101101011000101'
        bin_b = '0110010'
 
        self._compare_additions(bin_a, bin_b)
 
    def _compare_additions(self, bin_a, bin_b):
 
        """Compares the python implementation against ours"""
 
        bin_add = binary_addition(bin_a, bin_b)
        py_add = bin(eval("0b%s" % bin_a) + eval("0b%s" % bin_b))
 
        algo_res = bin_add[bin_add.index('1'):]
        py_res = py_add[py_add.index('1'):]
 
        self.assertEqual(py_res, algo_res)
 
 
 
if '__main__' == __name__:
    unittest.main()

Binary Multiplication

We are still using strings to represent bit sequences. We are still working from right to left, shifting to the left every number from the first number that needs to be multiplied by 1 in the second number. We then append the result to a list that we sum at the end, using the previous algorithm.

Code:

"""Simple Binary multiplication algorithm"""
 
 
import sys
import os.path
 
from binary_addition import binary_addition
 
 
def binary_multiplication(bin_a, bin_b):
    """Multiplies two binary numbers by using python lists to
    easily shift digits around"""
 
    temp_result = []
    result = "0"
 
    # Remove any unnecessary padding
    bin_a = bin_a[bin_a.index('1'):]
    bin_b = bin_b[bin_b.index('1'):]
 
    for i in range(0, len(bin_b))[::-1]:
        if bin_b[i] == '1':
            temp_result.append("%s%s" % (bin_a, "0" * (len(bin_b)-i-1)))
        else:
            temp_result.append("0")
 
 
    for val in temp_result:
        result = binary_addition(str(result), str(val))
 
    return result

Unit Test:

"""Unit test for binary_addition.py"""
 
import unittest
from binary_multiplication import binary_multiplication
 
class TestBinaryAddition(unittest.TestCase):
 
    """Comparing python binary multiplication against our own"""
 
    def test_add_same_length(self):
 
        """Multiplying 2 binary numbers of the same length"""
 
        bin_a = '001001101'
        bin_b = '011011010'
 
        self._compare_multiplications(bin_a, bin_b)
 
    def test_simple(self):
 
        """Multiplying 2 simple binary numbers"""
        bin_a = '110'
        bin_b = '101'
 
        self._compare_multiplications(bin_a, bin_b)
 
    def test_add_b_larger(self):
 
        """B has more digits than A"""
 
        bin_a = '010'
        bin_b = '111001011000101'
 
        self._compare_multiplications(bin_a, bin_b)
 
    def test_add_b_smaller(self):
 
        """ B has less digits than A """
 
        bin_a = '111001011000101'
        bin_b = '010'
 
        self._compare_multiplications(bin_a, bin_b)
 
    def _compare_multiplications(self, bin_a, bin_b):
 
        """Compares the python implementation against ours"""
 
        bin_mult = binary_multiplication(bin_a, bin_b)
        py_mult = bin(eval("0b%s" % bin_a) * eval("0b%s" % bin_b))
 
        algo_res = bin_mult[bin_mult.index('1'):]
        py_res = py_mult[py_mult.index('1'):]
 
        self.assertEqual(py_res, algo_res)
 
 
 
if '__main__' == __name__:
    unittest.main()

Algorithms in Python: Base Expansion

Posted on July 10, 2010 by Xavier

I felt it would be helpful to folks interested in Python and studying algorithms, to review some commonly studied algorithms in Computer Science by providing a small description and a Python implementation of each algorithm.

This week, we’ll cover an introductory algorithm for converting from one numeral base to another. Here is the python code:

"""Simple implementation of a base expansion algorithm"""
 
import math
 
def base_expand(base, val):
    """This simple function performs a base-expansion from decimal
    using moduli and a translation table. The translation table is
    a clear limitation here, in that it implies the maximum base
    is 36."""
 
    if (base < 2) or (base > 36):
        raise BaseOutOfBoundsError(base)
 
    trans_table = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    res = ''
 
    while val != 0:
        res += trans_table[(int(val % base))]
        val = math.floor(val / base)
    return res[::-1]
 
class BaseOutOfBoundsError(Exception):
    """Base must be between 2 and 36"""
    def __init__(self, val):
        self.val = val
    def __str__(self):
        print "\nInvalid base: %s. Base must be (x | x > 1; x < 37)" % \
            self.val

Here is a unit-test for base_expand.py:

"""Unit tests for base_expansion.py"""
 
import unittest
from base_expansion import base_expand, BaseOutOfBoundsError
 
# Unit tests for base_expansion.py
class TestVals(unittest.TestCase):
    """Test suite"""
 
    def test_known_values(self):
        """Testing against known values"""
 
        vals = [{'val': 8, 'base': 2, 'expect': '1000'},
            {'val': 915652, 'base': 16, 'expect': 'DF8C4'},
            {'val': 256, 'base': 10, 'expect': '256'},
            {'val': 88189, 'base': 8, 'expect': '254175'}]
 
        for val in vals:
            self.assertEqual(val['expect'], \
                base_expand(val['base'], val['val']))
 
    def test_invalid_base(self):
        """ Testing invalid bases """
 
        bases = [1, 37, 50, 100]
        for base in bases:
            self.assertRaises(BaseOutOfBoundsError, base_expand, \
                base, 1)
 
 
 
if '__main__' == __name__:
    unittest.main()