<?xml version="1.0" encoding="UTF-8"?>
 <rdf:RDF xmlns="http://purl.org/rss/1.0/" xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:taxo="http://purl.org/rss/1.0/modules/taxonomy/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:cc="http://web.resource.org/cc/" xmlns:syn="http://purl.org/rss/1.0/modules/syndication/" xmlns:admin="http://webns.net/mvcb/">
  <channel rdf:about="http://pinboard.in">
    <title>Pinboard (cshalizi)</title>
    <link>https://pinboard.in/u:cshalizi/public/</link>
    <description>recent bookmarks from cshalizi</description>
    <items>
      <rdf:Seq>	<rdf:li rdf:resource="https://arxiv.org/abs/2306.09335"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2305.05465"/>
	<rdf:li rdf:resource="https://www.pnas.org/content/119/4/e2003634119"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2107.07489"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2107.14677"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2009.04096"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2107.03684"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2106.02589"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2003.00381"/>
	<rdf:li rdf:resource="https://projecteuclid.org/euclid.aos/1611889238"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2101.08334"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2101.01908"/>
	<rdf:li rdf:resource="https://journals.aps.org/pre/abstract/10.1103/PhysRevE.103.012105"/>
	<rdf:li rdf:resource="https://projecteuclid.org/euclid.aos/1607677244"/>
	<rdf:li rdf:resource="https://www.cambridge.org/9781108477444"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1909.10832"/>
	<rdf:li rdf:resource="https://projecteuclid.org/euclid.ejs/1576119710"/>
	<rdf:li rdf:resource="https://ieeexplore.ieee.org/document/9159654"/>
	<rdf:li rdf:resource="https://ieeexplore.ieee.org/document/9136791"/>
	<rdf:li rdf:resource="https://doi.org/10.1111/sjos.12450"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/2001.01987"/>
	<rdf:li rdf:resource="http://proceedings.mlr.press/v54/hong17a.html"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1902.10288"/>
	<rdf:li rdf:resource="https://www.nature.com/articles/s41586-019-1816-9"/>
	<rdf:li rdf:resource="https://www.mitpressjournals.org/doi/full/10.1162/neco_a_01229"/>
	<rdf:li rdf:resource="https://ieeexplore.ieee.org/document/8758223"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1910.06943"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1910.04939"/>
	<rdf:li rdf:resource="https://www.tandfonline.com/doi/full/10.1080/10618600.2019.1647846"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1909.09370"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1909.06511"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1908.09946"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1908.07031"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1708.05254"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1908.01794"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1908.01039"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1907.07582"/>
	<rdf:li rdf:resource="https://www.cambridge.org/9781108494205"/>
	<rdf:li rdf:resource="https://arxiv.org/abs/1903.08125"/>
	<rdf:li rdf:resource="http://lanl.arxiv.org/abs/1802.04397"/>
	<rdf:li rdf:resource="http://science.sciencemag.org/content/353/6295/163"/>
	<rdf:li rdf:resource="http://www.pnas.org/content/113/42/11943.abstract"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1507.05910"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1507.02284"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1507.03194"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1507.06352"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1506.05900"/>
	<rdf:li rdf:resource="http://link.springer.com/article/10.1007/BF01200757"/>
	<rdf:li rdf:resource="http://www.genetics.org/content/155/2/945.short"/>
	<rdf:li rdf:resource="http://paintmychromosomes.blogspot.com/2014/06/what-did-we-learn-from-rosenberg-et-al.html"/>
	<rdf:li rdf:resource="http://www.jstor.org/stable/270873"/>
	<rdf:li rdf:resource="http://jmlr.org/papers/v15/coviello14a.html"/>
	<rdf:li rdf:resource="http://www.mitpressjournals.org/doi/abs/10.1162/NECO_a_00547"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1401.0871"/>
	<rdf:li rdf:resource="http://link.springer.com/article/10.1007/s10618-013-0312-3"/>
	<rdf:li rdf:resource="http://link.springer.com/article/10.1007/s10618-013-0317-y"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1301.6647"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1312.3790"/>
	<rdf:li rdf:resource="http://jmlr.org/papers/v14/lewis13a.html"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1311.1903"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1310.4249"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1310.4210"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1307.5339"/>
	<rdf:li rdf:resource="http://www.tandfonline.com/doi/abs/10.1080/01621459.2012.760458#.UdRPpRbPUlM"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1306.2194"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1305.6228"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1305.5879"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1305.4757"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1304.6478"/>
	<rdf:li rdf:resource="http://arxiv.org/abs/1304.3432"/>
      </rdf:Seq>
    </items>
  </channel><item rdf:about="https://arxiv.org/abs/2306.09335">
    <title>[2306.09335] Class-Conditional Conformal Prediction With Many Classes</title>
    <dc:date>2023-06-28T01:20:22+00:00</dc:date>
    <link>https://arxiv.org/abs/2306.09335</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Standard conformal prediction methods provide a marginal coverage guarantee, which means that for a random test point, the conformal prediction set contains the true label with a user-chosen probability. In many classification problems, we would like to obtain a stronger guarantee -- that for test points of a specific class, the prediction set contains the true label with the same user-chosen probability. Existing conformal prediction methods do not work well when there is a limited amount of labeled data per class, as is often the case in real applications where the number of classes is large. We propose a method called clustered conformal prediction, which clusters together classes that have "similar" conformal scores and then performs conformal prediction at the cluster level. Based on empirical evaluation across four image data sets with many (up to 1000) classes, we find that clustered conformal typically outperforms existing methods in terms of class-conditional coverage and set size metrics."]]></description>
<dc:subject>conformal_prediction tibshirani.ryan jordan.michael_i. clustering in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:3cdcb7591f00/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:conformal_prediction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:tibshirani.ryan"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:jordan.michael_i."/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2305.05465">
    <title>[2305.05465] The emergence of clusters in self-attention dynamics</title>
    <dc:date>2023-05-13T17:46:24+00:00</dc:date>
    <link>https://arxiv.org/abs/2305.05465</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Viewing Transformers as interacting particle systems, we describe the geometry of learned representations when the weights are not time dependent. We show that particles, representing tokens, tend to cluster toward particular limiting objects as time tends to infinity. The type of limiting object that emerges depends on the spectrum of the value matrix. Additionally, in the one-dimensional case we prove that the self-attention matrix converges to a low-rank Boolean matrix. The combination of these results mathematically confirms the empirical observation made by Vaswani et al. \cite{vaswani2017attention} that \emph{leaders} appear in a sequence of tokens when processed by Transformers."]]></description>
<dc:subject>in_NB large_language_models_(so_called) interacting_particle_systems clustering !!! to_read rigollet.philippe via:mraginsky re:large_language_models_in_statistical_perspective</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:a4cab6cd76f9/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:large_language_models_(so_called)"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:interacting_particle_systems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:!!!"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:rigollet.philippe"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:via:mraginsky"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:large_language_models_in_statistical_perspective"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://www.pnas.org/content/119/4/e2003634119">
    <title>A social perspective on perceived distances reveals deep community structure | PNAS</title>
    <dc:date>2022-01-31T14:25:30+00:00</dc:date>
    <link>https://www.pnas.org/content/119/4/e2003634119</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Community structure, including relationships between and within groups, is foundational to our understanding of the world around us. For dissimilarity-based data, leveraging social concepts of conflict and alignment, we provide an approach for capturing meaningful structural information resulting from induced local comparisons. In particular, a measure of local (community) depth is introduced that leads directly to a probabilistic partitioning conveying locally interpreted closeness (or cohesion). A universal choice of threshold for distinguishing strongly and weakly cohesive pairs permits consideration of both local and global structure. Cases in which one might benefit from use of the approach include data with varying density such as that arising as snapshots of complex processes in which differing mechanisms drive evolution locally. The inherent recalibrating in response to density allows one to sidestep the need for localizing parameters, common to many existing methods. Mathematical results together with applications in linguistics, cultural psychology, and genetics, as well as to benchmark clustering data have been included. Together, these demonstrate how meaningful community structure can be identified without additional inputs (e.g., number of clusters or neighborhood size), optimization criteria, iterative procedures, or distributional assumptions."

--- So, using community-discovery algorithms to do clustering?]]></description>
<dc:subject>to:NB clustering community_discovery</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:10c700d57f3f/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:community_discovery"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2107.07489">
    <title>[2107.07489] Clustering of heterogeneous populations of networks</title>
    <dc:date>2021-08-11T18:42:50+00:00</dc:date>
    <link>https://arxiv.org/abs/2107.07489</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Statistical methods for reconstructing networks from repeated measurements typically assume that all measurements are generated from the same underlying network structure. This need not be the case, however. People's social networks might be different on weekdays and weekends, for instance. Brain networks may differ between healthy patients and those with dementia or other conditions. Here we describe a Bayesian analysis framework for such data that allows for the fact that network measurements may be reflective of multiple possible structures. We define a finite mixture model of the measurement process and derive a fast Gibbs sampling procedure that samples exactly from the full posterior distribution of model parameters. The end result is a clustering of the measured networks into groups with similar structure. We demonstrate the method on both real and synthetic network populations."]]></description>
<dc:subject>in_NB clustering network_data_analysis re:network_differences newman.mark kith_and_kin statistics</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:15a8e80b2b7b/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:network_differences"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:newman.mark"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:kith_and_kin"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2107.14677">
    <title>[2107.14677] Inference for Dependent Data with Learned Clusters</title>
    <dc:date>2021-08-03T04:44:31+00:00</dc:date>
    <link>https://arxiv.org/abs/2107.14677</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["This paper presents and analyzes an approach to cluster-based inference for dependent data. The primary setting considered here is with spatially indexed data in which the dependence structure of observed random variables is characterized by a known, observed dissimilarity measure over spatial indices. Observations are partitioned into clusters with the use of an unsupervised clustering algorithm applied to the dissimilarity measure. Once the partition into clusters is learned, a cluster-based inference procedure is applied to a statistical hypothesis testing procedure. The procedure proposed in the paper allows the number of clusters to depend on the data, which gives researchers a principled method for choosing an appropriate clustering level. The paper gives conditions under which the proposed procedure asymptotically attains correct size. A simulation study shows that the proposed procedure attains near nominal size in finite samples in a variety of statistical testing problems with dependent data."]]></description>
<dc:subject>to:NB spatial_statistics clustering network_data_analysis to_read statistics</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:a2dcdacdd605/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:spatial_statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2009.04096">
    <title>[2009.04096] A Joint MLE Approach to Large-Scale Structured Latent Attribute Analysis</title>
    <dc:date>2021-07-12T15:32:33+00:00</dc:date>
    <link>https://arxiv.org/abs/2009.04096</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Structured Latent Attribute Models (SLAMs) are a family of discrete latent variable models widely used in education, psychology, and epidemiology to model multivariate categorical data. A SLAM assumes that multiple discrete latent attributes explain the dependence of observed variables in a highly structured fashion. Usually, the maximum marginal likelihood estimation approach is adopted for SLAMs, treating the latent attributes as random effects. The increasing scope of modern assessment data involves large numbers of observed variables and high-dimensional latent attributes. This poses challenges to classical estimation methods and requires new methodology and understanding of latent variable modeling. Motivated by this, we consider the joint maximum likelihood estimation (MLE) approach to SLAMs, treating latent attributes as fixed unknown parameters. We investigate estimability, consistency, and computation in the regime where sample size, number of variables, and number of latent attributes all can diverge. We establish the statistical consistency of the joint MLE and propose efficient algorithms that scale well to large-scale data for several popular SLAMs. Simulation studies demonstrate the superior empirical performance of the proposed methods. An application to real data from an international educational assessment gives interpretable findings of cognitive diagnosis."]]></description>
