[SOUND] In this session, we will give a general introduction on External Measures for Clustering Validation. We know clustering is unsupervised. In this sense, we really want to use some good judgement. External methods is to give some expert knowledge or some prior truths. So to that extent, we call these as ground truth T. So given ground truth T, then we want to measure the quality of clustering C, we use the quality measure Q(C, T). The function Q(CT) is good if it satisfies the following four essential criteria. The first one called cluster homogeneity. That means we want the cluster formed to be pure. That means they're in the same cluster. So, the purer the better, of course. The second one, called clustering completeness. That means we want to assign objects belonging to the same category in the ground truth to the same cluster. That means you may get all these object are a category a, but you assign them to two, to three clusters. That's no good. We want to be complete. The third on is rag bag better than alien. Simply says, you may have some heterogeneous object. 'Kay. If you put them into a pure cluster, you mix the other category up. That's no good. You want to penalize this. It's better even to put them into a rag bag. Rag bag means it's in the miscellaneous or other category. It's better than you mix up with some pure cluster. Then the fourth measure of course, small cluster preservation, simply says, if you got a pretty small cluster already, you do want to further split them into pieces because those pieces likely represent noises. In that case, you better split a larger category into smaller pieces. The reason is, the larger category likely, they may belong to different clusters, or different other smaller categories. That's small cluster preservation. Then, we will see what we are going to examine on those external measures. We often use this graph, this color graph. Those brown points, this dark brown points, suppose they are ground truth partitioning T1. That means expert label those points as T1, okay. Then the ground truth, the other ground truth may be they labeled as blue one. That means T2 dark blue one, actually is another category. 'Kay. That means for ground truth, for expert, they know that different colors belong to different truths. 'Kay. However your clustering algorithm may generate things circled by the light brown one or orange one, or the red one. That means they are not ideal, they may not be good enough for the matching what expert judgement. So, we want to measure whether your clustering method is good. 'Kay. So, the measure one we call matching-based measure. We, we have sev, several measures, like purity, maximum matching, or F-measure. Another kind of measure called entropy-based measures. There are conditional entropy, normalized mutual information, NMI, or variation of information. The certain kind of measures called pairwise measures. For example, we may have four possibilities, true positive, false negative. False positive, true negative. Okay. Then, we actually have Jaccard coefficient, Rand statistic, Fowlkes-Mallow measure. The fourth category called correlation measures. Essentially, they are discretized Huber static and normalized discretized Huber static. And those marked as to be covered. We will discuss them in more detail in the subsequent sessions. [MUSIC]
