基于布尔矩阵约简的Apriori算法改进研究

针对关联规则中Apriori算法存在的缺点,提出了一种基于布尔矩阵约简的Apriori改进算法。在该算法中,将事务数据库转换为布尔矩阵,并在矩阵最后增加1行2列,用来记录相同事务的个数和矩阵行与列中"1"的个数。将矩阵各列元素按支持数升序排列,使得算法在压缩过程中减少了扫描矩阵各列的次数,缩短了算法的运行时间。另外,为了提高算法的存储空间利用率,增加了删除非频繁项集的操作。实验结果和性能分析表明,相比现有的算法,改进后的算法具有更好的性能,能够有效地提高算法执行效率。     

Improved time and space bounds for Boolean matrix multiplication

Summary Using modular arithmetic we obtain the following improved bounds on the time and space complexities for n × n Boolean matrix multiplication: O(n ^log ₂ ⁷ lognlogloglognloglogloglogn) bit operations and O(n ²loglog n) bits of storage on a logarithmic cost RAM having no multiply or divide instruction; O(n ^log ₂ ⁷(logn)^2–1/2log ₂ ⁷(loglog n)^1/2log ₂ ^7–1) bit operations and O(n ²log n) bits of storage on a RAM which can use indirect addressing for table lookups. The first algorithm can be realized as a Boolean circuit with O(n ^log ₂ ⁷lognlogloglognloglogloglogn) gates. Whenever n×n arithmetic matrix multiplication can be performed in less than O(n ^log ₂ ⁷) arithmetic operations, our results have corresponding improvements.This work was supported in part by the Office of Naval Research under contract N00014-67-0204-0063, by the National Research Council of Canada under grant A4307, and by the National Science Foundation under grants MCS76-17321 and GJ-43332     

基于改进的布尔矩阵约简算法的入侵检测方法

针对入侵检测数据特征维数多,通过改进的布尔矩阵约简算法对入侵数据样本进行属性约简,再应用灰色关联算法,使得原数据集中每条记录由原来的41个属性约简为27个,从而提高了入侵检测的速度和效率。实验结果也表明,应用此种约简方法,提高了入侵检测的效率,且保持了较为理想的检测率。     

关于矩阵乘法问题的人工蜂群优化算法研究

矩阵乘法运算作为计算机科学和数学的一个基本运算,在科学研究和工程计算中有着广泛的应用。确定2个矩阵乘积所需要的最小乘法数是当今计算机代数中一直未能求解的重要问题之一。通过将矩阵乘法问题建模为一个组合优化问题,采用人工蜂群启发式搜索算法进行矩阵乘法问题求解。对人工蜂群算法进行了改进,给出一种绕圈遍历方法,避免了对同一个解的相同邻域的重复搜索。通过在2×2矩阵乘法问题上的数值实验验证了算法的有效性,所提算法能够快速地找到2×2矩阵分解的乘积方法。     

An improved constant coefficient multiplication algorithm based on cascaded adder graph

In many digital signal processing algorithms,e.g.,digital filters,the multiplier coefficients are constant.Hence,it is possible to implement the multiplier using shifts,adders,and subtracters.In this work a new algorithm of constant coefficient multiplication with few adders and registers is proposed.This approach is based on cascaded adder graph.In this paper all cascaded adder graph structures for any integer can be derived,and the analytical method for the number of register and adder occupation is given.Through comparison of occupied resources,the optimal adder graph can be obtained.Finally,comparing with previous optimal algorithms,a design example for finite impulse response(FIR) filter confirms the validity and good engineering practicability of this algorithm.     

Derandomization,witnesses for Boolean matrix multiplication and construction of perfect hash functions

Small sample spaces with almost independent random variables are applied to design efficient sequential deterministic algorithms for two problems. The first algorithm, motivated by the attempt to design efficient algorithms for the All Pairs Shortest Path problem using fast matrix multiplication, solves the problem of computingwitnesses for the Boolean product of two matrices. That is, ifA andB are twon byn matrices, andC=AB is their Boolean product, the algorithm finds for every entryC _ij =1 a witness: an indexk so thatA _ik =B _kj =1. Its running time exceeds that of computing the product of twon byn matrices with small integer entries by a polylogarithmic factor. The second algorithm is a nearly linear time deterministic procedure for constructing a perfect hash function for a givenn-subset of {1,...,m}.Part of this paper was presented at the IEEE 33rd Symposium on Foundations of Computer Science.Research supported in part by a USA-Israeli BSF grant and by the Fund for Basic Research administered by the Israel Academy of Sciences.Supported by an Alon Fellowship and by a grant from the Israel Science Foundation administered by the Israeli Academy of Sciences. Some of this work was done while the author was with the IBM Almaden Research Center.     

An efficient algorithm for calculating Boolean difference