<dc:subject>to:NB mixture_models clustering inference_to_latent_objects likelihood psychometrics statistics</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:be792de6fa63/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:mixture_models"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:inference_to_latent_objects"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:likelihood"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:psychometrics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2107.03684">
    <title>[2107.03684] Assigning Topics to Documents by Successive Projections</title>
    <dc:date>2021-07-09T14:32:11+00:00</dc:date>
    <link>https://arxiv.org/abs/2107.03684</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Topic models provide a useful tool to organize and understand the structure of large corpora of text documents, in particular, to discover hidden thematic structure. Clustering documents from big unstructured corpora into topics is an important task in various areas, such as image analysis, e-commerce, social networks, population genetics. A common approach to topic modeling is to associate each topic with a probability distribution on the dictionary of words and to consider each document as a mixture of topics. Since the number of topics is typically substantially smaller than the size of the corpus and of the dictionary, the methods of topic modeling can lead to a dramatic dimension reduction. In this paper, we study the problem of estimating topics distribution for each document in the given corpus, that is, we focus on the clustering aspect of the problem. We introduce an algorithm that we call Successive Projection Overlapping Clustering (SPOC) inspired by the Successive Projection Algorithm for separable matrix factorization. This algorithm is simple to implement and computationally fast. We establish theoretical guarantees on the performance of the SPOC algorithm, in particular, near matching minimax upper and lower bounds on its estimation risk. We also propose a new method that estimates the number of topics. We complement our theoretical results with a numerical study on synthetic and semi-synthetic data to analyze the performance of this new algorithm in practice. One of the conclusions is that the error of the algorithm grows at most logarithmically with the size of the dictionary, in contrast to what one observes for Latent Dirichlet Allocation."]]></description>
<dc:subject>to:NB topic_models text_mining tsybakov.alexandre clustering statistics</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:35ac01acf120/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:topic_models"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:text_mining"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:tsybakov.alexandre"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2106.02589">
    <title>[2106.02589] On Ensembling vs Merging: Least Squares and Random Forests under Covariate Shift</title>
    <dc:date>2021-06-08T13:55:10+00:00</dc:date>
    <link>https://arxiv.org/abs/2106.02589</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["It has been postulated and observed in practice that for prediction problems in which covariate data can be naturally partitioned into clusters, ensembling algorithms based on suitably aggregating models trained on individual clusters often perform substantially better than methods that ignore the clustering structure in the data. In this paper, we provide theoretical support to these empirical observations by asymptotically analyzing linear least squares and random forest regressions under a linear model. Our main results demonstrate that the benefit of ensembling compared to training a single model on the entire data, often termed 'merging', might depend on the underlying bias and variance interplay of the individual predictors to be aggregated. In particular, under both fixed and high dimensional linear models, we show that merging is asymptotically superior to optimal ensembling techniques for linear least squares regression due to the unbiased nature of least squares prediction. In contrast, for random forest regression under fixed dimensional linear models, our bounds imply a strict benefit of ensembling over merging. Finally, we also present numerical experiments to verify the validity of our asymptotic results across different situations."]]></description>
<dc:subject>to:NB ensemble_methods prediction clustering statistics</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:c784d0848e5a/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:ensemble_methods"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:prediction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2003.00381">
    <title>[2003.00381] Statistical power for cluster analysis</title>
    <dc:date>2021-04-22T15:32:01+00:00</dc:date>
    <link>https://arxiv.org/abs/2003.00381</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Cluster algorithms are gaining in popularity due to their compelling ability to identify discrete subgroups in data, and their increasing accessibility in mainstream programming languages and statistical software. While researchers can follow guidelines to choose the right algorithms, and to determine what constitutes convincing clustering, there are no firmly established ways of computing a priori statistical power for cluster analysis. Here, we take a simulation approach to estimate power and classification accuracy for popular analysis pipelines. We systematically varied cluster size, number of clusters, number of different features between clusters, effect size within each different feature, and cluster covariance structure in generated datasets. We then subjected these datasets to common dimensionality reduction approaches (none, multi-dimensional scaling, or uniform manifold approximation and projection) and cluster algorithms (k-means, hierarchical agglomerative clustering with Ward linkage and Euclidean distance, or average linkage and cosine distance, HDBSCAN). Furthermore, we simulated additional datasets to explore the effect of sample size and cluster separation on statistical power and classification accuracy. We found that clustering outcomes were driven by large effect sizes or the accumulation of many smaller effects across features, and were mostly unaffected by differences in covariance structure. Sufficient statistical power can be achieved with relatively small samples (N=20 per subgroup), provided cluster separation is large ({\Delta}=4). Finally, we discuss whether fuzzy clustering (c-means) could provide a more parsimonious alternative for identifying separable multivariate normal distributions, particularly those with lower centroid separation."

--- I'll be interested to see if they look at what happens when there are no clusters,...]]></description>
<dc:subject>to:NB clustering to_teach:data-mining color_me_skeptical</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:6df8375fa239/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:data-mining"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:color_me_skeptical"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://projecteuclid.org/euclid.aos/1611889238">
    <title>Amini , Razaee : Concentration of kernel matrices with application to kernel spectral clustering</title>
    <dc:date>2021-02-04T15:28:42+00:00</dc:date>
    <link>https://projecteuclid.org/euclid.aos/1611889238</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We study the concentration of random kernel matrices around their mean. We derive nonasymptotic exponential concentration inequalities for Lipschitz kernels assuming that the data points are independent draws from a class of multivariate distributions on ℝdRd, including the strongly log-concave distributions under affine transformations. A feature of our result is that the data points need not have identical distributions or zero mean, which is key in certain applications such as clustering. Our bound for the Lipschitz kernels is dimension-free and sharp up to constants. For comparison, we also derive the companion result for the Euclidean (inner product) kernel for a class of sub-Gaussian distributions. A notable difference between the two cases is that, in contrast to the Euclidean kernel, in the Lipschitz case, the concentration inequality does not depend on the mean of the underlying vectors. As an application of these inequalities, we derive a bound on the misclassification rate of a kernel spectral clustering (KSC) algorithm, under a perturbed nonparametric mixture model. We show an example where this bound establishes the high-dimensional consistency (as d→∞d→∞) of the KSC, when applied with a Gaussian kernel, to a noisy model of nested nonlinear manifolds."]]></description>
<dc:subject>kernel_methods concentration_of_measure clustering spectral_clustering random_matrices in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:539e93ef950f/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:kernel_methods"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:concentration_of_measure"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:spectral_clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:random_matrices"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2101.08334">
    <title>[2101.08334] Density-based clustering of social networks</title>
    <dc:date>2021-01-25T16:08:15+00:00</dc:date>
    <link>https://arxiv.org/abs/2101.08334</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["The idea underlying the modal formulation of density-based clustering is to associate groups with the regions around the modes of the probability density function underlying the data. This correspondence between clusters and dense regions in the sample space is here exploited to discuss an extension of this approach to the analysis of social networks. Such extension seems particularly appealing: conceptually, the notion of high-density cluster fits well the one of community in a network, regarded to as a collection of individuals with dense local ties in its neighbourhood. The lack of a probabilistic notion of density in networks is turned into a major strength of the proposed method, where node-wise measures that quantify the role and position of actors may be used to derive different community configurations. The approach allows for the identification of a hierarchical structure of clusters, which may catch different degrees of resolution of the clustering structure. This feature well fits the nature of social networks, disentangling a different involvement of individuals in social aggregations."

--- My skepticism is about whether there's really anything new here.  (Recall that the Girvan-Newman modularity, which got us in to this in the first place, is about comparing between- and within- community edges to a baseline expected under randomly re-distributed edges, i.e., a sort of density.)]]></description>
<dc:subject>to:NB network_data_analysis clustering community_discovery color_me_skeptical</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:719d5711e754/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:community_discovery"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:color_me_skeptical"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2101.01908">
    <title>[2101.01908] Factor Modelling for Clustering High-dimensional Time Series</title>
    <dc:date>2021-01-07T21:47:31+00:00</dc:date>
    <link>https://arxiv.org/abs/2101.01908</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We propose a new unsupervised learning method for clustering a large number of time series based on a latent factor structure. Each cluster is characterized by its own cluster-specific factors in addition to some common factors which impact on all the time series concerned. Our setting also offers the flexibility that some time series may not belong to any clusters. The consistency with explicit convergence rates is established for the estimation of the common factors, the cluster-specific factors, the latent clusters. Numerical illustration with both simulated data as well as a real data example is also reported. As a spin-off, the proposed new approach also advances significantly the statistical inference for the factor model of Lam and Yao (2012)."]]></description>
<dc:subject>to:NB clustering factor_analysis time_series</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:1217b18544b8/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:factor_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:time_series"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://journals.aps.org/pre/abstract/10.1103/PhysRevE.103.012105">
    <title>Phys. Rev. E 103, 012105 (2021) - Cascade of phase transitions for multiscale clustering</title>
    <dc:date>2021-01-06T17:12:22+00:00</dc:date>
    <link>https://journals.aps.org/pre/abstract/10.1103/PhysRevE.103.012105</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We present a framework exploiting the cascade of phase transitions occurring during a simulated annealing of the expectation-maximization algorithm to cluster datasets with multiscale structures. Using the weighted local covariance, we can extract, a posteriori and without any prior knowledge, information on the number of clusters at different scales together with their size. We also study the linear stability of the iterative scheme to derive the threshold at which the first transition occurs and show how to approximate the next ones. Finally, we combine simulated annealing together with recent developments of regularized Gaussian mixture models to learn a principal graph from spatially structured datasets that can also exhibit many scales."]]></description>
<dc:subject>to:NB clustering phase_transitions</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:87aad9991361/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:phase_transitions"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://projecteuclid.org/euclid.aos/1607677244">
    <title>Sanders , Proutière , Yun : Clustering in Block Markov Chains</title>
    <dc:date>2020-12-11T17:26:24+00:00</dc:date>
    <link>https://projecteuclid.org/euclid.aos/1607677244</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["This paper considers cluster detection in Block Markov Chains (BMCs). These Markov chains are characterized by a block structure in their transition matrix. More precisely, the nn possible states are divided into a finite number of KK groups or clusters, such that states in the same cluster exhibit the same transition rates to other states. One observes a trajectory of the Markov chain, and the objective is to recover, from this observation only, the (initially unknown) clusters. In this paper, we devise a clustering procedure that accurately, efficiently and provably detects the clusters. We first derive a fundamental information-theoretical lower bound on the detection error rate satisfied under any clustering algorithm. This bound identifies the parameters of the BMC, and trajectory lengths, for which it is possible to accurately detect the clusters. We next develop two clustering algorithms that can together accurately recover the cluster structure from the shortest possible trajectories, whenever the parameters allow detection. These algorithms thus reach the fundamental detectability limit, and are optimal in that sense."]]></description>
<dc:subject>to:NB markov_models statistical_inference_for_stochastic_processes clustering statistics</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:7c12332b27bd/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:markov_models"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistical_inference_for_stochastic_processes"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://www.cambridge.org/9781108477444">
    <title>Small summaries for big data | Knowledge management, databases and data mining | Cambridge University Press</title>
    <dc:date>2020-11-30T17:32:10+00:00</dc:date>
    <link>https://www.cambridge.org/9781108477444</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["The massive volume of data generated in modern applications can overwhelm our ability to conveniently transmit, store, and index it. For many scenarios, building a compact summary of a dataset that is vastly smaller enables flexibility and efficiency in a range of queries over the data, in exchange for some approximation. This comprehensive introduction to data summarization, aimed at practitioners and students, showcases the algorithms, their behavior, and the mathematical underpinnings of their operation. The coverage starts with simple sums and approximate counts, building to more advanced probabilistic structures such as the Bloom Filter, distinct value summaries, sketches, and quantile summaries. Summaries are described for specific types of data, such as geometric data, graphs, and vectors and matrices. The authors offer detailed descriptions of and pseudocode for key algorithms that have been incorporated in systems from companies such as Google, Apple, Microsoft, Netflix and Twitter."]]></description>
