数组的唯一计算值

Question

我一直在思考，但是已经没有更多的想法了。我有10个数组，每个数组长度为18，其中包含18个双精度值。这18个值是图像的特征。现在我需要对它们应用k-means聚类。

为了实现k-means聚类，我需要为每个数组创建一个唯一的计算值。是否有任何数学、统计或逻辑方法可以帮助我为每个数组创建一个计算值，该值基于其内部的值是唯一的。谢谢提前。

这是我的数组示例。还有10个以上。

[0.07518284315321135    
0.002987851573676068    
0.002963866526639678    
0.002526139418225552    
0.07444872939213325 
0.0037219653347541617   
0.0036979802877177715   
0.0017920256571474585   
0.07499695903867931 
0.003477831820276616    
0.003477831820276616    
0.002036159171625004    
0.07383539747505984 
0.004311312204791184    
0.0043352972518275745   
0.0011786937400740452   
0.07353130134299131 
0.004339580295941216]

- DarkHorse

---

@Octopus 已确认，它适用于单个值，我有10个这样的数组要用于聚类。1个数组=单个图像特征。简而言之，我必须创建相似图像的聚类。 - DarkHorse

梅克尔树对此是否可行？它似乎符合您的要求，既具有计算值的能力，又能检查相似性。http://en.wikipedia.org/wiki/Merkle_tree - mikea

@xlm 我很想让它在单个维度上运行。如果我可以用单个值唯一地表示每个数组，那不是更好吗？这也适用于我们可以检查数组之间的相似性的情况。 - DarkHorse

开发一个算法，将这些数字转换为基于18、36或72（或更多）的char表示。它需要是数字吗？如果是，为什么？如上所述，您无法仅使用10个（0-9）整数数字和长度较小的双精度浮点数唯一地表示这些双精度浮点数（'Real'）。但是根据我看到的数据集，您可以安全地删除实数中的第一个0、小数点和后面的0，并将它们表示为整数，但在将它们转换为整数数字表示时要注意前导零。 - user2880020

@Mani An 像哈希码这样的 int 值有 32 位，因此有 4294967296 种可能的哈希码。但是肯定有超过 4294967296 种可能的 double[] 数组。（事实上，已经有超过 4294967296 种不同的 double 值了）。因此，必须至少有两个 double[] 数组具有相同的哈希码。 - Marco13

Answer 1

你在Java 7中检查了Arrays.hashcode吗？

 /**
 * Returns a hash code based on the contents of the specified array.
 * For any two <tt>double</tt> arrays <tt>a</tt> and <tt>b</tt>
 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
 *
 * <p>The value returned by this method is the same value that would be
 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
 * method on a {@link List} containing a sequence of {@link Double}
 * instances representing the elements of <tt>a</tt> in the same order.
 * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
 *
 * @param a the array whose hash value to compute
 * @return a content-based hash code for <tt>a</tt>
 * @since 1.5
 */
public static int hashCode(double a[]) {
    if (a == null)
        return 0;

    int result = 1;
    for (double element : a) {
        long bits = Double.doubleToLongBits(element);
        result = 31 * result + (int)(bits ^ (bits >>> 32));
    }
    return result;
}

我不明白为什么@Marco13提到了“这不会为数组返回唯一值”。

更新

请参见@Macro13的评论原因，为什么它不能是唯一的..

---

更新

如果我们使用您的输入点绘制图形，（18个元素）有一个尖峰和3个低值，并且模式如下... 如果这是真的... 您可以找到峰值的平均值（1、4、8、12、16），并从剩余值中找到低平均值。

这样，您将拥有峰值平均值和低平均值。您可以找到唯一的数字来表示这两个值，同时使用双射算法 here来保留值。

此算法还提供了公式来反转，即从唯一值获取峰值和低平均值。

要查找唯一的配对< x; y >= x + (y + ( (( x +1 ) /2) * (( x +1 ) /2) ) )

还请参阅pdf第2页的Exercise 1以反转x和y。

用于查找平均值和查找匹配值。

public static double mean(double[] array){
    double peakMean = 0;
    double lowMean = 0;
    for (int i = 0; i < array.length; i++) {
        if ( (i+1) % 4 == 0 || i == 0){
            peakMean = peakMean + array[i];
        }else{
            lowMean = lowMean + array[i];
        }
    }
    peakMean = peakMean / 5;
    lowMean = lowMean / 13;
    return bijective(lowMean, peakMean);
}



public static double bijective(double x,double y){
    double tmp = ( y +  ((x+1)/2));
    return x +  ( tmp * tmp);
}

进行测试

