《大数据分析与处理》课程资料 (5).pptxVIP

ClusteringNote to other teachers and users of these slides: We would be delighted if you found this our material useful in giving your own lectures. Feel free to use these slides verbatim, or to modify them to fit your own needs. If you make use of a significant portion of these slides in your own lecture, please include this message, or a link to our web site: High Dimensional DataHigh dim. dataLocality sensitive hashingClusteringDimensionality reductionGraph dataPageRank, SimRankCommunity DetectionSpam DetectionInfinite dataFiltering data streamsWeb advertisingQueries on streamsMachine learningSVMDecision TreesPerceptron, kNNAppsRecommender systemsAssociation RulesDuplicate document detection2 High Dimensional DataGiven a cloud of data points we want to understand its structure3 4The Problem of ClusteringGiven a set of points, with a notion of distance between points, group the points into some number of clusters, so that Members of a cluster are close/similar to each otherMembers of different clusters are dissimilarUsually: Points are in a high-dimensional spaceSimilarity is defined using a distance measureEuclidean, Cosine, Jaccard, edit distance, … 5Example: Clusters Outliersx xx x x xx x x x x x xx xxxx xx x x x x xx x xx x xx x x x x x xx xxx xx x x xx x x x x x xx xxxx xx x x x x xx x xx x xx x x x x x xx OutlierCluster Clustering is a hard problem!6 7Why is it hard?Clustering in two dimensions looks easyClustering small amounts of data looks easyAnd in most cases, looks are not deceivingMany applications involve not 2, but 10 or 10,000 dimensionsHigh-dimensional spaces look different: Almost all pairs of points are at about the same distance Clustering Problem: GalaxiesA catalog of 2 billion “sky objects” represents objects by their radiation in 7 dimensions (frequency bands)Problem: Cluster into similar objects, e.g