基于等价类规则树的高效关联规则挖掘算法

传统的类关联规则挖掘方法在挖掘完整的规则数据集时往往需要消耗很长的时间。为了解决这个问题,提出一种高效的基于等价类规则树的类关联规则挖掘算法。首先,通过分析等价类规则树挖掘类关联规则算法存在的耗时问题,设计一个树结构存储数据集的频繁项集;接着,基于这棵树推导出一些修正树上节点和减少节点信息计算量的定理;最后,利用这些定理得到一个有效的适用于挖掘类关联规则的算法。实验结果表明,与其他较为先进的基于等价类规则树的关联规则挖掘算法相比,所提算法更加高效。     

基于USB的WSN测试与分析系统

实时监控无线传感器网络（WSN）从单个节点到整个网络的运行状态,是进行无线传感器各类研究及应用开发的关键技术之一,为了克服基于UART的数据传输所存在的速率瓶颈问题,设计了一种基于USB的WSN监测系统,主要包括侦听节点和监测分析系统两部分。侦听节点采用CC2531 USB Dongle,以被动侦听的方式获取无线传感器网络的数据包（符合IEEE802.15.4标准）,封装后通过USB接口上传至上位机监测分析系统。上位机监测系统,通过USB接口读取数据帧、完成帧信息存储、解析。实验结果表明该设计能够实现数据传输并以图形方式动态显示网络运行状态。本监测系统的设计为开展WSN的各类理论及实验研究提供了有力的分析工具。     

高光谱影像的BDT-SVM地物分类算法与应用

面对海量数据的特征空间高维性及训练样本的有限性,高光谱遥感影像若采用常规统计模式的分类方法难以获得较好的分类结果。因此探讨支持向量机(SVM)分类器的基本原理,针对EO-1Hyperion高光谱影像的分类特点及现有多类SVM算法所存在的训练时间长及分类精度低等问题,引入二叉决策树SVM(BDT-SVM)分类算法,并提出一种新的类间分离度定义方法及相应的客观确定二叉树结构的策略,由此生成改进的BDT-SVM算法。实验结果表明:与其他多类分类方法相比,基于改进的BDT-SVM算法的高光谱影像地物分类效果更好,总体精度达到90.96%,Kappa系数为0.89,该算法还解决了经典SVM多类分类可能存在的不可分区域问题。     

数据挖掘常用分类算法研究

数据库、数据仓库以及其他存储信息库中潜藏着很多与商业、科学研究等活动的决策有关的数据和知识。对于数据挖掘中的数据分析,通常有两种常见的方法,即分类和预测,首先对数据库中的数据进行分类归纳,然后根据分类规则可以得到比较有价值的数据,然后我们可以根据这个数据来预测得到一些包含未来趋势的信息。在常见的分类算法中,决策树算法是一个有着很好扩展性的算法,可以应用到大型数据库中,可以对多种数据类型进行处理,分类模式容易转化为分类规则,结果也十分的浅显易懂易于理解。该文主要先介绍了几种常用的分类算法,然后具体介绍决策树算法的过程以及在分类算法实际应用中的优缺点。     

基于树语言逼近的安全协议形式化分析

利用形式化方法或工具自动化分析实用安全协议十分必要,定理证明技术因其可解决无限状态系统的验证备受关注,但扩展其验证规模和自动化实现时仍然存在一些局限性。以定理证明和重写逼近理论为基础,以项重写形式化定义协议模型,以树自动机模拟协议攻击者知识集,给出攻击者知识集可达项逼近求解的算法,并根据上述模型讨论秘密性和认证性的验证方法,最后以Needham-Schroeder公钥认证协议为例验证模型的有效性,并指出下一步研究方向。     

基于后验概率SVM决策树多类的分类算法

后验概率支持向量机方法对孤立点和噪声具有鲁棒性,并且可以减少支持向量的数量,从而降低计算复杂度。因此,针对最近提出的快速分类算法c-BTS,引入样本的后验概率,提出了一种基于后验概率的SVM决策树算法P2BTS。实验结果证明,基于后验概率的支持向量机决策树P2BTS比c-BTS的分类精度更高,且所需的二类分类器个数减少,在一定程度上降低了P2BTS分类决策的时间和比较的次数,提高了分类效率。     

