Clustering reduced interval data using Hausdorff distance

Summary  In the last decade, factorial and clustering techniques have been developed to analyze multidimensional interval data (MIDs). In classic data analysis, PCA and clustering of the most significant components are usually performed to extract cluster structure from data. The clustering of the projected data is then performed, once the noise is filtered out, in a subspace generated by few orthogonal variables. In the framework of interval data analysis, we propose the same strategy. Several computational questions arise from this generalization. First of all, the representation of data onto a factorial subspace: in classic data analysis projected points remain points, but projected MIDs do not remains MIDs. Further, the choice of a distance between the represented data: many distances between points can be computed, few distances between convex sets of points are defined. We here propose optimized techniques for representing data by convex shapes, for computing the Hausdorff distance between convex shapes, based on an L ₂ norm, and for performing a hierarchical clustering of projected data.     

Hausdorff Measure for a Stable-Like Process over an Infinite Extension of a Local Field

We consider an infinite extension K of a local field of zero characteristic which is a union of an increasing sequence of finite extensions. K is equipped with an inductive limit topology; its conjugate K is a completion of K with respect to a topology given by certain explicitly written seminorms. The semigroup of measures, which defines a stable-like process X(t) on K, is concentrated on a compact subgroup S K. We study properties of the process X _S (t), a part of X(t) in S. It is shown that the Hausdorff and packing dimensions of the image of an interval equal 0 almost surely. In the case of tamely ramified extensions a correct Hausdorff measure for this set is found.     

基于Hausdorff距离的区间数多属性公路网综合评价

公路网评价对于了解区域公路网状态和交通需求间的关系非常重要.讨论了公路网属性表示为区间数的问题,通过计算属性值相对于属性等级的距离矩阵得到相应的加权可变相似度,再对可变相似度进行归一化处理,作为各属性等级的权重向量,同时应用级别特征公式求得综合属性值进行综合评价.实例表明,该方法和其他方法的评价结果一致,且能给出不同标准下的评价结果,计算过程简明且有效,而且能向属性值为其他类型的不确定量进行拓广.     

Applying an edit distance to the matching of tree ring sequences in dendrochronology

In dendrochronology wood samples are dated according to the tree rings they contain. The dating process consists of comparing the sequence of tree ring widths in the sample to a dated master sequence. Assuming that a tree forms exactly one ring per year a simple sliding algorithm solves this matching task.

But sometimes a tree produces no ring or even two rings in a year. If a sample sequence contains this kind of inconsistencies it cannot be dated correctly by the simple sliding algorithm. We therefore introduce a algorithm for dating such a sample sequence against an error-free master sequence, where n and m are the lengths of the sequences. Our algorithm takes into account that the sample might contain up to missing or double rings and suggests possible positions for these kind of inconsistencies. This is done by employing an edit distance as the distance measure.     

多维非退化扩散过程的象集与图集的一致Hausdorff维数

设X(t)=X(0)+∫^t_0α(X(s))dB(s)+∫^t_0β( X(s))ds为一d(d≥3)维非退化扩散过程。令X(E)={X(t): t∈E}, GRX(E)={(t,X(t)): t∈E}，该文证明了：对几乎所有ω：E B([0,∞)),有dimX(E,ω)=dimGRX(E,ω)=2dimE,这里dimF表示F的Hausdorff维数。     

Efficient exponential-time algorithms for edit distance between unordered trees

The edit distance problem for rooted unordered trees is known to be NP-hard. Based on this fact, this paper studies exponential-time algorithms for the problem. For a general case, an $O(\min ({1.26}^{n_1+n_2},2^{b_1+b_2}\cdot \text{<mi mathvariant="italic" is="true">poly</mi>}(n_1,n_2)))$ time algorithm is presented, where $n_1$ and $n_2$ are the numbers of nodes and $b_1$ and $b_2$ are the numbers of branching nodes in two input trees. This algorithm is obtained by a combination of dynamic programming, exhaustive search, and maximum weighted bipartite matching. For bounded degree trees over a fixed alphabet, it is shown that the problem can be solved in $O({(1+ϵ)}^{n_1+n_2})$ time for any fixed $ϵ>0$. This result is achieved by avoiding duplicate calculations for identical subsets of small subtrees.     

A note on generating functions for Hausdorff moment sequences

For functions whose Taylor coefficients at the origin form a Hausdorff moment sequence we study the behaviour of for ( fixed).

     

FFT-based algorithms for the string matching with mismatches problem

The string matching with mismatches problem requires finding the Hamming distance between a pattern P of length m and every length m substring of text T with length n. Fischer and Paterson's FFT-based algorithm solves the problem without error in O(σnlogm), where σ is the size of the alphabet Σ [SIAM–AMS Proc. 7 (1973) 113–125]. However, this in the worst case reduces to O(nmlogm). Atallah, Chyzak and Dumas used the idea of randomly mapping the letters of the alphabet to complex roots of unity to estimate the score vector in time O(nlogm) [Algorithmica 29 (2001) 468–486]. We show that the algorithm's score variance can be substantially lowered by using a bijective mapping, and specifically to zero in the case of binary and ternary alphabets. This result is extended via alphabet remappings to deterministically solve the string matching with mismatches problem with a constant factor of 2 improvement over Fischer–Paterson's method.     

