TAILIEUCHUNG - Sum-of-Squares clustering on networks

Finding p prototypes by minimizing the sum of the squared distances from a set of points to its closest prototype is a well-studied problem in clustering, data analysis and continuous location. In this note, this very same problem is addressed assuming, for the first time, that the space of possible prototype locations is a network. We develop some interesting properties of such clustering problem. We also show that optimal cluster prototypes are not necessary located at vertices of the network. | Yugoslav Journal of Operations Research 21 (2011), Number 2, 157-161 DOI: SUM-OF-SQUARES CLUSTERING ON NETWORKS Emilio CARRIZOSA Faculdad de Matemáticas, Universidad de Sevilla, Spain, ecarrizosa@ Nenad MLADENOVIĆ School of Mathematics, Brunel University-West London, UK, Raca TODOSIJEVIĆ Faculty of Mathematics, University of Belgrade, Serbia, racatodosijevic@ Received: October 2011 / Accepted: December 2011 Abstract: Finding p prototypes by minimizing the sum of the squared distances from a set of points to its closest prototype is a well-studied problem in clustering, data analysis and continuous location. In this note, this very same problem is addressed assuming, for the first time, that the space of possible prototype locations is a network. We develop some interesting properties of such clustering problem. We also show that optimal cluster prototypes are not necessary located at vertices of the network. Keywords: Networks, clustering, location, p-Median. MSC: 90C35, 90C30. 1. INTRODUCTION Let N (V , E ) be a connected and undirected network with a node set V and an edge set E . Each edge is represented by its endpoints and its length. Let x be a point on an edge, then its location is determined by its distance from a prescribed endpoint of that edge. If an edge has endpoints (u, v) and length l, then any real number x ∈ [0,l] denotes the location in that edge for which the length of sub-edge [u, x] is x . For any two points x and y in N , let d ( x, y ) denote the length of a shortest path connecting x and y. For 158 E. Carrizosa, N. Mladenović, R. Todosijević / Sum-Of-Squares Clustering any nonempty finite set P of points, let d ( x, P ) denote the minimum distance from x to P , d ( x, P ) = min {d ( x, p) : p ∈ P} (1) Consider a set P of p locations for prototypes on a network N and suppose that the cardinality of the set V is equal to n. Let each vertex x i ∈ V has .

• Kỹ thuật lập trình
• Sum of the squared distances
• Well studied problem
• Clustering problem
• Vertices of the network
• Data analysis
• Goal Seek
• Data Tables
• Scenarios
• Excel Data Analysis Tools
• Excel Data Analysis Functions
• Excel Data Analysis Resources
• Data mining
• Lecture Data mining and analysis
• Khai thác dữ liệu
• Data analysis foundations
• Frequent pattern mining
• Graph data
• High dimensional data
• Linear discriminant analysis
• Numeric attributes
• Categorical attributes
• Kernel methods
• Dimensionality reduction
• Itemset mining
• Summarizing itemsets
• Sequence mining
• Graph pattern mining
• Rule assessment
• Representative based clustering
• Hierarchical clustering
• Density based clustering
• Graph clustering
• Clustering validation
• Probabilistic classification
• Decision tree classifier
• Support vector machines