Abstract:Most existing semi-supervised clustering algorithms with pairwise constraints neither solve the problem of violation of pairwise constraints effectively, nor handle the high-dimensional data simultaneously. This paper presents a discriminative semi-supervised clustering analysis algorithm with pairwise constraints, called DSCA, which effectively utilizes supervised information to integrate dimensionality reduction and clustering. The proposed algorithm projects the data onto a low-dimensional manifold, where pairwise constraints based K-means algorithm is simultaneously used to cluster the data. Meanwhile, pairwise constraints based K-means algorithm presented in this paper reduces the computational complexity of constraints based semi-supervised algorithm and resolve the problem of violating pairwise constraints in the existing semi-supervised clustering algorithms. Experimental results on real-world datasets demonstrate that the proposed algorithm can effectively deal with high-dimensional data and provide an appealing clustering performance compared with the state-of-the-art semi-supervised algorithm.

Abstract:A semi-supervised clustering method based on affinity propagation (AP) algorithm is proposed in this paper. AP takes as input measures of similarity between pairs of data points. AP is an efficient and fast clustering algorithm for large dataset compared with the existing clustering algorithms, such as K-center clustering. But for the datasets with complex cluster structures, it cannot produce good clustering results. It can improve the clustering performance of AP by using the priori known labeled data or pairwise constraints to adjust the similarity matrix. Experimental results show that such method indeed reaches its goal for complex datasets, and this method outperforms the comparative methods when there are a large number of pairwise constraints.

Abstract:A semi-supervised K-means clustering algorithm for multi-type relational data is proposed, which extends traditional K-means clustering by new methods of selecting initial clusters and similarity measures, so that it can semi-supervise cluster multi-type relational data. In order to achieve high performance, in the algorithm, besides attribute information, both labeled data and relationship information are employed. Experimental results on Movie database show the effectiveness of this method.

Abstract:In this paper, a semi-supervised canonical correlation analysis algorithm called Semi-CCA is developed, which uses supervision information in the form of pair-wise constraints in canonical correlation analysis (CCA). In this setting, besides abundant unlabeled data examples, the domain knowledge in the form of pair-wise constraints which specify whether a pair of data examples belongs to the same class (must-link constraints) or not (cannot-link constraints) is also available. Meanwhile, the relative importance of must-link constraints and cannot-link constraints is validated. Experimental results on the artificial dataset, multiple feature database and facial database including Yale and AR show that the proposed Semi-CCA can effectively enhance the classifier performance by using only a small amount of supervision information.

Abstract:In many machine learning and data mining tasks, it can't achieve the best semi-supervised learning result if only use side-information. So, a local and global preserving based semi-supervised dimensionality reduction (LGSSDR) method is proposed in this paper. LGSSDR algorithm can not only preserve the positive and negative constraints but also preserve the local and global structure of the whole data manifold in the low dimensional embedding subspace. Besides, the algorithm can compute the transformation matrix and handle unseen samples easily. Experimental results on several datasets demonstrate the effectiveness of this method.

Abstract:This paper investigates a graph-based semi-supervised learning algorithm, that is, label propagation algorithm for relation extraction. Labeled and unlabeled examples are represented as the nodes, and their distances as the weights of edges in the graph. The relation extraction tries to obtain a labeling function on this graph to satisfy the global consistency assumption. Experimental results on the ACE (automatic content extraction) corpus showed that this method achieves a better performance than SVM (support vector machine) when only very few labeled examples are available, and it also performs better than bootstrapping for the relation extraction task.

Abstract:A higher-order tensor framework for video analysis and understanding is proposed in this paper. In this framework, image frame, audio and text are represented, which are the three modalities in video shots as data points by the 3rd-order tensor. Then a subspace embedding and dimension reduction method is proposed, which explicitly considers the manifold structure of the tensor space from temporal-sequenced associated co-occurring multimodal media data in video. It is called TensorShot approach. Transductive learning uses a large amount of unlabeled data together with the labeled data to build better classifiers. A transductive support tensor machines algorithm is proposed to train effective classifier. This algorithm preserves the intrinsic structure of the submanifold where tensorshots are sampled, and is also able to map out-of-sample data points directly. Moreover, the utilization of unlabeled data improves classification ability. Experimental results show that this method improves the performance of video semantic concept detection.