<dc:subject>to:NB books:noted random_projections locality-sensitive_hashing dimension_reduction clustering data_mining computational_statistics to_teach:data-mining books:in_library books:have_suggested_to_library downloaded re:codename:catherine_wheel</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:8fb436ef1b8f/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:books:noted"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:random_projections"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:locality-sensitive_hashing"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:dimension_reduction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:data_mining"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:computational_statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:data-mining"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:books:in_library"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:books:have_suggested_to_library"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:downloaded"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:codename:catherine_wheel"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1909.10832">
    <title>[1909.10832] High-dimensional clustering via Random Projections</title>
    <dc:date>2020-11-25T14:19:10+00:00</dc:date>
    <link>https://arxiv.org/abs/1909.10832</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["In this work, we address the unsupervised classification issue by exploiting the general idea of Random Projection Ensemble. Specifically, we propose to generate a set of low dimensional independent random projections and to perform model-based clustering on each of them. The top B∗ projections, i.e. the projections which show the best grouping structure are then retained. The final partition is obtained by aggregating the clusters found in the projections via consensus. The performances of the method are assessed on both real and simulated datasets. The obtained results suggest that the proposal represents a promising tool for high-dimensional clustering."]]></description>
<dc:subject>to:NB clustering random_projections data_mining</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:814eb4c5041a/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:random_projections"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:data_mining"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://projecteuclid.org/euclid.ejs/1576119710">
    <title>Verdinelli , Wasserman : Hybrid Wasserstein distance and fast distribution clustering</title>
    <dc:date>2020-11-16T16:12:38+00:00</dc:date>
    <link>https://projecteuclid.org/euclid.ejs/1576119710</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We define a modified Wasserstein distance for distribution clustering which inherits many of the properties of the Wasserstein distance but which can be estimated easily and computed quickly. The modified distance is the sum of two terms. The first term — which has a closed form — measures the location-scale differences between the distributions. The second term is an approximation that measures the remaining distance after accounting for location-scale differences. We consider several forms of approximation with our main emphasis being a tangent space approximation that can be estimated using nonparametric regression and leads to fast and easy computation of barycenters which otherwise would be very difficult to compute. We evaluate the strengths and weaknesses of this approach on simulated and real examples."]]></description>
<dc:subject>to:NB probability statistics clustering kith_and_kin wasserman.larry verdinelli.isa heard_the_talk</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:105837eab23d/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:probability"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:kith_and_kin"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:wasserman.larry"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:verdinelli.isa"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:heard_the_talk"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://ieeexplore.ieee.org/document/9159654">
    <title>Is Clustering Advantageous in Statistical Ill-Posed Linear Inverse Problems? - IEEE Journals &amp; Magazine</title>
    <dc:date>2020-11-16T16:09:39+00:00</dc:date>
    <link>https://ieeexplore.ieee.org/document/9159654</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["In many statistical linear inverse problems, one needs to recover classes of similar objects from their noisy images under an operator that does not have a bounded inverse. Problems of this kind appear in many areas of application. Routinely, in such problems clustering is carried out at a pre-processing step and then the inverse problem is solved for each of the cluster averages separately. As a result, the errors of the procedures are usually examined for the estimation step only. The objective of this paper is to examine, both theoretically and via simulations, the effect of clustering on the accuracy of the solutions of general ill-posed linear inverse problems. In particular, we assume that one observes Xm=Afm+δϵm , m=1,⋯,M , where functions fm can be grouped into K classes and one needs to recover a vector function f=(f1,⋯,fM)T . We construct an estimator for f as a solution of a penalized optimization problem which corresponds to the clustering before estimation setting. We derive an oracle inequality for its precision and confirm that the estimator is minimax optimal or nearly minimax optimal up to a logarithmic factor of the number of observations. One of the advantages of our approach is that we do not assume that the number of clusters is known in advance. Subsequently, we compare the accuracy of the above procedure with the precision of estimation without clustering, and clustering following the recovery of each of the unknown functions separately. We conclude that clustering at the pre-processing step is beneficial when the problem is moderately ill-posed. It should be applied with extreme care when the problem is severely ill-posed."]]></description>
<dc:subject>to:NB clustering inverse_problems statistics</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:f30dcf739c31/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:inverse_problems"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://ieeexplore.ieee.org/document/9136791">
    <title>&lt;italic&gt;k&lt;/italic&gt;-Vectors: An Alternating Minimization Algorithm for Learning Regression Functions - IEEE Journals &amp; Magazine</title>
    <dc:date>2020-11-16T16:08:36+00:00</dc:date>
    <link>https://ieeexplore.ieee.org/document/9136791</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["The k -vectors algorithm for learning regression functions proposed here is akin to the well-known k -means algorithm. Both algorithms partition the feature space, but unlike the k -means algorithm, the k -vectors algorithm aims to reconstruct the response rather than the feature. The partitioning rule of the algorithm is based on maximizing the correlation (inner product) of the feature vector with a set of k vectors, and generates polyhedral cells, similar to the ones generated by the nearest-neighbor rule of the k -means algorithm. Similarly to k -means, the learning algorithm alternates between two types of steps. In the first type of steps, k labels are determined via a centroid-type rule (in the response space), which uses a surrogate hinge-type loss function to the mean squared error loss function. In the second type of steps, the k vectors which determine the partition are updated according to a multiclass classification rule, in the spirit of support vector machines. It is proved that both steps of the algorithm only require solving convex optimization problems, and that the algorithm is empirically consistent - as the length of the training sequence increases to infinity, fixed-points of the empirical version of the algorithm tend to fixed points of the population version of the algorithm. Learnability of the predictor class posit by the algorithm is also established."]]></description>
<dc:subject>to:NB clustering regression nonparametrics statistics k-means nearest_neighbors to_read</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:fd9acdc3e960/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:regression"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:nonparametrics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:k-means"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:nearest_neighbors"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://doi.org/10.1111/sjos.12450">
    <title>Clustering with statistical error control - Vogt - - Scandinavian Journal of Statistics - Wiley Online Library</title>
    <dc:date>2020-11-15T20:51:15+00:00</dc:date>
    <link>https://doi.org/10.1111/sjos.12450</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["This article presents a clustering approach that allows for rigorous statistical error control similar to a statistical test. We develop estimators for both the unknown number of clusters and the clusters themselves. The estimators depend on a tuning parameter α which is similar to the significance level of a statistical hypothesis test. By choosing α, one can control the probability of overestimating the true number of clusters, while the probability of underestimation is asymptotically negligible. In addition, the probability that the estimated clusters differ from the true ones is controlled. In the theoretical part of the article, formal versions of these statements on statistical error control are derived in a baseline model with convex clusters. A simulation study and two applications to temperature and gene expression microarray data complement the theoretical analysis."]]></description>
<dc:subject>to:NB clustering hypothesis_testing statistics to_read to_teach:data-mining</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:c79397a7e54a/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:hypothesis_testing"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:data-mining"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/2001.01987">
    <title>[2001.01987] Softmax-based Classification is k-means Clustering: Formal Proof, Consequences for Adversarial Attacks, and Improvement through Centroid Based Tailoring</title>
    <dc:date>2020-03-18T17:56:52+00:00</dc:date>
    <link>https://arxiv.org/abs/2001.01987</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We formally prove the connection between k-means clustering and the predictions of neural networks based on the softmax activation layer. In existing work, this connection has been analyzed empirically, but it has never before been mathematically derived. The softmax function partitions the transformed input space into cones, each of which encompasses a class. This is equivalent to putting a number of centroids in this transformed space at equal distance from the origin, and k-means clustering the data points by proximity to these centroids. Softmax only cares in which cone a data point falls, and not how far from the centroid it is within that cone. We formally prove that networks with a small Lipschitz modulus (which corresponds to a low susceptibility to adversarial attacks) map data points closer to the cluster centroids, which results in a mapping to a k-means-friendly space. To leverage this knowledge, we propose Centroid Based Tailoring as an alternative to the softmax function in the last layer of a neural network. The resulting Gauss network has similar predictive accuracy as traditional networks, but is less susceptible to one-pixel attacks; while the main contribution of this paper is theoretical in nature, the Gauss network contributes empirical auxiliary benefits."]]></description>
<dc:subject>to:NB neural_networks classifiers clustering k-means adversarial_examples via:arsyed</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:1f1d75e91ff6/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:neural_networks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:classifiers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:k-means"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:adversarial_examples"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:via:arsyed"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://proceedings.mlr.press/v54/hong17a.html">
    <title>High-dimensional Time Series Clustering via Cross-Predictability</title>
    <dc:date>2020-02-16T16:28:47+00:00</dc:date>
    <link>http://proceedings.mlr.press/v54/hong17a.html</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["The key to time series clustering is how to characterize the similarity between any two time series. In this paper, we explore a new similarity metric called “cross-predictability”: the degree to which a future value in each time series is predicted by past values of the others. However, it is challenging to estimate such cross-predictability among time series in the high-dimensional regime, where the number of time series is much larger than the length of each time series. We address this challenge with a sparsity assumption: only time series in the same cluster have significant cross-predictability with each other. We demonstrate that this approach is computationally attractive, and provide a theoretical proof that the proposed algorithm will identify the correct clustering structure with high probability under certain conditions. To the best of our knowledge, this is the first practical high-dimensional time series clustering algorithm with a provable guarantee. We evaluate with experiments on both synthetic data and real-world data, and results indicate that our method can achieve more than 80% clustering accuracy on real-world data, which is 20% higher than the state-of-art baselines."

--- But, but, but... Schreiber (1997)! I repeat, (1997)!]]></description>
<dc:subject>to:NB time_series clustering statistics via:vaguery color_me_skeptical</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:22dc14dd624e/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:time_series"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:via:vaguery"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:color_me_skeptical"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1902.10288">
    <title>[1902.10288] Clustering, factor discovery and optimal transport</title>
    <dc:date>2020-01-31T00:20:49+00:00</dc:date>
    <link>https://arxiv.org/abs/1902.10288</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["The clustering problem, and more generally, latent factor discovery --or latent space inference-- is formulated in terms of the Wasserstein barycenter problem from optimal transport. The objective proposed is the maximization of the variability attributable to class, further characterized as the minimization of the variance of the Wasserstein barycenter. Existing theory, which constrains the transport maps to rigid translations, is extended to affine transformations. The resulting non-parametric clustering algorithms include k-means as a special case and exhibit more robust performance. A continuous version of these algorithms discovers continuous latent variables and generalizes principal curves. The strength of these algorithms is demonstrated by tests on both artificial and real-world data sets."]]></description>
