Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Sign In with Facebook Sign In with Google Sign In with OpenID

Categories

We have migrated to a new platform! Please note that you will need to reset your password to log in (your credentials are still in-tact though). Please contact lee@programmersheaven.com if you have questions.
Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

looking for an algorithm for classification clusters and sizes of them

udeludel Posts: 1Member
Hi All,

I am looking for an algorithm/program that separates all of the data chunk i,e how many chunks are there. Moreover, that program will also be giving information of the size of the chunks and which are the elements. I am explained my problem by this following example

suppose I have three chunk of data points and one isolated point. each chunk of data are related by some rule.

chunk1: 1,2,8,9,11,12; connectivity: 1-2, 2-12,2-11,8-9,8-11
chunk2: 4,7,10; connectivity: 4-7,7-10,4-10
chunk3: 5,6; connectivity 5-6
chunk4: 3

Therefore, the total no of data points in this system are 12 and the dimension of connectivity matrix will be 12X12. I have set 1 if the two elements are connected in this matrix and the rest of the elements are 0. Moreover, the diagonal elements of this matrix was st to 0 because connection within the same element is meaningless. Therefore, the matrix, h(i,j), looks like

0 1 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 1 0 1 0
0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 1 0 0 1 0 0 0 0 0
0 1 0 0 0 0 0 1 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0

Now, my question is, how do I find the the number of chunks and which elements constitute those chunks for a given matrix.

Can anyone help me in this regard? any logic or any idea will be helpful for me.

Thanks in advance
Sudipta

Comments

  • nitays974nitays974 Posts: 4Member
    Hi,

    Let me try using the following pseudo-code:
    [code]
    chunks=[][] = {0}
    chunks_counter[12] = {0}
    index_in_chunk[12] = {-1}
    number_of_chunks = 0

    for each row
    for element = 1 to row // [Use only lower matrix triangle]
    if matrix[row][element] == 1 then
    if index_in_chunk[row] == 0 then
    if index_in_chunk[element] == 0 //[new chunk]
    chunk_index = number_of_chunks
    index_in_chunk[row] = chunk_index
    chunks[chunk_index][chunks_counter[chunk_index]] = row
    chunks_counter[chunk_index] = chunks_counter[chunk_index] + 1
    number_of_chunks = number_of_chunks + 1
    else // The element was already clusterred
    chunk_index = index_in_chunk[element]
    index_in_chunk[row] = chunk_index
    chunks[chunk_index][chunks_counter[chunk_index]] = row
    chunks_counter[chunk_index] = chunks_counter[chunk_index] + 1
    number_of_chunks = number_of_chunks + 1
    end if
    else // [row index already in a chunk
    chunk_index = index_in_chunk[row]
    end if

    // check the rest of the element in the row
    if index_in_chunk[element] == 0 //[element not clusterred yet]
    index_in_chunk[element] = chunk_index
    chunks[chunk_index][chunks_counter[chunk_index]] = element
    chunks_counter[chunk_index] = chunks_counter[chunk_index] + 1
    end if
    end if
    next element

    if index_in_chunk[row] = -1 // row index is not in clusterred : single element chunk
    chunk_index = number_of_chunks
    index_in_chunk[row] = chunk_index
    chunks[chunk_index][0] = row
    chunks_counter[chunk_index] = 1
    number_of_chunks = number_of_chunks + 1
    end if
    next row
    [/code]

    The result data structure "chunks" will give you the expectet clusterring
Sign In or Register to comment.