DBSeminarSeriesHARPAHierarchicalAlgorithmwithAutomatic.pptVIP

* Our Approach: HARP More details: mutual disagreement Mutual disagreement prevention: Setup the md threshold to limit the maximum disagreement on the new set of attributes Get the statistics of the loss of information in all possible merges, discard those with extraordinary high loss Add a punishment factor to the similarity score * Our Approach: HARP.1 HARP.1: an implementation of HARP that defines the relevance of an attribute to a cluster by its density improvement from the global density Relevance score of an attribute to a cluster: Categorical: 1 – (1 – Mode-ratiolocal) / (1 – Mode-ratioglobal) Numeric: 1 – Varlocal / Varglobal *When Mode-ratioglobal = 1 or Varglobal = 0, the score = 0 If C1 and C2 merge into Cnew, we can use the records of C1 and C2 to evaluate their “agreement” on the selected attributes of Cnew in a similar way. * Our Approach: HARP.1 Mutual disagreement calculations: Den(Ci, a): how good is attribute a in Ci Den(Ci, Cnew, a): how good is the attribute a in Ci, evaluated by using the properties of a in Cnew Both values are in the range [0, 1] * Our Approach: HARP.1 Similarity score: * mapc dt md Threshold loosening 1 g mmd d 1 imd Our Approach: HARP.1 Multi-step clustering: Initial thresholds Cluster 1 Cluster2 Merge Score 2 6 27.6 3 8 24.3 12 13 24.1 1 5 18.5 … Merge score calculations Perform all possible merges 1 g mmd Baseline value for each dt variable: the global statistical value Initial and baseline values for the md variable: user parameters, default 10 and 50 With mutual disagreement prevention: MD(C1,C2) = md Sum of and difference between ILoss(C1,Cnew) and ILoss(C2,Cnew) not more than a certain s.d. from mean Punishment factor in similarity score Each cluster keeps a local score list (binary tree) containing merges with all other clusters. The best scores are propagated to a global score list mapc dt md d 1 imd * Our Approach: HARP.1 Time complexity: Speeding up: use a fast projected clustering algorithm to pre-cluster t