A neural network-based scheme coupled with the RPV model inversion package

A hybrid scheme for the inversion of the Rahman-Pinty-Verstraete (RPV) model is presented. It combines the inversion technique described by Lavergne et al. (Lavergne, T., Kaminski, T., Pinty, B., Taberner, M., Gobron, N., Verstraete, M.M., Vossbeck, M., Widlowski, J.L., Giering, R. (2007). Application to MISR land products of an RPV model inversion package using adjoint and Hessian codes. Remote Sensing of Environment, 107, 362-375.) and a multilayer backpropagation feedforward neural network. The RPV inversion package is applied to a sample set of pixels within the satellite scene. Subsequently the pairs of bidirectional reflectance factors (BRF) and model parameters estimated from the sample set of pixels are used to train the neural network. Since the mathematical formulation of the RPV model is embedded in these training data variables, the neural network can efficiently retrieve the model parameters for the whole satellite scene. This scheme has been tested for a MISR L2 BRF scene, MISR L1B2-derived BRF data corresponding to two different dates and a mosaic of MISR L2 BRF scenes acquired over Southern Africa covering a large extent of Miombo woodland. The results show this strategy retrieves the RPV model parameters and uncertainties with high accuracy and considerable speed over large areas.     

Floodplain roughness parameterization using airborne laser scanning and spectral remote sensing

Floodplain roughness parameterization is one of the key elements of hydrodynamic modeling of river flow, which is directly linked to exceedance levels of the embankments of lowland fluvial areas. The present way of roughness mapping is based on manually delineated floodplain vegetation types, schematized as cylindrical elements of which the height (m) and the vertical density (the projected plant area in the direction of the flow per unit volume, m^− 1) have to be assigned using a lookup table. This paper presents a novel method of automated roughness parameterization. It delivers a spatially distributed roughness parameterization in an entire floodplain by fusion of CASI multispectral data with airborne laser scanning (ALS) data. The method consists of three stages: (1) pre-processing of the raw data, (2) image segmentation of the fused data set and classification into the dominant land cover classes (KHAT = 0.78), (3) determination of hydrodynamic roughness characteristics for each land cover class separately. In stage three, a lookup table provides numerical values that enable roughness calculation for the classes water, sand, paved area, meadows and built-up area. For forest and herbaceous vegetation, ALS data enable spatially detailed analysis of vegetation height and density. The hydrodynamic vegetation density of forest is mapped using a calibrated regression model. Herbaceous vegetation cover is further subdivided in single trees and non-woody vegetation. Single trees were delineated using a novel iterative cluster merging method, and their height is predicted (R² = 0.41, rse = 0.84 m). The vegetation density of single trees was determined in an identical way as for forest. Vegetation height and density of non-woody herbaceous vegetation were also determined using calibrated regression models. A 2D hydrodynamic model was applied with the results of this novel method, and compared with a traditional roughness parameterization approach. The modeling results showed that the new method is well able to provide accurate output data. The new method provides a faster, repeatable, and more accurate way of obtaining floodplain roughness, which enables regular updating of river flow models.     

Path Hitting in Acyclic Graphs

An instance of the path hitting problem consists of two families of paths, and ℋ, in a common undirected graph, where each path in ℋ is associated with a non-negative cost. We refer to and ℋ as the sets of demand and hitting paths, respectively. When p∈ℋ and share at least one mutual edge, we say that p hits q. The objective is to find a minimum cost subset of ℋ whose members collectively hit those of . In this paper we provide constant factor approximation algorithms for path hitting, confined to instances in which the underlying graph is a tree, a spider, or a star. Although such restricted settings may appear to be very simple, we demonstrate that they still capture some of the most basic covering problems in graphs. Our approach combines several novel ideas: We extend the algorithm of Garg, Vazirani and Yannakakis (Algorithmica, 18:3–20, 1997) for approximate multicuts and multicommodity flows in trees to prove new integrality properties; we present a reduction that involves multiple calls to this extended algorithm; and we introduce a polynomial-time solvable variant of the edge cover problem, which may be of independent interest. An extended abstract of this paper appeared in Proceedings of the 14th Annual European Symposium on Algorithms, 2006. This work is part of D. Segev’s Ph.D. thesis prepared at Tel-Aviv University under the supervision of Prof. Refael Hassin.