半结构化数据的模式抽取

模式抽取在半结构化数据研究领域中具有重要意义。论文结合同类对象集和标签路径的概念,提出了一种从OEM模型中抽取模式的新方法。算法的基本思想是:在用OEM模型表示的半结构化数据中查找同类对象集,并通过构造模式表的方法来实现模式抽取。这种方法不但能从层次结构数据中抽取模式,而且还能从包含环路的OEM数据中进行模式抽取,克服了其它一些算法不能从带有环路的数据中进行模式抽取的缺点。     

基于标签路径的Web结构化数据自动抽取

提出了一种基于标签路径的Web结构化数据自动抽取方法。该方法通过对网页DOM树的解析获取完整标签路径集合,并依据路径相似度测量方法来聚类标签路径,实现目标数据区域的定位,然后通过标签节点坐标位置的特性来分离各个数据项,过滤冗余数据,最终完成数据抽取。实验结果表明,与MDR方法相比,该方法在处理拥有结构化数据的网页时,有更高的查全率和查准率。     

基于标签路径聚类的文本信息抽取算法

针对网页噪音和网页非结构化信息抽取复杂度高的问题,提出一种基于标签路径聚类的文本信息抽取算法。对网页噪音进行预处理,根据网页的文档对象模型树结构进行标签路径聚类,通过自动训练的阈值和网页分割算法快速判定网页的关键部分,根据数据块中的嵌套结构获取网页文本抽取模板。对不同类型网站的实验结果表明,该算法运行速度快、准确度高。     

自动粒度选择的半结构化页面信息抽取

半结构化页面的数据记录间存在结构相似性,在先序遍历DOM树生成的标记序列中表现为重复出现的模式,可利用后缀树进行挖掘。由于标记序列可以在块粒度和文本粒度两个级别上展现,而不同粒度下产生的最佳抽取模式在抽取效果方面又表现出不确定性,因此提出一种自动粒度选择的半结构化页面信息抽取方法。算法从后缀树获取的重复模式中选取最大重复和串联重复构成候选模式集,通过特征参数确定两个粒度各自的最佳模式集,最后引入抽取结果规则度参数并进行综合评价,以确定抽取模式完成半结构化页面数据记录的自动抽取。     

基于文本块密度和标签路径覆盖率的网页正文抽取

针对大多数网页除了正文信息外,还包括导航、广告和免责声明等噪声信息的问题。为了提高网页正文抽取的准确性,提出了一种基于文本块密度和标签路径覆盖率的抽取方法（CETD-TPC）,结合网页文本块密度特征和标签路径特征的优点,设计了融合两种特征的新特征,利用新特征抽取网页中的最佳文本块,最后,抽取该文本块中的正文内容。该方法有效地解决了网页正文中噪声块信息过滤和短文本难以抽取的问题,且无需训练和人工处理。在CleanEval数据集和从知名网站上随机选取的新闻网页数据集上的实验结果表明,CETD-TPC方法在不同数据源上均具有很好的适用性,抽取性能优于CETR、CETD和CEPR等算法。     

流形结构保持的传播半监督降维算法

标签传播算法(LP)是一种基于图的半监督学习算法,通过保持数据间的某些特殊结构,将部分有标签数据的标签信息迭代传递给无标签数据,直至获得全局的稳定状态.结合标签传播算法和线性鉴别分析提出一种流形结构保持的传播半监督降维算法(SDRMPP),采用流行结构上的重构权重并结合已知的部分标签信息进行标签传播,利用传播后获得的全体软标签信息构造离散度矩阵实现鉴别分析,通过求解目标函数的最优值获得特征抽取空间,从而对测试样本进行分类.在Yale和Feret两个标准人脸库上实验验证了该算法的有效性,尤其在只存有少量有标签样本的情况下,该算法仍能保持良好的分类性能.     

基于网络和标签的混合推荐算法

基于网络结构的推荐算法利用用户与项目间的结构关系进行推荐,忽略了用户偏好,而项目的标签隐含了项目的内容及用户的偏好,提出一种基于网络结构和标签的混合推荐方法。算法根据用户选择项目的标签统计信息,分别采用TF-IDF和用户对标签的支持度两种方法构建用户偏好模型,与基于网络的推荐模型进行线性组合推荐。通过在基准数据集MovieLens上测试证明,该算法在推荐结果命中率、个性化程度、多样性等方面均优于基于网络的推荐算法。     

标签扩展的协同过滤推荐算法

