LAE

Note: This was originally posted by an inactive account. Content was preserved by moving under an admin account.

Originally posted by: dvs79

I have a set of records (each with a unic ID). By some method I defined which records make pairs with each other.

So now I have a reference table, containing all existing pairs (the table consists of 2 fields - ID1 and ID2). Each pair of IDs occurs once ("ID1=x, ID2=y" where x<y ) and also there're "degenerate pairs" like "ID1=x, ID2=x".

How can I assign a cluster ID for each record in the initial table using the reference table? Cluster ID must be the same for the records which linked according to the ref. table. Moreover, cluster ID must be the same also for the records which don't have direct link between themselves, but are linked via one or more other records (e. g. rec.1<->rec.2, rec.2<->rec.3, *then rec.1<->rec.3 and so for all three records cluster ID must be same).
In attachment the example graph (data, reftable and expected result).

Thanks in advance!
Attachments:
clusterization.brg

Note: This was originally posted by an inactive account. Content was preserved by moving under an admin account.

Originally posted by: dvs79

I've got an idea to use "Reduce To List" node, getting in this way for each id1 a string , containing all its "neighbouring" id2's (like "*1*5*88*153*" etc). Then I could Join this table with itself, using as JoinExpression the condition that these strings must have at least one common element (numbers between asterisks). And then to repeat it iteratively (by the way - is it possible in LAE to make loops in the graph? ) until there'll be no joining records, thus enlargening clusters.

The question that I don't know answer yet - how to make this Join using such a fuzzy comparing of two strings? I can write a BRAINscript code, consecutively extracting numbers from one string (in a loop) and searching them in the other string. But I can't make out how to use this code in the "JoinExpr"-field of Join-node.
Please, have a look at the example in attachment.
Attachments:
clusterization_ex2.brg

Note: This was originally posted by an inactive account. Content was preserved by moving under an admin account.

Originally posted by: dvs79

Well, I continue to talk to myself I thought better of how to realize the generic clusterization algorithm (frequent task in data mining).

Maybe it'll be useful for somebody.

So:

I have 2 tables:
a) list of items (with unic IDs);
b) "matrix of connectivity", consisting of 2 fields "id1" and "id2", where each record represents a pair of connected items (i.e. items, belonging to the same cluster).

The task is to assign a cluster_ID (CL_ID) to every item, so that connected items (from matrix of connectivity) would have common CL_ID.

To do so, I do as follows:


1. Execute BRX Node consecutively takes each pair of IDs from the connectivity matrix and give them to the main graph (brx).


2. In the main graph the iterative algorithm is realized:

2.1 There's generated a list of items with field "CL_ID" added (initially it's filled with "0"s). This field is being filled consecutively with each iteration.

2.2 Each pair of IDs is checked against this table and there're 4 possible situations:

a) The both items has already CL_ID values assigned and these CL_IDs are equal.

Do nothing.


b) The both items has already CL_ID values assigned and these CL_IDs are different.

Then the greater CL_ID is "absorbed" by the smaller (or vice versa, doesn't matter), i.e. two clusters are merged


c) One item has already CL_ID, but the other hasn't.

Assign to the latter the CL_ID of the former.


d) The both items have no CL_ID.

Assign them both the new CL_ID, greater by 1 than the current maximum CL_ID.


The main flaw of this solution - it's sooo slow I'd be happy to get advice how to optimize it.

The graphs are in attachment.
Attachments:
clusterization_brx.zip

Note: This was originally posted by an inactive account. Content was preserved by moving under an admin account.

Originally posted by: Tim Meagher

Hey,

Sorry for delays in replying to this - wasn't something I knew the answer to off the top of my head & took a while to actually understand the problem.

In any case, I've attached a solution which I think does what you want - it certainly produces the correct results on the samples you posted.

If I'm right, then this can all be done in an Agg node ("Find Clusters") without resorting to complicated fuzzy matching lookups, Execute BRX subgraphs, or any sort of looping outside of the node. It can all be handled within BRAINscript.