基于Hausdorff距离的模糊数互补判断矩阵排序研究

基于Bonissone近似计算、Hausdorff距离和模糊折衷型决策方法,给出带有梯形模糊数互补判断矩阵的一种排序方法。同时给出精确值、三角模糊数的互补判断矩阵转化为梯形模糊数互补判断矩阵的方法,因此本文方法同样适合于处理精确值、三角模糊数的互补判断矩阵的排序问题。最后用算例说明了计算过程。     

Faster algorithms for string matching with k mismatches

The string matching with mismatches problem is that of finding the number of mismatches between a pattern P of length m and every length m substring of the text T. Currently, the fastest algorithms for this problem are the following. The Galil–Giancarlo algorithm finds all locations where the pattern has at most k errors (where k is part of the input) in time O(nk). The Abrahamson algorithm finds the number of mismatches at every location in time . We present an algorithm that is faster than both. Our algorithm finds all locations where the pattern has at most k errors in time . We also show an algorithm that solves the above problem in time O((n+(nk³)/m)logk).     

A new learning strategy for stereo matching derived from a fuzzy clustering method

This paper presents an approach to the local stereo correspondence problem. The primitives or features used are groups of collinear connected edge points called segments. Each segment has several associated attributes or properties. We have verified that the differences of the attributes for the true matches cluster in a cloud around a center. Then for each current pair of primitives we compute a distance between the difference of its attributes and the cluster center. The correspondence is established in the basis of the minimum distance criterion (similarity constraint). We have designed an image understanding system to learn the best representative cluster center. For such purpose a new learning method is derived from the Fuzzy c-Means (FcM) algorithm where the dispersion of the true samples in the cluster is taken into account through the Mahalanobis distance. This is the main contribution of this paper. A better performance of the proposed local stereo-matching learning method is illustrated with a comparative analysis between classical local methods without learning.     

Distance measures based on the edit distance for permutation-type representations

In this paper, we discuss distance measures for a number of different combinatorial optimization problems of which the solutions are best represented as permutations of items, sometimes composed of several permutation (sub)sets. The problems discussed include single-machine and multiple-machine scheduling problems, the traveling salesman problem, vehicle routing problems, and many others. Each of these problems requires a different distance measure that takes the specific properties of the representation into account. The distance measures discussed in this paper are based on a general distance measure for string comparison called the edit distance. We introduce several extensions to the simple edit distance, that can be used when a solution cannot be represented as a simple permutation, and develop algorithms to calculate them efficiently.     

Improving bounds on the minimum Euclidean distance for block codes by inner distance measure optimization

The minimum Euclidean distance is a fundamental quantity for block coded phase shift keying (PSK). In this paper we improve the bounds for this quantity that are explicit functions of the alphabet size q, block length n and code size |C|. For q=8, we improve previous results by introducing a general inner distance measure allowing different shapes of a neighborhood for a codeword. By optimizing the parameters of this inner distance measure, we find sharper bounds for the outer distance measure, which is Euclidean.The proof is built upon the Elias critical sphere argument, which localizes the optimization problem to one neighborhood. We remark that any code with q=8 that fulfills the bound with equality is best possible in terms of the minimum Euclidean distance, for given parameters n and |C|. This is true for many multilevel codes.     

A partial regularity result for an anisotropic smoothing functional for image restoration in BV space

Here we examine the partial regularity of minimizers of a functional used for image restoration in BV space. This functional is a combination of a regularized p-Laplacian for the part of the image with small gradient and a total variation functional for the part with large gradient. This model was originally introduced in Chambolle and Lions using the Laplacian. Due to the singular nature of the p-Laplacian we study a regularized p-Laplacian. We show that where the gradient is small, the regularized p-Laplacian smooths the image u, in the sense that u∈C1,α for some 0<α<1. This functional thus anisotropically smooths the image where the gradient is small and preserves edges via total variation where the gradient is large.     

Commuting relations for Hausdorff operators and Hilbert transforms on real Hardy spaces

We consider Hausdorff operators generated by a function ϕ integrable in Lebesgue"s sense on either R or R ², and acting on the real Hardy space H ¹(R), or the product Hardy space H ¹¹(R×R), or one of the hybrid Hardy spaces H ¹⁰(R ²) and H ⁰¹(R ²), respectively. We give a necessary and sufficient condition in terms of ϕ that the Hausdorff operator generated by it commutes with the corresponding Hilbert transform. This revised version was published online in June 2006 with corrections to the Cover Date.     

Improved lower bounds on the total variation distance for the Poisson approximation

New lower bounds on the total variation distance between the distribution of a sum of independent Bernoulli random variables and the Poisson random variable (with the same mean) are derived via the Chen–Stein method. The new bounds rely on a non-trivial modification of the analysis by Barbour and Hall (1984) which surprisingly gives a significant improvement. A use of the new lower bounds is addressed.     

A greedy algorithm for finding a large 2‐matching on a random cubic graph

A 2‐matching of a graph G is a spanning subgraph with maximum degree two. The size of a 2‐matching U is the number of edges in U and this is at least where n is the number of vertices of G and κ denotes the number of components. In this article, we analyze the performance of a greedy algorithm 2greedy for finding a large 2‐matching on a random 3‐regular graph. We prove that with high probability, the algorithm outputs a 2‐matching U with .