大多数利用标签与用户和项目之间关系的推荐算法,都要面临用户个体不同所导致的标签稀疏问题,不同的用户为项目所标注的标签会有所不同.针对由于用户标注标签的随意性而导致的用户标签和项目标签矩阵稀疏问题,提出了一种标签扩展的协同过滤推荐算法.该算法根据用户标注标签的行为计算基于标签的标签相似度,根据用户标注的标签语义计算基于标签语义的标签相似度,从用户行为和标签语义2个方面评估标签的相似度,并利用标签相似度来扩展每个项目标签,降低由项目与标签的关联关系产生的矩阵稀疏度.在M ovieLens数据集上的实验结果表明,所提算法在精度上有所提高.     

基于半结构化数据模型的频繁模式挖掘研究

为了有效快速地得到频繁模式,通过公共路径舍弃中间重新构造模式树的步骤,充分利用层次结构和深度优先遍历,提出了直接从待挖掘原始半结构化数据中挖掘频繁模式的算法。     

一种基于受限约束范围标签传播的半监督学习算法

提出一种基于受限约束范围标签传播的半监督学习算法。首先利用相似性矩阵计算得出概率转移矩阵,进而通过概率转移矩阵得出受限约束范围。然后在约束范围内利用半监督学习框架下的标签传播算法计算基于路径的相似性,路径相似性决定了标签传播的重要路径。由于只使用几条重要的传播路径使得算法中省去计算每一条路径的相似度,计算复杂度大大减少。最终使得标签在带标签数据与未标签数据之间通过几条重要的路径之间传播。实验已经证明此算法的有效性。     

A Branch-Checking Algorithm for All-Pairs Shortest Paths

We formulate and study an algorithm for all-pairs shortest paths in a network with $n $ nodes and $m $ arcs of positive length. Using the dynamic programming principle of optimality of subpaths the algorithm avoids redundant updates of distance labels. A shortest $v$--$w$ path, say $\langle v, r_{1} , r_{2} , \ldots , r_{k } = w \rangle$ with $k $ arcs ($k \geq 1$), is only then combined with an arc $(w,t) \in A$ to update the distance label of pair $v$--$t$, if $(w,t) $ is present on the shortest $r_{\ell } $--$ t$ path for each node $r_{\ell}$ $(\ell=k- 1 , k- 2, \ldots, 1) $. The algorithm extracts shortest paths in order of length from a data structure and builds two shortest path trees per node, an extra effort of $O(n^{2})$. This way it can execute efficiently only the aforementioned distance updates, by picking the arcs $(w,t)$ out of these trees. The time complexity order per distance update and path extraction is similar as in other algorithms. An implementation with a data structure of heaps is possible, but a bucket-type data structure may be more appropriate. The implied number of distance updates does not exceed $nm_{0}$ ($m_{0}$ being the total number of shortest path arcs), but is frequently much lower. In extreme cases the new algorithm applies $O(n^{2})$ distance updates, whereas known algorithms require $\Omega( n ^{3})$ updates. The algorithm is especially suited for undirected graphs; here the construction of one tree per node is sufficient and the computation times halve.     

A Branch-Checking Algorithm for All-Pairs Shortest Paths

We formulate and study an algorithm for all-pairs shortest paths in a network with $n $ nodes and $m $ arcs of positive length. Using the dynamic programming principle of optimality of subpaths the algorithm avoids redundant updates of distance labels. A shortest $v$--$w$ path, say $\langle v, r_{1} , r_{2} , \ldots , r_{k } = w \rangle$ with $k $ arcs ($k \geq 1$), is only then combined with an arc $(w,t) \in A$ to update the distance label of pair $v$--$t$, if $(w,t) $ is present on the shortest $r_{\ell } $--$ t$ path for each node $r_{\ell}$ $(\ell=k- 1 , k- 2, \ldots, 1) $. The algorithm extracts shortest paths in order of length from a data structure and builds two shortest path trees per node, an extra effort of $O(n^{2})$. This way it can execute efficiently only the aforementioned distance updates, by picking the arcs $(w,t)$ out of these trees. The time complexity order per distance update and path extraction is similar as in other algorithms. An implementation with a data structure of heaps is possible, but a bucket-type data structure may be more appropriate. The implied number of distance updates does not exceed $nm_{0}$ ($m_{0}$ being the total number of shortest path arcs), but is frequently much lower. In extreme cases the new algorithm applies $O(n^{2})$ distance updates, whereas known algorithms require $\Omega( n ^{3})$ updates. The algorithm is especially suited for undirected graphs; here the construction of one tree per node is sufficient and the computation times halve.     

基于中轴线约束的最短路径的血管提取算法

