python ds evidence theory code

""" A framework for performing computations in the Dempster-Shafer theory. """ from __future__ import print_function from itertools import chain, combinations from functools import partial, reduce from operator import mul from math import log, fsum, sqrt from random import random, shuffle, uniform import sys try: import numpy try: from scipy.stats import chi2 from scipy.optimize import fmin_cobyla except: print('SciPy not found: some features will not work.', file=sys.stderr) except: print('NumPy not found: some features will not work.', file=sys.stderr) class MassFunction(dict): """ A Dempster-Shafer mass function (basic probability assignment) based on a dictionary. Both normalized and unnormalized mass functions are supported. The underlying frame of discernment is assumed to be discrete. Hypotheses and their associated mass values can be added/changed/removed using the standard dictionary methods. Each hypothesis can be an arbitrary sequence which is automatically converted to a 'frozenset', meaning its elements must be hashable. """ def __init__(self, source=None): """ Creates a new mass function. If 'source' is not None, it is used to initialize the mass function. It can either be a dictionary mapping hypotheses to non-negative mass values or an iterable containing tuples consisting of a hypothesis and a corresponding mass value. """ if source != None: if isinstance(source, dict): source = source.items() for (h, v) in source: self[h] += v @staticmethod def _convert(hypothesis): """Convert hypothesis to a 'frozenset' in order to make it hashable.""" if isinstance(hypothesis, frozenset): return hypothesis else: return frozenset(hypothesis) @staticmethod def gbt(likelihoods, normalization=True, sample_count=None): """ Constructs a mass function using the generalized Bayesian theorem. For more information, see Smets. 1993. Belief functions: The disjunctive rule of combination and the generalized Bayesian theorem. International Journal of Approximate Reasoning. 'likelihoods' specifies the conditional plausibilities for a set of singleton hypotheses. It can either be a dictionary mapping singleton hypotheses to plausibilities or an iterable containing tuples consisting of a singleton hypothesis and a corresponding plausibility value. 'normalization' determines whether the resulting mass function is normalized, i.e., whether m({}) == 0. If 'sample_count' is not None, the true mass function is approximated using the specified number of samples. """ m = MassFunction() if isinstance(likelihoods, dict): likelihoods = list(likelihoods.items()) # filter trivial likelihoods 0 and 1 ones = [h for (h, l) in likelihoods if l >= 1.0] likelihoods = [(h, l) for (h, l) in likelihoods if 0.0 < l < 1.0] if sample_count == None: # deterministic def traverse(m, likelihoods, ones, index, hyp, mass): if index == len(likelihoods): m[hyp + ones] = mass else: traverse(m, likelihoods, ones, index + 1, hyp + [likelihoods[index][0]], mass * likelihoods[index][1]) traverse(m, likelihoods, ones, index + 1, hyp, mass * (1.0 - likelihoods[index][1])) traverse(m, likelihoods, ones, 0, [], 1.0) if normalization: m.normalize() else: # Monte-Carlo if normalization: empty_mass = reduce(mul, [1.0 - l[1] for l in likelihoods], 1.0) for _ in range(sample_count): rv = [random() for _ in range(len(likelihoods))] subtree_mass = 1.0 hyp = set(ones) for k in range(len(likelihoods)): l = likelihoods[k][1] p_t = l * subtree_mass p_f = (1.0 - l) * subtree_mass if normalization and not hyp: # avoid empty hypotheses in the normalized case p_f -= empty_mass if p_t > rv[k] * (p_t + p_f): hyp.add(likelihoods[k][0]) else: subtree_mass *= 1 - l # only relevant for the normalized empty case m[hyp] += 1.0 / sample_count return m @staticmethod def from_bel(bel): """ Creates a mass function from a corresponding belief function. 'bel' is a dictionary mapping hypotheses to belief values (like the dictionary returned by 'bel(None)'). """ m = MassFunction() for h1 in bel.keys(): v = fsum([bel[h2] * (-1)**(len(h1 - h2)) for h2 in powerset(h1)]) if v > 0: m[h1] = v mass_sum = fsum(m.values()) if mass_sum < 1.0: m[frozenset()] = 1.0 - mass_sum return m @staticmethod def from_pl(pl): """ Creates a mass function from a corresponding plausibility function. 'pl' is a dictionary mapping hypotheses to plausibility values (like the dictionary returned by 'pl(None)'). """ frame = max(pl.keys(), key=len) bel_theta = pl[frame] bel = {frozenset(frame - h):bel_theta - v for (h, v) in pl.items()} # follows from bel(-A) = bel(frame) - pl(A) return MassFunction.from_bel(bel) @staticmethod def from_q(q): """ Creates a mass function from a corresponding commonality function. 'q' is a dictionary mapping hypotheses to commonality values (like the dictionary returned by 'q(None)'). """ m = MassFunction() frame = max(q.keys(), key=len) for h1 in q.keys(): v = fsum([q[h1 | h2] * (-1)**(len(h2 - h1)) for h2 in powerset(frame - h1)]) if v > 0: m[h1] = v mass_sum = fsum(m.values()) if mass_sum < 1.0: m[frozenset()] = 1.0 - mass_sum return m def __missing__(self, key): """Return 0 mass for hypotheses that are not contained.""" return 0.0 def __copy__(self): c = MassFunction() for k, v in self.items(): c[k] = v return c def copy(self): """Creates a shallow copy of the mass function.""" return self.__copy__() def __contains__(self, hypothesis): return dict.__contains__(self, MassFunction._convert(hypothesis)) def __getitem__(self, hypothesis): return dict.__getitem__(self, MassFunction._convert(hypothesis)) def __setitem__(self, hypothesis, value): """ Adds or updates the mass value of a hypothesis. 'hypothesis' is automatically converted to a 'frozenset' meaning its elements must be hashable. In case of a negative mass value, a ValueError is raised. """ if value < 0.0: raise ValueError("mass value is negative: %f" % value) dict.__setitem__(self, MassFunction._convert(hypothesis), value) def __delitem__(self, hypothesis): return dict.__delitem__(self, MassFunction._convert(hypothesis)) def frame(self): """ Returns the frame of discernment of the mass function as a 'frozenset'. The frame of discernment is the union of all contained hypotheses. In case the mass function does not contain any hypotheses, an empty set is returned. """ if not self: return frozenset() else: return frozenset.union(*self.keys()) def singleton