[SOLVED] CSI 2120 page 12 __________________________________________________________

CSI 2120 page 12 _________________________________________________________________________________________________
2. (Prolog) [8 points][8% de votre note finale]
In this part of the comprehensive assignment, we will focus on the third step of the parallel DBSCAN algorithm introduced in the previous concurrent assignment. We will merge intersecting clusters from adjacent partitions.
The parallel DBSCAN algorithm extracts the clusters of a set by subdividing the region into a number of overlapping partitions. The fact that these partitions overlap with each other implies that some points (at the periphery of the partitions) might belong to more than one partition. Consequently, some clusters may contain the same point(s) and are then said to intersect. In this case, these clusters must be merged because they should in fact constitute one large cluster covering more than one partition. The merging can be simply done by changing the label of one of the clusters to the one of the second.

Copyright By Assignmentchef assignmentchef

We will solve this problem by using a simple but not very efficient algorithm. We will apply it on a subset of the data generated in the previous step.
Pour cette partie du projet intgrateur, nous nous concentrerons sur la troisime tape de lalgorithme DBSCAN parallle, introduite dans la partie concurrente du projet. Nous allons donc fusionner les groupes provenant de partitions adjacentes.
Lalgorithme parallle du DBSCAN extrait les groupes dun ensemble de points en subdivisant la rgion en un certain nombre de partitions qui se chevauchent. Le fait que ces partitions se superposent implique que certains points ( la priphrie des partitions) peuvent appartenir plus dune partition. Consquemment, certains groupes peuvent avoir des points en commun, cest–dire quils sintersectent. Lorsque cela se produit, ces groupes doivent tre fusionns car ils constituent, dans les faits, un seul grand groupe stendant sur plus dune partition. Cette fusion se fait simplement en changeant ltiquette dun groupe pour ltiquette du groupe avec lequel il se fusionne.
Nous vous demandons de rsoudre ce problme en utilisant un algorithme simple mais pas trs efficace. Vous appliquerez cet algorithme un sous-ensemble des donnes obtenues ltape prcdente.

