A decision tree using ID3 algorithm for English semantic analysis

Natural language processing has been studied for many years, and it has been applied to many researches and commercial applications. A new model is proposed in this paper, and is used in the English document-level emotional classification. In this survey, we proposed a new model by using an ID3 algorithm of a decision tree to classify semantics (positive, negative, and neutral) for the English documents. The semantic classification of our model is based on many rules which are generated by applying the ID3 algorithm to 115,000 English sentences of our English training data set. We test our new model on the English testing data set including 25,000 English documents, and achieve 63.6% accuracy of sentiment classification results.     

面向无线内容分发网络的树形拓扑生成算法

在无线内容分发网络中,为减轻骨干网络的传输压力,可将网络拓扑结构构建为以基站和Wi Fi接入点为根的若干棵最小生成树,并对生成树的深度和每个节点的度数进行约束。这种深度和度数约束的最小生成树问题是一个NP完全问题。针对该问题,首先提出能够生成优质近似解的启发式算法,该算法在不违反深度以及度数约束的情况下构建生成树,算法思想为在服务性节点相连的边中选择与当前生成树相连且权值最小的边加入生成树。然后在生成初始近似解的基础上采用定制的禁忌搜索算法和模拟退火算法对该近似解实施进一步优化。实验结果表明,在给定的约束条件下,禁忌搜索算法求得的解优于现有的遗传算法,在深度约束为4以及度数约束为10的条件下,解的改进幅度可达18.5%,所提算法的运行速度比遗传算法提高了10倍。     

提取全局语义信息的场景图生成算法

目的 场景图能够简洁且结构化地描述图像。现有场景图生成方法重点关注图像的视觉特征,忽视了数据集中丰富的语义信息。同时,受到数据集长尾分布的影响,大多数方法不能很好地对出现概率较小的三元组进行推理,而是趋于得到高频三元组。另外,现有大多数方法都采用相同的网络结构来推理目标和关系类别,不具有针对性。为了解决上述问题,本文提出一种提取全局语义信息的场景图生成算法。方法 网络由语义编码、特征编码、目标推断以及关系推理等4个模块组成。语义编码模块从图像区域描述中提取语义信息并计算全局统计知识,融合得到鲁棒的全局语义信息来辅助不常见三元组的推理。目标编码模块提取图像的视觉特征。目标推断和关系推理模块采用不同的特征融合方法,分别利用门控图神经网络和门控循环单元进行特征学习。在此基础上,在全局统计知识的辅助下进行目标类别和关系类别推理。最后利用解析器构造场景图,进而结构化地描述图像。结果 在公开的视觉基因组数据集上与其他10种方法进行比较,分别实现关系分类、场景图元素分类和场景图生成这3个任务,在限制和不限制每对目标只有一种关系的条件下,平均召回率分别达到了44.2%和55.3%。在可视化实验中,相比...     

A VLSI Algorithm for Calculating the Tree to Tree Distance

Given two ordered, labeled trees β and α, to find the distance from tree β to tree α is an important problem in many fields, for example, the pattern recognition field. In this paper, a VLSI algorithm for calculating the tree to tree distance is presented. The computation structure of the algorithm is a 2-D Mesh with the sizem*n and the time isO(m+n), wherem,n are the numbers of nodes of the tree β and tree α, respectively.     

Bernstein多项式的移位-加算法

提出了一个基于CODIC的计算Bernstein多项式的移位-加算法.该算法可以在存在于许多领域的基本计算系统中实现.证明了算法的收敛性,给出了误差分析,做了数值实验,验证了算法的有效性和效率.     

A join tree probability propagation architecture for semantic modeling

We propose the first join tree (JT) propagation architecture that labels the probability information passed between JT nodes in terms of conditional probability tables (CPTs) rather than potentials. By modeling the task of inference involving evidence, we can generate three work schedules that are more time-efficient for LAZY propagation. Our experimental results, involving five real-world or benchmark Bayesian networks (BNs), demonstrate a reasonable improvement over LAZY propagation. Our architecture also models inference not involving evidence. After the CPTs identified by our architecture have been physically constructed, we show that each JT node has a sound, local BN that preserves all conditional independencies of the original BN. Exploiting inference not involving evidence is used to develop an automated procedure for building multiply sectioned BNs. It also allows direct computation techniques to answer localized queries in local BNs, for which the empirical results on a real-world medical BN are promising. Screen shots of our implemented system demonstrate the improvements in semantic knowledge.     