<dc:subject>to:NB clustering factor_analysis inference_to_latent_objects statistics</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:9c27e8511952/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:factor_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:inference_to_latent_objects"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://www.nature.com/articles/s41586-019-1816-9">
    <title>Frontal cortex neuron types categorically encode single decision variables | Nature</title>
    <dc:date>2019-12-06T15:36:09+00:00</dc:date>
    <link>https://www.nature.com/articles/s41586-019-1816-9</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Individual neurons in many cortical regions have been found to encode specific, identifiable features of the environment or body that pertain to the function of the region1,2,3. However, in frontal cortex, which is involved in cognition, neural responses display baffling complexity, carrying seemingly disordered mixtures of sensory, motor and other task-related variables4,5,6,7,8,9,10,11,12,13. This complexity has led to the suggestion that representations in individual frontal neurons are randomly mixed and can only be understood at the neural population level14,15. Here we show that neural activity in rat orbitofrontal cortex (OFC) is instead highly structured: single neuron activity co-varies with individual variables in computational models that explain choice behaviour. To characterize neural responses across a large behavioural space, we trained rats on a behavioural task that combines perceptual and value-guided decisions. An unbiased, model-free clustering analysis identified distinct groups of OFC neurons, each with a particular response profile in task-variable space. Applying a simple model of choice behaviour to these categorical response profiles revealed that each profile quantitatively corresponds to a specific decision variable, such as decision confidence. Additionally, we demonstrate that a connectivity-defined cell type, orbitofrontal neurons projecting to the striatum, carries a selective and temporally sustained representation of a single decision variable: integrated value. We propose that neurons in frontal cortex, as in other cortical regions, form a sparse and overcomplete representation of features relevant to the region’s function, and that they distribute this information selectively to downstream regions to support behaviour."

--- "unbiased, model-free clustering"?!?]]></description>
<dc:subject>to:NB neuroscience decision-making neural_coding_and_decoding clustering</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:f612847d10cc/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:neuroscience"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:decision-making"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:neural_coding_and_decoding"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://www.mitpressjournals.org/doi/full/10.1162/neco_a_01229">
    <title>Capturing the Forest but Missing the Trees: Microstates Inadequate for Characterizing Shorter-Scale EEG Dynamics | Neural Computation | MIT Press Journals</title>
    <dc:date>2019-10-24T14:52:17+00:00</dc:date>
    <link>https://www.mitpressjournals.org/doi/full/10.1162/neco_a_01229</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["The brain is known to be active even when not performing any overt cognitive tasks, and often it engages in involuntary mind wandering. This resting state has been extensively characterized in terms of fMRI-derived brain networks. However, an alternate method has recently gained popularity: EEG microstate analysis. Proponents of microstates postulate that the brain discontinuously switches between four quasi-stable states defined by specific EEG scalp topologies at peaks in the global field potential (GFP). These microstates are thought to be “atoms of thought,” involved with visual, auditory, salience, and attention processing. However, this method makes some major assumptions by excluding EEG data outside the GFP peaks and then clustering the EEG scalp topologies at the GFP peaks, assuming that only one microstate is active at any given time. This study explores the evidence surrounding these assumptions by studying the temporal dynamics of microstates and its clustering space using tools from dynamical systems analysis, fractal, and chaos theory to highlight the shortcomings in microstate analysis. The results show evidence of complex and chaotic EEG dynamics outside the GFP peaks, which is being missed by microstate analysis. Furthermore, the winner-takes-all approach of only one microstate being active at a time is found to be inadequate since the dynamic EEG scalp topology does not always resemble that of the assigned microstate, and there is competition among the different microstate classes. Finally, clustering space analysis shows that the four microstates do not cluster into four distinct and separable clusters. Taken collectively, these results show that the discontinuous description of EEG microstates is inadequate when looking at nonstationary short-scale EEG dynamics."]]></description>
<dc:subject>to:NB clustering neuroscience neural_data_analysis</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:f94e5139fbe1/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:neuroscience"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:neural_data_analysis"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://ieeexplore.ieee.org/document/8758223">
    <title>The Informativeness of $k$-Means for Learning Mixture Models - IEEE Journals &amp; Magazine</title>
    <dc:date>2019-10-24T14:29:44+00:00</dc:date>
    <link>https://ieeexplore.ieee.org/document/8758223</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["The learning of mixture models can be viewed as a clustering problem. Indeed, given data samples independently generated from a mixture of distributions, we often would like to find the correct target clustering of the samples according to which component distribution they were generated from. For a clustering problem, practitioners often choose to use the simple $k$ -means algorithm. $k$ -means attempts to find an optimal clustering which minimizes the sum-of-squares distance between each point and its cluster center. In this paper, we consider fundamental (i.e., information-theoretic) limits of the solutions (clusterings) obtained by optimizing the sum-of-squares distance. In particular, we provide sufficient conditions for the closeness of any optimal clustering and the correct target clustering assuming that the data samples are generated from a mixture of spherical Gaussian distributions. We also generalize our results to log-concave distributions. Moreover, we show that under similar or even weaker conditions on the mixture model, any optimal clustering for the samples with reduced dimensionality is also close to the correct target clustering. These results provide intuition for the informativeness of $k$ -means (with and without dimensionality reduction) as an algorithm for learning mixture models."]]></description>
<dc:subject>to:NB k-means clustering mixture_models to_teach:data-mining</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:67fc5d172f77/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:k-means"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:mixture_models"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:data-mining"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1910.06943">
    <title>[1910.06943] The Local Elasticity of Neural Networks</title>
    <dc:date>2019-10-16T15:51:32+00:00</dc:date>
    <link>https://arxiv.org/abs/1910.06943</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["This paper presents a phenomenon in neural networks that we refer to as \textit{local elasticity}. Roughly speaking, a classifier is said to be locally elastic if its prediction at a feature vector $\bx'$ is \textit{not} significantly perturbed, after the classifier is updated via stochastic gradient descent at a (labeled) feature vector $\bx$ that is \textit{dissimilar} to $\bx'$ in a certain sense. This phenomenon is shown to persist for neural networks with nonlinear activation functions through extensive simulations on real-life and synthetic datasets, whereas this is not observed in linear classifiers. In addition, we offer a geometric interpretation of local elasticity using the neural tangent kernel \citep{jacot2018neural}. Building on top of local elasticity, we obtain pairwise similarity measures between feature vectors, which can be used for clustering in conjunction with K-means. The effectiveness of the clustering algorithm on the MNIST and CIFAR-10 datasets in turn corroborates the hypothesis of local elasticity of neural networks on real-life data. Finally, we discuss some implications of local elasticity to shed light on several intriguing aspects of deep neural networks."]]></description>
<dc:subject>adversarial_examples neural_networks your_favorite_deep_neural_network_sucks clustering statistics in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:cc210569d434/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:adversarial_examples"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:neural_networks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:your_favorite_deep_neural_network_sucks"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1910.04939">
    <title>[1910.04939] Rk-means: Fast Clustering for Relational Data</title>
    <dc:date>2019-10-15T18:08:55+00:00</dc:date>
    <link>https://arxiv.org/abs/1910.04939</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Conventional machine learning algorithms cannot be applied until a data matrix is available to process. When the data matrix needs to be obtained from a relational database via a feature extraction query, the computation cost can be prohibitive, as the data matrix may be (much) larger than the total input relation size. This paper introduces Rk-means, or relational k -means algorithm, for clustering relational data tuples without having to access the full data matrix. As such, we avoid having to run the expensive feature extraction query and storing its output. Our algorithm leverages the underlying structures in relational data. It involves construction of a small {\it grid coreset} of the data matrix for subsequent cluster construction. This gives a constant approximation for the k -means objective, while having asymptotic runtime improvements over standard approaches of first running the database query and then clustering. Empirical results show orders-of-magnitude speedup, and Rk-means can run faster on the database than even just computing the data matrix."]]></description>
<dc:subject>to:NB relational_learning data_mining k-means clustering to_teach:data-mining</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:18d422e3d7fc/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:relational_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:data_mining"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:k-means"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:data-mining"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://www.tandfonline.com/doi/full/10.1080/10618600.2019.1647846">
    <title>Estimating the Number of Clusters Using Cross-Validation: Journal of Computational and Graphical Statistics: Vol 0, No 0</title>
    <dc:date>2019-10-01T16:20:36+00:00</dc:date>
    <link>https://www.tandfonline.com/doi/full/10.1080/10618600.2019.1647846</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Many clustering methods, including k-means, require the user to specify the number of clusters as an input parameter. A variety of methods have been devised to choose the number of clusters automatically, but they often rely on strong modeling assumptions. This article proposes a data-driven approach to estimate the number of clusters based on a novel form of cross-validation. The proposed method differs from ordinary cross-validation, because clustering is fundamentally an unsupervised learning problem. Simulation and real data analysis results show that the proposed method outperforms existing methods, especially in high-dimensional settings with heterogeneous or heavy-tailed noise. In a yeast cell cycle dataset, the proposed method finds a parsimonious clustering with interpretable gene groupings. Supplementary materials for this article are available online.]]></description>
<dc:subject>to:NB cross-validation clustering k-means statistics perry.patrick_o. to_read to_teach:data-mining</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:da89de164589/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:cross-validation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:k-means"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:perry.patrick_o."/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:data-mining"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1909.09370">
    <title>[1909.09370] Consensual aggregation of clusters based on Bregman divergences to improve predictive models</title>
    <dc:date>2019-09-23T14:37:06+00:00</dc:date>
    <link>https://arxiv.org/abs/1909.09370</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["A new procedure to construct predictive models in supervised learning problems by paying attention to the clustering structure of the input data is introduced. We are interested in situations where the input data consists of more than one unknown cluster, and where there exist different underlying models on these clusters. Thus, instead of constructing a single predictive model on the whole dataset, we propose to use a K-means clustering algorithm with different options of Bregman divergences, to recover the clustering structure of the input data. Then one dedicated predictive model is fit per cluster. For each divergence, we construct a simple local predictor on each observed cluster. We obtain one estimator, the collection of the K simple local predictors, per divergence, and we propose to combine them in a smart way based on a consensus idea. Several versions of consensual aggregation in both classification and regression problems are considered. A comparison of the performances of all constructed estimators on different simulated and real data assesses the excellent performance of our method. In a large variety of prediction problems, the consensual aggregation procedure outperforms all the other models."

--- Compare to Gershenfeld's old cluster-weighted modeling...]]></description>
<dc:subject>to:NB clustering regression statistics</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:b8987e96e064/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:regression"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1909.06511">
    <title>[1909.06511] A highly likely clusterable data model with no clusters</title>
    <dc:date>2019-09-18T12:51:17+00:00</dc:date>
    <link>https://arxiv.org/abs/1909.06511</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We propose a model for a dataset in ℝD that does not contain any clusters but yet is such that a projection of the points on a random one-dimensional subspace is likely to yield a clustering of the points. This model is compatible with some recent empirical observations."]]></description>
<dc:subject>to:NB clustering geometry probability random_projections data_mining</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:4312f0086079/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:geometry"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:probability"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:random_projections"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:data_mining"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1908.09946">
    <title>[1908.09946] An empirical comparison between stochastic and deterministic centroid initialisation for K-Means variations</title>
    <dc:date>2019-09-15T14:22:10+00:00</dc:date>
    <link>https://arxiv.org/abs/1908.09946</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["K-Means is one of the most used algorithms for data clustering and the usual clustering method for benchmarking. Despite its wide application it is well-known that it suffers from a series of disadvantages, such as the positions of the initial clustering centres (centroids), which can greatly affect the clustering solution. Over the years many K-Means variations and initialisations techniques have been proposed with different degrees of complexity. In this study we focus on common K-Means variations and deterministic initialisation techniques and we first show that more sophisticated initialisation methods reduce or alleviates the need of complex K-Means clustering, and secondly, that deterministic methods can achieve equivalent or better performance than stochastic methods. These conclusions are obtained through extensive benchmarking using different model data sets from various studies as well as clustering data sets."]]></description>
