共查询到19条相似文献,搜索用时 234 毫秒
1.
2.
3.
用实数编码的遗传算法构造斜决策树 总被引:5,自引:0,他引:5
决策树方法是一种通过构造决策树来发现训练集中分类知识的数据采掘方法,其核心是如何构造决策树,构造决策树的关键是找出表示内部节点的最佳扩展属性。扩展属性有单属性和联合属性,由单属性形成的扩展属性集小,可以容易地找出最佳扩展属性,构造单元树的速度快,但是生成的单元树规模大,并可导致子树复制、一个属性的多次测试等;用联合属性作为扩展属性,生成的多元树规模小,能有效地克服单元树 相似文献
4.
合理构建规则树可以提高Snort的匹配效率。当前常见的规则树构建方法不能很好反映实际工作环境的特点,从而造成某些重要的规则属性得不到优先匹配。主要是基于对网络实际数据的统计来构建规则树,提出了一种属性重要性的测度方法,使得规则树能够适应实际的网络工作环境,从而提高了规则匹配的速度。 相似文献
5.
网络安全事件的多样性和复杂性使得传统方法难以对网络安全态势作出实时动态的评估。鉴于此,提出一种面向网络实时业务的网络安全态势评估方法。尝试以网络实时业务为切入点来降低评估复杂度,实时动态地评估网络安全态势。基本思路是采用层次化方法建立实时业务风险模型,采用攻击树方法建立攻击威胁模型,将这两个模型作为评估的数据支撑;对D-S证据理论合成公式进行改进;利用改进后的D-S证据理论实现上述两个模型的关联,进而得出实时的评估结果。最后通过一个测试实验对评估方法进行验证与分析。 相似文献
6.
有向赋权网络中任意节点对的最短路径集求解方法 总被引:1,自引:0,他引:1
有向赋权网络任意节点对之间的最短路径可能多于一条,运用Floyd算法对已知加权交互网络的最短路径进行求解,对获得最短路径后的每一个节点对,向其中插入已知交互网络中的其余所有节点,并计算此时的节点对之间的路径,通过与前次Floyd算法计算出的最短路径进行比较,筛选出构成最短路径的所有中间节点,并构建路径支撑树,基于路径支撑树确定任意节点对的最短路径集. 相似文献
7.
基于数据的贝叶斯网络结构学习是一个NP难题.基于条件约束和评分搜索相结合的方法是贝叶斯网络结构学习的一个热点.基于互信息理论提出一种最大支撑树(MWST)机制,并基于最大支撑树结合贪婪搜索的思想提出一种简化贪婪算法.简化贪婪算法不依赖先验知识,完全基于数据集.首先,通过计算互信息建立目标网络的最大支撑树;然后,在最大支撑树的基础上学习初始网络结构,最后,利用简化搜索机制对初始结构进一步优化,最终完成贝叶斯网络的结构学习.数据仿真实验证明,简化贪婪算法不仅具有很高的精度而且具有高效率. 相似文献
8.
基于前人提出的双环网络G(N;r,s)的分步直径求解法,提出了一个等价树直径求解方法,得到一个新的研究双环网络的拓扑结构-等价树;研究了双环网络等价树的性质并给出了等价树的构造算法;给出了双环网络直径d(N;r,s)的显示公式;利用C#编程语言对等价生成树的结构模型进行了仿真实现;对任意给定的N,1≤r≠s相似文献
9.
为延长网络寿命,缩短网络汇聚时延,提出了一个时延受限,能耗均衡的传感网数据采集树构建方法。该方法以节点的剩余能量和节点间距离为参数构建权值函数,使用Dijkstra算法计算一个最小加权能耗生成树。在此基础上,沿最小加权路径,对生成树进行局部调整,从而在满足时延要求的同时,均衡网络能耗。实验表明,该方法延长了网络平均生存期,达到了均衡网络能耗的目的。 相似文献
10.
11.
The problem of counting the number of spanning trees is an old topic in graph theory with important applications to reliable network design. Usually, it is desirable to put forward a formula of the number of spanning trees for various graphs, which is not only interesting in its own right but also in practice. Since some large graphs can be composed of some existing smaller graphs by using the product of graphs, the number of spanning trees of such large graph is also closely related to that of the corresponding smaller ones. In this article, we establish a formula for the number of spanning trees in the lexicographic product of two graphs, in which one graph is an arbitrary graph G and the other is a complete multipartite graph. The results extend some of the previous work, which is closely related to the number of vertices and Lapalacian eigenvalues of smaller graphs only. 相似文献
12.
The problem of counting the number of spanning trees is an old topic in graph theory with important applications to reliable network design. Usually, it is desirable to put forward a formula of the number of spanning trees for various graphs, which is not only interesting in its own right but also in practice. Since some large graphs can be composed of some existing smaller graphs by using the product of graphs, the number of spanning trees of such large graph is also closely related to that of the corresponding smaller ones. In this article, we establish a formula for the number of spanning trees in the lexicographic product of two graphs, in which one graph is an arbitrary graph G and the other is a complete multipartite graph. The results extend some of the previous work, which is closely related to the number of vertices and Lapalacian eigenvalues of smaller graphs only. 相似文献
13.
《国际计算机数学杂志》2012,89(3-4):185-200
The classic theorem on graphs and matrices is the Matrix-Tree Theorem, which gives the number of spanning trees t(G) of any graph G as the value of a certain determinant. However, in this paper, we will derive a simple formula for the number of spanning trees of the regular networks. 相似文献
14.
《国际计算机数学杂志》2012,89(4):229-241
In this paper, we derive a simple formula for the number of spanning trees of the circulant graphs. Some special cases of the circulant graphs are also taken into account. 相似文献
15.
《Parallel and Distributed Systems, IEEE Transactions on》2007,18(5):644-657
This paper is concerned with a particular family of regular 4-connected graphs, called chordal rings. Chordal rings are a variation of ring networks. By adding two extra links (or chords) at each vertex in a ring network, the reliability and fault-tolerance of the network are enhanced. Two spanning trees on a graph are said to be independent if they are rooted at the same vertex, say, r, and for each vertex v neq r, the two paths from r to v, one path in each tree, are internally disjoint. A set of spanning trees on a given graph is said to be independent if they are pairwise independent. Iwasaki et al. [CHECK END OF SENTENCE] proposed a linear time algorithm for finding four independent spanning trees on a chordal ring. In this paper, we give a new linear time algorithm to generate four independent spanning trees with a reduced height in each tree. Moreover, a complete analysis of our improvements on the heights of independent spanning trees is also provided. 相似文献
16.
《Parallel and Distributed Systems, IEEE Transactions on》2007,18(4):c1-c1
This paper is concerned with a particular family of regular 4-connected graphs, called chordal rings. Chordal rings are a variation of ring networks. By adding two extra links (or chords) at each vertex in a ring network, the reliability and fault-tolerance of the network are enhanced. Two spanning trees on a graph are said to be independent if they are rooted at the same vertex, say, r, and for each vertex vner, the two paths from r to v, one path in each tree, are internally disjoint. A set of spanning trees on a given graph is said to be independent if they are pairwise independent. Iwasaki et al. (1999) proposed a linear time algorithm for finding four independent spanning trees on a chordal ring. In this paper, we give a new linear time algorithm to generate four independent spanning trees with a reduced height in each tree. Moreover, a complete analysis of our improvements on the heights of independent spanning trees is also provided 相似文献
17.
Estimating the partition function is a key but difficult computation in graphical models. One approach is to estimate tractable
upper and lower bounds. The piecewise upper bound of Sutton et al. is computed by breaking the graphical model into pieces
and approximating the partition function as a product of local normalizing factors for these pieces. The tree reweighted belief
propagation algorithm (TRW-BP) by Wainwright et al. gives tighter upper bounds. It optimizes an upper bound expressed in terms
of convex combinations of spanning trees of the graph. Recently, Globerson et al. gave a different, convergent iterative dual
optimization algorithm TRW-GP for the TRW objective. However, in many practical applications, particularly those that train
CRFs with many nodes, TRW-BP and TRW-GP are too slow to be practical. Without changing the algorithm, we prove that TRW-BP
converges in a single iteration for associative potentials, and give a closed form for the solution it finds. The closed-form
solution obviates the need for complex optimization. We use this result to develop new closed-form upper bounds for MRFs with
arbitrary pairwise potentials. Being closed-form, they are much faster to compute than TRW-based bounds. We also prove similar
convergence results for loopy belief propagation (LBP) and use it to obtain closed-form solutions to the LBP pseudomarginals
and approximation to the partition function for associative potentials. We then use recent results proved by Wainwright et
al for binary MRFs to obtain closed-form lower bounds on the partition function. We then develop novel lower bounds for arbitrary
associative networks. We report on experiments with synthetic and real-world graphs. Our new upper bounds are considerably
tighter than the piecewise bounds in practice. Moreover, we can compute our bounds on several graphs where TRW-BP does not
converge. Our novel lower bound, in spite of being closed-form and much faster to compute, outperforms more complicated popular
algorithms for computing lower bounds like mean-field on densely connected graphs by wide margins although it does worse on
sparsely connected graphs like chains. 相似文献
18.
In this paper we propose a limit characterization of the behaviour of classes of graphs with respect to their number of spanning trees. Let {Gn} be a sequence of graphs G0,G1,G2,… that belong to a particular class. We consider graphs of the form Kn−Gn that result from the complete graph Kn after removing a set of edges that span Gn. We study the spanning tree behaviour of the sequence {Kn−Gn} when n→∞ and the number of edges of Gn scales according to n. More specifically, we define the spanning tree indicator ({Gn}), a quantity that characterizes the spanning tree behaviour of {Kn−Gn}. We derive closed formulas for the spanning tree indicators for certain well-known classes of graphs. Finally, we demonstrate that the indicator can be used to compare the spanning tree behaviour of different classes of graphs (even when their members never happen to have the same number of edges). 相似文献
19.
Rainer Schmidt 《Performance Evaluation》1997,29(4):245-254
Mean value analysis (MVA) is an efficient algorithm for determining the mean sojourn time, the mean queue length, and the throughput in a closed multiclass queueing network. It provides exact results for the class of product-form networks. Often different classes have different service requirements in FCFS queues, but such networks are not of product form. There are several possibilities to compute performance measure for such nodes and networks. In this paper we present an approximation formula for multiple-server FCFS queues with class-dependent service times as a Norton flow equivalent product node, where the departure rate of any class depends on the number of customers of all classes in the queue. We will use this approximation in the sojourn time formula of some exact and approximate MVA algorithms. 相似文献