A semantic approach for automated test oracle generation

This paper presents the design, implementation, and applications of a software testing tool, TAO, which allows users to specify and generate test cases and oracles in a declarative way. Extended from its previous grammar-based test generation tool, TAO provides a declarative notation for defining denotational semantics on each productive grammar rule, such that when a test case is generated, its expected semantics will be evaluated automatically as well, serving as its test oracle. TAO further provides a simple tagging mechanism to embed oracles into test cases for bridging the automation between test case generation and software testing. Two practical case studies are used to illustrate how automated oracle generation can be effectively integrated with grammar-based test generation in different testing scenarios: locating fault-inducing input patterns on Java applications; and Selenium-based automated web testing.     

基于BIM的钢筋骨架语义设计点云自动生成算法

当前预制构配件钢筋骨架质量检查主要依靠人工,存在效率低、容易出错的问题。建筑信息模 型(BIM)、三维重建等技术为改进预制构配件钢筋骨架质量检查方法提供可能。运用这些技术时,有必要由钢 筋骨架 BIM 模型生成可区分每根钢筋的点云。为此,提出了语义设计点云的概念,并构建了基于 BIM 的钢筋 骨架语义设计点云自动生成算法。该算法首先从钢筋骨架 BIM 模型中提取每根钢筋并分别存储于不同的文件, 然后对每根钢筋所在文件进行格式转换,接着生成每根钢筋的语义设计点云,最后基于每根钢筋的语义设计点 云生成钢筋骨架语义设计点云。分别用简单钢筋骨架和复杂钢筋骨架对基于 BIM 的钢筋骨架语义设计点云自 动生成算法进行实验验证,结果表明,该算法能够自动并快速地生成准确的钢筋骨架语义设计点云。      

A semantic recommendation algorithm for the PaaSport platform-as-a-service marketplace

Platform as a service (PaaS) is one of the Cloud computing services that provide a computing platform in the Cloud, allowing customers to develop, run, and manage web applications without the complexity of building and maintaining the infrastructure. The primary disadvantage for an SME to enter the emerging PaaS market is the possibility of being locked into a certain platform, mostly provided by the market's giants. The PaaSport project focuses on facilitating SMEs to deploy business applications on the best-matching Cloud PaaS offering and to seamlessly migrate these applications on demand, via a thin, non-intrusive Cloud-broker, in the form of a Cloud PaaS Marketplace. PaaSport enables PaaS provider SMEs to roll out semantically interoperable PaaS offerings, by annotating them using a unified PaaS semantic model that has been defined as an OWL ontology. In this paper we focus on the recommendation algorithm that has been developed on top of the ontology, for providing the application developer with recommendations about the best-matching Cloud PaaS offering. The algorithm consists of: a) a matchmaking part, where the functional parameters of the application are taken into account to rule out inconsistent offerings, and b) a ranking part, where the non-functional parameters of the application are considered to score and rank offerings. Τhe algorithm is extensively evaluated showing linear scalability to the number of offerings and application requirements. Furthermore, it is extensible upon future semantic model extensions, because it is agnostic to domain specific concepts and parameters, using SPARQL template queries.     

A semantic backend for content management systems

The users of a content repository express the semantics they have in mind while defining the content items and their properties, and forming them into a particular hierarchy. However, this valuable semantics is not formally expressed, and hence cannot be used to discover meaningful relationships among the content items in an automated way. Although the need is apparent, there are several challenges in explicating this semantics in a fully automated way: first, it is difficult to distinguish between data and the metadata in the repository and secondly, not all the metadata defined, such as the file size or encoding type, contribute to the meaning. More importantly, for the developed solution to have practical value, it must address the constraints of the content management system (CMS) industry: CMS industry cannot change their repositories in production use and they need a generic solution not limited to a specific repository architecture. In this article, we address all these challenges through a set of tools developed which first semi-automatically explicate the content repository semantics to a knowledge-base and establish semantic bridges between this backend knowledge-base and the content repository. The repository content is dynamic; to be able to maintain the content repository semantics while new content is created, the changes in the repository semantics are reflected onto the knowledge-base through the semantic bridges. The tool set is complemented with a search engine that make use of the explicated semantics.     

A note on the Bernstein algorithm for bounds for interval polynomials