<dc:subject>to:NB clustering k-means data_mining to_teach:data-mining</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:2a411d4f9e54/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:k-means"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:data_mining"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:data-mining"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1908.07031">
    <title>[1908.07031] Evaluating Hierarchies through A Partially Observable Markov Decision Processes Methodology</title>
    <dc:date>2019-08-21T13:17:49+00:00</dc:date>
    <link>https://arxiv.org/abs/1908.07031</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Hierarchical clustering has been shown to be valuable in many scenarios, e.g. catalogues, biology research, image processing, and so on. Despite its usefulness to many situations, there is no agreed methodology on how to properly evaluate the hierarchies produced from different techniques, particularly in the case where ground-truth labels are unavailable. This motivates us to propose a framework for assessing the quality of hierarchical clustering allocations which covers the case of no ground-truth information. Such a quality measurement is useful, for example, to assess the hierarchical structures used by online retailer websites to display their product catalogues. Differently to all the previous measures and metrics, our framework tackles the evaluation from a decision theoretic perspective. We model the process as a bot searching stochastically for items in the hierarchy and establish a measure representing the degree to which the hierarchy supports this search. We employ the concept of Partially Observable Markov Decision Processes (POMDP) to model the uncertainty, the decision making, and the cognitive return for searchers in such a scenario. In this paper, we fully discuss the modeling details and demonstrate its application on some datasets."]]></description>
<dc:subject>to:NB clustering hierarchical_structure information_retrieval to_teach:data-mining</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:ba57f7ffe636/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:hierarchical_structure"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:information_retrieval"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:data-mining"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1708.05254">
    <title>[1708.05254] Adaptive Clustering Using Kernel Density Estimators</title>
    <dc:date>2019-08-20T15:34:14+00:00</dc:date>
    <link>https://arxiv.org/abs/1708.05254</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We derive and analyze a generic, recursive algorithm for estimating all splits in a finite cluster tree as well as the corresponding clusters. We further investigate statistical properties of this generic clustering algorithm when it receives level set estimates from a kernel density estimator. In particular, we derive finite sample guarantees, consistency, rates of convergence, and an adaptive data-driven strategy for choosing the kernel bandwidth. For these results we do not need continuity assumptions on the density such as Hölder continuity, but only require intuitive geometric assumptions of non-parametric nature."]]></description>
<dc:subject>to:NB density_estimation clustering statistics kernel_smoothing</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:360ad9210178/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:density_estimation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:kernel_smoothing"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1908.01794">
    <title>[1908.01794] Some Developments in Clustering Analysis on Stochastic Processes</title>
    <dc:date>2019-08-07T12:29:36+00:00</dc:date>
    <link>https://arxiv.org/abs/1908.01794</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We review some developments on clustering stochastic processes and come with the conclusion that asymptotically consistent clustering algorithms can be obtained when the processes are ergodic and the dissimilarity measure satisfies the triangle inequality. Examples are provided when the processes are distribution ergodic, covariance ergodic and locally asymptotically self-similar, respectively."]]></description>
<dc:subject>to:NB stochastic_processes ergodic_theory clustering</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:fbbeae07f608/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:stochastic_processes"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:ergodic_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1908.01039">
    <title>[1908.01039] Linear Dynamics: Clustering without identification</title>
    <dc:date>2019-08-06T14:45:25+00:00</dc:date>
    <link>https://arxiv.org/abs/1908.01039</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Clustering time series is a delicate task; varying lengths and temporal offsets obscure direct comparisons. A natural strategy is to learn a parametric model foreach time series and to cluster the model parameters rather than the sequences themselves. Linear dynamical systems are a fundamental and powerful parametric model class. However, identifying the parameters of a linear dynamical systems is a venerable task, permitting provably efficient solutions only in special cases. In this work, we show that clustering the parameters of unknown linear dynamical systems is, in fact, easier than identifying them. We analyze a computationally efficient clustering algorithm that enjoys provable convergence guarantees under a natural separation assumption. Although easy to implement, our algorithm is general, handling multi-dimensional data with time offsets and partial sequences. Evaluating our algorithm on both synthetic data and real electrocardiogram (ECG) signals, we see significant improvements in clustering quality over existing baselines."]]></description>
<dc:subject>to:NB clustering time_series statistics data_mining</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:ec791d241cef/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:time_series"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:data_mining"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1907.07582">
    <title>[1907.07582] Testing for Unobserved Heterogeneity via k-means Clustering</title>
    <dc:date>2019-07-18T10:55:01+00:00</dc:date>
    <link>https://arxiv.org/abs/1907.07582</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Clustering methods such as k-means have found widespread use in a variety of applications. This paper proposes a formal testing procedure to determine whether a null hypothesis of a single cluster, indicating homogeneity of the data, can be rejected in favor of multiple clusters. The test is simple to implement, valid under relatively mild conditions (including non-normality, and heterogeneity of the data in aspects beyond those in the clustering analysis), and applicable in a range of contexts (including clustering when the time series dimension is small, or clustering on parameters other than the mean). We verify that the test has good size control in finite samples, and we illustrate the test in applications to clustering vehicle manufacturers and U.S. mutual funds."]]></description>
<dc:subject>hypothesis_testing model_selection model_checking clustering statistics in_NB time_series have_read</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:1cda8c06d404/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:hypothesis_testing"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:model_selection"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:model_checking"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:time_series"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:have_read"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://www.cambridge.org/9781108494205">
    <title>Model based clustering and classification</title>
    <dc:date>2019-05-14T15:51:14+00:00</dc:date>
    <link>https://www.cambridge.org/9781108494205</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Cluster analysis finds groups in data automatically. Most methods have been heuristic and leave open such central questions as: how many clusters are there? Which method should I use? How should I handle outliers? Classification assigns new observations to groups given previously classified observations, and also has open questions about parameter tuning, robustness and uncertainty assessment. This book frames cluster analysis and classification in terms of statistical models, thus yielding principled estimation, testing and prediction methods, and sound answers to the central questions. It builds the basic ideas in an accessible but rigorous way, with extensive data examples and R code; describes modern approaches to high-dimensional data and networks; and explains such recent advances as Bayesian regularization, non-Gaussian model-based clustering, cluster merging, variable selection, semi-supervised and robust classification, clustering of functional data, text and images, and co-clustering. Written for advanced undergraduates in data science, as well as researchers and practitioners, it assumes basic knowledge of multivariate calculus, linear algebra, probability and statistics."]]></description>
<dc:subject>to:NB books:noted classifiers clustering statistics raftery.adrian</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:7836a1deb5ca/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:books:noted"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:classifiers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:raftery.adrian"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="https://arxiv.org/abs/1903.08125">
    <title>[1903.08125] Predictive Clustering</title>
    <dc:date>2019-04-11T00:23:45+00:00</dc:date>
    <link>https://arxiv.org/abs/1903.08125</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We show how to convert any clustering into a prediction set. This has the effect of converting the clustering into a (possibly overlapping) union of spheres or ellipsoids. The tuning parameters can be chosen to minimize the size of the prediction set. When applied to k-means clustering, this method solves several problems: the method tells us how to choose k, how to merge clusters and how to replace the Voronoi partition with more natural shapes. We show that the same reasoning can be applied to other clustering methods."]]></description>
<dc:subject>to:NB statistics kith_and_kin prediction clustering rinaldo.alessandro wasserman.larry</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:65859d38374c/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:kith_and_kin"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:prediction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:rinaldo.alessandro"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:wasserman.larry"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://lanl.arxiv.org/abs/1802.04397">
    <title>[1802.04397] Identifiability of Nonparametric Mixture Models and Bayes Optimal Clustering</title>
    <dc:date>2018-03-27T00:34:29+00:00</dc:date>
    <link>http://lanl.arxiv.org/abs/1802.04397</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Motivated by problems in data clustering, we establish general conditions under which families of nonparametric mixture models are identifiable by introducing a novel framework for clustering overfitted \emph{parametric} (i.e. misspecified) mixture models. These conditions generalize existing conditions in the literature, and are flexible enough to include for example mixtures of Gaussian mixtures. In contrast to the recent literature on estimating nonparametric mixtures, we allow for general nonparametric mixture components, and instead impose regularity assumptions on the underlying mixing measure. As our primary application, we apply these results to partition-based clustering, generalizing the well-known notion of a Bayes optimal partition from classical model-based clustering to nonparametric settings. Furthermore, this framework is constructive in that it yields a practical algorithm for learning identified mixtures, which is illustrated through several examples. The key conceptual device in the analysis is the convex, metric geometry of probability distributions on metric spaces and its connection to optimal transport and the Wasserstein convergence of mixing measures. The result is a flexible framework for nonparametric clustering with formal consistency guarantees."]]></description>
<dc:subject>to:NB mixture_models clustering statistics xing.eric ravikumar.pradeep</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:aebbc3bb3eec/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:mixture_models"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:xing.eric"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:ravikumar.pradeep"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://science.sciencemag.org/content/353/6295/163">
    <title>Higher-order organization of complex networks | Science</title>
    <dc:date>2016-12-13T14:43:28+00:00</dc:date>
    <link>http://science.sciencemag.org/content/353/6295/163</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Networks are a fundamental tool for understanding and modeling complex systems in physics, biology, neuroscience, engineering, and social science. Many networks are known to exhibit rich, lower-order connectivity patterns that can be captured at the level of individual nodes and edges. However, higher-order organization of complex networks—at the level of small network subgraphs—remains largely unknown. Here, we develop a generalized framework for clustering networks on the basis of higher-order connectivity patterns. This framework provides mathematical guarantees on the optimality of obtained clusters and scales to networks with billions of edges. The framework reveals higher-order organization in a number of networks, including information propagation units in neuronal networks and hub structure in transportation networks. Results show that networks exhibit rich higher-order organizational structures that are exposed by clustering based on higher-order connectivity patterns."

--- It sounds like this is just clustering based on vectors of motif counts, which would be very disappointing.  Last tag applies.]]></description>
<dc:subject>to:NB to_read network_data_analysis clustering statistics color_me_skeptical</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:5e27e42572fb/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:color_me_skeptical"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.pnas.org/content/113/42/11943.abstract">
    <title>Predictability and hierarchy in Drosophila behavior</title>
    <dc:date>2016-10-18T21:04:50+00:00</dc:date>
    <link>http://www.pnas.org/content/113/42/11943.abstract</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Even the simplest of animals exhibit behavioral sequences with complex temporal dynamics. Prominent among the proposed organizing principles for these dynamics has been the idea of a hierarchy, wherein the movements an animal makes can be understood as a set of nested subclusters. Although this type of organization holds potential advantages in terms of motion control and neural circuitry, measurements demonstrating this for an animal’s entire behavioral repertoire have been limited in scope and temporal complexity. Here, we use a recently developed unsupervised technique to discover and track the occurrence of all stereotyped behaviors performed by fruit flies moving in a shallow arena. Calculating the optimally predictive representation of the fly’s future behaviors, we show that fly behavior exhibits multiple time scales and is organized into a hierarchical structure that is indicative of its underlying behavioral programs and its changing internal states."]]></description>
<dc:subject>to:NB clustering data_mining biology information_theory statistics bialek.william</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:409a3bc79e22/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:data_mining"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:biology"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:information_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:bialek.william"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1507.05910">
    <title>[1507.05910] Clustering is Efficient for Approximate Maximum Inner Product Search</title>
    <dc:date>2015-08-05T17:51:33+00:00</dc:date>
    <link>http://arxiv.org/abs/1507.05910</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Locality Sensitive Hashing (LSH) techniques have recently become a popular solution for solving the approximate Maximum Inner Product Search (MIPS) problem, which arises in many situations and have in particular been used as a speed-up for the training of large neural probabilistic language models. 