Abstract:This paper is primarily to improve the efficiency of real-time dynamic programming (RTDP) algorithm for solving Markov decision problems. Several typical convergence criteria are compared and analyzed. A criterion called optimal action criterion and a corresponding branch strategy are proposed on the basis of the upper and lower bound theory. This criterion guarantees that the agent can act earlier in a real-time decision process while an optimal policy with sufficient precision still remains. It can be proved that under certain conditions one can obtain an optimal policy with arbitrary precision by using such an incremental method. With these new techniques, a bounded incremental real-time dynamic programming (BI-RTDP) algorithm is designed. In the experiments of two typical real-time simulation systems, BI-RTDP outperforms the other state-of-the-art RTDP algorithms tested.

Abstract:P₂-Packing is a typical NP-hard problem. This paper provides a further study on the structures of the P₂-packing problem, and proposes a kernelization algorithm that can obtain a kernel of size at most 7k, which greatly reduces the current best kernel 15k. Based on the kernelization algorithm, an improved parameterized algorithm with running time O^*(2^4.142k) is also presented, which greatly improves the current best result O^*(2^5.301k).

Abstract:This paper investigates the reasons for generation of noises in feedbacks of filtering system by analyzing the knowledge expressions and text structures, and builds a two-dimension similarity (DTS) model of information based on the opposed relation between the noises and user profiles. At the same time, by using the algorithm of AdaBoost based on the LMS (least mean square) classifier, this paper builds a classification curve between the noises and related information according to their distribution in two-dimension similarity space, which helps information filtering system detect and filter the noises in feedback. Experiments validated this algorithm substantially improved the capability of filtering system to rule out the noises.

Abstract:The Cross Entropy method is a new search strategy for combinatorial optimization problems. However, it usually needs considerable computational time to achieve good solution quality. This paper introduces a Cross Entropy algorithm for solving maximum clique problem (MCP). To make the Cross Entropy algorithm faster, this paper proposes a leader-based cooperative parallel strategy. Unlike the widely used coarse-grained parallel strategy, our method has a leader, who can move around the parallel processors and collect data actively, and several followers whose main job are simply to sample the cliques guided by the leader via transition matrix. To evaluate the performance of the algorithm, this paper implements the algorithm using OpenMPI on MIMD architecture, and applies it on the MCP benchmark problems. The speedup and efficiency are analyzed, and the results are compared with those obtained by four other best heuristic algorithms. The results show that the presented method has achieved good performance among those best population-based heuristics.

Abstract:Isomap has attracted attentions recently due to its prominent performance on nonlinear dimensionality reduction. However, how to implement effective learning for data on manifold with rings is still a remaining problem. To solve this problem, a systemic strategy is presented in this study. Based on the intrinsic implementation principle of Isomap, a theorem is presented which gives a sufficient and necessary condition to judge whether a manifold is with rings. Besides, an algorithm for detecting ring structures in the manifold is constructed and a nonlinear dimensionality reduction strategy is developed through polar coordinates transformation. A series of simulation results implemented on a series of synthetic and real-world data sets generated by manifolds with or without rings verify the prominent performance of the new method.

Abstract:According to support vector machines (SVMs), for those geometric approach based classification methods, examples close to the class boundary usually are more informative than others. Taking face detection as an example, this paper addresses the problem of enhancing given training set and presents a nonlinear method to tackle the problem effectively. Based on SVM and improved reduced set algorithm (IRS), the method generates new examples lying close to the face/non-face class boundary to enlarge the original dataset and hence improve its sample distribution. The new IRS algorithm has greatly improved the approximation performance of the original reduced set (RS) method by embedding a new distance metric called image Euclidean distance (IMED) into the kernel function. To verify the generalization capability of the proposed method, the enhanced dataset is used to train an AdaBoost-based face detector and test it on the MIT+CMU frontal face test set. The experimental results show that the original collected database can be enhanced effectively by the proposed method to learn a face detector with improved generalization performance.