In computing the range of values of a polynomial over an intervala≤x≤b one may use polynomials of the form $$\left( {\begin{array}{*{20}c} k \\ j \\ \end{array} } \right)\left( {x - a} \right)^j \left( {b - x} \right)^{k - j} $$ called Bernstein polynomials of the degreek. An arbitrary polynomial of degreen may be written as a linear combination of Bernstein polynomials of degreek≥n. The coefficients of this linear combination furnish an upper/lower bound for the range of the polynomial. In this paper a finite differencelike scheme is investigated for this computation. The scheme is then generalized to interval polynomials.     

Transition-aware DVS algorithm for real-time systems using tree structure analysis

Dynamic voltage scaling (DVS) is a key technique for embedded real-time systems to reduce energy consumption by lowering the supply voltage and operating frequency. Many existing DVS algorithms have to generate the canonical schedules or estimate the lengths of slack time in advance for generating the voltage scaling decisions. Therefore, these methods have to compute the schedules with exponential time complexities in general. In this paper, we consider a set of jitter-controlled, independent, periodic, hard real-time tasks scheduled according to preemptive pinwheel model. Our approach constructs a tree structure corresponding to a schedule and maintains the data structure at each early-completion point. Our approach consists of off-line and on-line algorithms which consider the effects of transition time and energy. The off-line and on-line algorithm takes O(k + n log n) and O(k + (p_max/p_min)) time complexity, respectively, where n, k, p_max and p_min denotes the number of tasks, jobs, longest and shortest task period, respectively. Experimental results show that the proposed approach is effective in reducing computational complexity, transition time and energy overhead.     

A new algorithm for sparse interpolation of multivariate polynomials

To reconstruct a black box multivariate sparse polynomial from its floating point evaluations, the existing algorithms need to know upper bounds for both the number of terms in the polynomial and the partial degree in each of the variables. Here we present a new technique, based on Rutishauser’s qd$qd$-algorithm, in which we overcome both drawbacks.     

A linear-time algorithm for the generation of trees

We present a linear algorithm which generates randomly and with uniform probability many kinds of trees: binary trees, ternary trees, arbitrary trees, forests ofp k-ary trees,.... The algorithm is based on the definition of generic trees which can be coded as words. These words, in turn, are generated in linear time.     

一种新的不确定树模式聚类算法

不确定树模式聚类是数据挖掘领域中的一个重要问题,提出了一种新的不确定树模式聚类算法,有效地解决了因数据的不确定性而导致的无法聚类的问题.为了更加准确地度量树模式之间的相似性,提出了一种语义相似度计算方法与结构相似度计算方法.设计了一个动态聚类过程,自适应获取聚类阈值,较大程度上减少了人为干扰导致聚类结果不准确的影响,使得具有相似结构的子树聚集在同一个相似分组中,不同分组之间的子树相似度达到最小化.通过模拟数据和真实环境两部分实验表明,算法有效可行,聚类结果较准确且具有较好的运行效率.     

A new algorithm for solving the tree isomorphism problem

The problem and known algorithms for its solution are briefly discussed. An efficient algorithm for canonical coding of unlabelled trees is described. Several applications of the code, including the tree isomorphism problem, are considered. Efficiency of the algorithm is evaluated and discussed.     

基于语义树的语义关联度算法改进

某项目平台中存在大量用户数据,由于数据的复杂性,采用传统的语义相关度计算方法无法准确获得所需要的用户信息.本文针对这个问题,对数据构建语义树,改进了现有的计算语义联系的方法,在原有的计算方法基础上,加入了上下文权重描述数据之间的语义联系.本文方法可以更好的对用户的查询请求进行概念扩充,从而找出相关数据,满足用户的检索需求.     

A tree search algorithm for the container loading problem

This paper presents a binary tree search algorithm for the three dimensional container loading problem (3D-CLP). The 3D-CLP is about how to load a subset of a given set of rectangular boxes into a rectangular container, such that the packing volume is maximized. In this algorithm, all the boxes are grouped into strips and layers while three constraints, i.e., full support constraint, orientation constraint and guillotine cutting constraint are satisfied. A binary tree is created where each tree node denotes a container loading plan. For a non-root each node, the layer set of its left (or right) child is obtained by inserting a directed layer into its layer set. A directed layer is parallel (or perpendicular) to the left side of the container. Each leaf node denotes a complete container loading plan. The solution is the layer set whose total volume of the boxes is the greatest among all tree nodes. The proposed algorithm achieves good results for the well-known 3D-CLP instances suggested by Bischoff and Ratcliff with reasonable computing time.