"In this paper we propose a new approach for solving approximate MIPS based on a variant of the k-means algorithm. We suggest using spherical k-means which is an algorithm that can efficiently be used to solve the approximate Maximum Cosine Similarity Search (MCSS), and basing ourselves on previous work by Shrivastava and Li we show how it can be adapted for approximate MIPS. 
"Our new method compares favorably with LSH-based methods on a simple recall rate test, by providing a more accurate set of candidates for the maximum inner product. The proposed method is thus likely to benefit the wide range of problems with very large search spaces where a robust approximate MIPS heuristic could be of interest, such as for providing a high quality short list of candidate words to speed up the training of neural probabilistic language models."

---- I thought people viewed k-means as a _kind_ of locality-sensitive hashing?]]></description>
<dc:subject>to:NB databases hashing clustering k-means nearest_neighbors locality-sensitive_hashing data_mining</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:beb119aaae96/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:databases"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:hashing"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:k-means"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:nearest_neighbors"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:locality-sensitive_hashing"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:data_mining"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1507.02284">
    <title>[1507.02284] The Information Sieve</title>
    <dc:date>2015-08-05T16:27:53+00:00</dc:date>
    <link>http://arxiv.org/abs/1507.02284</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We introduce a new framework for unsupervised learning of deep representations based on a novel hierarchical decomposition of information. Intuitively, data is passed through a series of progressively fine-grained sieves. Each layer of the sieve recovers a single latent factor that is maximally informative about multivariate dependence in the data. The data is transformed after each pass so that the remaining unexplained information trickles down to the next layer. Ultimately, we are left with a set of latent factors explaining all the dependence in the original data and remainder information consisting of independent noise. We present a practical implementation of this framework for discrete variables and apply it to a variety of tasks including independent component analysis, lossy and lossless compression, and predicting missing values in data."]]></description>
<dc:subject>to:NB information_theory inference_to_latent_objects factor_analysis clustering statistics kith_and_kin ver_steeg.greg galstyan.aram</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:008a92480f1d/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:information_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:inference_to_latent_objects"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:factor_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:kith_and_kin"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:ver_steeg.greg"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:galstyan.aram"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1507.03194">
    <title>[1507.03194] A Review of Nonnegative Matrix Factorization Methods for Clustering</title>
    <dc:date>2015-08-05T16:23:46+00:00</dc:date>
    <link>http://arxiv.org/abs/1507.03194</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Nonnegative Matrix Factorization (NMF) was first introduced as a low-rank matrix approximation technique, and has enjoyed a wide area of applications. Although NMF does not seem related to the clustering problem at first, it was shown that they are closely linked. In this report, we provide a gentle introduction to clustering and NMF before reviewing the theoretical relationship between them. We then explore several NMF variants, namely Sparse NMF, Projective NMF, Nonnegative Spectral Clustering and Cluster-NMF, along with their clustering interpretations."]]></description>
<dc:subject>to:NB low-rank_approximation clustering statistics data_mining</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:cf45d9fb1975/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:low-rank_approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:data_mining"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1507.06352">
    <title>[1507.06352] Co-clustering of Nonsmooth Graphons</title>
    <dc:date>2015-08-05T14:59:02+00:00</dc:date>
    <link>http://arxiv.org/abs/1507.06352</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Performance bounds are given for exploratory co-clustering/ blockmodeling of bipartite graph data, where we assume the rows and columns of the data matrix are samples from an arbitrary population. This is equivalent to assuming that the data is generated from a nonsmooth graphon. It is shown that co-clusters found by any method can be extended to the row and column populations, or equivalently that the estimated blockmodel approximates a blocked version of the generative graphon, with estimation error bounded by OP(n−1/2). Analogous performance bounds are also given for degree-corrected blockmodels and random dot product graphs, with error rates depending on the dimensionality of the latent variable space."]]></description>
<dc:subject>to:NB network_data_analysis clustering graph_limits statistics kith_and_kin choi.david_s. to_teach:graphons</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:df67a75fa650/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_limits"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:kith_and_kin"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:choi.david_s."/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:graphons"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1506.05900">
    <title>[1506.05900] Representation Learning for Clustering: A Statistical Framework</title>
    <dc:date>2015-07-14T09:50:06+00:00</dc:date>
    <link>http://arxiv.org/abs/1506.05900</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We address the problem of communicating domain knowledge from a user to the designer of a clustering algorithm. We propose a protocol in which the user provides a clustering of a relatively small random sample of a data set. The algorithm designer then uses that sample to come up with a data representation under which k-means clustering results in a clustering (of the full data set) that is aligned with the user's clustering. We provide a formal statistical model for analyzing the sample complexity of learning a clustering representation with this paradigm. We then introduce a notion of capacity of a class of possible representations, in the spirit of the VC-dimension, showing that classes of representations that have finite such dimension can be successfully learned with sample size error bounds, and end our discussion with an analysis of that dimension for classes of representations induced by linear embeddings."]]></description>
<dc:subject>to:NB machine_learning representation learning_theory clustering vc-dimension</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:6432afb4e8cc/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:machine_learning"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:representation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:vc-dimension"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://link.springer.com/article/10.1007/BF01200757">
    <title>The geometry of graphs and some of its algorithmic applications (Linial, London and Rabinovich, 1995)</title>
    <dc:date>2015-07-14T04:02:31+00:00</dc:date>
    <link>http://link.springer.com/article/10.1007/BF01200757</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["In this paper we explore some implications of viewing graphs asgeometric objects. This approach offers a new perspective on a number of graph-theoretic and algorithmic problems. There are several ways to model graphs geometrically and our main concern here is with geometric representations that respect themetric of the (possibly weighted) graph. Given a graphG we map its vertices to a normed space in an attempt to (i) keep down the dimension of the host space, and (ii) guarantee a smalldistortion, i.e., make sure that distances between vertices inG closely match the distances between their geometric images.
"In this paper we develop efficient algorithms for embedding graphs low-dimensionally with a small distortion. Further algorithmic applications include:
"•A simple, unified approach to a number of problems on multicommodity flows, including the Leighton-Rao Theorem [37] and some of its extensions. We solve an open question in this area, showing that the max-flow vs. min-cut gap in thek-commodities problem isO(logk). Our new deterministic polynomial-time algorithm finds a (nearly tight) cut meeting this bound.
"•For graphs embeddable in low-dimensional spaces with a small distortion, we can find low-diameter decompositions (in the sense of [7] and [43]). The parameters of the decomposition depend only on the dimension and the distortion and not on the size of the graph.
"•In graphs embedded this way, small balancedseparators can be found efficiently.
"Given faithful low-dimensional representations of statistical data, it is possible to obtain meaningful and efficientclustering. This is one of the most basic tasks in pattern-recognition. For the (mostly heuristic) methods used in the practice of pattern-recognition, see [20], especially chapter 6.
"Our studies of multicommodity flows also imply that every embedding of (the metric of) ann-vertex, constant-degree expander into a Euclidean space (of any dimension) has distortion Ω(logn). This result is tight, and closes a gap left open by Bourgain [12]."

--- So why don't we think of communities in terms of low-diameter decompositions?]]></description>
<dc:subject>in_NB graph_theory dimension_reduction mathematics random_projections clustering have_read</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:bfbac4c36470/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graph_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:dimension_reduction"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:mathematics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:random_projections"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:have_read"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.genetics.org/content/155/2/945.short">
    <title>Inference of Population Structure Using Multilocus Genotype Data</title>
    <dc:date>2014-06-08T12:10:19+00:00</dc:date>
    <link>http://www.genetics.org/content/155/2/945.short</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["arthegall" is right, this is "just" LDA applied to alleles instead of words.  (Or, considering publication dates, LDA is "just" STRUCTURE.)  Note that the algorithm _presumes_ the existence of K discrete populations.  None of the simulations look at what happens when, say, each point in space has its own distribution of genotypes, but those distributions vary continuously...]]></description>
<dc:subject>to:NB genetics have_read clustering statistics to_teach:data-mining historical_genetics via:arthegall latent_dirichlet_allocation topic_models to:blog</dc:subject>
<dc:identifier>https://pinboard.in/u:cshalizi/b:c38b295faa36/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:genetics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:have_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:data-mining"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:historical_genetics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:via:arthegall"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:latent_dirichlet_allocation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:topic_models"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:blog"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://paintmychromosomes.blogspot.com/2014/06/what-did-we-learn-from-rosenberg-et-al.html">
    <title>What did we learn from Rosenberg et al. 2002, actually? | Ancestry matters</title>
    <dc:date>2014-06-04T12:35:44+00:00</dc:date>
    <link>http://paintmychromosomes.blogspot.com/2014/06/what-did-we-learn-from-rosenberg-et-al.html</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA[Really, LDA?]]></description>
<dc:subject>historical_genetics clustering statistics to_teach:data-mining to_teach:undergrad-ADA via:arthegall track_down_references latent_dirichlet_allocation</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:eb60732ffe45/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:historical_genetics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:data-mining"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:undergrad-ADA"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:via:arthegall"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:track_down_references"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:latent_dirichlet_allocation"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.jstor.org/stable/270873">
    <title>The Algebra of Blockmodeling</title>
    <dc:date>2014-03-27T21:37:27+00:00</dc:date>
    <link>http://www.jstor.org/stable/270873</link>
    <dc:creator>cshalizi</dc:creator><dc:subject>to_read algebra network_data_analysis community_discovery clustering re:network_differences in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:7afae637a588/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:algebra"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:community_discovery"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:re:network_differences"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://jmlr.org/papers/v15/coviello14a.html">
    <title>Clustering Hidden Markov Models with Variational HEM</title>
    <dc:date>2014-03-13T14:18:32+00:00</dc:date>
    <link>http://jmlr.org/papers/v15/coviello14a.html</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["The hidden Markov model (HMM) is a widely-used generative model that copes with sequential data, assuming that each observation is conditioned on the state of a hidden Markov chain. In this paper, we derive a novel algorithm to cluster HMMs based on the hierarchical EM (HEM) algorithm. The proposed algorithm i) clusters a given collection of HMMs into groups of HMMs that are similar, in terms of the distributions they represent, and ii) characterizes each group by a “cluster center”, that is, a novel HMM that is representative for the group, in a manner that is consistent with the underlying generative model of the HMM. To cope with intractable inference in the E-step, the HEM algorithm is formulated as a variational optimization problem, and efficiently solved for the HMM case by leveraging an appropriate variational approximation. The benefits of the proposed algorithm, which we call variational HEM (VHEM), are demonstrated on several tasks involving time-series data, such as hierarchical clustering of motion capture sequences, and automatic annotation and retrieval of music and of online hand- writing data, showing improvements over current methods. In particular, our variational HEM algorithm effectively leverages large amounts of data when learning annotation models by using an efficient hierarchical estimation procedure, which reduces learning times and memory requirements, while improving model robustness through better regularization."]]></description>
<dc:subject>to:NB markov_models state-space_models clustering time_series variational_inference statistics</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:dc91071effcf/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:markov_models"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:state-space_models"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:time_series"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:variational_inference"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.mitpressjournals.org/doi/abs/10.1162/NECO_a_00547">
    <title>Spontaneous Clustering via Minimum Gamma-Divergence</title>
    <dc:date>2014-03-11T21:14:03+00:00</dc:date>
    <link>http://www.mitpressjournals.org/doi/abs/10.1162/NECO_a_00547</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We propose a new method for clustering based on local minimization of the gamma-divergence, which we call spontaneous clustering. The greatest advantage of the proposed method is that it automatically detects the number of clusters that adequately reflect the data structure. In contrast, existing methods, such as K-means, fuzzy c-means, or model-based clustering need to prescribe the number of clusters. We detect all the local minimum points of the gamma-divergence, by which we define the cluster centers. A necessary and sufficient condition for the gamma-divergence to have local minimum points is also derived in a simple setting. Applications to simulated and real data are presented to compare the proposed method with existing ones."]]></description>