public static void main(String[] args) {
    double[] arrays = {0.07518284315321135,0.002963866526639678,0.002526139418225552,0.07444872939213325,0.0037219653347541617,0.0036979802877177715,0.0017920256571474585,0.07499695903867931,0.003477831820276616,0.003477831820276616,0.002036159171625004,0.07383539747505984,0.004311312204791184,0.0043352972518275745,0.0011786937400740452,0.07353130134299131,0.004339580295941216};
    System.out.println(mean(arrays));
}

你可以使用峰值和低谷值来查找相似的图像。

- Mani

---

你的更新答案卡在了一个模式上，但是数组并不遵循像1个尖峰和3个低值这样的模式，我得到一些有2个或3个尖峰的数组..它是随机的..但是使用双射确实是对你的答案的补充..数组可以按降序排序，并计算中间值以找到峰值平均值和低值平均值，但值的位置反映了相似性。这将受到影响。但如果我有一个类似的模式，这将是一个完美的答案 :) - DarkHorse

Answer 2

这里有一种适用于任意数量双精度浮点数的方法。

public BigInteger uniqueID(double[] array) {
    final BigInteger twoToTheSixtyFour = 
            BigInteger.valueOf(Long.MAX_VALUE).add(BigInteger.ONE);

    BigInteger count = BigInteger.ZERO;
    for (double d : array) {
        long bitRepresentation = Double.doubleToRawLongBits(d);
        count = count.multiply(twoToTheSixtyFour);
        count = count.add(BigInteger.valueOf(bitRepresentation));
    }
    return count;
}

解释

每个double是一个64位的值，这意味着有2^64种不同的双精度浮点数值。由于long更容易处理此类问题，并且它具有相同数量的位，我们可以使用Double.doubleToRawLongBits(double)将双精度浮点数映射为长整型。

这很棒，因为现在我们可以像简单的组合问题一样处理它。你知道如何确定1234是一个独特的数字吗？没有其他具有相同值的数字。这是因为我们可以通过它的数字来分解它：

1234 = 1 * 10^3 + 2 * 10^2 + 3 * 10^1 + 4 * 10^0

十进制数的基本元素是10的幂，如果您了解线性代数的话。因此，十进制数就像由0到9（包括）的值组成的数组一样。

如果我们想要类似于双重数组的东西，我们可以讨论基数为2的64次方的计数系统。每个双精度浮点数值将是一个基数为2的64次方表示值的数字。如果有18个数字，则长度为18的double[]会有(2^64)^18个唯一值。

这个数字是巨大的，所以我们需要使用BigInteger数据结构来表示它，而不是原始数字。那个数字有多大呢？

(2^64)^18 = 61172327492847069472032393719205726809135813743440799050195397570919697796091958321786863938157971792315844506873509046544459008355036150650333616890210625686064472971480622053109783197015954399612052812141827922088117778074833698589048132156300022844899841969874763871624802603515651998113045708569927237462546233168834543264678118409417047146496

长度为18的double[]数组有这么多个唯一的配置，这段代码让您能够唯一地描述它们。

- Axoren

Answer 3

你可以使用双精度简单地对这些值进行求和，结果值大多数情况下是唯一的。另一方面，如果值的位置很重要，那么你可以使用索引作为乘数来进行求和。

代码可能会非常简单：

public static double sum(double[] values) {
    double val = 0.0;
    for (double d : values) {
        val += d;
    }
    return val;
}

public static double hash_w_order(double[] values) {
    double val = 0.0;
    for (int i = 0; i < values.length; i++) {
        val += values[i] * (i + 1);
    }
    return val;
}

public static void main(String[] args) {
    double[] myvals =
        { 0.07518284315321135, 0.002987851573676068, 0.002963866526639678, 0.002526139418225552, 0.07444872939213325, 0.0037219653347541617, 0.0036979802877177715, 0.0017920256571474585, 0.07499695903867931, 0.003477831820276616,
                0.003477831820276616, 0.002036159171625004, 0.07383539747505984, 0.004311312204791184, 0.0043352972518275745, 0.0011786937400740452, 0.07353130134299131, 0.004339580295941216 };

    System.out.println("Computed value based on sum: " + sum(myvals));
    System.out.println("Computed value based on values and its position: " + hash_w_order(myvals));
}

使用您提供的值列表，该代码的输出为：

Computed value based on sum: 0.41284176550504803
Computed value based on values and its position: 3.7396448842464496

- Roberto

---

求和函数不起作用，平均数也不行。但是将索引位置与值相乘的想法似乎很好。必须检查一下，这个想法对结果会产生什么影响，才能确定它是否非常有用。 - DarkHorse

Answer 4

我将提出三种方法，它们各有利弊，我将进行概述。

