1
$\begingroup$

I'm unsure in designing a test case for a clustering method of bitsets.

At the moment I define some centroids C like

C_ref = { 11110000
        , 00001111 }

with equal Hamming-distance (c_i ^ c_j = 4) to each other.

Now I create bitsets b like

B_ref = { 11010000
        , 11110010
        , 00001110
        , 00011111
        , ...      }

Every b has a distance (b_i ^ c_n > 4) to each centroid except to exactly one centroid c_b. The centroid cb and its corresponding b have a shorter distance (b_i ^ c_b < 4).

Maybe it's better explained in short with matrices

Distance|c_ref_0 c_ref_1
--------+---------------
c_ref_0 |      0       4
c_ref_1 |      4       0

Distance|c_ref_0 c_ref_1
--------+---------------
b_ref_0 |      1       7
b_ref_1 |      1       5
b_ref_2 |      7       1
b_ref_3 |      7       1

So my working steps are

create centroids C_ref as reference
create bitsets B_ref (with help of C_ref) as reference
find centroids C_res (with help of B_ref) as result

I check the distances of C_ref and C_res with

bitset-length 256 bit
8 centroids with distance 64 to each other
1000 descriptors with distance < 16 or distance > 64


Distance  | Centroids Ref 0 to 8
----------+-----------------------
Centroids | 0 64 64 64 64 64 64 64 
Ref       | 64 0 64 64 64 64 64 64 
0 to 8    | 64 64 0 64 64 64 64 64 
          | 64 64 64 0 64 64 64 64 
          | 64 64 64 64 0 64 64 64 
          | 64 64 64 64 64 0 64 64 
          | 64 64 64 64 64 64 0 64 
          | 64 64 64 64 64 64 64 0

Centroids | 32 68 34 36 39 32 32  4 
Res       | 32 68 34 36 39 32 32 68 
0 to 8    | 32 68 34 36 39 32 32 68 
          | 32 68 34 36 39 32 32 68 
          | 32 68 34 36 39 32 32 68 
          | 32 68 34 36 39 32 32 68 
          | 32  4 34 36 39 32 32 68 
          | 32 60 30 28 25 32 32 60

Looks not good. Nevertheless, what are your suggestions to test binary clustering?

Update 1

Above I've tried (in a glumsy way) to ask how to test a clustering method of bit-vectors. Binary vectors are clustered with Hamming distance as distance-function into 8 or 10 clusters. The resulting centroids should be verified.

My approach is to create artificial centroids (like C_ref above) and produce artificial binary vectors (like B_ref above). Both sets are not random.

The clustering takes B_ref as input and produces C_res as output.

The last step is the distance matrix C_ref X C_res. A perfect result would be (in my eyes) C_ref X C_ref == C_ref X C_res.

$\endgroup$

closed as unclear what you're asking by ttnphns, Peter Flom Jun 26 '17 at 12:08

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ There is some unclear points in your question and terminology. What is "binary clustering"? - binary data or clustering to two clusters? What is the use of centroids for binary (categorical) data? Expressions like b_i ^ c_n > 4 are unclear, notation not explained. $\endgroup$ – ttnphns Jun 26 '17 at 8:19
  • $\begingroup$ I use binary vectors with 256 bit each. In total some billions of vectors. I try to cluster these binary vectors into 8 or 10 cluster. As so, I try to find 8 to 10 centroids. I have adapted link. b_i ^ c_n > 4 means Hamming-distance greater 4. $\endgroup$ – user1587451 Jun 26 '17 at 13:13
2
$\begingroup$

If you predefine the centroids, this isnot clustering, but nearest neighbor classification.

You can use any classification evaluation such as precision and recall.

$\endgroup$
  • $\begingroup$ I predefine centroids just for testing purposes. So to check if my implementation is approximating against the artificial centroids. $\endgroup$ – user1587451 Jun 26 '17 at 13:15

Not the answer you're looking for? Browse other questions tagged or ask your own question.