智能决策支持系统中定量特征规则的挖掘方法研究

定量特征规则通过将定量信息与规则相结合定量地反映了概念的主要特征和次要特征,面向属性的归纳学习算法是在数据库中挖掘定量特征规则的一个重要手段,但直接采用这种方法往往会使同一个概念有不同的特征描述,这种现象必然降低规则对决策的参考价值.本文提出了一个测量定量特征规律有效性的计算指标,并结合该指标设计出一个新的面向属性的归纳算法,该算法使定量特征规则在有效性上达到最优,避免了同一概念有不同的特征规则的现象.     

大型数据库中数据挖掘算法SLIQ的研究及仿真

大型数据库中的数据挖掘是目前数据挖掘领域重要的前沿课题.SLIQ算法是处理大型数据库数据的有效算法之一.该算法分为三个阶段在预处理阶段,对数值属性进行预排序;在树的构建阶段采用了树的宽度优先增长策略,使得SLIQ能够处理海量的磁盘数据;在树的修剪阶段,采用了一种基于最小描述长度原理的修剪算法.实验结果表明,SLIQ能够较快且准确地处理海量的数据.     

基于Web的概念属性抽取的研究

针对现今通用搜索引擎存在信息量大、查询不准确、深度不够的问题,提出概念分析的方法.它是用于研究信息检索的一条重要思路,它所倡导的以叠置原理为核心的语义分析技术,目标是自动地解析复合概念的语义,解决从简单的符号处理走向词的意义处理.通过实现基于Web的属性抽取,以支持基于概念的搜索模型.最终使用实验来分析验证算法,所获得的查全率随着迭代的递增,不断增加;相反,准确率却相应下降,这个评测结果说明属性抽取方法的可行性.     

基于粗糙集的决策方法及其在房地产预测中的应用

利用差别矩阵的差别元素的重要度的思想给出了信息系统属性的重要度,然后利用该重要度给出了信息系统中属性的权重,再由属性的权重给出了将信息系统转化成决策机构表的方法.在此基础上,利用正区域的大小作为属性选择标准,给出决策树的生成算法.将该算法运用到产品销售预测过程中,获取了一些较合理的简洁规则.     

面向在线定制的配置BOM及约束下在线配置过程研究

分析了顾客在线定制产品时重视的因素;提出了面向在线定制的配置BOM的概念,并且详细介绍了其具体内容;定义了在线配置过程的原则和配置依据;应用配置矩阵对零部件和零件属性的配置过程进行了详细的分析,同时给出了配置后产品的价格计算方法.在文章结论中,将本文提出的概念和方法与文献中提到的方法进行了仔细的比较,总结出其主要优势.     

基于概念格的B2C网站导航研究

以产品数据库为输入,提取产品属性并进行概念换算转化,再通过FCA得到其聚类的概念格,然后结合产品的概念格和用户对产品属性的要求,提出了B2C网站导航的实现步骤。以开源商城系统ECShop数据库为例对该方法进行详细描述。实验结果证实该导航方法能很好地引导用户寻找目标产品。     

创业研究前沿理论探讨--定义、概念框架与研究边界

目前创业研究领域还没有发展出一个真正意义上的创业理论.比较并归纳较有影响、有代表性的创业定义,找出创业定义的立足点,在此基础上初步确定创业研究的原始概念框架;为进一步修正这个概念框架,利用数据库检索并查阅了核心管理期刊和创业研究专刊的相关文献,进一步细化了各个因素涉及的变量,最终提出了一个包括创业者特征、创业过程、创业结果和创业环境的概念框架--研究边界模型.     

MapGIS数据中心规则设计器设计与实现

MapGIS数据中心支持不同种类的数据的可视化功能,并提供扩展机制,支持自定义数据的表达,并提供数据加载工具,支持ACCESS、SQL、Oracle数据库并提供数据库表的驱动。遵循Access分组驱动的XML存储规范,可将Access数据库中的一个表或多个表绑定在数据中心的任意一个节点上对应建立一颗子树,实现分组建树,表中的字段对应子树的节点。分组建树的实际意义就是把复杂树抽象成层次多结构简单的树。数据中心是以XML为存储格式的,数据中心的XML存储文件主要描述数据中心的属性,数据中心节点样式类型,数据中心节点属性三大部分。为了建立相应的XML规则,需要一个规则设计器。     

基于闭包系统划分的概念格并行构造算法

随着处理的形式背景的增大,概念格的时空复杂度也会随着急剧增大.研究新的方法和手段来构造概念格,是概念格技术应用于大型复杂数据系统的前提,提高其构造效率的一种有效途径是利用高性能并行计算机和网络并行计算的能力,因此概念格的并行构造算法已成为众多学者的一个新的研究方向.概念格的并行构造思想就是根据不同的原理,采用分治策略,通过对形式背景的拆分,形成分布存储的多个子背景,然后构造相应的子概念格,再由子概念格的合并得到所需的概念格.目前建格算法的分布处理研究主要有形式背景的并置和叠置以及形式背景的折叠搜索子空间划分两种方法,本文在总结研究这两种方法的基础上,基于偏序集上闭包系统分解的思想,对提出的闭包系统划分为多个子闭包系统的判定定理进行了证明,使闭包系统的分解既不会产生冗余信息,也不会使信息丢失,并把所提出的判定定理用于概念格的并行处理,提出了一个新的基于闭包划分的概念格并行生成算法--Para-Prunjng算法.通过实验,利用随机生成的数据集同经典NextClosure算法进行比较分析,验证了新算法的正确性和有效性.     