In this paper we have proposed a method of computing Boolean difference by means of transition operators. This method considerably simplifies the computational complexity. Particularly, when the method is used in the test generation of digital circuits, the Boolean difference can be calculated iteratively from the outputs of gates to their inputs level by level, no matter whether there are reconvergent fanout lines or not. When there are m different paths from a given fault line to the primary output of the circuit, using traditional Boolean difference methods, the result formula will contain 2 ^m ?1 product terms, whereas using the method presented in this paper, the result formula will contain onlym product terms. On the other hand, the m product terms are connected by “OR” operators, therefore it is very convenient to generate partial test patterns. We also introduce a method in which partial test patterns along a given path can be generated. The method discussed in this paper have been used in the test generation of the PCBs of several computers and the results were quite satisfactory.     

SUMMA: scalable universal matrix multiplication algorithm

In the paper we give a straightforward, highly efficient, scalable implementation of common matrix multiplication operations. The algorithms are much simpler than previously published methods, yield better performance, and require less work space. MPI implementations are given, as are performance results on the Intel Paragon system. © 1997 by John Wiley & Sons, Ltd.     

An improved test of Boolean functions for k-dimensionality

A probabilistic test of Boolean functions for k-dimensionality is constructed. The test has a less time complexity and a smaller first kind error probability (with the same upper bound for the second kind error probability) in comparison with a well-known previously proposed test.     

An efficient algorithm for parallel integer multiplication

In this paper we propose an efficient algorithm to implement parallel integer multiplication by a combination of parallel additions, shifts and reads from a memory-resident lookup table dedicated to squares. Such an operator called PIM (parallel integer multiplication) is in fact microprogrammed at the PROM level. Our theoretical approach is included within the framework of time and space parallel complexity theory. The mathematical relation used defines this multiplication operator in terms of a difference of two quadratic expressions, each being computed in parallel by one addition and one shift. This leads to the CPU time for any pair of numbers being constant. Our contribution is above all of practical interest on any massively parallel architecture in the field of scientific and numerical computing.     

一种基于De Bruijn网络结构的并行矩阵乘算法

在De Bruijn网络中进行并行矩阵乘法运算,算法简单,容易实现。首先介绍了De Bruijn网络结构,然后提出了一种基于De Bruijn网络结构的矩阵乘法的并行算法,分析了它的加速比、效率等性能及可扩展性,通过与Cannon算法的比较,证明它的时间复杂度等效于Cannon算法,最后通过实验验证了这个结论的正确性。     

一种基于MPICH的高效矩阵相乘并行算法

根据MPICH并行编程环境中任务间通信的特点,设计了一种基于MPICH的矩阵相乘并行算法。根据运行在COW（工作站机群）上的进程数目将矩阵A按行划分成相应数目的子矩阵,每个进程完成一个子矩阵与矩阵B的相乘运算。实验结果表明,该算法提高了机群并行环境中资源的利用率,提高了程序的运行效率。     

基于布尔矩阵的关联规则算法研究*

针对可快速在大型交易事务数据库中挖掘关联规则的问题,基于布尔矩阵提出一种新的挖掘算法。该算法通过仅需存储布尔位节约了内存,通过简单布尔运算提高了求解频繁项集的效率。实验证明该算法较之于Apriori 算法有更好的性能。     

A sparse matrix algorithm on the Boolean vector machine

The Boolean Vector Machine (BVM) is a large network of extremely small processors with very small memories operating in SIMD mode using bit serial arithmetic. Individual processors communicate via a hardware implementation of the Cube Connected Cycles (CCC) network. A prototype BVM with 2048 processing elements, each with 200 binary bits of memory, is currently being built using VLSI technology.

The BVM's bit-serial arithmetic and the small memories of individual processors are apparently a drawback to its effectiveness when applied to large numerical problems. In this paper we analyze an implementation of a basic matrix-vector iteration algorithm for sparse matrices on the BVM. We show that a 2²⁰ Pe BVM can deliver over 1 billion (10⁹) useful floating-point operations per second for this problem. The algorithm is expressed in a new language (BVL) which has been defined for programming the BVM.     

改进的布尔冲突矩阵的高效属性约简算法

近年来,诸多学者喜欢用差别矩阵的方法来设计属性约简的算法,但由于计算差别矩阵不仅费时且还浪费空间,导致这些属性约简算法都不够理想。为了降低属性约简算法的复杂度,在布尔冲突矩阵的基础上,定义了一个启发函数,该函数能求出决策表中条件属性导致的冲突个数,同时给出了计算该启发函数的快速算法。然后用该启发函数设计了一个有效的基于改进的布尔冲突矩阵的不完备决策表的高效属性约简算法,该算法能够有效降低时间复杂度。最后实验结果说明了新算法的有效性。     

基于散列布尔矩阵的关联规则Eclat改进算法*

将散列表与布尔矩阵相结合,提出了一种基于散列布尔矩阵的Eclat改进算法,通过提高求交集的速度来加快整个算法生成频集的过程。实验结果表明,改进的Eclat算法在计算性能和时间效率上均优于传统算法。