looking for an algorithm for classification clusters and sizes of them - Programmers Heaven

#### Howdy, Stranger!

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

#### Categories

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

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.

Sudipta

• 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