血管分割对于血管精确可视化、心血管疾病诊断和血管疾病定量至关重要。本文提出了基于中轴线约束的最短路径的血管提取算法。该算法包括了两次最短路径搜索过程,第一次搜索过程使用了回溯累加技术来提取血管的中轴线,然后结合中轴线信息将其作为血管搜索的能量约束进行第二次搜索过程来提取血管。本文的方法只需要为血管提取设置一个起点,并不需要为血管树复杂的分支结构设置另外的端点。本文使用三维冠状动脉CT血管造影数据来验证本文的算法的可行性和有效性。     

Automatic generation of basis test paths using variable length genetic algorithm

Path testing is the strongest coverage criterion in white box testing. Finding target paths is a key challenge in path testing. Genetic algorithms have been successfully used in many software testing activities such as generating test data, selecting test cases and test cases prioritization. In this paper, we introduce a new genetic algorithm for generating test paths. In this algorithm the length of the chromosome varies from iteration to another according to the change in the length of the path. Based on the proposed algorithm, we present a new technique for automatically generating a set of basis test paths which can be used as testing paths in any path testing method. The proposed technique uses a method to verify the independency of the generated paths to be included in the basis set of paths. In addition, this technique employs a method for checking the feasibility of the generated paths. We introduce new definitions for the key concepts of genetic algorithm such as chromosome representation, crossover, mutation, and fitness function to be compatible with path generation. In addition, we present a case study to show the efficiency of our technique. We conducted a set of experiments to evaluate the effectiveness of the proposed path generation technique. The results showed that the proposed technique causes substantial reduction in path generation effort, and that the proposed GA algorithm is effective in test path generation.     

一种基于桶结构的单源最短路径算法

以单源最短路径为主的最优路径问题是众多社会应用领域内选择最优问题的基础。本文分析了不同实现技术求解单源最短路径问题的算法,结合基于标记设定的Dijkstra算法和基于标记修正的BFM算法的思想,提出了一种基于桶结构的单源最短路径算法。实验结果表明,该算法与前两种算法相比,具有好的运行时间复杂度和可并行性。     

基于VLIW的数据通路分配算法

体系结构相关的优化编译模型需要考虑底层硬件的特性。该文针对目标机具有软件可以控制数据通路的特点提出了一个数据通路分配算法,该算法综合考虑了两个关键因素——子通路和通路操作,从而减小了分配结果对并行性的影响。该算法不仅可以用来解决数据通路分配问题,而且可作为解决多重资源分配问题的一个参考方法。     

交通网络最短路径标号算法的实现与效率分析

标号算法是交通网络最短路径算法族中应用最广泛的算法,其中以各种D ijkstra算法为核心的标号设定算法是各种商用G IS平台网络分析算法的首选。然而,同样隶属于标号算法的标号改正算法在交通网络路径分析中却罕有应用。为了将标号改正算法应用于交通网络路径分析,首先讨论了标号算法的基本结构;然后分析了标号设定算法和标号改正算法的实现过程、复杂度、运行特点和适用性,进而选择了标号设定和标号改正算法中公认的几种优秀算法———基于逼近桶结构和改进四叉堆的D ijkstra算法(D IKBA与D IKQH)以及Pallottino算法(TWO-Q),并结合交通网络邻接链表结构予以实现;最后采用城市交通网络数据,对几种算法的实际运行效率进行了对比试验,试验结果表明,标号改正算法和标号设定算法优点各异;由于交通网络路径算法的应用越来越强调动态性和网络适用性,而且标号改正算法较之标号设定算法具有更大的适用范围,因此其在交通网络路径分析中具有极大的应用潜力。     

A Holographic Diffraction Label Recognition Algorithm Based on Fusion Double Tensor Features

As an efficient technique for anti-counterfeiting, holographic diffraction labels has been widely applied to various fields. Due to their unique feature, traditional image recognition algorithms are not ideal for the holographic diffraction label recognition. Since a tensor preserves the spatiotemporal features of an original sample in the process of feature extraction, in this paper we propose a new holographic diffraction label recognition algorithm that combines two tensor features. The HSV (Hue Saturation Value) tensor and the HOG (Histogram of Oriented Gradient) tensor are used to represent the color information and gradient information of holographic diffraction label, respectively. Meanwhile, the tensor decomposition is performed by high order singular value decomposition, and tensor decomposition matrices are obtained. Taking into consideration of the different recognition capabilities of decomposition matrices, we design a decomposition matrix similarity fusion strategy using a typical correlation analysis algorithm and projection from similarity vectors of different decomposition matrices to the PCA (Principal Component Analysis) sub-space , then, the sub-space performs KNN (K-Nearest Neighbors) classification is performed. The effectiveness of our fusion strategy is verified by experiments. Our double tensor recognition algorithm complements the recognition capability of different tensors to produce better recognition performance for the holographic diffraction label system.