<dc:subject>to:NB model_selection clustering statistics</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:ad8910c64e8e/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:model_selection"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1401.0871">
    <title>[1401.0871] Stylistic Clusters and the Syrian/South Syrian Tradition of First-Millennium BCE Levantine Ivory Carving: A Machine Learning Approach</title>
    <dc:date>2014-03-09T17:13:14+00:00</dc:date>
    <link>http://arxiv.org/abs/1401.0871</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Thousands of first-millennium BCE ivory carvings have been excavated from Neo-Assyrian sites in Mesopotamia (primarily Nimrud, Khorsabad, and Arslan Tash) hundreds of miles from their Levantine production contexts. At present, their specific manufacture dates and workshop localities are unknown. Relying on subjective, visual methods, scholars have grappled with their classification and regional attribution for over a century. This study combines visual approaches with machine-learning techniques to offer data-driven perspectives on the classification and attribution of this early Iron Age corpus. The study sample consisted of 162 sculptures of female figures. We have developed an algorithm that clusters the ivories based on a combination of descriptive and anthropometric data. The resulting categories, which are based on purely statistical criteria, show good agreement with conventional art historical classifications, while revealing new perspectives, especially with regard to the contested Syrian/South Syrian/Intermediate tradition. Specifically, we have identified that objects of the Syrian/South Syrian/Intermediate tradition may be more closely related to Phoenician objects than to North Syrian objects; we offer a reconsideration of a subset of Phoenician objects, and we confirm Syrian/South Syrian/Intermediate stylistic subgroups that might distinguish networks of acquisition among the sites of Nimrud, Khorsabad, Arslan Tash and the Levant. We have also identified which features are most significant in our cluster assignments and might thereby be most diagnostic of regional carving traditions. In short, our study both corroborates traditional visual classification methods and demonstrates how machine-learning techniques may be employed to reveal complementary information not accessible through the exclusively visual analysis of an archaeological corpus."]]></description>
<dc:subject>to:NB clustering art_history archaeology ancient_history ancient_trade statistics wiggins.christopher kith_and_kin to_teach:data-mining</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:151d8191f91f/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:art_history"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:archaeology"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:ancient_history"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:ancient_trade"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:wiggins.christopher"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:kith_and_kin"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:data-mining"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://link.springer.com/article/10.1007/s10618-013-0312-3">
    <title>CID: an efficient complexity-invariant distance for time series - Springer</title>
    <dc:date>2014-02-19T02:47:38+00:00</dc:date>
    <link>http://link.springer.com/article/10.1007/s10618-013-0312-3</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["The ubiquity of time series data across almost all human endeavors has produced a great interest in time series data mining in the last decade. While dozens of classification algorithms have been applied to time series, recent empirical evidence strongly suggests that simple nearest neighbor classification is exceptionally difficult to beat. The choice of distance measure used by the nearest neighbor algorithm is important, and depends on the invariances required by the domain. For example, motion capture data typically requires invariance to warping, and cardiology data requires invariance to the baseline (the mean value). Similarly, recent work suggests that for time series clustering, the choice of clustering algorithm is much less important than the choice of distance measure used.In this work we make a somewhat surprising claim. There is an invariance that the community seems to have missed, complexity invariance. Intuitively, the problem is that in many domains the different classes may have different complexities, and pairs of complex objects, even those which subjectively may seem very similar to the human eye, tend to be further apart under current distance measures than pairs of simple objects. This fact introduces errors in nearest neighbor classification, where some complex objects may be incorrectly assigned to a simpler class. Similarly, for clustering this effect can introduce errors by “suggesting” to the clustering algorithm that subjectively similar, but complex objects belong in a sparser and larger diameter cluster than is truly warranted.We introduce the first complexity-invariant distance measure for time series, and show that it generally produces significant improvements in classification and clustering accuracy. We further show that this improvement does not compromise efficiency, since we can lower bound the measure and use a modification of triangular inequality, thus making use of most existing indexing and data mining algorithms. We evaluate our ideas with the largest and most comprehensive set of time series mining experiments ever attempted in a single work, and show that complexity-invariant distance measures can produce improvements in classification and clustering in the vast majority of cases."

- And what does "complexity" mean here, exactly?]]></description>
<dc:subject>to:NB time_series clustering classifiers data_mining complexity_measures statistics</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:b818e22f6c68/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:time_series"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:classifiers"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:data_mining"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:complexity_measures"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://link.springer.com/article/10.1007/s10618-013-0317-y">
    <title>Subspace clustering of high-dimensional data: a predictive approach - Springer</title>
    <dc:date>2014-02-19T02:46:07+00:00</dc:date>
    <link>http://link.springer.com/article/10.1007/s10618-013-0317-y</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["In several application domains, high-dimensional observations are collected and then analysed in search for naturally occurring data clusters which might provide further insights about the nature of the problem. In this paper we describe a new approach for partitioning such high-dimensional data. Our assumption is that, within each cluster, the data can be approximated well by a linear subspace estimated by means of a principal component analysis (PCA). The proposed algorithm, Predictive Subspace Clustering (PSC) partitions the data into clusters while simultaneously estimating cluster-wise PCA parameters. The algorithm minimises an objective function that depends upon a new measure of influence for PCA models. A penalised version of the algorithm is also described for carrying our simultaneous subspace clustering and variable selection. The convergence of PSC is discussed in detail, and extensive simulation results and comparisons to competing methods are presented. The comparative performance of PSC has been assessed on six real gene expression data sets for which PSC often provides state-of-art results."]]></description>
<dc:subject>to:NB low-rank_approximation principal_components clustering data_mining statistics</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:e61894d2a58c/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:low-rank_approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:principal_components"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:data_mining"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1301.6647">
    <title>[1301.6647] Feature allocations, probability functions, and paintboxes</title>
    <dc:date>2014-01-20T21:27:53+00:00</dc:date>
    <link>http://arxiv.org/abs/1301.6647</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["The problem of inferring a clustering of a data set has been the subject of much research in Bayesian analysis, and there currently exists a solid mathematical foundation for Bayesian approaches to clustering. In particular, the class of probability distributions over partitions of a data set has been characterized in a number of ways, including via exchangeable partition probability functions (EPPFs) and the Kingman paintbox. Here, we develop a generalization of the clustering problem, called feature allocation, where we allow each data point to belong to an arbitrary, non-negative integer number of groups, now called features or topics. We define and study an "exchangeable feature probability function" (EFPF)---analogous to the EPPF in the clustering setting---for certain types of feature models. Moreover, we introduce a "feature paintbox" characterization---analogous to the Kingman paintbox for clustering---of the class of exchangeable feature models. We provide a further characterization of the subclass of feature allocations that have EFPF representations."]]></description>
<dc:subject>heard_the_talk clustering probability exchangeability stochastic_processes jordan.michael_i. in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:4305d1ad923b/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:heard_the_talk"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:probability"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:exchangeability"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:stochastic_processes"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:jordan.michael_i."/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1312.3790">
    <title>[1312.3790] Sample Complexity of Dictionary Learning and other Matrix Factorizations</title>
    <dc:date>2014-01-02T17:52:57+00:00</dc:date>
    <link>http://arxiv.org/abs/1312.3790</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Many modern tools in machine learning and signal processing, such as sparse dictionary learning, principal component analysis (PCA), non-negative matrix factorization (NMF), K-means clustering, etc., rely on the factorization of a matrix obtained by concatenating high-dimensional vectors from a training collection. While the idealized task would be to optimize the expected quality of the factors over the underlying distribution of training vectors, it is achieved in practice by minimizing an empirical average over the considered collection. The focus of this paper is to provide sample complexity estimates to uniformly control how much the empirical average deviates from the expected cost function. Standard arguments imply that the performance of the empirical predictor also exhibit such guarantees. The level of genericity of the approach encompasses several possible constraints on the factors (tensor product structure, shift-invariance, sparsity \ldots), thus providing a unified perspective on the sample complexity of several widely used matrix factorization schemes."]]></description>
<dc:subject>low-rank_approximation learning_theory clustering factor_analysis statistics in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:9a4f571e8eee/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:low-rank_approximation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:factor_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://jmlr.org/papers/v14/lewis13a.html">
    <title>Divvy: Fast and Intuitive Exploratory Data Analysis</title>
    <dc:date>2013-11-18T14:43:37+00:00</dc:date>
    <link>http://jmlr.org/papers/v14/lewis13a.html</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Divvy is an application for applying unsupervised machine learning techniques (clustering and dimensionality reduction) to the data analysis process. Divvy provides a novel UI that allows researchers to tighten the action-perception loop of changing algorithm parameters and seeing a visualization of the result. Machine learning researchers can use Divvy to publish easy to use reference implementations of their algorithms, which helps the machine learning field have a greater impact on research practices elsewhere."]]></description>
<dc:subject>to:NB visual_display_of_quantitative_information data_mining clustering to_teach:data-mining</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:64dad777a9c9/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:visual_display_of_quantitative_information"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:data_mining"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:data-mining"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1311.1903">
    <title>[1311.1903] Moment-based Uniform Deviation Bounds for $k$-means and Friends</title>
    <dc:date>2013-11-14T04:49:17+00:00</dc:date>
    <link>http://arxiv.org/abs/1311.1903</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Suppose k centers are fit to m points by heuristically minimizing the k-means cost; what is the corresponding fit over the source distribution? This question is resolved here for distributions with p≥4 bounded moments; in particular, the difference between the sample cost and distribution cost decays with m and p as mmin{−1/4,−1/2+2/p}. The essential technical contribution is a mechanism to uniformly control deviations in the face of unbounded parameter sets, cost functions, and source distributions. To further demonstrate this mechanism, a soft clustering variant of k-means cost is also considered, namely the log likelihood of a Gaussian mixture, subject to the constraint that all covariance matrices have bounded spectrum. Lastly, a rate with refined constants is provided for k-means instances possessing some cluster structure."]]></description>
<dc:subject>clustering k-means deviation_inequalities mixture_models learning_theory statistics telgarsky.matus heard_the_talk in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:945a43f138f9/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:k-means"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:deviation_inequalities"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:mixture_models"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:learning_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:telgarsky.matus"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:heard_the_talk"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1310.4249">
    <title>[1310.4249] Mapping the structure of drosophilid behavior</title>
    <dc:date>2013-10-23T22:21:21+00:00</dc:date>
    <link>http://arxiv.org/abs/1310.4249</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Most animals possess the ability to actuate a vast diversity of movements, ostensibly constrained only by morphology and physics. In practice, however, a frequent assumption in behavioral science is that most of an animal's activities can be described in terms of a small set of stereotyped motifs. Here we introduce a method for mapping the behavioral space of organisms, relying only upon the underlying structure of postural movement data to organize and classify behaviors. We find that six different drosophilid species each perform a mix of non-stereotyped actions and over one hundred hierarchically-organized, stereotyped behaviors. Moreover, we use this approach to compare these species' behavioral spaces, systematically identifying subtle behavioral differences between closely-related species."]]></description>
<dc:subject>to:NB biology psychology clustering bialek.william to_read</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:2469c4104486/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:biology"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:psychology"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:bialek.william"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_read"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1310.4210">
    <title>[1310.4210] Demystifying Information-Theoretic Clustering</title>
    <dc:date>2013-10-23T19:52:15+00:00</dc:date>
    <link>http://arxiv.org/abs/1310.4210</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We propose a novel method for clustering data which is grounded in information-theoretic principles and requires no parametric assumptions. Previous attempts to use information theory to define clusters in an assumption-free way are based on maximizing mutual information between data and cluster labels. We demonstrate that this intuition suffers from a fundamental conceptual flaw that causes clustering performance to deteriorate as the amount of data increases. Instead, we return to the axiomatic foundations of information theory to define a meaningful clustering measure based on the notion of consistency under coarse-graining for finite data."

