The analysis of Range Quickselect and related problems

Range Quickselect, a simple modification of the well-known Quickselect algorithm for selection, can be used to efficiently find an element with rank k in a given range [i..j], out of n given elements. We study basic cost measures of Range Quickselect by computing exact and asymptotic results for the expected number of passes, comparisons and data moves during the execution of this algorithm.The key element appearing in the analysis of Range Quickselect is a trivariate recurrence that we solve in full generality. The general solution of the recurrence proves to be very useful, as it allows us to tackle several related problems, besides the analysis that originally motivated us.In particular, we have been able to carry out a precise analysis of the expected number of moves of the pth element when selecting the jth smallest element with standard Quickselect, where we are able to give both exact and asymptotic results.Moreover, we can apply our general results to obtain exact and asymptotic results for several parameters in binary search trees, namely the expected number of common ancestors of the nodes with rank i and j, the expected size of the subtree rooted at the least common ancestor of the nodes with rank i and j, and the expected distance between the nodes of ranks i and j.     

Comparing and aggregating partially resolved trees

Partially-resolved-that is, non-binary-trees arise frequently in the analysis of species evolution. Non-binary nodes, also called multifurcations, must be treated carefully, since they can be interpreted as reflecting either lack of information or actual evolutionary history. While several distance measures exist for comparing trees, none of them deal explicitly with this dichotomy. Here we introduce two kinds of distance measures between rooted and unrooted partially-resolved phylogenetic trees over the same set of species; the measures address multifurcations directly. For rooted trees, the measures are based on the topologies the input trees induce on triplets; that is, on three-element subsets of the set of species. For unrooted trees, the measures are based on quartets (four-element subsets). The first class of measures are parametric distances, where there is a parameter that weighs the difference between an unresolved triplet/quartet topology and a resolved one. The second class of measures are based on the Hausdorff distance, where each tree is viewed as a set of all possible ways in which the tree can be refined to eliminate unresolved nodes. We give efficient algorithms for computing parametric distances and give conditions under which Hausdorff distances can be calculated approximately in polynomial time. Additionally, we (i) derive the expected value of the parametric distance between two random trees, (ii) characterize the conditions under which parametric distances are near-metrics or metrics, (iii) study the computational and algorithmic properties of consensus tree methods based on the measures, and (iv) analyze the interrelationships among Hausdorff and parametric distances.     

一个新的基于Merkle树的移动代理路由解决方案

移动代理是一种软件程序,被认为在未来的电子商务中将起到很重要的作用。但安全问题一直是移动代理得到实际应用的一个很大障碍。对已有的移动代理路由协议进行了分析讨论,在此基础上,利用一种特殊单向函数,结合Merkle树结构,构造了一个新的基于Merkle树的移动代理路由解决方案。该方案不仅具有更好的使用安全性和便利性,而且具有更低的计算复杂度。     

Using Semantic Classification Trees for WSD

This paper describes the evaluation of a WSD method withinSENSEVAL. This method is based on Semantic Classification Trees (SCTs)and short context dependencies between nouns and verbs. The trainingprocedure creates a binary tree for each word to be disambiguated. SCTsare easy to implement and yield some promising results. The integrationof linguistic knowledge could lead to substantial improvement.     

Enlarging the Margins in Perceptron Decision Trees

Capacity control in perceptron decision trees is typically performed by controlling their size. We prove that other quantities can be as relevant to reduce their flexibility and combat overfitting. In particular, we provide an upper bound on the generalization error which depends both on the size of the tree and on the margin of the decision nodes. So enlarging the margin in perceptron decision trees will reduce the upper bound on generalization error. Based on this analysis, we introduce three new algorithms, which can induce large margin perceptron decision trees. To assess the effect of the large margin bias, OC1 (Journal of Artificial Intelligence Research, 1994, 2, 1–32.) of Murthy, Kasif and Salzberg, a well-known system for inducing perceptron decision trees, is used as the baseline algorithm. An extensive experimental study on real world data showed that all three new algorithms perform better or at least not significantly worse than OC1 on almost every dataset with only one exception. OC1 performed worse than the best margin-based method on every dataset.     

Automated Cellular Modeling and Prediction on a Large Scale

We describe CHAMP (CHurn Analysis, Modeling, andPrediction), an automated system for modeling cellularsubscriber churn that is predicting which customerswill discontinue cellular phone service. We describevarious issues related to developing and deployingthis system including automating data access from aremote data warehouse, preprocessing, featureselection, model validation, and optimization toreflect business tradeoffs. Using data from GTE'sdata warehouse for cellular phone customers, CHAMP iscapable of developing churn models customized byregion for over one hundred GTE cellular phone marketstotaling over 5 million customers. Every month churnfactors are identified for each geographic region andmodels are updated to generate churn scores predictingwho is likely to churn in the short term. Learningmethods such as decision trees and genetic algorithmsare used for feature selection and a cascade neuralnetwork is used for predicting churn scores. Inaddition to producing churn scores, CHAMP alsoproduces qualitative results in the form of rules andcomparison of market trends that are disseminatedthrough a web based interface.     

FRCT: fuzzy-rough classification trees

Using fuzzy-rough hybrids, we have proposed a measure to quantify the functional dependency of decision attribute(s) on condition attribute(s) within fuzzy data. We have shown that the proposed measure of dependency degree is a generalization of the measure proposed by Pawlak for crisp data. In this paper, this new measure of dependency degree has been encapsulated into the decision tree generation mechanism to produce fuzzy-rough classification trees (FRCT); efficient, top-down, multi-class decision tree structures geared to solving classification problems from feature-based learning examples. The developed FRCT generation algorithm has been applied to 16 real-world benchmark datasets. It is experimentally compared with the five fuzzy decision tree generation algorithms reported so far, and the rough decomposition tree algorithm. Comparison has been made in terms of number of rules, average training time, and classification accuracy. Experimental results show that the proposed algorithm to generate FRCT outperforms existing fuzzy decision tree generation techniques and rough decomposition tree induction algorithm.

Property Testing of Regular Tree Languages

We consider the edit distance with moves on the class of words and the class of ordered trees. We first exhibit a simple tester for the class of regular languages on words and generalize it to the class of ranked and unranked regular trees. We also show that this distance problem is -complete on ordered trees. A preliminary version of this paper appeared in Proceedings of 31st International Colloquium on Automata, Languages and Programming, volume 3142 of Lecture Notes in Computer Science, pages 932–944, Springer, 2005. Work supported by ACI Sécurité Informatique: VERA of the French Ministry of research.