CSI 2120 page 13 _________________________________________________________________________________________________
Algorithme
The input to the algorithm is a knowledge base describing the current clustering over the partitions. It is made of facts using the partition predicate:
partition(PARTITION_ID, POINT_ID, X, Y, CLUSTER_ID).
From this predicate, we want to verify if clusters in one partition intersect with clusters of adjacent partitions. This is accomplished by the simplified algorithm shown on the next page. The output will be a final list of (merged) clusters in the form:
[[POINT_ID, X,Y,CLUSTER_ID], ]
Lentre de cet algorithme sera une base de faits dcrivant les groupes obtenus travers les diffrentes partitions. Cette base est constitue de faits dcrits laide du prdicat suivant :
partition(PARTITION_ID, POINT_ID, X, Y, CLUSTER_ID).
A partir de ce prdicat, nous voulons vrifier si les groupes dune partition intersectent avec les groupes des partitions adjacentes. Ceci est ralis partir de lalgorithme prsent ci-dessous. La sortie de cet algorithme sera une liste de groupes (fusionns) reprsente ainsi :
[[POINT_ID, X,Y,CLUSTER_ID], ]
ClusterList := 0 // list of clusters to be produced for each partition P in knowledge base {
for each cluster C in P { for each cluster C in P {
I := C ClusterList // List of points in ClusterList intersecting with points in C for each label L in I {
change label L in ClusterList to Label(C)
ClusterList := C ClusterList }

CSI 2120 page 14 _________________________________________________________________________________________________
As an example, consider the figure below.
Illustrons le fonctionnement de cet algorithme avec la figure suivante.
Suppose we have the 5 points of cluster A and the 8 points of cluster C in current ClusterList. We are now processing the partition containing clusters B and D. We first consider cluster D; it has no intersection with the points in ClusterList so its 4 points will simply be inserted to the list. Now if we consider cluster B, it has 3 points intersecting with cluster A and 4 points intersecting with cluster C. These 7 points will constitute the intersection set I and the labels of I are A and C. Consequently, the cluster label of all points in ClusterList having label A will be changed to B and same for the points having label C. Finally, the points in B are inserted into the ClusterList.
Note that the proposed algorithm does not check if partitions are adjacent before computing cluster intersection. This is not efficient since clusters in non-adjacent partitions cannot have intersection but for simplicity, we will accept these useless computations and proceed as proposed in the algorithm. One could also initialize the ClusterList with all clusters from one first partition instead of starting with an empty list but again efficient is not a concern here. Note that for computing the intersection, use the POINT_ID to compare the points and not their X,Y coordinates.
Supposons que nous avons les 5 points du groupe A et les 8 points du groupe C dans la liste courante ClusterList. Nous sommes traiter la partition contenant les groupes B et D. Considrons dabord le groupe D, celui-ci na pas dintersection avec les points de ClusterList, alors ses 4 points sont simplement insrs dans cette liste. Maintenant si nous considrons le groupe B, celui-ci a 3 points en intersection avec le groupe A et 4 points en intersection avec le groupe C. Ces 7 points forment lensemble dintersection I et les tiquette de I sont A et C. Il sensuit donc que tous les points dans ClusterList ayant ltiquette A et C seront changs en B. Finalement les points restants de B sont insrs dans ClusterList.

CSI 2120 page 15 _________________________________________________________________________________________________
Notons que cet algorithme ne vrifie si les partitions sont adjacentes avant de calculer les intersections. Ceci nest pas trs efficace car nous savons que les groupes provenant de partitions non-adjacentes ne peuvent pas avoir dintersection. Toutefois, afin de simplifier notre problme, nous allons procder ainsi et accepter ces quelques inefficacits. Il serait aussi possible dinitialiser la ClusterList avec tous les groupes provenant dune partition initiale (au lieu de lensemble vide) mais encore, notre souci nest pas lefficacit. Notons enfin que pour le calcul des intersections, il est prfrable dutiliser le POINT_ID afin de comparer les points et non leur coordonne X,Y.
Programmation
We provide you with the clustering results of 7 partitions described in 7 csv files.
You first run the provided helper predicate import that creates the knowledge base using the predicate partition. Just make sure the csv files are in the working directory of your Prolog console. From this knowledge base write Prolog predicates that will implements the cluster merging algorithm.
Your solution must include a helper predicate called mergeClusters and that produces the list of all points with their cluster ID.
Nous vous donnons les groupes provenant de 7 partitions et dcrits dans 7 fichiers csv.
Vous devez dabord lancer le prdicat assistant import qui va crer la base de faits des partitions. Veuillez simplement vous assurer que les fichiers se trouve dans votre rpertoire de travail Prolog. A partir de cette base de faits, crire les prdicats Prolog qui raliseront lalgorithme de fusion des groupes.
Votre solution doit inclure un prdicat appel mergeClusters et qui produit la liste de tous les points avec leur tiquette de groupe.
?- import.
partition(65, 1345, 40.750304, -73.952031, 65000001).
partition(65, 6017, 40.760146, -73.957873, 65000002).
partition(65, 17457, 40.760213, -73.955471, 65000003).
partition(65, 18582, 40.750299, -73.952027, 65000001).
partition(65, 20050, 40.750365, -73.952127, 65000001).
partition(65, 25351, 40.760153, -73.955467, 65000003).
partition(65, 34767, 40.758621, -73.957704, 65000004).
partition(65, 36487, 40.758621, -73.957704, 65000004).
?- mergeClusters(L),open(clusters.txt,write,F),write(F,L),close(F). L=[

CSI 2120 page 16 _________________________________________________________________________________________________
Finally, for each predicate include a test predicate that demonstrates the results obtained using it. You must also adequately comment each of your predicates. See example below.
Finalement, pour chaque prdicat inclure un prdicat test dmontrant les rsultats obtenus en lutilisant. Vous devez aussi commenter adquatement chacun de vos prdicats. Par exemple :
% relabel/4
% relabels the points of cluster O with label R % relabel(O,R,clusterListIn, clusterListOut) relabel(
?- test(relabel).
relabel(33, 77, [[1,2.2,3.1,33], [2,2.1,3.1,22], [3,2.5,3.1,33], [4,2.1,4.1,33], [5,4.1,3.1,30]],Result) [[1,2.2,3.1,77],[2,2.1,3.1,22],[3,2.5,3.1,77],[4,2.1,4.1,77],[5,4.1,3.1,30]]
Where the definition of test(relabel) is as follows: Avec la dfinition suivante:
test(relabel) :- write(relabel(33, 77,
[[1,2.2,3.1,33], [2,2.1,3.1,22], [3,2.5,3.1,33], [4,2.1,4.1,33],[5,4.1,3.1,30]],Result)),nl,
relabel(33, 77,
[[1,2.2,3.1,33], [2,2.1,3.1,22], [3,2.5,3.1,33], [4,2.1,4.1,33], [5,4.1,3.1,30]],Result),
write(Result).
Hint: Since the main loops are across all partitions and all clusters, it is also possible to work from a
global list of clusters, removing the partition information. This list can be obtained as below.
Indice: Puisque la boucle principale se fait travers toutes les partitions et tous les groupes, il est aussi possible de fonctionner partir dune liste globale de groupes (retirant linformation sur les partitions). Cette liste globale sobtient ainsi :
?- findall([D,X,Y,C],partition(_,D,X,Y,C),L).
L = [[1345, 40.750304, -73.952031, 65000001], [6017, 40.760146, -73.957873, 65000002], [17457, 40.760213, -73.955471, 65000003], [18582, 40.750299, -73.952027, 65000001], [20050, 40.750365, -73.952127, 65000001], [25351, 40.760153, 73.955467|], [34767, 40.758621|], [36487|], [|]|].

CS: assignmentchef QQ: 1823890830 Email: [email protected]