用于近似算法复杂度的块分解方法的Python实现。
pybdm的Python项目详细描述
块分解方法(BDM)近似于算法复杂度 对于任意大小的数据集,也就是最短计算机的长度 生成它的程序。作为算法的复杂性,这并不是微不足道的 在一般情况下是不可计算的量 数据集的算法复杂性非常有用,因为它指出 系统各要素之间的机械联系 不要产生任何可以用 更传统的工具基于概率论和信息论。在
目前支持1D和2D二进制数组,以及1D数组 具有4、5、6和9个离散符号。在
BDM与算法信息论的必要部分 它是基于this article中描述的。在
有关详细信息,请参阅官方documentation。在
安装
标准安装(稳定):
pip install pybdm
开发版本安装:
^{pr2}$地方发展:
git clone https://github.com/sztal/pybdm cd pybdm pip install --editable .
支持的版本
支持Python3.5+。测试是针对Linux运行的,但是 Windows和OSX应该也能工作。在
使用
BDM是使用面向对象的方法实现的 输入表示为整数类型的Numpy数组。在
^{tt1}$ objects operate exclusively on integer arrays. Hence, any alphabet must be first mapped to a set of integers ranging from ^{tt2}$ to ^{tt3}$.
在官方的documentation中可以找到详细的使用示例。在
二进制序列(1D)
importnumpyasnpfrompybdmimportBDM# Create a dataset (must be of integer type)X=np.ones((100,),dtype=int)# Initialize BDM object# ndim argument specifies dimensionality of BDMbdm=BDM(ndim=1)# Compute BDMbdm.bdm(X)# BDM objects may also compute standard Shannon entropy in base 2bdm.ent(X)
二元矩阵(2D)
importnumpyasnpfrompybdmimportBDM# Create a dataset (must be of integer type)X=np.ones((100,100),dtype=int)# Initialize BDM objectbdm=BDM(ndim=2)# Compute BDMbdm.bdm(X)# BDM objects may also compute standard Shannon entropy in base 2bdm.ent(X)
<1DEH(非二进制序列)>importnumpyasnpfrompybdmimportBDM# Create a dataset (4 discrete symbols)np.random.seed(303)X=np.random.randint(0,4,(100,))# Initialize BDM object with 4-symbols alphabetbdm=BDM(ndim=1,nsymbols=4)# Compute BDMbdm.bdm(X)
并行处理
PyBDM的设计考虑了并行处理。 使用现代软件包实现并行化,例如 joblib 使计算大质量物体的BDM变得非常容易。在
在这个例子中,我们将把一个1000x1000的数据集分成200x200个部分 计算所谓的counter对象(最终的BDM计算对这些对象进行操作) 在4个独立的过程中并行,并聚合结果 转化为单个BDM近似的算法复杂度的数据集。在
Remember that data has to be sliced correctly during parallelization in order to ensure fully correct BDM computations. That is, all slices except lower and right boundaries have to be decomposable without any boundary leftovers by the selected decomposition algorithm.
importnumpyasnpfromjoblibimportParallel,delayedfrompybdmimportBDMfrompybdm.utilsimportdecompose_dataset# Create a dataset (must be of integer type)X=np.ones((1000,1000),dtype=int)# Initialize BDM objectbdm=BDM(ndim=2)# Compute counter objects in parallelcounters=Parallel(n_jobs=4) \ (delayed(bdm.decompose_and_count)(d)fordindecompose_dataset(X,(200,200)))# Compute BDMbdm.compute_bdm(*counters)
扰动分析
除了主Block Decomposition Method实现之外,PyBDM还提供 基于BDM (或标准香农熵)。在
微扰实验研究了BDM/熵在变化下的变化 应用于基础数据集。这是检测的主要工具 系统中具有某种因果意义的部分,与之相反 噪声部件。在
对整体产生负面影响的部分 变更后的复杂性可能对系统很重要, 因为它们的移除会使它更加嘈杂。另一方面 改变后的整体复杂性可能会有积极的贡献 因为它们扩展了系统的描述长度。在
importnumpyasnpfrompybdmimportBDMfrompybdm.algorithmsimportPerturbationExperiment# Create a dataset (must be of integer type)X=np.ones((100,100),dtype=int)# Initialize BDM objectbdm=BDM(ndim=2)# Initialize perturbation experiment object# (may be run for both bdm or entropy)perturbation=PerturbationExperiment(bdm,X,metric='bdm')# Compute BDM change for all data pointsdelta_bdm=perturbation.run()# Compute BDM change for selected data points and keep the changes while running# One array provide indices of elements that are to be change.idx=np.array([[0,0],[10,10]],dtype=int)# Another array provide new values to assign.# Negative values mean that new values will be selected# randomly from the set of other possible values from the alphabet.values=np.array([-1,-1],dtype=int)delta_bdm=perturbation.run(idx,values,keep_changes=True)
- 项目
标签: