CluStream流数据聚类 java 代码和jar包_聚类_java_其他

<html xmlns="http://www.w3.org/1999/xhtml"> <head> <meta charset="utf-8"> <meta name="generator" content="pdf2htmlEX"> <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1"> <link rel="stylesheet" href="https://static.pudn.com/base/css/base.min.css"> <link rel="stylesheet" href="https://static.pudn.com/base/css/fancy.min.css"> <link rel="stylesheet" href="https://static.pudn.com/prod/directory_preview_static/6268425c4c65f41259806be7/raw.css"> <script src="https://static.pudn.com/base/js/compatibility.min.js"></script> <script src="https://static.pudn.com/base/js/pdf2htmlEX.min.js"></script> <script> try{ pdf2htmlEX.defaultViewer = new pdf2htmlEX.Viewer({}); }catch(e){} </script> <title></title> </head> <body> <div id="sidebar" style="display: none"> <div id="outline"> </div> </div> <div id="pf1" class="pf w0 h0" data-page-no="1"><div class="pc pc1 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://static.pudn.com/prod/directory_preview_static/6268425c4c65f41259806be7/bg1.jpg"><div class="t m0 x1 h2 y1 ff1 fs0 fc0 sc0 ls0 ws0">Streaming-Data Algorithms For High-Quality Clustering</div><div class="t m0 x2 h2 y2 ff2 fs0 fc0 sc0 ls0 ws0">Liadan O'Callaghan</div><div class="t m0 x3 h2 y3 ff3 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 x4 h2 y2 ff2 fs0 fc0 sc0 ls0 ws0">Nina Mishra Adam Meyerson Sudipto Guha</div><div class="t m0 x5 h2 y4 ff2 fs0 fc0 sc0 ls0 ws0">Ra jeev Motwani</div><div class="t m0 x6 h2 y5 ff2 fs0 fc0 sc0 ls0 ws0">October 22, 2001</div><div class="t m0 x7 h2 y6 ff4 fs0 fc0 sc0 ls0 ws0">Abstract</div><div class="t m0 x8 h2 y7 ff5 fs0 fc0 sc0 ls0 ws0">As data gathering grows easier, and as researchers discover new ways to interpret data, streaming-</div><div class="t m0 x9 h2 y8 ff5 fs0 fc0 sc0 ls0 ws0">data algorithms have b ecome essential in many elds. Data stream computation precludes algo-</div><div class="t m0 x9 h2 y9 ff5 fs0 fc0 sc0 ls0 ws0">rithms that require random access or large memory. In this paper, we consider the problem of</div><div class="t m0 x9 h2 ya ff5 fs0 fc0 sc0 ls0 ws0">clustering data streams, which is imp ortant in the analysis a variety of sources of data streams,</div><div class="t m0 x9 h2 yb ff5 fs0 fc0 sc0 ls0 ws0">such as routing data, telephone records, web documents, and clickstreams. We provide a new clus-</div><div class="t m0 x9 h2 yc ff5 fs0 fc0 sc0 ls0 ws0">tering algorithms with theoretical guarantees on its performance. We give empirical evidence of</div><div class="t m0 x9 h2 yd ff5 fs0 fc0 sc0 ls0 ws0">its sup eriority over the commonly-used</div><div class="t m0 xa h2 yd ff6 fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 xb h2 yd ff5 fs0 fc0 sc0 ls0 ws0">{Means algorithm. We then adapt our algorithm to b e</div><div class="t m0 x9 h2 ye ff5 fs0 fc0 sc0 ls0 ws0">able to operate on data streams and exp erimentally demonstrate its superior performance in this</div><div class="t m0 x9 h2 yf ff5 fs0 fc0 sc0 ls0 ws0">context.</div><div class="t m0 xc h2 y10 ff7 fs0 fc0 sc0 ls0 ws0">1 Intro duction</div><div class="t m0 xc h2 y11 ff8 fs0 fc0 sc0 ls0 ws0">For many recent applications, the concept of a</div><div class="t m0 xd h2 y11 ff9 fs0 fc0 sc0 ls0 ws0">data stream</div><div class="t m0 xe h2 y11 ff8 fs0 fc0 sc0 ls0 ws0">is more appropriate than a data set. By</div><div class="t m0 xc h2 y12 ff8 fs0 fc0 sc0 ls0 ws0">nature, a stored data set is an appropriate mo del when signicant p ortions of the data are queried</div><div class="t m0 xc h2 y13 ff8 fs0 fc0 sc0 ls0 ws0">again and again, and up dates are small and/or relatively infrequent. In contrast, a data stream is an</div><div class="t m0 xc h2 y14 ff8 fs0 fc0 sc0 ls0 ws0">appropriate mo del when a large volume of data is arriving continuously and it is either unnecessary or</div><div class="t m0 xc h2 y15 ff8 fs0 fc0 sc0 ls0 ws0">impractical to store the data in some form of memory. Data streams are also appropriate as a mo del</div><div class="t m0 xc h2 y16 ff8 fs0 fc0 sc0 ls0 ws0">of access to large data sets stored in secondary memory where p erformance requirements necessitate</div><div class="t m0 xc h2 y17 ff8 fs0 fc0 sc0 ls0 ws0">access via linear scans.</div><div class="t m0 xf h2 y18 ff8 fs0 fc0 sc0 ls0 ws0">In the data stream model [17], the data p oints can only b e accessed in the order in which they</div><div class="t m0 xc h2 y19 ff8 fs0 fc0 sc0 ls0 ws0">arrive. Random access to the data is not allowed; memory is assumed to b e small relative to the</div><div class="t m0 xc h2 y1a ff8 fs0 fc0 sc0 ls0 ws0">number of points, and so only a limited amount of information can b e stored. In general, algorithms</div><div class="t m0 xc h2 y1b ff8 fs0 fc0 sc0 ls0 ws0">operating on streams will b e restricted to fairly simple calculations b ecause of the time and space</div><div class="t m0 xc h2 y1c ff8 fs0 fc0 sc0 ls0 ws0">constraints. The challenge facing algorithm designers is to p erform meaningful computation with</div><div class="t m0 xc h2 y1d ff8 fs0 fc0 sc0 ls0 ws0">these restrictions.</div><div class="t m0 xf h2 y1e ff8 fs0 fc0 sc0 ls0 ws0">Some applications naturally generate data</div><div class="t m0 x10 h2 y1e ff9 fs0 fc0 sc0 ls0 ws0">streams</div><div class="t m0 x11 h2 y1e ff8 fs0 fc0 sc0 ls0 ws0">as opp osed to simple data sets. Astronomers,</div><div class="t m0 xc h2 y1f ff8 fs0 fc0 sc0 ls0 ws0">telecommunications companies, banks, stock-market analysts, and news organizations, for example,</div><div class="t m0 x12 h2 y20 ffa fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 xf h2 y21 ffb fs0 fc0 sc0 ls0 ws0">Contact author; e-mail:lo c@cs.stanford.edu; other authors' e-mails: nmishra@hpl.hp.com, awm@cs.stanford.edu,</div><div class="t m0 xc h2 y22 ffb fs0 fc0 sc0 ls0 ws0">sudipto@research.att.com,rajeev@cs.stanford.edu .</div><div class="t m0 x13 h2 y23 ff8 fs0 fc0 sc0 ls0 ws0">1</div></div><div class="pi" data-data='{"ctm":[1.568627,0.000000,0.000000,1.568627,0.000000,0.000000]}'></div></div> </body> </html>

