Finding Median and Center Strings for a Probability Distribution on a Set of Strings Under Levenshtein Distance Based on Integer Linear Programming
Finding Median and Center Strings for a Probability Distribution on a Set of Strings Under Levenshtein Distance Based on Integer Linear Programming
复制标题
DOI：
10.1007/978-3-319-54717-6_7
复制
发表时间：
2016-02
期刊：
影响因子：
--
通讯作者：
M. Hayashida;H. Koyano
中科院分区：
文献类型：
--
作者：
M. Hayashida;H. Koyano
对于由数字或数值向量组成的数据集，均值是捕获数据中心的最基本的度量。然而，对于字符串数据集，无法定义数据的均值，因此，中位数和中心字符串经常被用作数据中心的度量。与计算数值数据的均值相比，构造字符串数据的中值和中心串并不容易，并且没有找到保证构造中心串的精确解的算法。在本研究中，我们首先将字符串数据的中位数和中心字符串的定义概括为由给定字母表中的字母组成的所有字符串的集合的概率分布。这种概括对应于将数值数据的平均值转化为一组数字或数值向量的概率分布的期望值。接下来，我们开发应用整数线性规划为一组字符串上的概率分布构造中值和中心字符串的精确解的方法。在一组字符串是具有编辑距离的度量空间的情况下，通过使用编辑距离上的三角不等式将这些方法改进为更快的方法。此外，如果由相似字符串组成的子集的概率接近于 1，我们还开发了非常快速地构造中值字符串和中心字符串的近似解的方法。最后，我们进行模拟实验来检验我们提出的方法在实际应用中的有用性。
For a data set composed of numbers or numerical vectors, a mean is the most fundamental measure for capturing the center of the data. However, for a data set of strings, a mean of the data cannot be defined, and therefore, median and center strings are frequently used as a measure of the center of the data. In contrast to calculating a mean of numerical data, constructing median and center strings of string data is not easy, and no algorithm is found that is guaranteed to construct exact solutions of center strings. In this study, we first generalize the definitions of median and center strings of string data into those of a probability distribution on a set of all strings composed of letters in a given alphabet. This generalization corresponds to that of a mean of numerical data into an expected value of a probability distribution on a set of numbers or numerical vectors. Next, we develop methods for constructing exact solutions of median and center strings for a probability distribution on a set of strings, applying integer linear programming. These methods are improved into faster ones by using the triangle inequality on the Levenshtein distance in the case where a set of strings is a metric space with the Levenshtein distance. Furthermore, we also develop methods for constructing approximate solutions of median and center strings very rapidly if the probability of a subset composed of similar strings is close to one. Lastly, we perform simulation experiments to examine the usefulness of our proposed methods in practical applications.