阵列的唯一计算值

Question

我一直在想它,但已经没有想法了.我有10个长度为18的数组,其中包含18个双精度值.这18个值是图像的特征.现在我必须在它们上应用k-means聚类.

为了实现k均值聚类,我需要为每个数组提供唯一的计算值.是否有任何数学或统计或任何逻辑可以帮助我为每个数组创建计算值,这是基于其中的值所独有的.提前致谢.

这是我的数组示例.还有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]

Answer 1

我将建议三种方法，并概述其不同的优缺点。

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。请注意，权重数组需要存储在 _Big Decimal_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;

}