<div id="pf2" class="pf w0 h0" data-page-no="2"><div class="pc pc2 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://static.pudn.com/prod/directory_preview_static/6268425c4c65f41259806be7/bg2.jpg"><div class="t m0 xc h2 y24 ff8 fs0 fc0 sc0 ls0 ws0">have vast amounts of data arriving continuously. In telecommunications, for example,</div><div class="t m0 x14 h2 y24 ff9 fs0 fc0 sc0 ls0 ws0">cal l records</div><div class="t m0 x15 h2 y24 ff8 fs0 fc0 sc0 ls0 ws0">are</div><div class="t m0 xc h2 y25 ff8 fs0 fc0 sc0 ls0 ws0">generated continuously. Typically, most pro cessing is done by examining a call record once, after which</div><div class="t m0 xc h2 y26 ff8 fs0 fc0 sc0 ls0 ws0">records are archived and not examined again. For example, Cortes et al. [6] report working with AT&T</div><div class="t m0 xc h2 y27 ff8 fs0 fc0 sc0 ls0 ws0">long distance call records, consisting of 300 million records per day for 100 million customers. There</div><div class="t m0 xc h2 y28 ff8 fs0 fc0 sc0 ls0 ws0">are also applications where traditional (non-streaming) data is treated as a stream due to p erformance</div><div class="t m0 xc h2 y2 ff8 fs0 fc0 sc0 ls0 ws0">constraints. For researchers mining medical or marketing data, for example, the volume of data stored</div><div class="t m0 xc h2 y29 ff8 fs0 fc0 sc0 ls0 ws0">on disk is so large that it is only possible to make one pass (or p erhaps a very small number of passes)</div><div class="t m0 xc h2 y2a ff8 fs0 fc0 sc0 ls0 ws0">over the data. Research on data stream computation includes work on sampling [30], nding quantiles</div><div class="t m0 xc h2 y2b ff8 fs0 fc0 sc0 ls0 ws0">of a stream of p oints [22], and calculating the</div><div class="t m0 x16 h2 y2b ffc fs0 fc0 sc0 ls0 ws0">L</div><div class="t m0 xd h2 y2b ff8 fs0 fc0 sc0 ls0 ws0">1-dierence of two streams [11].</div><div class="t m0 xf h2 y2c ff8 fs0 fc0 sc0 ls0 ws0">A common form of data analysis in these applications involves</div><div class="t m0 x17 h2 y2c ff9 fs0 fc0 sc0 ls0 ws0">clustering</div><div class="t m0 x18 h2 y2c ff8 fs0 fc0 sc0 ls0 ws0">, i.e., partitioning the data</div><div class="t m0 xc h2 y2d ff8 fs0 fc0 sc0 ls0 ws0">set into subsets (clusters) such that memb ers of the same cluster are similar and members of distinct</div><div class="t m0 xc h2 y2e ff8 fs0 fc0 sc0 ls0 ws0">clusters are dissimilar. Typically, a cluster is characterized by a canonical element or representative</div><div class="t m0 xc h2 y2f ff8 fs0 fc0 sc0 ls0 ws0">called the</div><div class="t m0 x19 h2 y2f ff9 fs0 fc0 sc0 ls0 ws0">cluster center</div><div class="t m0 x1a h2 y2f ff8 fs0 fc0 sc0 ls0 ws0">. The goal is either to determine cluster centers or to actually compute the</div><div class="t m0 xc h2 y30 ff8 fs0 fc0 sc0 ls0 ws0">clustered partition of the data set. This pap er is concerned with the challenging problem of clustering</div><div class="t m0 xc h2 y31 ff8 fs0 fc0 sc0 ls0 ws0">data arriving in the form of stream. We provide a new clustering algorithm with theoretical guarantees</div><div class="t m0 xc h2 y32 ff8 fs0 fc0 sc0 ls0 ws0">on its p erformance. We give empirical evidence of its sup eriority over the commonly-used</div><div class="t m0 x1b h2 y32 ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x1c h2 y32 ff8 fs0 fc0 sc0 ls0 ws0">{Means</div><div class="t m0 xc h2 y33 ff8 fs0 fc0 sc0 ls0 ws0">algorithm. We then adapt our algorithm to be able to op erate on data streams and exp erimentally</div><div class="t m0 xc h2 y34 ff8 fs0 fc0 sc0 ls0 ws0">demonstrate its superior performance in this context.</div><div class="t m0 xf h2 y35 ff8 fs0 fc0 sc0 ls0 ws0">In what follows, we will rst describe the clustering problem in greater detail, then give a high-level</div><div class="t m0 xc h2 y36 ff8 fs0 fc0 sc0 ls0 ws0">overview of our results and the organization of the paper, followed a discussion of earlier related work.</div><div class="t m0 xc h2 y37 ffd fs0 fc0 sc0 ls0 ws0">The Clustering Problem</div><div class="t m0 x1d h2 y37 ff8 fs0 fc0 sc0 ls0 ws0">There are many dierent variants of the clustering problem [7, 16], and</div><div class="t m0 xc h2 y38 ff8 fs0 fc0 sc0 ls0 ws0">literature in this eld spans a large variety of application areas, including data mining [10], data</div><div class="t m0 xc h2 y39 ff8 fs0 fc0 sc0 ls0 ws0">compression [12], pattern recognition [7], and machine learning [27]. In our work, we will fo cus on</div><div class="t m0 xc h2 y3a ff8 fs0 fc0 sc0 ls0 ws0">following version of the problem: given an integer</div><div class="t m0 x1e h2 y3a ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x1f h2 y3a ff8 fs0 fc0 sc0 ls0 ws0">and a collection</div><div class="t m0 x20 h2 y3a ffc fs0 fc0 sc0 ls0 ws0">N</div><div class="t m0 x21 h2 y3a ff8 fs0 fc0 sc0 ls0 ws0">of</div><div class="t m0 x22 h2 y3a ffc fs0 fc0 sc0 ls0 ws0">n</div><div class="t m0 x23 h2 y3a ff8 fs0 fc0 sc0 ls0 ws0">points in a metric space,</div><div class="t m0 xc h2 y3b ff8 fs0 fc0 sc0 ls0 ws0">nd</div><div class="t m0 x24 h2 y3b ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x25 h2 y3b ff8 fs0 fc0 sc0 ls0 ws0">medians (cluster centers) in the metric space so that each p oint in</div><div class="t m0 x26 h2 y3b ffc fs0 fc0 sc0 ls0 ws0">N</div><div class="t m0 x23 h2 y3b ff8 fs0 fc0 sc0 ls0 ws0">is assigned to the cluster</div><div class="t m0 xc h2 y3c ff8 fs0 fc0 sc0 ls0 ws0">dened by the median point nearest to it. The quality of the clustering is measured by the sum of</div><div class="t m0 xc h2 y3d ff8 fs0 fc0 sc0 ls0 ws0">squared distances (SSQ) of data points from their assigned medians. The goal is to nd a set of</div><div class="t m0 xc h2 y3e ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x27 h2 y3e ff8 fs0 fc0 sc0 ls0 ws0">medians which minimize the SSQ measure. The generalized optimization problem, in which any</div><div class="t m0 xc h2 y3f ff8 fs0 fc0 sc0 ls0 ws0">distance metric substitutes for the squared Euclidean distance, is known as the</div><div class="t m0 x28 h2 y3f ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x29 h2 y3f ff8 fs0 fc0 sc0 ls0 ws0">{Median problem</div><div class="t m0 x2a h2 y40 ffe fs0 fc0 sc0 ls0 ws0">1</div><div class="t m0 x2b h2 y3f ff8 fs0 fc0 sc0 ls0 ws0">.</div><div class="t m0 xc h2 y41 ff8 fs0 fc0 sc0 ls0 ws0">Other variants of the clustering problem may not involve centers, may employ a measure other than</div><div class="t m0 xc h2 y42 ff8 fs0 fc0 sc0 ls0 ws0">SSQ, and may consider sp ecial cases of a metric space such as</div><div class="t m0 x2c h2 y42 ffc fs0 fc0 sc0 ls0 ws0">d</div><div class="t m0 x2d h2 y42 ff8 fs0 fc0 sc0 ls0 ws0">-dimensional Euclidean space. Since</div><div class="t m0 xc h2 y43 ff8 fs0 fc0 sc0 ls0 ws0">most variants are known to b e NP-hard, the goal is to devise algorithms that pro duce solutions with</div><div class="t m0 xc h2 y44 ff8 fs0 fc0 sc0 ls0 ws0">near-optimal solutions in near-linear running time.</div><div class="t m0 xf h2 y45 ff8 fs0 fc0 sc0 ls0 ws0">Although nding an optimal solution to the</div><div class="t m0 x2e h2 y45 ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x2f h2 y45 ff8 fs0 fc0 sc0 ls0 ws0">{Median problem is known to b e NP-hard, many</div><div class="t m0 xc h2 y46 ff8 fs0 fc0 sc0 ls0 ws0">useful heuristics, including</div><div class="t m0 x30 h2 y46 ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x31 h2 y46 ff8 fs0 fc0 sc0 ls0 ws0">{Means, have b een prop osed. The</div><div class="t m0 x32 h2 y46 ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x33 h2 y46 ff8 fs0 fc0 sc0 ls0 ws0">{Means algorithm has enjoyed con-</div><div class="t m0 xc h2 y47 ff8 fs0 fc0 sc0 ls0 ws0">siderable practical success [3], although the solution it produces is only guaranteed to b e a lo cal</div><div class="t m0 xc h2 y48 ff8 fs0 fc0 sc0 ls0 ws0">optimum [28]. On the other hand, in the algorithms literature, several approximation algorithms have</div><div class="t m0 x12 h2 y49 fff fs0 fc0 sc0 ls0 ws0">1</div><div class="t m0 xf h2 y4a ffb fs0 fc0 sc0 ls0 ws0">Although squared Euclidean distance is not a metric, it obeys a relaxed triangle inequality and therefore b ehaves</div><div class="t m0 xc h2 y4b ffb fs0 fc0 sc0 ls0 ws0">much like a metric.</div><div class="t m0 x13 h2 y4c ff8 fs0 fc0 sc0 ls0 ws0">2</div></div><div class="pi" data-data='{"ctm":[1.568627,0.000000,0.000000,1.568627,0.000000,0.000000]}'></div></div>

<div id="pf3" class="pf w0 h0" data-page-no="3"><div class="pc pc3 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://static.pudn.com/prod/directory_preview_static/6268425c4c65f41259806be7/bg3.jpg"><div class="t m0 xc h2 y24 ff8 fs0 fc0 sc0 ls0 ws0">been prop osed for</div><div class="t m0 x34 h2 y24 ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x35 h2 y24 ff8 fs0 fc0 sc0 ls0 ws0">{Median. A</div><div class="t m0 x36 h2 y24 ffc fs0 fc0 sc0 ls0 ws0">c</div><div class="t m0 x37 h2 y24 ff8 fs0 fc0 sc0 ls0 ws0">-approximation algorithm is guaranteed to nd a solution whose SSQ</div><div class="t m0 xc h2 y25 ff8 fs0 fc0 sc0 ls0 ws0">is within a factor</div><div class="t m0 x38 h2 y25 ffc fs0 fc0 sc0 ls0 ws0">c</div><div class="t m0 x39 h2 y25 ff8 fs0 fc0 sc0 ls0 ws0">of the optimal SSQ, even for a worst-case input. Recently, Jain and Vazirani [20]</div><div class="t m0 xc h2 y26 ff8 fs0 fc0 sc0 ls0 ws0">and Charikar and Guha [5] have provided such approximation algorithms for constants</div><div class="t m0 x3a h2 y26 ffc fs0 fc0 sc0 ls0 ws0">c</div><div class="t m0 x3b h2 y26 ff10 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 x1b h2 y26 ff8 fs0 fc0 sc0 ls0 ws0">6. These</div><div class="t m0 xc h2 y27 ff8 fs0 fc0 sc0 ls0 ws0">algorithms typically run in time and space (</div><div class="t m0 x7 h2 y27 ffc fs0 fc0 sc0 ls0 ws0">n</div><div class="t m0 x3c h2 y4d ffe fs0 fc0 sc0 ls0 ws0">2</div><div class="t m0 x3d h2 y27 ff8 fs0 fc0 sc0 ls0 ws0">) and require random access to the data. Both space</div><div class="t m0 xc h2 y28 ff8 fs0 fc0 sc0 ls0 ws0">requirements and the need for random access render these algorithms inapplicable to data streams.</div><div class="t m0 xc h2 y2 ff8 fs0 fc0 sc0 ls0 ws0">Most heuristics, including</div><div class="t m0 x3e h2 y2 ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x3f h2 y2 ff8 fs0 fc0 sc0 ls0 ws0">{Means, are also infeasible for data streams b ecause they require random</div><div class="t m0 xc h2 y29 ff8 fs0 fc0 sc0 ls0 ws0">access. As a result, several heuristics have b een proposed for scaling clustering algorithms, for exam-</div><div class="t m0 xc h2 y2a ff8 fs0 fc0 sc0 ls0 ws0">ple [4, 14]. In the database literature, the BIRCH system [32] is commonly considered to provide a</div><div class="t m0 xc h2 y2b ff8 fs0 fc0 sc0 ls0 ws0">competitive heuristic for this problem. While these heuristics have been tested on real and synthetic</div><div class="t m0 xc h2 y2c ff8 fs0 fc0 sc0 ls0 ws0">datasets, there are no guarantees on their SSQ p erformance.</div><div class="t m0 xc h2 y4e ffd fs0 fc0 sc0 ls0 ws0">Overview of Results</div><div class="t m0 x40 h2 y4e ff8 fs0 fc0 sc0 ls0 ws0">We will present a fast</div><div class="t m0 x10 h2 y4e ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x3d h2 y4e ff8 fs0 fc0 sc0 ls0 ws0">{Median algorithm called LOCALSEARCH that uses</div><div class="t m0 xc h2 y4f ff8 fs0 fc0 sc0 ls0 ws0">local search techniques, give theoretical justication for its success, and present experimental results</div><div class="t m0 xc h2 y50 ff8 fs0 fc0 sc0 ls0 ws0">showing how it out-p erforms</div><div class="t m0 x31 h2 y50 ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x1d h2 y50 ff8 fs0 fc0 sc0 ls0 ws0">{Means. Next, we will convert the algorithm into a streaming algorithm</div><div class="t m0 xc h2 y51 ff8 fs0 fc0 sc0 ls0 ws0">using the technique in [13]. This conversion will decrease the asymptotic running time, drastically</div><div class="t m0 xc h2 y52 ff8 fs0 fc0 sc0 ls0 ws0">cut the memory usage, and remove the random-access requirement, making the algorithm suitable for</div><div class="t m0 xc h2 y53 ff8 fs0 fc0 sc0 ls0 ws0">use on streams. We will also present exp erimental results showing how the stream algorithm p erforms</div><div class="t m0 xc h2 y54 ff8 fs0 fc0 sc0 ls0 ws0">against popular heuristics.</div><div class="t m0 xf h2 y55 ff8 fs0 fc0 sc0 ls0 ws0">The rest of this paper is organized as follows. We b egin in Section 2 by formally dening the stream</div><div class="t m0 xc h2 y56 ff8 fs0 fc0 sc0 ls0 ws0">model and the</div><div class="t m0 x41 h2 y56 ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x42 h2 y56 ff8 fs0 fc0 sc0 ls0 ws0">{Median problem. Our solution for</div><div class="t m0 x43 h2 y56 ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x44 h2 y56 ff8 fs0 fc0 sc0 ls0 ws0">{Median is obtained via a variant called facility</div><div class="t m0 xc h2 y57 ff8 fs0 fc0 sc0 ls0 ws0">location, which does not specify in advance the number of clusters desired, and instead evaluates an</div><div class="t m0 xc h2 y58 ff8 fs0 fc0 sc0 ls0 ws0">algorithm's p erformance by a combination of SSQ and the numb er of centers used. To our knowledge,</div><div class="t m0 xc h2 y59 ff8 fs0 fc0 sc0 ls0 ws0">this is the rst time this approach has been used to attack the</div><div class="t m0 x45 h2 y59 ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x46 h2 y59 ff8 fs0 fc0 sc0 ls0 ws0">{Median problem.</div><div class="t m0 xf h2 y5a ff8 fs0 fc0 sc0 ls0 ws0">Our discussion about streaming can b e found in Section 3. The streaming algorithm given in</div><div class="t m0 xc h2 y5b ff8 fs0 fc0 sc0 ls0 ws0">this section is shown to enjoy theoretical quality guarantees. As described later, our empirical results</div><div class="t m0 xc h2 y5c ff8 fs0 fc0 sc0 ls0 ws0">reveal that, on both synthetic and real streams, our theoretically sound algorithm achieves dramatically</div><div class="t m0 xc h2 y5d ff8 fs0 fc0 sc0 ls0 ws0">better clustering quality (SSQ) than BIRCH, although it takes longer to run. Section 3.2 describ es</div><div class="t m0 xc h2 y5e ff8 fs0 fc0 sc0 ls0 ws0">new and critical conceptualizations that characterize which instances of facility lo cation we will solve</div><div class="t m0 xc h2 y5f ff8 fs0 fc0 sc0 ls0 ws0">to obtain a</div><div class="t m0 x47 h2 y5f ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x48 h2 y5f ff8 fs0 fc0 sc0 ls0 ws0">{Median solution, and also what subset of feasible facilities is sucient to obtain an</div><div class="t m0 xc h2 y60 ff8 fs0 fc0 sc0 ls0 ws0">approximate solution. LOCALSEARCH is also detailed in this section.</div><div class="t m0 xf h2 y61 ff8 fs0 fc0 sc0 ls0 ws0">We performed an extensive series of exp eriments comparing LOCALSEARCH against the</div><div class="t m0 x1b h2 y61 ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x1c h2 y61 ff8 fs0 fc0 sc0 ls0 ws0">{Means</div><div class="t m0 xc h2 y62 ff8 fs0 fc0 sc0 ls0 ws0">algorithm, on numerous low- and high-dimensional data. The results presented in Section 4.1 uncover</div><div class="t m0 xc h2 y63 ff8 fs0 fc0 sc0 ls0 ws0">an interesting trade-o b etween the cluster quality and the running time. We found that SSQ for</div><div class="t m0 xc h2 y64 ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x49 h2 y64 ff8 fs0 fc0 sc0 ls0 ws0">-means was worse than that for LOCALSEARCH , and that LOCALSEARCH typically found near-</div><div class="t m0 xc h2 y65 ff8 fs0 fc0 sc0 ls0 ws0">optimum (if not the optimum) solution. Since both algorithms are randomized, we ran each one several</div><div class="t m0 xc h2 y66 ff8 fs0 fc0 sc0 ls0 ws0">times on each dataset; over the course of multiple runs, there was a large variance in the performance</div><div class="t m0 xc h2 y67 ff8 fs0 fc0 sc0 ls0 ws0">of</div><div class="t m0 x4a h2 y67 ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x4b h2 y67 ff8 fs0 fc0 sc0 ls0 ws0">{Means, whereas LOCALSEARCH was consistently go o d. LOCALSEARCH to ok longer to run</div><div class="t m0 xc h2 y68 ff8 fs0 fc0 sc0 ls0 ws0">for each trial but for most datasets found a near-optimal answer b efore</div><div class="t m0 x4c h2 y68 ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x4d h2 y68 ff8 fs0 fc0 sc0 ls0 ws0">{Means found an equally</div><div class="t m0 xc h2 y69 ff8 fs0 fc0 sc0 ls0 ws0">goo d solution. On many datasets, of course,</div><div class="t m0 x4e h2 y69 ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x4f h2 y69 ff8 fs0 fc0 sc0 ls0 ws0">{Means never found a go o d solution.</div><div class="t m0 xf h2 y6a ff8 fs0 fc0 sc0 ls0 ws0">We view both</div><div class="t m0 x50 h2 y6a ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x51 h2 y6a ff8 fs0 fc0 sc0 ls0 ws0">-Means and BIRCH as algorithms that do a quick-and-dirty job of obtaining a</div><div class="t m0 x13 h2 y6b ff8 fs0 fc0 sc0 ls0 ws0">3</div></div><div class="pi" data-data='{"ctm":[1.568627,0.000000,0.000000,1.568627,0.000000,0.000000]}'></div></div>

<div id="pf4" class="pf w0 h0" data-page-no="4"><div class="pc pc4 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://static.pudn.com/prod/directory_preview_static/6268425c4c65f41259806be7/bg4.jpg"><div class="t m0 xc h2 y24 ff8 fs0 fc0 sc0 ls0 ws0">solution. Finding a higher quality solution takes more time, and thus as one would expect while our</div><div class="t m0 xc h2 y25 ff8 fs0 fc0 sc0 ls0 ws0">algorithms require more running time, they do app ear to nd exceptionally goo d solutions.</div><div class="t m0 xc h2 y6c ffd fs0 fc0 sc0 ls0 ws0">Related Work</div><div class="t m0 x34 h2 y6c ff8 fs0 fc0 sc0 ls0 ws0">The</div><div class="t m0 x52 h2 y6c ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x53 h2 y6c ff8 fs0 fc0 sc0 ls0 ws0">-Means algorithm and BIRCH [32] are most relevant to our results. We discuss</div><div class="t m0 xc h2 y6d ff8 fs0 fc0 sc0 ls0 ws0">these in more detail in Section 4. Most other previous work on clustering either does not oer the</div><div class="t m0 xc h2 y6e ff8 fs0 fc0 sc0 ls0 ws0">scalability required for a fast streaming algorithm or does not directly optimize SSQ. We briey review</div><div class="t m0 xc h2 y6f ff8 fs0 fc0 sc0 ls0 ws0">these results | a thorough treatment can b e found in Han and Kinber's b o ok [15].</div><div class="t m0 xf h2 y70 ff8 fs0 fc0 sc0 ls0 ws0">Partitioning metho ds sub divide a dataset into</div><div class="t m0 x1f h2 y70 ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x54 h2 y70 ff8 fs0 fc0 sc0 ls0 ws0">groups. One such example is the</div><div class="t m0 x55 h2 y70 ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x1b h2 y70 ff8 fs0 fc0 sc0 ls0 ws0">-medoids</div><div class="t m0 xc h2 y71 ff8 fs0 fc0 sc0 ls0 ws0">algorithm [21] which selects</div><div class="t m0 x56 h2 y71 ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x57 h2 y71 ff8 fs0 fc0 sc0 ls0 ws0">initial centers, repeatedly chooses a data point randomly, and replaces</div><div class="t m0 xc h2 y72 ff8 fs0 fc0 sc0 ls0 ws0">it with an existing center if there is an improvement in SSQ.</div><div class="t m0 xe h2 y72 ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x58 h2 y72 ff8 fs0 fc0 sc0 ls0 ws0">-medoids is related to the CG algorithm</div><div class="t m0 xc h2 y73 ff8 fs0 fc0 sc0 ls0 ws0">given in Section 3.2.1, except that CG solves the facility location variant which is more desirable since</div><div class="t m0 xc h2 y4e ff8 fs0 fc0 sc0 ls0 ws0">in practice one do es not know the exact number of clusters</div><div class="t m0 xe h2 y4e ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x59 h2 y4e ff8 fs0 fc0 sc0 ls0 ws0">(and facility location allows as input a</div><div class="t m0 xc h2 y4f ff8 fs0 fc0 sc0 ls0 ws0">range of number of centers). Choosing a new medoid among all the remaining points is time-consuming;</div><div class="t m0 xc h2 y50 ff8 fs0 fc0 sc0 ls0 ws0">to address this problem, CLARA [21] used sampling to reduce the number of feasible centers. This</div><div class="t m0 xc h2 y51 ff8 fs0 fc0 sc0 ls0 ws0">technique is similar to what we propose in Theorem 4. A distinguishing feature of our approach is</div><div class="t m0 xc h2 y52 ff8 fs0 fc0 sc0 ls0 ws0">a careful understanding of how sample size aects clustering quality. CLARANS [26] draws a fresh</div><div class="t m0 xc h2 y53 ff8 fs0 fc0 sc0 ls0 ws0">sample of feasible centers b efore each calculation of SSQ improvement. All of the</div><div class="t m0 x5a h2 y53 ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x5b h2 y53 ff8 fs0 fc0 sc0 ls0 ws0">-medoid types of</div><div class="t m0 xc h2 y54 ff8 fs0 fc0 sc0 ls0 ws0">approaches, including PAM, CLARA, and CLARANS, are known not to b e scalable and thus are not</div><div class="t m0 xc h2 y55 ff8 fs0 fc0 sc0 ls0 ws0">appropriate in a streaming context.</div><div class="t m0 xf h2 y56 ff8 fs0 fc0 sc0 ls0 ws0">Other examples of partitioning methods include that of Bradley et al. [4] and its subsequent im-</div><div class="t m0 xc h2 y57 ff8 fs0 fc0 sc0 ls0 ws0">provement by Farnstorm et al. [9] which rep eatedly takes</div><div class="t m0 x5c h2 y57 ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x5d h2 y57 ff8 fs0 fc0 sc0 ls0 ws0">weighted centers (initially chosen randomly</div><div class="t m0 xc h2 y58 ff8 fs0 fc0 sc0 ls0 ws0">with weight 1) and as much data as can t in main memory and computes a</div><div class="t m0 x5e h2 y58 ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x5f h2 y58 ff8 fs0 fc0 sc0 ls0 ws0">-clustering. The new</div><div class="t m0 xc h2 y59 ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x27 h2 y59 ff8 fs0 fc0 sc0 ls0 ws0">centers so obtained are then weighted by the number of points assigned, the data in memory is</div><div class="t m0 xc h2 y5a ff8 fs0 fc0 sc0 ls0 ws0">discarded, and the process rep eats on the remaining data. A key dierence between this approach and</div><div class="t m0 xc h2 y5b ff8 fs0 fc0 sc0 ls0 ws0">ours is that their algorithm places higher signicance on points later in the data set - we assume that</div><div class="t m0 xc h2 y5c ff8 fs0 fc0 sc0 ls0 ws0">our data stream is not sorted in any way. Furthermore, these approaches are not known to outp erform</div><div class="t m0 xc h2 y5d ff8 fs0 fc0 sc0 ls0 ws0">the popular BIRCH algorithm.</div><div class="t m0 xf h2 y5e ff8 fs0 fc0 sc0 ls0 ws0">Hierarchical methods decomp ose a dataset into a tree-like structure. HAC, the most common,</div><div class="t m0 xc h2 y5f ff8 fs0 fc0 sc0 ls0 ws0">treats each p oint as a cluster and then rep eatedly merges the closest ones. If the numb er of clusters</div><div class="t m0 x60 h2 y5f ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 xc h2 y60 ff8 fs0 fc0 sc0 ls0 ws0">is known, then merging stops when only</div><div class="t m0 x61 h2 y60 ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x5 h2 y60 ff8 fs0 fc0 sc0 ls0 ws0">separate clusters remain. Hierarchical algorithms are known</div><div class="t m0 xc h2 y61 ff8 fs0 fc0 sc0 ls0 ws0">to suer from the problem that hierarchical merge or split operations are irrevocable [15]. Another</div><div class="t m0 xc h2 y62 ff8 fs0 fc0 sc0 ls0 ws0">hierarchical technique is CURE [14], which represents a cluster by multiple p oints that are initially</div><div class="t m0 xc h2 y63 ff8 fs0 fc0 sc0 ls0 ws0">well-scattered in the cluster and then shrunk toward the cluster center by a certain fraction. HAC and</div><div class="t m0 xc h2 y64 ff8 fs0 fc0 sc0 ls0 ws0">CURE are designed to discover clusters of arbitrary shap e and thus do not necessarily optimize SSQ.</div><div class="t m0 xf h2 y65 ff8 fs0 fc0 sc0 ls0 ws0">Density-based methods dene clusters as dense regions of space separated by less dense regions.</div><div class="t m0 xc h2 y66 ff8 fs0 fc0 sc0 ls0 ws0">Such metho ds typically continue to grow clusters as long as their density exceeds a specied thresh-</div><div class="t m0 xc h2 y67 ff8 fs0 fc0 sc0 ls0 ws0">old. Desnsity-based algorithms like DBSCAN [8], OPTICS [2] and DENCLUE [18] are not explicitly</div><div class="t m0 xc h2 y68 ff8 fs0 fc0 sc0 ls0 ws0">designed to minimize SSQ.</div><div class="t m0 xf h2 y69 ff8 fs0 fc0 sc0 ls0 ws0">Grid-based methods typically quantize the space into a xed number of cells that form a grid-</div><div class="t m0 xc h2 y6a ff8 fs0 fc0 sc0 ls0 ws0">like structure. Clustering is then p erformed on this structure. Examples of such algorithms include</div><div class="t m0 x13 h2 y6b ff8 fs0 fc0 sc0 ls0 ws0">4</div></div><div class="pi" data-data='{"ctm":[1.568627,0.000000,0.000000,1.568627,0.000000,0.000000]}'></div></div>

<div id="pf5" class="pf w0 h0" data-page-no="5"><div class="pc pc5 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://static.pudn.com/prod/directory_preview_static/6268425c4c65f41259806be7/bg5.jpg"><div class="t m0 xc h2 y24 ff8 fs0 fc0 sc0 ls0 ws0">STING [31], CLIQUE [1], Wave-Cluster [29], and OPTIGRID [19]. Cluster boundaries in these meth-</div><div class="t m0 xc h2 y25 ff8 fs0 fc0 sc0 ls0 ws0">ods are axis-aligned hyperplanes, (no diagonal separations are allowed) and so grid-based approaches</div><div class="t m0 xc h2 y26 ff8 fs0 fc0 sc0 ls0 ws0">are also not designed to optimize SSQ.</div><div class="t m0 xc h2 y74 ff7 fs0 fc0 sc0 ls0 ws0">2 Preliminaries</div><div class="t m0 xc h2 y75 ff8 fs0 fc0 sc0 ls0 ws0">We begin by dening a stream more formally. A data stream is a nite set</div><div class="t m0 x62 h2 y75 ffc fs0 fc0 sc0 ls0 ws0">N</div><div class="t m0 x18 h2 y75 ff8 fs0 fc0 sc0 ls0 ws0">of points</div><div class="t m0 x63 h2 y75 ffc fs0 fc0 sc0 ls0 ws0">x</div><div class="t m0 x64 h2 y76 ffe fs0 fc0 sc0 ls0 ws0">1</div><div class="t m0 x14 h2 y75 ffc fs0 fc0 sc0 ls0 ws0">; : : : ; x</div><div class="t m0 x65 h2 y76 ff11 fs0 fc0 sc0 ls0 ws0">i</div><div class="t m0 x1c h2 y75 ffc fs0 fc0 sc0 ls0 ws0">; : : : ; x</div><div class="t m0 x60 h2 y76 ff11 fs0 fc0 sc0 ls0 ws0">n</div><div class="t m0 xc h2 y77 ff8 fs0 fc0 sc0 ls0 ws0">read in increasing order of the indices</div><div class="t m0 x66 h2 y77 ffc fs0 fc0 sc0 ls0 ws0">i</div><div class="t m0 x67 h2 y77 ff8 fs0 fc0 sc0 ls0 ws0">. For example, these points might b e vectors in</div><div class="t m0 x3a h2 y77 ff10 fs0 fc0 sc0 ls0 ws0"><</div><div class="t m0 x3b h2 y78 ff11 fs0 fc0 sc0 ls0 ws0">d</div><div class="t m0 x55 h2 y77 ff8 fs0 fc0 sc0 ls0 ws0">. Random</div><div class="t m0 xc h2 y79 ff8 fs0 fc0 sc0 ls0 ws0">access to the data is not allowed. A stream algorithm is allowed to remember a small amount of</div><div class="t m0 xc h2 y7a ff8 fs0 fc0 sc0 ls0 ws0">information ab out the data it has seen so far. The p erformance of a stream algorithm is measured</div><div class="t m0 xc h2 y7b ff8 fs0 fc0 sc0 ls0 ws0">by the amount of information it retains about the data that has streamed by, as well as by the usual</div><div class="t m0 xc h2 y7c ff8 fs0 fc0 sc0 ls0 ws0">measures: in the case of a clustering algorithm, for example, these could be SSQ and running time.</div><div class="t m0 xf h2 y7d ff8 fs0 fc0 sc0 ls0 ws0">In what follows, we give a more detailed and formal denition of the</div><div class="t m0 x68 h2 y7d ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x69 h2 y7d ff8 fs0 fc0 sc0 ls0 ws0">-Median problem and of the</div><div class="t m0 xc h2 y7e ff8 fs0 fc0 sc0 ls0 ws0">related</div><div class="t m0 x6a h2 y7e ff9 fs0 fc0 sc0 ls0 ws0">facility location</div><div class="t m0 x6b h2 y7e ff8 fs0 fc0 sc0 ls0 ws0">problem.</div><div class="t m0 xf h2 y7f ff8 fs0 fc0 sc0 ls0 ws0">Suppose we are given a set</div><div class="t m0 x6c h2 y7f ffc fs0 fc0 sc0 ls0 ws0">N</div><div class="t m0 x4 h2 y7f ff8 fs0 fc0 sc0 ls0 ws0">of</div><div class="t m0 x6d h2 y7f ffc fs0 fc0 sc0 ls0 ws0">n</div><div class="t m0 x6e h2 y7f ff8 fs0 fc0 sc0 ls0 ws0">ob jects. There is some notion of \similarity" between the</div><div class="t m0 xc h2 y80 ff8 fs0 fc0 sc0 ls0 ws0">ob jects, and the goal is to group the ob jects into exactly</div><div class="t m0 x6f h2 y80 ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x70 h2 y80 ff8 fs0 fc0 sc0 ls0 ws0">clusters so that similar ob jects b elong to</div><div class="t m0 xc h2 y81 ff8 fs0 fc0 sc0 ls0 ws0">the same cluster while dissimilar ob jects are in dierent clusters. We will assume that the ob jects</div><div class="t m0 xc h2 y82 ff8 fs0 fc0 sc0 ls0 ws0">are represented as points in a metric space whose distance function conveys similarity. The</div><div class="t m0 x71 h2 y82 ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x72 h2 y82 ff8 fs0 fc0 sc0 ls0 ws0">{Median</div><div class="t m0 xc h2 y83 ff8 fs0 fc0 sc0 ls0 ws0">problem may now be formally dened as follows:</div><div class="t m0 xc h2 y84 ffd fs0 fc0 sc0 ls0 ws0">Denition 1 (The</div><div class="t m0 x73 h2 y84 ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x74 h2 y84 ffd fs0 fc0 sc0 ls0 ws0">{Median Problem)</div><div class="t m0 x4e h2 y84 ff9 fs0 fc0 sc0 ls0 ws0">We are given a set</div><div class="t m0 x75 h2 y84 ffc fs0 fc0 sc0 ls0 ws0">N</div><div class="t m0 x76 h2 y84 ff9 fs0 fc0 sc0 ls0 ws0">of</div><div class="t m0 x77 h2 y84 ffc fs0 fc0 sc0 ls0 ws0">n</div><div class="t m0 x21 h2 y84 ff9 fs0 fc0 sc0 ls0 ws0">data points in a metric space,</div><div class="t m0 xc h2 y85 ff9 fs0 fc0 sc0 ls0 ws0">a distance function</div><div class="t m0 x51 h2 y85 ffc fs0 fc0 sc0 ls0 ws0">d</div><div class="t m0 x74 h2 y85 ff8 fs0 fc0 sc0 ls0 ws0">:</div><div class="t m0 x6b h2 y85 ffc fs0 fc0 sc0 ls0 ws0">N</div><div class="t m0 x78 h2 y85 ff10 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 x56 h2 y85 ffc fs0 fc0 sc0 ls0 ws0">N</div><div class="t m0 x79 h2 y85 ff10 fs0 fc0 sc0 ls0 ws0">! <</div><div class="t m0 x7a h2 y86 ffe fs0 fc0 sc0 ls0 ws0">+</div><div class="t m0 x7b h2 y85 ff9 fs0 fc0 sc0 ls0 ws0">, and a number</div><div class="t m0 x7c h2 y85 ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x7d h2 y85 ff9 fs0 fc0 sc0 ls0 ws0">. For any choice of</div><div class="t m0 x7e h2 y85 ffc fs0 fc0 sc0 ls0 ws0">C</div><div class="t m0 x7f h2 y85 ff8 fs0 fc0 sc0 ls0 ws0">=</div><div class="t m0 x80 h2 y85 ff10 fs0 fc0 sc0 ls0 ws0">f</div><div class="t m0 x81 h2 y85 ffc fs0 fc0 sc0 ls0 ws0">c</div><div class="t m0 x82 h2 y87 ffe fs0 fc0 sc0 ls0 ws0">1</div><div class="t m0 x5b h2 y85 ffc fs0 fc0 sc0 ls0 ws0">; c</div><div class="t m0 x14 h2 y87 ffe fs0 fc0 sc0 ls0 ws0">2</div><div class="t m0 x83 h2 y85 ffc fs0 fc0 sc0 ls0 ws0">; : : : ; c</div><div class="t m0 x1c h2 y87 ff11 fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x84 h2 y85 ff10 fs0 fc0 sc0 ls0 ws0">g </div><div class="t m0 x85 h2 y85 ffc fs0 fc0 sc0 ls0 ws0">N</div><div class="t m0 xc h2 y88 ff9 fs0 fc0 sc0 ls0 ws0">of</div><div class="t m0 x4a h2 y88 ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x86 h2 y88 ff9 fs0 fc0 sc0 ls0 ws0">cluster centers, dene a partition of</div><div class="t m0 x87 h2 y88 ffc fs0 fc0 sc0 ls0 ws0">N</div><div class="t m0 x4e h2 y88 ff9 fs0 fc0 sc0 ls0 ws0">into</div><div class="t m0 x13 h2 y88 ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x88 h2 y88 ff9 fs0 fc0 sc0 ls0 ws0">clusters</div><div class="t m0 xe h2 y88 ffc fs0 fc0 sc0 ls0 ws0">N</div><div class="t m0 x59 h2 y89 ffe fs0 fc0 sc0 ls0 ws0">1</div><div class="t m0 x45 h2 y88 ffc fs0 fc0 sc0 ls0 ws0">; N</div><div class="t m0 x89 h2 y89 ffe fs0 fc0 sc0 ls0 ws0">2</div><div class="t m0 x76 h2 y88 ffc fs0 fc0 sc0 ls0 ws0">; : : : ; N</div><div class="t m0 x8a h2 y89 ff11 fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x7e h2 y88 ff9 fs0 fc0 sc0 ls0 ws0">such that</div><div class="t m0 x8b h2 y88 ffc fs0 fc0 sc0 ls0 ws0">N</div><div class="t m0 x8c h2 y89 ff11 fs0 fc0 sc0 ls0 ws0">i</div><div class="t m0 x8d h2 y88 ff9 fs0 fc0 sc0 ls0 ws0">contains al l</div><div class="t m0 xc h2 y8a ff9 fs0 fc0 sc0 ls0 ws0">points in</div><div class="t m0 x1 h2 y8a ffc fs0 fc0 sc0 ls0 ws0">N</div><div class="t m0 x47 h2 y8a ff9 fs0 fc0 sc0 ls0 ws0">that are closer to</div><div class="t m0 x8e h2 y8a ffc fs0 fc0 sc0 ls0 ws0">c</div><div class="t m0 x8f h2 y8b ff11 fs0 fc0 sc0 ls0 ws0">i</div><div class="t m0 x90 h2 y8a ff9 fs0 fc0 sc0 ls0 ws0">than to any other center. The goal is to select</div><div class="t m0 x28 h2 y8a ffc fs0 fc0 sc0 ls0 ws0">C</div><div class="t m0 x91 h2 y8a ff9 fs0 fc0 sc0 ls0 ws0">so as to minimize</div><div class="t m0 xc h2 y8c ff9 fs0 fc0 sc0 ls0 ws0">the sum of squared distance (SSQ) measure:</div><div class="t m0 x92 h2 y8d ffc fs0 fc0 sc0 ls0 ws0">S S Q</div><div class="t m0 x93 h2 y8d ff8 fs0 fc0 sc0 ls0 ws0">(</div><div class="t m0 x6 h2 y8d ffc fs0 fc0 sc0 ls0 ws0">N ; C</div><div class="t m0 x4f h2 y8d ff8 fs0 fc0 sc0 ls0 ws0">) =</div><div class="t m0 x94 h2 y8e ff11 fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x13 h2 y8f ff12 fs0 fc0 sc0 ls0 ws0">X</div><div class="t m0 x13 h2 y90 ff11 fs0 fc0 sc0 ls0 ws0">i</div><div class="t m0 x2f h2 y90 ffe fs0 fc0 sc0 ls0 ws0">=1</div><div class="t m0 x95 h2 y8f ff12 fs0 fc0 sc0 ls0 ws0">X</div><div class="t m0 x96 h2 y91 ff11 fs0 fc0 sc0 ls0 ws0">x</div><div class="t m0 x97 h2 y91 ff3 fs0 fc0 sc0 ls0 ws0">2</div><div class="t m0 x98 h2 y91 ff11 fs0 fc0 sc0 ls0 ws0">N</div><div class="t m0 x99 h2 y92 ff13 fs0 fc0 sc0 ls0 ws0">i</div><div class="t m0 x6f h2 y93 ffc fs0 fc0 sc0 ls0 ws0">d</div><div class="t m0 x9a h2 y93 ff8 fs0 fc0 sc0 ls0 ws0">(</div><div class="t m0 x70 h2 y93 ffc fs0 fc0 sc0 ls0 ws0">x; c</div><div class="t m0 x2c h2 y94 ff11 fs0 fc0 sc0 ls0 ws0">i</div><div class="t m0 x75 h2 y93 ff8 fs0 fc0 sc0 ls0 ws0">)</div><div class="t m0 x9b h2 y93 ffc fs0 fc0 sc0 ls0 ws0">:</div><div class="t m0 xf h2 y95 ff8 fs0 fc0 sc0 ls0 ws0">Assuming that the points in</div><div class="t m0 x37 h2 y95 ffc fs0 fc0 sc0 ls0 ws0">N</div><div class="t m0 x4 h2 y95 ff8 fs0 fc0 sc0 ls0 ws0">are drawn from a metric space means that the distance function</div><div class="t m0 xc h2 y96 ff8 fs0 fc0 sc0 ls0 ws0">is</div><div class="t m0 x27 h2 y96 ff9 fs0 fc0 sc0 ls0 ws0">reexive</div><div class="t m0 x9c h2 y96 ff8 fs0 fc0 sc0 ls0 ws0">(i.e.,</div><div class="t m0 x42 h2 y96 ffc fs0 fc0 sc0 ls0 ws0">d</div><div class="t m0 x9d h2 y96 ff8 fs0 fc0 sc0 ls0 ws0">(</div><div class="t m0 x9e h2 y96 ffc fs0 fc0 sc0 ls0 ws0">x; y</div><div class="t m0 x74 h2 y96 ff8 fs0 fc0 sc0 ls0 ws0">) = 0 i</div><div class="t m0 x57 h2 y96 ffc fs0 fc0 sc0 ls0 ws0">x</div><div class="t m0 x9f h2 y96 ff8 fs0 fc0 sc0 ls0 ws0">=</div><div class="t m0 xa0 h2 y96 ffc fs0 fc0 sc0 ls0 ws0">y</div><div class="t m0 x7a h2 y96 ff8 fs0 fc0 sc0 ls0 ws0">) and</div><div class="t m0 xa1 h2 y96 ff9 fs0 fc0 sc0 ls0 ws0">symmetric</div><div class="t m0 x96 h2 y96 ff8 fs0 fc0 sc0 ls0 ws0">(i.e.,</div><div class="t m0 x5d h2 y96 ffc fs0 fc0 sc0 ls0 ws0">d</div><div class="t m0 xa2 h2 y96 ff8 fs0 fc0 sc0 ls0 ws0">(</div><div class="t m0 xa3 h2 y96 ffc fs0 fc0 sc0 ls0 ws0">x; y</div><div class="t m0 x75 h2 y96 ff8 fs0 fc0 sc0 ls0 ws0">) =</div><div class="t m0 xa4 h2 y96 ffc fs0 fc0 sc0 ls0 ws0">d</div><div class="t m0 xa5 h2 y96 ff8 fs0 fc0 sc0 ls0 ws0">(</div><div class="t m0 xa6 h2 y96 ffc fs0 fc0 sc0 ls0 ws0">y ; x</div><div class="t m0 x26 h2 y96 ff8 fs0 fc0 sc0 ls0 ws0">)), and satises the</div><div class="t m0 x1c h2 y96 ff9 fs0 fc0 sc0 ls0 ws0">triangle</div><div class="t m0 xc h2 y97 ff9 fs0 fc0 sc0 ls0 ws0">inequality</div><div class="t m0 xa7 h2 y97 ff8 fs0 fc0 sc0 ls0 ws0">(i.e.,</div><div class="t m0 xa8 h2 y97 ffc fs0 fc0 sc0 ls0 ws0">d</div><div class="t m0 xa9 h2 y97 ff8 fs0 fc0 sc0 ls0 ws0">(</div><div class="t m0 x38 h2 y97 ffc fs0 fc0 sc0 ls0 ws0">x; y</div><div class="t m0 xaa h2 y97 ff8 fs0 fc0 sc0 ls0 ws0">) +</div><div class="t m0 x40 h2 y97 ffc fs0 fc0 sc0 ls0 ws0">d</div><div class="t m0 x3e h2 y97 ff8 fs0 fc0 sc0 ls0 ws0">(</div><div class="t m0 xab h2 y97 ffc fs0 fc0 sc0 ls0 ws0">y ; z</div><div class="t m0 x8e h2 y97 ff8 fs0 fc0 sc0 ls0 ws0">)</div><div class="t m0 x9f h2 y97 ff10 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 xa0 h2 y97 ffc fs0 fc0 sc0 ls0 ws0">d</div><div class="t m0 x7a h2 y97 ff8 fs0 fc0 sc0 ls0 ws0">(</div><div class="t m0 xac h2 y97 ffc fs0 fc0 sc0 ls0 ws0">x; z</div><div class="t m0 xad h2 y97 ff8 fs0 fc0 sc0 ls0 ws0">)). The rst prop erty is natural for any similarity measure.</div><div class="t m0 xc h2 y98 ff8 fs0 fc0 sc0 ls0 ws0">The second prop erty is valid for most commonly-used similarity measures (e.g., Euclidean distance,</div><div class="t m0 xc h2 y99 ffc fs0 fc0 sc0 ls0 ws0">L</div><div class="t m0 xae h2 y9a ffe fs0 fc0 sc0 ls0 ws0">1</div><div class="t m0 xaf h2 y99 ff8 fs0 fc0 sc0 ls0 ws0">norm,</div><div class="t m0 xb0 h2 y99 ffc fs0 fc0 sc0 ls0 ws0">L</div><div class="t m0 xb1 h2 y9a ff3 fs0 fc0 sc0 ls0 ws0">1</div><div class="t m0 xb2 h2 y99 ff8 fs0 fc0 sc0 ls0 ws0">norm), and for other measures it holds in an approximate sense (e.g.,</div><div class="t m0 x91 h2 y99 ffc fs0 fc0 sc0 ls0 ws0">d</div><div class="t m0 xb3 h2 y99 ff8 fs0 fc0 sc0 ls0 ws0">(</div><div class="t m0 x64 h2 y99 ffc fs0 fc0 sc0 ls0 ws0">x; y</div><div class="t m0 xb4 h2 y99 ff8 fs0 fc0 sc0 ls0 ws0">) +</div><div class="t m0 x1b h2 y99 ffc fs0 fc0 sc0 ls0 ws0">d</div><div class="t m0 x1c h2 y99 ff8 fs0 fc0 sc0 ls0 ws0">(</div><div class="t m0 x84 h2 y99 ffc fs0 fc0 sc0 ls0 ws0">y ; z</div><div class="t m0 xb5 h2 y99 ff8 fs0 fc0 sc0 ls0 ws0">)</div><div class="t m0 x2a h2 y99 ff10 fs0 fc0 sc0 ls0 ws0"></div><div class="t m0 xb6 h2 y9b ffe fs0 fc0 sc0 ls0 ws0">1</div><div class="t m0 xb6 h2 y9c ffe fs0 fc0 sc0 ls0 ws0">2</div><div class="t m0 xb7 h2 y9d ffc fs0 fc0 sc0 ls0 ws0">d</div><div class="t m0 x12 h2 y9d ff8 fs0 fc0 sc0 ls0 ws0">(</div><div class="t m0 xf h2 y9d ffc fs0 fc0 sc0 ls0 ws0">x; z</div><div class="t m0 xb8 h2 y9d ff8 fs0 fc0 sc0 ls0 ws0">)). An approximate triangle inequality is sucient for our purp oses and will enable us to prove</div><div class="t m0 xc h2 y9e ff8 fs0 fc0 sc0 ls0 ws0">bounds on the p erformance of our algorithms, p ossibly with some increase in the constant factors. As</div><div class="t m0 xc h2 y9f ff8 fs0 fc0 sc0 ls0 ws0">will b e clear from our experiments, the actual performance of our algorithms is very close to optimal,</div><div class="t m0 xc h2 ya0 ff8 fs0 fc0 sc0 ls0 ws0">even when the provable constants are large.</div><div class="t m0 xf h2 ya1 ff8 fs0 fc0 sc0 ls0 ws0">In some domains, such as real space with the Euclidean metric, we can relax the restriction that</div><div class="t m0 xc h2 ya2 ffc fs0 fc0 sc0 ls0 ws0">C</div><div class="t m0 x12 h2 ya2 ff8 fs0 fc0 sc0 ls0 ws0">must b e a subset of</div><div class="t m0 xb9 h2 ya2 ffc fs0 fc0 sc0 ls0 ws0">N</div><div class="t m0 xba h2 ya2 ff8 fs0 fc0 sc0 ls0 ws0">, and instead allow the medians to b e chosen from some larger set.</div><div class="t m0 xf h2 ya3 ff8 fs0 fc0 sc0 ls0 ws0">We now turn to a closely-related problem, called</div><div class="t m0 xbb h2 ya3 ff9 fs0 fc0 sc0 ls0 ws0">facility location</div><div class="t m0 xbc h2 ya3 ff8 fs0 fc0 sc0 ls0 ws0">. The facility lo cation problem is</div><div class="t m0 xc h2 ya4 ff8 fs0 fc0 sc0 ls0 ws0">a Lagrangian relaxation of</div><div class="t m0 xab h2 ya4 ffc fs0 fc0 sc0 ls0 ws0">k</div><div class="t m0 x31 h2 ya4 ff8 fs0 fc0 sc0 ls0 ws0">{Median. We are again given</div><div class="t m0 xbd h2 ya4 ffc fs0 fc0 sc0 ls0 ws0">n</div><div class="t m0 xbe h2 ya4 ff8 fs0 fc0 sc0 ls0 ws0">data points to be group ed into clusters,</div><div class="t m0 x13 h2 ya5 ff8 fs0 fc0 sc0 ls0 ws0">5</div></div><div class="pi" data-data='{"ctm":[1.568627,0.000000,0.000000,1.568627,0.000000,0.000000]}'></div></div>