Abstract:In this paper, an algorithm for corner detection and localization is proposed based on local orientation distribution (LOD). The algorithm consists of two steps: The first is to detect corners by using the absolute corner energy and the relative corner energy; Then, the detected corners are re-located to sub-pixel accuracy by fitting the intersection of orientation lines of support pixels by the least squares technique. Experimental results show that the LOD-based algorithm can not only provide a higher localization accuracy than most popular detectors, but also has a better performance in resisting noises.

Abstract:In this paper, the disadvantages of some existing algorithms in handling constrained objective problems (COPs) are analyzed and an algorithm used for COPs—immune clonal multi-objective optimization algorithm (ICMOA) is proposed. This algorithm treats constrained optimization as a multi-objective optimization with two objectives. One objective is the original objective function and the other is obtained by the constraints. The concept of the Pareto-dominance in multi-objective optimization is introduced and each individual is implemented clone, mutation, selection and other operations based on the degree of its Pareto-dominance. The clone operation implements the searching for optimal solution in the global region and is available for getting a high quality solution. The mutation operation improves the searching for optimal solution in the local region and assures the diversity of the solutions. The selection operation guarantees the convergence to the optimal solution and improves the convergence speed. Based on the theorem of Markov chain, the global convergence of the new algorithm is proved. Compared with the existing algorithms, simulation results on 13 benchmark test problems show that the new algorithm has some advantages in convergence speed and precision.

Abstract:For conflict game, a rational but conservative action selection method is investigated, namely, minimizing regret function in the worst case. By this method the loss incurred possibly in future is the lowest under this very policy, and Nash equilibrium mixed policy is obtained without information about other agents. Based on regret, a reinforcement learning model and its algorithm for conflict game under multi-agent complex environment are put forward. This model also builds agents' belief updating process on the concept of cross entropy distance, which further optimizes action selection policy for conflict games. Based on Markov repeated game model, this paper demonstrates the convergence property of this algorithm, and analyzes the relationship between belief and optimal policy. Additionally, compared with extended Q-learning algorithm under MMDP (multi-agent markov decision process), the proposed algorithm decreases the number of conflicts dramatically, enhances coordination among agents, improves system performance, and helps to maintain system stability.

Abstract:Because of the absence of a whole logic to represent and reason various kinds of preferences, MPL (logic of many kinds of preference) is presently constructed to fill the gap. But, the semantics of MPL is based on the complete pre-order, so incomplete preferences cannot be expressed in it. In this paper, GMPL (a generalized edition of MPL) is introduced to supply the gap. In addition, the expressive power of GMPL is showed by rewriting several familiar logical preferences. Moreover, a decision procedure is introduced to reduce SAT problem of GMPL into that of propositional logic.

Abstract:In this paper, a time window mechanism based on the penalty value of route flap damping is designed to improve routing convergence. This mechanism judges the route stability in the network from BGP (border gateway protocol) routes correlation by observing multiple routes received from different peers jointly. Then BGP speaker can find instable routes earlier and makes stable routes get the chance to be selected earlier in route selection, thus curtail path exploration. Simulation results prove that with proper parameters this method can reduce convergence delay and communication overhead obviously. Furthermore, without addition information in BGP Update message, time window mechanism is a practical method to be deployed in the Internet.

Abstract:As for different level side-channel leakages, a general side-channel leakage-tolerated model is proposed and a formal description is given by entropy theory. This model adopts (t,n) threshold leakage mechanism, and thus the security do not compromise with partial side-channel leakages. Based on the proposed model, a two-phase masking method is utilized to build leakage-tolerated Advanced Encryption Standard (AES-128). Compared with the conventional countermeasures, this method can resist higher-order side-channel attack and template attack simultaneously. The effectiveness of this method is verified by theoretical analysis and simulation.

Abstract:This paper makes a full-scale introduction to the advancement of research on group mobility model and analyses characteristics and the application range of different models. Most of the existing group mobility models exhibit certain drawbacks in describing the group movement behaviors. A Gibbs sampler based simulated annealing group mobility (GGM) model is proposed to address this deficiency. By simulation comparison with reference point group mobility (RPGM) model, this paper analyzes the impact of two models on Ad Hoc network protocol performance. Experimental results show that the proposed GGM model can describe three different behaviors of group movements effectively, which are group gathering, dispersion, and linear formation, by choosing Gibbs potential functions. The simulation also indicates that different group mobility models have different impact on the performance evaluation of ad hoc network protocol.