我国棉花市场价格形成机制概念框架及研究综述

科学上的任何一次进步都是因为站在前人的肩膀上,对既有的文献进行回顾与分析是一个不可或缺的过程.在本研究中,所有研究问题的提出,研究目标的设定以及研究思路的拓展,都建立在对现有理论和文献总结归纳的基础之上,本文首先基于本研究的内容即我国棉花市场价格形成机制建立了概念框架,然后对关键的概念进行了定义,并对前人的研究进行了综述.     

Approximation algorithms for multicast routing in ad hoc wireless networks

Energy efficient multicast problem is one of important issues in ad hoc networks. In this paper, we address the energy efficient multicast problem for discrete power levels in ad hoc wireless networks. The problem of our concern is: given n nodes deployed over 2-D plane and each node v has l(v) transmission power levels and a multicast request (s,D) (clearly, when D is V∖{s}, the multicast request is a broadcast request), how to find a multicast tree rooted at s and spanning all destinations in D such that the total energy cost of the multicast tree is minimized. We first prove that this problem is NP-hard and it is unlikely to have an approximation algorithm with performance ratio ρlnn(ρ<1). Then, we propose a general algorithm for the multicast/broadcast tree problem. And based on the general algorithm, we propose an approximation algorithm and a heuristics for multicast tree problem. Especially, we also propose an efficient heuristic for broadcast tree problem. Simulations ensure our algorithms are efficient.     

When Costs Are Unequal and Unknown: A Subtree Grafting Approach for Unbalanced Data Classification*

In binary classifications, a decision tree learned from unbalanced data typically creates an important challenge related to the high misclassification rate of the minority class. Assigning different misclassification costs can address this problem, though usually at the cost of accuracy for the majority class. This effect can be particularly hazardous if the costs cannot be specified precisely. When the costs are unknown or difficult to determine, decision makers may prefer a classifier with more balanced accuracy for both classes rather than a standard or cost‐sensitively learned one. In the context of learning trees, this research therefore proposes a new tree induction approach called subtree grafting (STG). On the basis of a real bank data set and several other data sets, we test the proposed STG method and find that our proposed approach provides a successful compromise between standard and cost‐sensitive trees.     

基于multi-agent的大型人群活动多阶段动态协调控制模型

随着经济的快速发展,我国举办的各类大型人群活动越来越多,例如奥运会、世博会等。针对大型人群活动中存在的游客长时间排队与拥挤问题,为了降低人群事故发生的风险,提高游客的满意度,提出了基于multi-agent的大型人群活动多阶段动态协调控制模型,并设计出了协调算法PCI,该算法在引入帕累托最优概念的基础上给出参观目标点的选择方法,使用Logit模型进行路线的选择。把该协调算法与现有的其它两种算法进行了计算机仿真对比,仿真结果表明,协调算法PCI可以满足实时性响应的要求,算法C和PCI能够有效的减少排队时间,算法PCI可以得到最优的社会福利,而且随着人群规模的增加这种优势更加明显。     

Online tree node assignment with resource augmentation

Given a complete binary tree of height h, the online tree node assignment problem is to serve a sequence of assignment/release requests, where an assignment request, with an integer parameter 0≤i≤h, is served by assigning a (tree) node of level (or height) i and a release request is served by releasing a specified assigned node. The node assignments have to guarantee that no node is assigned to two assignment requests unreleased, and every leaf-to-root path of the tree contains at most one assigned node. With assigned node reassignments allowed, the target of the problem is to minimize the number of assignments/reassignments, i.e., the cost, to serve the whole sequence of requests. This online tree node assignment problem is fundamental to many applications, including OVSF code assignment in WCDMA networks, buddy memory allocation and hypercube subcube allocation.     

Improving robustness of next-hop routing

A weakness of next-hop routing is that following a link or router failure there may be no routes between some source-destination pairs, or packets may get stuck in a routing loop as the protocol operates to establish new routes. In this article, we address these weaknesses by describing mechanisms to choose alternate next hops. Our first contribution is to model the scenario as the following tree augmentation problem. Consider a mixed graph where some edges are directed and some undirected. The directed edges form a spanning tree pointing towards the common destination node. Each directed edge represents the unique next hop in the routing protocol. Our goal is to direct the undirected edges so that the resulting graph remains acyclic and the number of nodes with outdegree two or more is maximized. These nodes represent those with alternative next hops in their routing paths. We show that tree augmentation is NP-hard in general and present a simple \(\frac{1}{2}\)-approximation algorithm. We also study 3 special cases. We give exact polynomial-time algorithms for when the input spanning tree consists of exactly 2 directed paths or when the input graph has bounded treewidth. For planar graphs, we present a polynomial-time approximation scheme when the input tree is a breadth-first search tree. To the best of our knowledge, tree augmentation has not been previously studied.     