Basically, the Agg node is defined with a constant GroupBy parameter, meaning that there will be 1 group.
Within the agg, a list of clusters is maintained.
Each cluster is itself a list which defines the member ids that belong to that cluster.
Any time a new record is processed, the node checks all of the existing clusters to see if either of the ids exist as a member id in any of the clusters - if this happens, then the first-found cluster is updated to contain the new ids (ensuring no duplicates).
If the ids appear across multiple clusters, then all of the clusters which weren't found first have their ids merged into the first-found cluster.
The clusters that who's members were merged are then removed from the cluster list.

The node then uses a "do output" statement to loop through the clusters and output a new record for each ClusterId, MemberId pair.

A simple lookup node can then be used to search for the input ID on the left hand side against the member id on the right hand side. When a match is found, then the ID & description from the left are taken, along with the Cluster Id from the right.

See attached graph.

Tim.
Attachments:
clusterization_ex2.brg

Note: This was originally posted by an inactive account. Content was preserved by moving under an admin account.

Originally posted by: dvs79

Tim, thank you very much! That's exactly what I wanted.

I tried to use list initially, but didn't guessed to use it inside aggregation in 1 group (and so list didn't keep its content when the script passed to the next record in the input table).

Thanks again!

--
PS Or, on afterthought, the case is that I didn't know how to use "do output". A lot of space for self-development

Note: This was originally posted by an inactive account. Content was preserved by moving under an admin account.

Originally posted by: rboccuzzi

Just to make things more confusing, possibly...I have another example. I just wanted to show the similarities between this problem, and the one about duplicate testing. So I took that example, and adapted it for this problem.

It has the benefit of running reasonably quickly, and not having a lot of BRAINscript. It is limited in that the number of transitive connections, however, so it may not work for your full data. I have coded it to find 3, and it returns the same result as the previous examples (with different actual clusterIds, but grouped correctly). If you knew the maximum number of transitive steps, this mechanism could work...if not, this unfortunately won't, but might provide insight as another way to solve a problem, for future reference.

Cheers
Rich
Attachments:
Clusterization_ex3.brg

Note: This was originally posted by an inactive account. Content was preserved by moving under an admin account.

Originally posted by: dvs79

Rich, thanks.

Yours and Tim's examples helped a lot to understand how BRAINscript works.

Note: This was originally posted by an inactive account. Content was preserved by moving under an admin account.

Originally posted by: kursattaskin

Hello everyone
I have tested this example with small data its if fine but for big one, it does not give result in 5 days, on 1.3 million records. However, my question is a bit different than this application. Assume we have two different fields and we want to find the groups or clusters of them. the only criteria is we will get them in same group if there is at least one relation

the input is as following
KID MID
K1 M1
K2 M2
K3 M1
K1 M4
K4 M4
K4 M8
K2 M3
K5 M7
K6 M3
K5 M9

so the result should be like that (GID is the group ID)

GID KID MID
G1 K1,K3,K4 M1,M4,M8
G2 K2,K6 M2,M3
G3 K5 M7,M9

any idea on this how to make?

Kind Regards,

Note: This was originally posted by an inactive account. Content was preserved by moving under an admin account.

Originally posted by: rboccuzzi

Greetings kursattaskin, I have attached a potential solution for you here. I am sure there are other ways, but this seems to do what you are looking for. I suspect there is an R algorithm that could do this as well, but as I am not familiar with that, I chose to do it purely in the LAE.

Cheers
Rich
Attachments:
Clusterization Question.brg

Note: This was originally posted by an inactive account. Content was preserved by moving under an admin account.

Originally posted by: rboccuzzi

I also wanted to mention, but forgot in my previous post, that I think what you are asking is similar to another thread here, discussing a similar clustering. It clearly isn't the same, but if you look at that solution and discussion, it might be of interest as well.

Cheers
Rich