Abstract:In this paper, a hierarchical semantic service case is outlined, which supports overall description of functionality, behavior restraints and features. An adaptable similarity degree measurement is proposed to retrieve a service case which is more similar to the target case and easier to be revised if necessary. Moreover, a method based on the interaction ontology is presented to realize dynamically revising service case to support Web service composition. The method of Web service composition proposed in this paper is proved to be feasible and effective by examinations.

Abstract:With click-through data analysis, an automatic search engine performance evaluation method is proposed. This method generates navigational type query topics and answers automatically based on search users' querying and clicking behavior. Experimental results based on a commercial Chinese search engine's user logs show that the automatic method gets a similar evaluation result with the traditional assessor-based ones. This method can also provide timely evaluation results with little human efforts.

Abstract:To address the phenomenon of temporary communication blindness resulted from fixed period beacon exchange in mobile wireless sensor networks, an adaptive beacon exchange algorithm is proposed. The key idea is that work node calculates variable beacon period according to characteristic value relative to up node. idle node calculates variable beacon period according to characteristic value relative to its all neighbors.The threshold probability can be adjusted to meet the performance requirement of networks. Forwarding node removes the next hop from neighbors table if its overtime to wait for the feedback beacon. The simulation shows that the adaptive beacon exchange algorithm can acquire high reach rate for eliminating the phenomenon of temporary communication blindness, especially in work-node-sparse sceneries, with low consumption. So the algorithm is scalable and applicable to large-scale mobile wireless sensor networks.

Abstract:Cooperative caching has been adequately addressed in MANETs for QoS and cooperative computing. This paper presents a Cluster-based Consistency Scheme, CCS. In CCS, the close nodes in locality are organized into a cluster, where a more stable and powerful node is selected as header in each cluster and the others are at most 2 hops away from the header as the members of the cluster. All header nodes form a ring with Chord as group management protocol. An updating tree is built dynamically on top of the Chord ring to propagate the updated data items. In this way, the updated data item is broadcasted within cluster at MAC layer and transmitted among the header nodes along the updating tree. The simulation results demonstrate CCS outperforms the Gossip scheme for consistency of cooperative caching with less workload, higher success rate and less updating time.

Abstract:For a given set S of line segments, finding a straight line intersecting with all the line segments in S is studied in this paper. If an intersection restriction is satisfied by the set, the algorithm presented is to answer whether there is a straight line intersecting with all the line segments in S. If the straight lines exist, the algorithm finds a maximum range, where every straight line located in the range intersects with all the line segments in S. The time complexity of the algorithm is O(n×log n). The algorithm can be used in pattern marching and so on.

Abstract:An automatic Polycube construction and parameterization method is proposed in this paper. This approach first decomposes the input mesh into a set of feature regions. Each region is approximated by a simple Polycube which is further split into several patches. Since each patch corresponds to a rectangular sub-surface of the Polycube, they can be parameterized independently. A smoothing procedure between patches is performed to reduce the overall parametric distortion. This method makes Polycube parameterization more convenient in texture mapping and other applications.

Abstract:A Focus+Context technique based on circle packing is presented for interactive visualization of large hierarchical data. First, a triangular mesh generating method based on externally tangent circles packing is proposed to establish context. Then a method for triangular mesh neighbors tracking is introduced. To realize the context consistency for Focus+Context technique, a layout method for the distorted brother nodes of the focus node is presented based on triangular mesh neighbors tracking, and a recursive method for the children nodes of the focus node is described. Experimental results show that this method can realize fisheye view and can achieve focus and context consistency. The method has been applied to the interactive visualization of file systems, and an interactive visualization tool is introduced.

Abstract:A method for extracting realistic textures from real-world reference spheres is proposed in this paper. The BRDF (bidirectional reflectance distribution function) parameters of fundamental materials, as well as a material weight map for the sphere are obtained through a non-linear optimization process. The material weight map can be used as a conventional texture for relighting. With the BRDF models recovered, the rendered 3D objects can exhibit real and complex appearances with varying light direction/intensity, view point and surface orientations.