列表1: 1 2 3 4
列表2: 1 3 2 4
我描述的方法生成的矩阵如下(其中1表示行号高于列号,0表示反之):
列表1: 1 2 3 4 1 1 1 1 2 1 1 3 1 4
列表2: 1 2 3 4 1 1 1 1 2 0 1 3 1 4
由于唯一的区别是元素2和3的顺序,因此应该认为它们非常相似。这两个矩阵的Pearson相关系数为0,表明它们根本没有相关性。我想问题在于我要寻找的不是相关系数,而是其他类型的相似度量。编辑距离,也许?有人能提供更好的建议吗?
每个元素索引差的平方和。
List 1: A B C D E
List 2: A D C B E
在 List 2 中找到 List 1 中每个元素的索引(从0开始)
A B C D E
0 3 2 1 4
List 1中每个元素在List 1中的索引(从0开始计数)
A B C D E
0 1 2 3 4
区别:
A B C D E
0 -2 0 2 0
差的平方:
A B C D E
4 4
不同性的平均值 = 8/5。
你可能需要考虑转换一个字符串成另一个字符串需要多少次变化(我猜你提到编辑距离时就是在谈论这个问题)。
参见:http://en.wikipedia.org/wiki/Levenshtein_distance
虽然我认为编辑距离并不考虑旋转。如果你允许旋转作为一种操作,那么:
1、2、3、4
和
2、3、4、1
非常相似。
如果有人在使用R语言,我已经实现了一个函数,可以使用@bubake 这里描述的方法计算“斯皮尔曼等级相关系数”:
get_spearman_coef <- function(objectA, objectB) {
#getting the spearman rho rank test
spearman_data <- data.frame(listA = objectA, listB = objectB)
spearman_data$rankA <- 1:nrow(spearman_data)
rankB <- c()
for (index_valueA in 1:nrow(spearman_data)) {
for (index_valueB in 1:nrow(spearman_data)) {
if (spearman_data$listA[index_valueA] == spearman_data$listB[index_valueB]) {
rankB <- append(rankB, index_valueB)
}
}
}
spearman_data$rankB <- rankB
spearman_data$distance <-(spearman_data$rankA - spearman_data$rankB)**2
spearman <- 1 - ( (6 * sum(spearman_data$distance)) / (nrow(spearman_data) * ( nrow(spearman_data)**2 -1) ) )
print(paste("spearman's rank correlation coefficient"))
return( spearman)
}
结果:
get_spearman_coef(c("a","b","c","d","e"), c("a","b","c","d","e"))
斯皮尔曼等级相关系数:1
get_spearman_coef(c("a","b","c","d","e"), c("b","a","d","c","e"))
斯皮尔曼等级相关系数:0.9
有一种分支定界算法,适用于任何您喜欢的运算符集。它可能不是非常快。伪代码大致如下:
bool bounded_recursive_compare_routine(int* a, int* b, int level, int bound){
if (level > bound) return false;
// if at end of a and b, return true
// apply rule 0, like no-change
if (*a == *b){
bounded_recursive_compare_routine(a+1, b+1, level+0, bound);
// if it returns true, return true;
}
// if can apply rule 1, like rotation, to b, try that and recur
bounded_recursive_compare_routine(a+1, b+1, level+cost_of_rotation, bound);
// if it returns true, return true;
...
return false;
}
int get_minimum_cost(int* a, int* b){
int bound;
for (bound=0; ; bound++){
if (bounded_recursive_compare_routine(a, b, 0, bound)) break;
}
return bound;
}
这个算法所需的时间大致是指数级的,因为它受到最后一个可行的边界的支配。
补充一下:这可以扩展到查找存储在trie中的最近匹配字符串。 我多年前在拼写校正算法中做过这件事。
我不确定它在底层使用的确切公式,但是difflib.SequenceMatcher.ratio()
正好可以做到这一点:
ratio(self) method of difflib.SequenceMatcher instance:
Return a measure of the sequences' similarity (float in [0,1]).
from difflib import SequenceMatcher
sm = SequenceMatcher(None, '1234', '1324')
print sm.ratio()
>>> 0.75
另一种基于一点数学的方法是计算将一个数组转换为另一个数组所需的逆序对数量。一个逆序对是交换两个相邻数组元素。在Ruby中,可以这样做:
# extend class array by new method
class Array
def dist(other)
raise 'can calculate distance only to array with same length' if length != other.length
# initialize count of inversions to 0
count = 0
# loop over all pairs of indices i, j with i<j
length.times do |i|
(i+1).upto(length) do |j|
# increase count if i-th and j-th element have different order
count += 1 if (self[i] <=> self[j]) != (other[i] <=> other[j])
end
end
return count
end
end
l1 = [1, 2, 3, 4]
l2 = [1, 3, 2, 4]
# try an example (prints 1)
puts l1.dist(l2)
长度为n的两个数组之间的距离可以在0(它们相同)和n *(n + 1)/ 2之间(将第一个数组反转得到第二个数组)。如果您希望始终将距离保持在0和1之间,以便比较不同长度的数组对的距离,请除以n *(n + 1)/ 2。
这种算法的缺点是其运行时间为n ^ 2。它还假设数组没有重复项,但可以进行调整。
关于代码行“count + = 1 if ...”的说明:只有当第一个列表的第i个元素小于其第j个元素且第二个列表的第i个元素大于其第j个元素或反之亦然时,计数才会增加(这意味着第一个列表的第i个元素大于其第j个元素且第二个列表的第i个元素小于其第j个元素)。简而言之:(l1 [i]&lt; l1 [j] and l2 [i]&gt; l2 [j])or(l1 [i] > l1 [j] and l2 [i] < l2 [j])
如果有两个订单,应该查看两个重要的排名相关系数:
斯皮尔曼等级相关系数:https://en.wikipedia.org/wiki/Spearman%27s_rank_correlation_coefficient
这与Jamesh的答案几乎相同,但在范围为-1到1之间进行缩放。
它的定义为:
1 - (6 * 平方距离之和) / (样本数 * (样本数**2 - 1))
在使用Python时,可以使用以下代码:
from scipy import stats
order1 = [ 1, 2, 3, 4]
order2 = [ 1, 3, 2, 4]
print stats.spearmanr(order1, order2)[0]
>> 0.8000
print stats.kendalltau(order1, order2)[0]
>> 0.6667