1. 哈希码 这是显而易见的“解决方案”，尽管已经正确指出它不会是唯一的。但是，任何两个数组具有相同值的可能性非常小。

2. 加权和 您的元素似乎是有界的；也许它们的范围从0到1。如果是这样，您可以将第一个数字乘以N^0，第二个数字乘以N^1，第三个数字乘以N^2等等，其中N是某个大数（理想情况下是您的精度的倒数）。这很容易实现，特别是如果您使用矩阵包，则速度非常快。我们可以选择使其唯一。

3. 离均差距 从每个数组中减去其平均值，平方结果，求和平方。如果您有预期的平均值，则可以使用该值。同样，不是唯一的，会有冲突，但您（几乎）无法避免。

唯一性的难点

已经解释过了，哈希不能提供唯一的解决方案。在理论上，使用加权和可以得到唯一的数字，但必须使用非常大的数字。假设你的数字在内存中是64位。这意味着它们可以表示2^64个可能的数字（使用浮点数会略少）。一个包含18个这样数字的数组可以表示2^(64*18)个不同的数字。这很庞大。如果你使用任何更小的数字，由于鸽巢原理，无法保证唯一性。

让我们看一个简单的例子。如果你有四个字母a、b、c和d，并且你必须使用1到3的数字分别对它们进行编号，你无法完成任务。这就是鸽巢原理。你有2^(18*64)个可能的数字。你不能用少于2^(18*64)个数字唯一地给它们编号，而哈希也做不到这一点。

如果您使用BigDecimal，您可以表示（几乎）任意大的数字。 如果您可以获得的最大元素为1，最小值为0，则可以设置N = 1 /（精度），并应用上述加权总和。 这将保证唯一性。 Java中双精度的精度为Double.MIN_VALUE。 请注意，权重数组需要存储在_BigDecimal_s中！

这满足了您问题的这一部分：

创建每个数组的计算值，该值基于其中的值是唯一的

但是，存在一个问题：

1和2对K均值来说很糟糕

我假设您根据与Marco 13的讨论，在单个值而不是长度18的数组上执行聚类。 正如Marco已经提到的那样，哈希对于K均值来说很糟糕。 整个想法是数据中最小的更改将导致哈希值的大更改。 这意味着两个相似的图像，产生两个非常相似的数组，产生两个非常不同的“唯一”数字。 相似性未得到保留。 结果将是伪随机的！

加权和是更好的选择，但仍然不够理想。它基本上会忽略除最后一个元素以外的所有元素，除非最后一个元素与之前的元素相同。只有在这种情况下，它才会查看倒数第二个元素，以此类推。相似性无法真正得到保留。

从平均值（或者至少某个点）的欧几里得距离能够以一种合理的方式将事物分组在一起。方向将被忽略，但是远离平均值的事物不会与靠近平均值的事物分组在一起。其中一个特征的相似性被保留，而其他特征则丢失。

总结

1 很容易实现，但不是唯一的，不能保持相似性。

2 容易实现，可以保持唯一性，不能保持相似性。

3 容易实现，但不是唯一的，保留了一些相似性。

加权和的实现。没有经过真正测试。

public class Array2UniqueID {

private final double min;
private final double max;
private final double prec;
private final int length;

/**
 * Used to provide a {@code BigInteger} that is unique to the given array.
 * <p>
 * This uses weighted sum to guarantee that two IDs match if and only if
 * every element of the array also matches. Similarity is not preserved.
 *
 * @param min smallest value an array element can possibly take
 * @param max largest value an array element can possibly take
 * @param prec smallest difference possible between two array elements
 * @param length length of each array
 */
public Array2UniqueID(double min, double max, double prec, int length) {
    this.min = min;
    this.max = max;
    this.prec = prec;
    this.length = length;
}

/**
 * A convenience constructor which assumes the array consists of doubles of
 * full range.
 * <p>
 * This will result in very large IDs being returned.
 *
 * @see Array2UniqueID#Array2UniqueID(double, double, double, int)
 * @param length
 */
public Array2UniqueID(int length) {
    this(-Double.MAX_VALUE, Double.MAX_VALUE, Double.MIN_VALUE, length);
}

public BigDecimal createUniqueID(double[] array) {
    // Validate the data
    if (array.length != length) {
        throw new IllegalArgumentException("Array length must be "
                + length + " but was " + array.length);
    }
    for (double d : array) {
        if (d < min || d > max) {
            throw new IllegalArgumentException("Each element of the array"
                    + " must be in the range [" + min + ", " + max + "]");
        }
    }

    double range = max - min;

    /* maxNums is the maximum number of numbers that could possibly exist
     * between max and min.
     * The ID will be in the range 0 to maxNums^length.
     * maxNums = range / prec + 1
     * Stored as a BigDecimal for convenience, but is an integer
     */
    BigDecimal maxNums = BigDecimal.valueOf(range)
            .divide(BigDecimal.valueOf(prec))
            .add(BigDecimal.ONE);
    // For convenience

    BigDecimal id = BigDecimal.valueOf(0);

    // 2^[ (el-1)*length + i ]
    for (int i = 0; i < array.length; i++) {
        BigDecimal num = BigDecimal.valueOf(array[i])
                .divide(BigDecimal.valueOf(prec))
                .multiply(maxNums).pow(i);

        id = id.add(num);
    }

    return id;

}

- timbo

---

这是一个相当不错的解释。谢谢你 ;) - DarkHorse

