The rotational dimension of a graph

Given a connected graph G = (N, E) with node weights s∈? and nonnegative edge lengths, we study the following embedding problem related to an eigenvalue optimization problem over the second smallest eigenvalue of the (scaled) Laplacian of G: Find v_i∈?^|N|, i∈N so that distances between adjacent nodes do not exceed prescribed edge lengths, the weighted barycenter of all points is at the origin, and is maximized. In the case of a two‐dimensional optimal solution this corresponds to the equilibrium position of a quickly rotating net consisting of weighted mass points that are linked by massless cables of given lengths. We define the rotational dimension of G to be the minimal dimension k so that for all choices of lengths and weights an optimal solution can be found in ?^k and show that this is a minor monotone graph parameter. We give forbidden minor characterizations up to rotational dimension 2 and prove that the rotational dimension is always bounded above by the tree‐width of G plus one. © 2010 Wiley Periodicals, Inc. J Graph Theory 66:283‐302, 2011     

A novel kernel Fisher discriminant analysis: constructing informative kernel by decision tree ensemble for metabolomics data analysis

Large amounts of data from high-throughput metabolomics experiments become commonly more and more complex, which brings an enormous amount of challenges to existing statistical modeling. Thus there is a need to develop statistically efficient approach for mining the underlying metabolite information contained by metabolomics data under investigation. In the work, we developed a novel kernel Fisher discriminant analysis (KFDA) algorithm by constructing an informative kernel based on decision tree ensemble. The constructed kernel can effectively encode the similarities of metabolomics samples between informative metabolites/biomarkers in specific parts of the measurement space. Simultaneously, informative metabolites or potential biomarkers can be successfully discovered by variable importance ranking in the process of building kernel. Moreover, KFDA can also deal with nonlinear relationship in the metabolomics data by such a kernel to some extent. Finally, two real metabolomics datasets together with a simulated data were used to demonstrate the performance of the proposed approach through the comparison of different approaches.     

Decomposition tree of a lexicographic product of binary structures

Given a set S and a positive integer k, a binary structure is a function . The set S is denoted by V(B) and the integer k is denoted by . With each subset X of V(B) associate the binary substructure B[X] of B induced by X defined by B[X](x,y)=B(x,y) for any x≠y∈X. A subset X of V(B) is a clan of B if for any x,y∈X and v∈V(B)?X, B(x,v)=B(y,v) and B(v,x)=B(v,y). A subset X of V(B) is a hyperclan of B if X is a clan of B satisfying: for every clan Y of B, if X∩Y≠0?, then X⊆Y or Y⊆X. With each binary structure B associate the family Π(B) of the maximal proper and nonempty hyperclans under inclusion of B. The decomposition tree of a binary structure B is constituted by the hyperclans X of B such that Π(B[X])≠0? and by the elements of Π(B[X]). Given binary structures B and C such that , the lexicographic product B⌊C⌋ of C by B is defined on V(B)×V(C) as follows. For any (x,y)≠(x^′,y^′)∈V(B)×V(C), B⌊C⌋((x,x^′),(y,y^′))=B(x,y) if x≠y and B⌊C⌋((x,x^′),(y,y^′))=C(x^′,y^′) if x=y. The decomposition tree of the lexicographic product B⌊C⌋ is described from the decomposition trees of B and C.     

The critical group of <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">m</Emphasis></Subscript> × <Emphasis Type="Italic">C</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>

In this paper, the structure of the critical group of the graph K _m × C _n is determined, where m, n ≥ 3.     

最小成本生成树对策上Shapley值的新刻画及其应用

2002年,Kar利用有效性、无交叉补贴性、群独立性和等处理性四个公理对最小成本生成树对策上的Shapley值进行了刻画。本文提出了“群有效性”这一公理,利用这一公理和“等处理性”两个公理,给出了最小成本生成树对策上Shapley值的一种新的公理化刻画。最后,运用最小成本生成树对策的Shapley值,对网络服务的费用分摊问题进行了分析。     

