如何进行高性能的相似性比较？
本帖最后由 shendaowu 于 2013-05-20 09:26:18 编辑 首先问一下将一个集合内的所有元素进行多对多的相似性比较有高效的方法么？就是不用将每一个元素都和其他全部元素进行比较。
如果上面说的情况只能执行n（n是元素个数）次一对n的比较的话，那么考虑一对n有没有什么高效的算法。数据的结构大概是这样的：集合中每个数据元素A都是一个数组，每个数组的元素a都是整数，并且值域比较“窄”。可能只有0~10。要求算出集合中两个元素A的相似性。另外集合中的元素A的数量非常多，可能上亿，而数组中的元素a也非常多，可能上千万。但是元素a可能会比较少，可能不过千，但是元素A还是上亿，如果是这样可以进行特殊的优化么？比如 10 10 10 和 10 10 10 的相似度是1，10 10 10 和 0 0 0 的相似度是0。相似度的定义可以为了效率做适当调整。值域的“宽”“窄”会影响对效率的优化么？
我的要求是搜索时的效率要尽可能地高，最好是可以不比较n次，比如在修改或者添加集合中的元素A的时候生成这个元素A的特征码。但是要求绝对不能漏掉相似的元素A。另外是否可以第一次扫描得到大致相似的元素，这个过程比较快，然后第二次扫描在上次扫描的结果中仔细搜索相似性？还有占用的空间最好不要太多，但是如果占用的空间是个定值的话，并且可以放到硬盘中，那还是可以考虑的，比如这个：http://www.doc88.com/p-91994430706.html。考虑到这么大的数据量本来就不可能放到内存中，所以用硬盘的空间换效率应该是可行的。另外如何节省空间也是个问题，如果元素A上亿，元素a上千万的话，那数据库占用的空间可能就能在世界上排上名次了，显然成本太高。还有如果是稀疏矩阵如何优化？
另外问一下相似性的判断属于计算机科学的哪个分支？有没有这方面的书？
[解决办法]
相似度判定我大多用余弦相似度算法
public class CosineCompare {
/*余弦相似度算法*/
public static void main(String[] args) throws Exception {
double[] curve_1 = { 1, 4, 5, 7, 8, 9, 6, 5, 3, 2, 1 }; //坐标
double[] curve_2 = { 1, 1.2, 8, 20, 9, 8, 6, 5, 3, 2, 1 }; //坐标
double x = 0, y = 0, z = 0;
for (int i = 0; i < curve_1.length; i++) {
x += curve_1[i] * curve_1[i];
y += curve_2[i] * curve_2[i];
z += curve_1[i] * curve_2[i];
}
x = Math.sqrt(x);
y = Math.sqrt(y);
System.out.println(z / (x * y));
}
}