- Not clear here why it wouldn't be even better to just set each point to its own cluster.]]></description>
<dc:subject>clustering information_theory statistics kith_and_kin dedeo.simon ver_steeg.greg galstyan.aram to_teach:data-mining have_read in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:b665d03f23af/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:information_theory"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:kith_and_kin"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:dedeo.simon"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:ver_steeg.greg"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:galstyan.aram"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:data-mining"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:have_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1307.5339">
    <title>[1307.5339] The Cluster Graphical Lasso for improved estimation of Gaussian graphical models</title>
    <dc:date>2013-07-26T16:38:51+00:00</dc:date>
    <link>http://arxiv.org/abs/1307.5339</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["We consider the task of estimating a Gaussian graphical model in the high-dimensional setting. The graphical lasso, which involves maximizing the Gaussian log likelihood subject to an l1 penalty, is a well-studied approach for this task. We begin by introducing a surprising connection between the graphical lasso and hierarchical clustering: the graphical lasso in effect performs a two-step procedure, in which (1) single linkage hierarchical clustering is performed on the variables in order to identify connected components, and then (2) an l1-penalized log likelihood is maximized on the subset of variables within each connected component. In other words, the graphical lasso determines the connected components of the estimated network via single linkage clustering. Unfortunately, single linkage clustering is known to perform poorly in certain settings. Therefore, we propose the cluster graphical lasso, which involves clustering the features using an alternative to single linkage clustering, and then performing the graphical lasso on the subset of variables within each cluster. We establish model selection consistency for this technique, and demonstrate its improved performance relative to the graphical lasso in a simulation study, as well as in applications to an equities data set, a university webpage data set, and a gene expression data set."]]></description>
<dc:subject>to:NB sparsity graphical_models lasso clustering statistics</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:73a45418d335/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:sparsity"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:graphical_models"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:lasso"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://www.tandfonline.com/doi/abs/10.1080/01621459.2012.760458#.UdRPpRbPUlM">
    <title>Taylor &amp; Francis Online :: Clustering High-Dimensional Time Series Based on Parallelism - Journal of the American Statistical Association - Volume 108, Issue 502</title>
    <dc:date>2013-07-03T16:34:33+00:00</dc:date>
    <link>http://www.tandfonline.com/doi/abs/10.1080/01621459.2012.760458#.UdRPpRbPUlM</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["This article considers the problem of clustering high-dimensional time series based on trend parallelism. The underlying process is modeled as a nonparametric trend function contaminated by locally stationary errors, a special class of nonstationary processes. For each group where the parallelism holds, I semiparametrically estimate its representative trend function and vertical shifts of group members, and establish their central limit theorems. An information criterion, consisting of in-group similarities and number of groups, is then proposed for the purpose of clustering. I prove its theoretical consistency and propose a splitting-coalescence algorithm to reduce the computational burden in practice. The method is illustrated by both simulation and a real-data example."]]></description>
<dc:subject>to:NB time_series clustering statistics</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:64ffadd3522b/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to:NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:time_series"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1306.2194">
    <title>[1306.2194] Adaptive Noisy Clustering</title>
    <dc:date>2013-06-11T22:26:53+00:00</dc:date>
    <link>http://arxiv.org/abs/1306.2194</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["The problem of adaptive noisy clustering is investigated. Given a set of noisy observations $Z_i=X_i+\epsilon_i$, $i=1,...,n$, the goal is to design clusters associated with the law of $X_i$'s, with unknown density $f$ with respect to the Lebesgue measure. Since we observe a corrupted sample, a direct approach as the popular {\it $k$-means} is not suitable in this case. In this paper, we propose a noisy $k$-means minimization, which is based on the $k$-means loss function and a deconvolution estimator of the density $f$. In particular, this approach suffers from the dependence on a bandwidth involved in the deconvolution kernel. Fast rates of convergence for the excess risk are proposed for a particular choice of the bandwidth, which depends on the smoothness of the density $f$. 
"Then, we turn out into the main issue of the paper: the data-driven choice of the bandwidth. We state an adaptive upper bound for a new selection rule, called ERC (Empirical Risk Comparison). This selection rule is based on the Lepski's principle, where empirical risks associated with different bandwidths are compared. Finally, we illustrate that this adaptive rule can be used in many statistical problems of $M$-estimation where the empirical risk depends on a nuisance parameter."]]></description>
<dc:subject>clustering density_estimation statistics in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:cdb027004d08/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:density_estimation"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1305.6228">
    <title>[1305.6228] Detecting hierarchical and overlapping network communities using locally optimal modularity changes</title>
    <dc:date>2013-05-28T17:33:56+00:00</dc:date>
    <link>http://arxiv.org/abs/1305.6228</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Agglomerative clustering is a well established strategy for identifying communities in networks. Communities are successively merged into larger communities, coarsening a network of actors into a more manageable network of communities. The order in which merges should occur is not in general clear, necessitating heuristics for selecting pairs of communities to merge. We describe a hierarchical clustering algorithm based on a local optimality property. For each edge in the network, we associate the modularity change for merging the communities it links. For each community vertex, we call the preferred edge that edge for which the modularity change is maximal. When an edge is preferred by both vertices that it links, it appears to be the optimal choice from the local viewpoint. We use the locally optimal edges to define the algorithm: simultaneously merge all pairs of communities that are connected by locally optimal edges that would increase the modularity, redetermining the locally optimal edges after each step and continuing so long as the modularity can be further increased. We apply the algorithm to model and empirical networks, demonstrating that it can efficiently produce high-quality community solutions. We relate the performance and implementation details to the structure of the resulting community hierarchies. We additionally consider a complementary local clustering algorithm, describing how to identify overlapping communities based on the local optimality condition."]]></description>
<dc:subject>community_discovery network_data_analysis clustering in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:4a8f8e8c011e/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:community_discovery"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:network_data_analysis"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1305.5879">
    <title>[1305.5879] Statistical Significance of Clustering using Soft Thresholding</title>
    <dc:date>2013-05-28T17:33:35+00:00</dc:date>
    <link>http://arxiv.org/abs/1305.5879</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Clustering methods have led to a number of important discoveries in bioinformatics and beyond. A major challenge in their use is determining which clusters represent important underlying structure, as opposed to spurious sampling artifacts. This challenge is especially serious, and very few methods are available when the data are very high in dimension. Statistical Significance of Clustering (SigClust) is a recently developed cluster evaluation tool for high dimensional low sample size data. An important component of the SigClust approach is the very definition of a single cluster as a subset of data sampled from a multivariate Gaussian distribution. The implementation of SigClust requires the estimation of the eigenvalues of the covariance matrix for the null multivariate Gaussian distribution. We show that the original eigenvalue estimation can lead to a test that suffers from severe inflation of type-I error, in the important case where there are huge single spikes in the eigenvalues. This paper addresses this critical challenge using a novel likelihood based soft thresholding approach to estimate these eigenvalues which leads to a much improved SigClust. These major improvements in SigClust performance are shown by both theoretical work and an extensive simulation study. Applications to some cancer genomic data further demonstrate the usefulness of these improvements."]]></description>
<dc:subject>clustering mixture_models goodness-of-fit statistics in_NB high-dimensional_statistics</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:16b6d2746542/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:mixture_models"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:goodness-of-fit"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:statistics"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:high-dimensional_statistics"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1305.4757">
    <title>[1305.4757] Power to the Points: Validating Data Memberships in Clusterings</title>
    <dc:date>2013-05-22T02:50:44+00:00</dc:date>
    <link>http://arxiv.org/abs/1305.4757</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["A clustering is an implicit assignment of labels of points, based on proximity to other points. It is these labels that are then used for downstream analysis (either focusing on individual clusters, or identifying representatives of clusters and so on). Thus, in order to trust a clustering as a first step in exploratory data analysis, we must trust the labels assigned to individual data. Without supervision, how can we validate this assignment? In this paper, we present a method to attach affinity scores to the implicit labels of individual points in a clustering. The affinity scores capture the confidence level of the cluster that claims to "own" the point. This method is very general: it can be used with clusterings derived from Euclidean data, kernelized data, or even data derived from information spaces. It smoothly incorporates importance functions on clusters, allowing us to eight different clusters differently. It is also efficient: assigning an affinity score to a point depends only polynomially on the number of clusters and is independent of the number of points in the data. The dimensionality of the underlying space only appears in preprocessing. We demonstrate the value of our approach with an experimental study that illustrates the use of these scores in different data analysis tasks, as well as the efficiency and flexibility of the method. We also demonstrate useful visualizations of these scores; these might prove useful within an interactive analytics framework."

--- Rather heuristic; they mention stability but don't really explore the connection to it, and they don't mention Nugent's "clustering with confidence"]]></description>
<dc:subject>clustering data_mining to_teach:data-mining venkatasubramanian.suresh have_read in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:155017712790/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:data_mining"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:data-mining"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:venkatasubramanian.suresh"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:have_read"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1304.6478">
    <title>[1304.6478] The K-modes algorithm for clustering</title>
    <dc:date>2013-04-25T16:40:19+00:00</dc:date>
    <link>http://arxiv.org/abs/1304.6478</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["Many clustering algorithms exist that estimate a cluster centroid, such as K-means, K-medoids or mean-shift, but no algorithm seems to exist that clusters data by returning exactly K meaningful modes. We propose a natural definition of a K-modes objective function by combining the notions of density and cluster assignment. The algorithm becomes K-means and K-medoids in the limit of very large and very small scales. Computationally, it is slightly slower than K-means but much faster than mean-shift or K-medoids. Unlike K-means, it is able to find centroids that are valid patterns, truly representative of a cluster, even with nonconvex clusters, and appears robust to outliers and misspecification of the scale and number of clusters."]]></description>
<dc:subject>clustering data_mining in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:9f052b5aa948/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:data_mining"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
<item rdf:about="http://arxiv.org/abs/1304.3432">
    <title>[1304.3432] Machine Learning, Clustering, and Polymorphy</title>
    <dc:date>2013-04-16T01:04:47+00:00</dc:date>
    <link>http://arxiv.org/abs/1304.3432</link>
    <dc:creator>cshalizi</dc:creator><description><![CDATA["This paper describes a machine induction program (WITT) that attempts to model human categorization. Properties of categories to which human subjects are sensitive includes best or prototypical members, relative contrasts between putative categories, and polymorphy (neither necessary or sufficient features). This approach represents an alternative to usual Artificial Intelligence approaches to generalization and conceptual clustering which tend to focus on necessary and sufficient feature rules, equivalence classes, and simple search and match schemes. WITT is shown to be more consistent with human categorization while potentially including results produced by more traditional clustering schemes. Applications of this approach in the domains of expert systems and information retrieval are also discussed."

--- From UAI1985!]]></description>
<dc:subject>clustering cognitive_science data_mining hanson.stephen_jose to_teach:data-mining in_NB</dc:subject>
<dc:source>https://pinboard.in/</dc:source>
<dc:identifier>https://pinboard.in/u:cshalizi/b:817dc227b01a/</dc:identifier>
<taxo:topics><rdf:Bag>	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:clustering"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:cognitive_science"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:data_mining"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:hanson.stephen_jose"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:to_teach:data-mining"/>
	<rdf:li rdf:resource="https://pinboard.in/u:cshalizi/t:in_NB"/>
</rdf:Bag></taxo:topics>
</item>
</rdf:RDF>