An improved distributed data aggregation scheduling in wireless sensor networks

This paper focuses on the distributed data aggregation collision-free scheduling problem, which is one of very important issues in wireless sensor networks. Bo et al. (Proc. IEEE INFOCOM, 2009) proposed an approximate distributed algorithm for the problem and Xu et al. (Proc. ACM FOWANC, 2009) proposed a centralized algorithm and its distributed implementation to generate a collision-free scheduling for the problem, which are the only two existing distributed algorithms. Unfortunately, there are a few mistakes in their performance analysis in Bo et al. (Proc. IEEE INFOCOM, 2009), and the distributed algorithm can not get the same latency as the centralized algorithm because the distributed implementation was not an accurate implementation of the centralized algorithm (Xu et al. in Proc. ACM FOWANC, 2009). According to those, we propose an improved distributed algorithm to generate a collision-free schedule for data aggregation in wireless sensor networks. Not an arbitrary tree in Bo et al. (Proc. IEEE INFOCOM, 2009) but a breadth first search tree (BFS) rooted at the sink node is adopted, the bounded latency 61R+5Δ?67 of the schedule is obtained, where R is the radius of the network with respect to the sink node and Δ is the maximum node degree. We also correct the latency bound of the schedule in Bo et al. (Proc. IEEE INFOCOM, 2009) as 61D+5Δ?67, where D is a diameter of the network and prove that our algorithm is more efficient than the algorithm (Bo et al. in Proc. IEEE INFOCOM, 2009). We also give a latency bound for the distributed implementation in Xu et al. (Proc. ACM FOWANC, 2009).     

On broadcasting in unicyclic graphs

Broadcasting is an information dissemination problem in a connected network, in which one node, called the originator, disseminates a message to all other nodes by placing a series of calls along the communication lines of the network. Finding the broadcast time of a vertex in an arbitrary graph is NP-complete. The polynomial time solvability is shown only for trees. In this paper we present a linear algorithm that determines the broadcast time of any originator in an arbitrary unicyclic graph. As a byproduct, we find a broadcast center of the unicyclic graph. We also present an O(|V|+k ²) algorithm to find the broadcast time of an arbitrary unicyclic graph, where k is the length of the cycle. In the last section we give tight lower and upper bounds on broadcast time of a spanning tree based on the broadcast time of the unicyclic graph. The results of Sects. 2, 3 and most of the proofs in Sects. 2, 3 of this paper are presented by Harutyunyan and Maraachlian (Proceedings of 13th annual COCOON, pp. 372–383, 2007). All results in Sects. 4, 5 and the complete proof of Theorem 3 are new results.     

Tree edge decomposition with an application to minimum ultrametric tree approximation

A k-decomposition of a tree is a process in which the tree is recursively partitioned into k edge-disjoint subtrees until each subtree contains only one edge. We investigated the problem how many levels it is sufficient to decompose the edges of a tree. In this paper, we show that any n-edge tree can be 2-decomposed (and 3-decomposed) within at most ⌈1.44 log n⌉ (and ⌈log n⌉ respectively) levels. Extreme trees are given to show that the bounds are asymptotically tight. Based on the result, we designed an improved approximation algorithm for the minimum ultrametric tree.     

局内租赁问题的风险补偿模型及其竞争分析

将风险的概念引入局内租赁问题中,建立了该问题的风险补偿模型,并对存在和不存在 利率情况下的局内租赁问题作了分析. 和局内问题中传统的竞争比分析不同的是,竞争比分析 只反映局内策略与基准算法(局外最优算法) 的相对绩效,但这往往忽略了很多的有用信息,且 分析模型很不灵活. 然而在风险补偿模型中,投资者可以控制风险,根据自己不同的风险容忍 度和未来预期选择最优的租赁策略     

A hybrid beam search looking-ahead algorithm for the circular packing problem

In this paper, we study the circular packing problem. Its objective is to pack a set of n circular pieces into a rectangular plate R of fixed dimensions L×W. Each piece’s type i, i=1,…,m, is characterized by its radius r _i and its demand b _i . The objective is to determine the packing pattern corresponding to the minimum unused area of R for the circular pieces placed. This problem is solved by using a hybrid algorithm that adopts beam search and a looking-ahead strategy. A node at a level ℓ of the beam-search tree contains a partial solution corresponding to the circles already placed inside R. Each node is then evaluated using a looking-ahead strategy, based on the minimum local-distance heuristic, by computing the corresponding complete solution. The nodes leading to the best solutions at level ℓ are then chosen for branching. A multi-start strategy is also considered in order to diversify the search space. The computational results show, on a set of benchmark instances, the effectiveness of the proposed algorithm.