考虑到与平均值的欧几里得距离，如果我通过乘以值但是索引位置来计算平均值，那么它是否会保留相似性？我认为会的..对吗？ - DarkHorse

通过索引位置相乘可以得到类似加权和的结果。实际上，它是一种加权和（使用索引位置作为权重）。这并不保证唯一性，也不保留相似性，但它也不会完全破坏所有相似性。 - timbo

还有另一种选择，介于2和3之间的折衷方案，可以保留一些相似性并确保唯一性；使用交错。我会尝试编辑并可能添加一些代码来演示。 - timbo

好的，我会尝试这个。问题是我一直忙于工作，无法在程序上尝试所有建议。我有这个周末来尝试找到并接受一个答案。可惜赏金期对我来说不够长，一半的赏金被分配给了得到最多赞的答案。好的，我很快会接受一个正确的答案... :) 再次感谢您 :) - DarkHorse

Answer 5

据我所知，您打算基于双精度值进行k-聚类。

为什么不只是将双精度值包装在一个对象中，带有数组和位置标识符，这样您就可以知道它属于哪个聚类？

类似于：

 public class Element {
     final public double value;
     final public int array;
     final public int position;
     public Element(double value, int array, int position) {
         this.value = value;
         this.array = array;
         this.position = position;
     }
 }

如果您需要将数组作为整体进行聚类，

1. 您可以将长度为18的原始数组转换为长度为19的数组，其中最后或第一个元素是唯一的ID，在聚类期间将忽略该元素，但在聚类完成后可以引用它。这样可以使内存占用小 - 对于一个数组而言，额外的8个字节，并且与原始值的关联容易。
2. 如果空间绝对是问题，并且数组的所有值都小于1，则可以为每个数组添加大于等于1的唯一ID，并根据除以1的余数进行聚类，0.07518284315321135保持为第1个的0.07518284315321135，而0.07518284315321135变为第2个的1.07518284315321135，尽管这会增加聚类期间计算的复杂性。

- mavarazy

---

我想对数组中的双精度值执行k聚类，而不是对数组中的所有双精度值执行。这将为k聚类添加额外的对象创建，对于成千上万个数组来说不可行。 - DarkHorse

在数组的最前面添加一个具有唯一ID的额外元素，这个元素将被聚类忽略，这样只会增加一个额外的元素开销。 - mavarazy

你能在回答中详细阐述一下你的想法吗？ - DarkHorse

好的，你的回答更关注如何对数组进行聚类，而我的问题更关注如何为一个数组获取唯一的单个值，以便我可以在1D中执行k-means。正如@xlm所提到的，k-means适用于n空间，但我想让它在n-数组wid n值的单空间中工作。 - DarkHorse

如果你要基于单个唯一值进行聚类，那么这并没有太多意义，因为你的结果将取决于你选择生成此唯一值的函数，所以它们不能被依赖。如果你已经有一个将数组转换为单个值的函数，那么你已经拥有了唯一标识符。 - mavarazy

是的，目前我没有这样的功能，因此我需要想法。我将测试其效率。如果不行，那么我只能转向D空间... - DarkHorse

Answer 6

首先，让我们尝试理解您在数学上的需求：

将一个包含m个实数的数组唯一映射到一个数字，实际上是R^m和R之间的双射，或者至少是N。

由于浮点数实际上是有理数，因此您的问题是要找到Q^m和N之间的双射，可以将其转换为N^n到N，因为您知道您的值始终大于0（只需将您的值乘以精度即可）。

因此，您需要将N^m映射到N。查看Cantor配对函数以获取一些想法。

- aviggiano

Answer 7

一个保证基于数组生成唯一结果的方法是将其转换为一个大字符串，并将其用作计算值。

• 它可能会慢一些，但它将基于数组的值是唯一的。

实现示例： 将ArrayList转换为字符串的最佳方法

- Matt Woelk