融合学习模型的岩石光谱特征自动分类

岩石光谱综合反映了岩石的物理化学性质、成分及其结构构造。岩石光谱数据已被应用于岩石分类的研究,但是不同于矿物光谱,岩石光谱并无标准数据库,且受较多干扰因素影响,例如矿物组分、结构构造、化学成分、风化力度,测量仪器的误差等。传统岩石光谱分类模型先是对岩石光谱进行预处理排除干扰,然后采用不同方法对部分光谱特征分析,以达到分类目的。但对光谱数据特征遗失较多,使得分类准确率低下且操作过程繁琐、效率不高。因此,建立一个简单、快速、准确的岩石光谱自动分类模型具有重要意义。机器学习能够对获得的所有数据进行学习,不存在遗漏,大大提高了分类精度,且是对原始数据直接操作,不需预处理,简化流程。为此,选取辽宁兴城地区作为研究区,采集了若干种典型岩石样本,利用美国ASD便携式光谱仪实测光谱,最终获得608条数据,依据岩石光谱特征分为三类进行研究。首先利用决策树(DT)及决策树的升级模型--随机森林（RF）对数据进行分类,但当数据噪音较大时随机森林容易陷入过拟合;因而利用对异常值不敏感的K-最近邻（KNN）建模,但KNN需要对每个样本都考虑,数据量大时计算量会很大,效率不高;所以通过支持向量机（SVM）来提升分类准确率。从实验结果可以看出,4种分类模型的准确率排序为：SVM>KNN>RF>DT。为进一步提高岩石光谱特征的自动分类精度,采取了融合多个不同模型的办法,即对不同模型的分类结果进行投票,选择投票最多的作为最后分类结果。由于硬投票可在一定程度上减少过拟合现象的发生,更加适合分类模型,所以利用硬投票法融合了RF、KNN与SVM三个机器学习模型,最终的分类准确率可达到99.17%。综上所述,基于融合学习模型进行岩石光谱特征自动分类是切实可行且准确高效的。     

淡水鱼养殖环节中副溶血性弧菌预测统计建模与分析

以全国6个省份淡水鱼养殖环节中副溶血性弧菌检测结果为样本,对样本进行主成分分析与列联表分析,得出影响副溶血性弧菌是否存在二分类变量的因素为地理位置、温度、盐度、PH值及其交互作用;建立二分类Logistic回归模型和经典决策树模型,预测副溶血性弧菌是否存在;将预测结论与实测结果进行比对,实证检验模型预测效果好,预报准确率高,可用于实际预测预报。     

基于流率入树枝向量行列式算法的循环经济系统增长反馈分析

设计了江西省萍乡市兰坡村“猪-沼-粮”循环经济系统工程的流率入树模型,并利用流率入树枝向量行列式算法得到了系统的反馈环,在反馈环基础上,构造了系统增长基模,得到结论,以沼气工程（沼肥）为纽带,发展养殖业能实现生猪养殖、稻谷种植和蔬菜种植之间的良性循环,能够达到稻谷增产和收入增长,在微观层面上实现粮食安全和农民增收双赢。     

关于树上连续状态马氏泛函的一类强偏差定理

强偏差定理一直是国际概率论界研究的中心课题之一.通过构造适当的非负鞅,将Doob鞅收敛定理应用于几乎处处收敛的研究,给出了一类特殊非齐次树上连续状态马氏泛函的若干强偏差定理.     

A greedy algorithm for multicut and integral multiflow in rooted trees

We present an O(min(Kn,n²)) algorithm to solve the maximum integral multiflow and minimum multicut problems in rooted trees, where K is the number of commodities and n is the number of vertices. These problems are NP-hard in undirected trees but polynomial in directed trees. In the algorithm we propose, we first use a greedy procedure to build the multiflow then we use duality properties to obtain the multicut and prove the optimality.