text:
DeepAI

# A Family of Metrics for Clustering Algorithms

We give the motivation for scoring clustering algorithms and a metric M : A →N from the set of clustering algorithms to the natural numbers which we realize as M(A) = ∑_i α_i |f_i - β_i|^w_i where α_i,β_i,w_i are parameters used for scoring the feature f_i, which is computed empirically.. We give a method by which one can score features such as stability, noise sensitivity, etc and derive the necessary parameters. We conclude by giving a sample set of scores.

• 8 publications
• 3 publications
02/27/2013

### A Bayesian Method Reexamined

This paper examines the "K2" network scoring metric of Cooper and Hersko...
10/22/2021

### Validation of point process predictions with proper scoring rules

We introduce a class of proper scoring rules for evaluating spatial poin...
03/01/2022

### Sensitivity Measures Based on Scoring Functions

We propose a holistic framework for constructing sensitivity measures fo...
11/22/2019

### Responsible Scoring Mechanisms Through Function Sampling

Human decision-makers often receive assistance from data-driven algorith...
11/23/2020

### Ensemble- and Distance-Based Feature Ranking for Unsupervised Learning

In this work, we propose two novel (groups of) methods for unsupervised ...
12/31/2021

### Clustering Vietnamese Conversations From Facebook Page To Build Training Dataset For Chatbot

The biggest challenge of building chatbots is training data. The require...
05/07/2019

### Transparent pronunciation scoring using articulatorily weighted phoneme edit distance

For researching effects of gamification in foreign language learning for...

## 1 Introduction

Data science has been around in form and function if not necessarily in name for the better half of the last century. Among the main problems that we encounter is “clustering” which one can describe in layman’s terms as grouping elements from a (data)set into subsets which share some feature. Early uses for data clustering came from the world of particle physics wherein particle accelerators sent large numbers of elementary particles in opposite directions in hopes of some of them colliding with each other to produce nuclear debris. Several questions arose naturally from this process. First; how does one read off the data? Second; if two particles collide, how do we detect this? Third; is a collision head-on or are the particles glancing off each other? Fourth; which data are simply noise? An additional source of data clustering, which arrived later came in the form of astronomy. One can ask, given a telescope image, how do we discern which spots are stars, galaxies, nebulae, planets, etc?

Since digital computers were in the nascence in the late 1970s the algorithms needed to operate quickly and stably, with as little sensitivity to noise as possible. The big constraints then were speed and processing power. It was difficult to run through a small dataset thousands of times. This led to algorithms like CLASSY and k-means (reference to 1979 CLASSY article)

In the early decades of the twenty first century running through datasets of as much as a billion points requires very little runtime, and thus thousands of tests is a feasible computational task. This, however, is buoyed by the fact that datasets are becoming larger and more noisy, to the point where stability and noise sensitivity become even more important. At present there are dozens, if not hundreds, of well-known algorithms for clustering built for tackling specific problems. The question naturally arises as to which algorithm is the best. Perhaps a hybridized approach works for some industries better than others. Thus we have turned the question of clustering into a question of metrology. How does one measure the effectiveness of a particular algorithm? We attempt to answer this question by giving a metric inspired by the points systems for multi-sport events such as pentathlon, heptathlon, and the decathlon. To measure the athletic performance in such an event, we take into account that there are essentially two types of sports contained within (i) those in which the highest score is the winner, (i.e. pole vault, long jump, javelin), (ii) those in which the lowest score is the winner (i.e. hurdles, 100m, 800m, etc). In sports where the highest score is the winner one wishes to add scores: thus one considers a point value given by

 α(score−β)w

In this case, is a reference point, perhaps the lowest qualifying score. For example in the pole vault, one only considers vaults that get above the 4m mark. In order to scale the unit into “points” one uses a scaling factor . The scaling factor also allows one to scale in such a way that vastly scattered scores (such as long jump measured in cm) does not drastically affect the score versus the 100m sprint measured in seconds. Finally, the weight

allows one to scale the score so that roughly every event can have roughly the same mean or same variance as whichever criterion an athletic committee would deem more desirable. One can add more parameters to give the scores some other sort of unity such as maximum range of scores, difference from theoretical maximum, etc. In our scoring we consider only three parameters, for reference, units, and weighting.

## 2 Stability

Our algorithmic scores are based on their utility for our purposes. The parameters we derive for our algorithm may be modified for any researcher to meet her/his needs. For our purposes we wish to have an algorithm with a high amount of stability. In order to quantify stability, we offer the heuristic definition that given a sufficiently large dataset with

features we shall test some subset features at a time and then exchange one feature at a time. For example, given a test dataset with 100 features, we shall test approximately 20 at a time. After we test 20 features we mark the clusters to which each datum belongs. We then repeat the algorithm while testing 20 features, 19 of which are similar. We calculate how many points move from their clusters (considering the 20th cluster to be the “same”). If nearly half of all points move, then we consider this algorithm to score badly in stability. In fact, we will mark this as zero-stable. We test this algorithm multiple times and each time count the proportion of points which move from test run to test run. The average of moving points will be our instability, and thus we define stability of an algorithm as follows:

 Stability(A)=1−#Moving Points#Points (2.1)

Where the number of moving points is calculated empirically. Obviously, unless our dataset is sufficiently small, we cannot get the true measure of stability, but we give some confidence interval around the measured mean. From first year statistics we simply apply the student’s

-score to find a confidence interval around the measured mean (stability).

 μ∈[^μ−t^s√n,^μ+t^s√n]

where is the number of measurements and

are the measured standard deviation and mean respectively. Thus we set a threshold of allowable error and calculate the number of experiments necessary to achieve the desired precision. For our purposes, all datasets will be significantly larger than 30 points which a first course in elementary statistics tells us is a sufficient quantity to estimate with

-score. For the sake of simplicity we shall take and score a 95% (approximately) confidence interval around our measured stability.

Once we have a quantity called stability, we now scale it to give a maximum of 100 points. The choice of 100 is completely arbitrary and may be moved to any number to fit a particular researcher’s needs. Our reference point, as mentioned above will be . That is to say, if on average half of the points move at every exchanged feature then the algorithm will not be considered stable. For example, k-means/medians will be considered highly unstable because the choice of initial means/medians dramatical affects the final outcome. This is particularly noticeable in k-means when considered dimensional subspaces of dimensional data.

## 3 Noise

Noise sensitivity is among the more difficult qualities to quantify with any consistency. Part of the problem is that we have different types of noise and of utmost importance is the arbitrary nature of the “shape” of a general dataset. Thus measuring noise sensitivity requires a little bit of bootstrapping and we will reverse engineer our datasets to test an algorithm’s efficacy. The initial thought in characterizing an algorithm’s sensitivity to noise saw the assignment of the score

 P(x causes a problem |x is noise)

Defining “causes a problem” is already subjective enough in the sense that this can mean widely varying things for different researchers. For example, DBSCAN generally handles noise well unless is too large. In this case, a noisy point can tie together two distinct clusters. This particular type of error can show up in drawing political district maps. The second problem with the initial assignment of score is that, if we know a priori that is, in fact, noise, then we can filter it in preprocessing. In essence the definition is still too heuristic to be computationally useful; that is, it’s not constructive.

The solution we propose to measuring is noise is to begin with a properly clustered dataset of arbitrary size. For example we build a spatial dataset which has “well-defined” clusters of different sizes, shapes, and densities. Once we have a well-clustered dataset we add noise to it and then recluster. The main measure then shall be entropy. More precisely, we will define two probability distributions and measure their Kullback-Leibler divergence.

First, let’s give some definitions and conventions about how we shall calculate sensitivity to noise.

###### Definition 1.

Let

 X={x1,…,xN}

be a dataset of points. Furthermore, let

 Z={n1,…,nq}

be a set of points which we consider to be noise. Let be well-clustered with clusters .

 X=⊔iCi

We shall assign to the probability mass function which assigns to each cluster its proportional weight.

 pi=|Ci|/N

The entropy associated to is now defined as

 H(X)=−∑ipilog(pi) (3.1)

Notice that so the negative sign gives us a positive value. This gives us a good measure of the already existing noise or uncertainty present within . Now we introduce the Kullback-Leibler divergence

###### Definition 2.

Given two probability distributions and the Kullback-Leibler divergence is

 D(p∥q)=−∑p(x)log(p(x)q(x)) (3.2)

This gives us a canonical way to measure the “difference” between two random variables with distributions

and . In our case, the distribution will always be the distribution defined by our well-clustered set .

Now we define the sets

 Z[k]⊆Z

so that has noisy points. There are such sets . for given . and if we consider all then there are total noisy sets. Now we create the new sets:

 X∪Z[k]

and we make the probability associations

 X⇝p,X∪Z[k]⇝~p[k]

From here we make the formal definition

 D(p∥~p)=12q∑all Z[k]D(p∥~p[k]) (3.3)

After having made this formal definition, we realize that it is impossible to calculate this divergence exactly, since we cannot test every possible noisy dataset in existence. Thus we pick some amount of noisy points and compute several different divergences and again estimate the true divergence against our measured divergence using the -statistic.

 ^D(p∥~p)∈[D(p∥~p)−t^sD√n,D(p∥~p)+t^sD√n] (3.4)

Thus the larger number of samples we take, the more accurate our measured divergence is against the true value. As a quick counting exercise, let’s pick

 q=clusters×dimensions:=CX×d

then we pick . This gives us a good bound on the number of possible noisy datasets we can choose of size .

 |Z[k]| ≈ (2kk) ≈ 4k√πk

where we have used Stirling’s approximation

 k!≈√2πkkkek

to compute the second line. Thus we have approximately

 4dCX√πdCX

possible noisy datasets containing roughly half the noisy points to test. Even in low dimensions (i.e. ) and a small number of clusters, this allows us sufficiently many tests to get a measured divergence to within any chosen accuracy at the cost of running more experiments.

Given that we have a precise measure for divergence we read the consequences of the definition. Having no divergence means that an algorithm is not susceptible to noise. The larger the divergence, the higher the susceptibility to noise. Thus we seek a score in the form

 α(β−^D(p∥~p))w

By our choice of we can get a bound on maximal divergence. If our algorithm is highly susceptible to noise then each noisy point will create a new cluster. Then we see

 D(p∥~p)=−∑pln(p~p)=−∑pln(pkp)=ln(k)∑p=ln(k)

Recalling that we have chosen we find a maximal divergence of

 maxD=ln(dCX)−ln(2)

In this case we will pick as our reference point. This will give a minimum score of and a maximal score of . We wish to have the raw score as 100 before weighting so we pick .

We view noise (in)sensitivity as among the most important features in our metric, thus we give the initial weight . Notice here, that and thus we wish to increase its overall importance with a weighting factor, thus we pick It is important to note, however, that divergence is highly sensitive to the initial dataset and so each researcher must adjust according to her or his dataset.

## 4 Complexity

Complexity is a well established concept in the theory of computing. In this case, we shall prefer to use the standard definition of big-Oh. Our choice of big-Oh rather than big-Theta is based on the fact that we want to score our algorithms based on the slowest that they might be. Indeed, a different researcher may prefer to use big-Theta, or perhaps for a widely distributed system, clock time. In all cases, the scoring procedure follows in a nearly identical fashion; the faster the better. In terms of big-Oh we will look only at the exponent.

###### Definition 3.

Consider two functions . We say

 f(x)∈O(g(x))

if there exists a pair of positive numbers so that

 ∀x>N,|f(x)|≤k⋅|g(x)|

Notice our slight deviation from the standard to . This more properly reflects the fact that is not an equivalence relation since it is not symmetric. This also allows us to avoid “tight” bounds. In essence we are really scoring the highest exponent of versus the highest exponent of . A slight reformulation gives us

 f(x)∈O(g(x))⟺limx→∞∣∣∣f(x)g(x)∣∣∣<∞. (4.1)

Many of the “common” clustering algorithms (e.g. K-means, BIRCH, STING, CURE, wavecluster, Particle Swarm Optimization, Quantum Dynamic Clustering, etc)

have well established complexity classes. Amongst the algorithms we are testing, the complexity classes are of the form

 aNblogc(N)

where may be a combination of factors such as dimension of data, branching threshold, minimum number of points, , etc. With the size of the datasets we are scoring, none of these additional factors will be larger than where is some number less than one. We in fact, test a branching factor where we have . The logarithmic factor contributes very little to clock speed, so we score this as where is very small. Of course, when we consider the limit

 ∀c,α>0,limN→∞logc(N)Nα=0

we can consider to be essentially constant. However, in order to score our algorithms for speed, we need to set our reference point above our largest exponent. The largest algorithm we have tested has the complexity

 O(aN2log2(N))⟹O(N2+1)

Thus we have not seen an algorithm larger than where is the size of the dataset. We thus set our reference point at 4. Our score for complexity now takes the form

 α(4−log(f(N))log(N))w (4.2)

Many of the algorithms we have tested clock-in around thus we shall set . Furthermore we asses complexity to be highly important, but not at the cost of all other features, thus we set . Giving us a score for complexity as

 50(4−log(f(N))log(N))2 (4.3)

### 4.1 Scalability and Dimensionality

In some instances, one may wish to differentiate between row search and column search. For a general algorithm, complexity takes these into account as a single quantity which is superceded by runtime complexity. Thus for the current metric, we allow complexity to take this score into account.

## 5 Homogeneity

By homogeneity we shall mean the homogeneity of a cluster after having determined by a clustering algorithm. To accomplish this task we will work first on a single cluster. Within this cluster we will determine how to score its individual homogeneity and then we will consider how to score the clusters in ensemble to gain our overall score.

We begin our task by considering the points in our cluster to be the vertices of a graph. In this graph we will build the minimal spanning tree in which the weights are calculated by mutual reachability distance as in HDBSCAN[6].

Once we have built our minimal spanning tree we compute the mean and variance

of the weights of our minimal spanning tree. Intuitively we guess that having a very small mean implies that our cluster is highly homogeneous. The problem we run into is that we may have a dataset with highly varying densities in different regions. Thus we shall also like to take variance into account. Consider for a moment the following though experiments:

Consider three different clusters each with 100 points. The first is the set of evenly spaced points on a circle of radius , the second is the set of evenly spaced points on a cirle of radius , and the third a set of points on a cirle of radius , but the spacings are random (Gaussian, with fixed variance). Shown here

We see that the smaller circle with evenly spaced points is the most homogeneous. It is now a question of how to rank the other 2. Which is more homogeneous? Are they the same?

In order to answer this question we appeal to the Fisher information metric as in [4, 5]. Given a set of random variables obeying some probability distribution we build a statistical manifold from its parameter space. Given that many datasets we will encounter have a large number of points

we appeal to the central limit theorem and assume that our means and variances will obey a nearly normal distribution. When we have a set

with clusters and we construct the statistical manifold in the variables:

 (θ1,θ2,…,θ2N−1,θ2N)=(μ1,σ21,…,μN,σ2N)

.

The canonical metric for a statistical manifold is given by

 gαβ(θ)=∫all space∂log(f)∂θα∂log(f)∂θβf(x,θ)dx (5.1)

In the case of Gaussian distributions the metric becomes

 g=⎡⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢⎣1/σ212/σ21⋱1/σ2N2/σ2N⎤⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥⎦ (5.2)

This gives us a length element of

 dℓ2=∑dμ2i+2dσ2iσ2i (5.3)

We recognize that this is the metric for the upper half space model of hyperbolic space, with some scaling factor on the variance. In particular, for a single Gaussian distribution, we can see the scaling in distance becomes [5]

 dF((μ1,σ1),(μ2,σ2))=√2dH((μ1√2,σ1),(μ2√2,σ2)) (5.4)

From our construction within clusters, we have the minimal spanning tree with weights determined by mutual reachability distance.

 ∀i≤|CX|,Ti=(Vi,Ei,wi)

In this case we know that all distances and variances will be positive, and thus we wish to compute homogeneity as the fisher distance of from the origin. Unfortunately, every point is infinitely far from the origin by the construction of the metric. In order to get a meaningful measure, we shall scale up every variance one exactly one, and calculate distance of a cluster from . That is, we define the score by

 hi:=dF((μi,√σ2i+1),(0,1)) (5.5)

Luckily much work has been done in this space and given we have an explicit expression for as

 hi=√2arcosh⎛⎜ ⎜⎝1+μ2i/2+(√σ2i+1−1)22√σ2i+1⎞⎟ ⎟⎠ (5.6)
###### Remark 4.

This formula comes from the fact that the hyperbolic distance is given in general by

 dH((x1,y1),(x2,y2))=arcosh(1+(x2−x1)2+(y2−y1)22y1y2)

When is small, we have a highly homogeneous cluster, and when it is large, we have an inhomogeneous cluster. We define the dataset’s homogeneity score by

 G:=1+N∑j=1hj (5.7)

This gives us the bounds

 Gmin=1

Recalling that gives us many () highly inhomogeneous clusters we set this as our reference point . Now we wish to score things from zero to one-hundred, so we pick . Finally we give our weight factor as . We pick since it gives our homogeneity score a little more importance than simple linearity, but will give extraordinarily large values only in extreme cases when is very tiny and is large. Even so we’re bounded above by

 100Gmax(Gmax−G)1.1<100G0.1max
 100Gmax(Gmax−G)1.1 (5.9)

## 6 Intercluster Distance

Intercluster distance is mildly important for most needs, but we can still glean some useful information from it. If we have many large distances between clusters this means our algorithm separates clusters well. For example, in a highly dense dataset -means is likely to have very small separation between clusters, but Quantum Dynamic Clustering is likely to have a much large separation of clusters.

In order to define our intercluster distance, we consider the distance between two given clusters .

 d(C1,C2):=minx∈C1,y∈C2d(x,y) (6.1)

where is an arbitrarily chosen metric suitable for one’s purpose. In our case we shall choose the simple Euclidean metric.

 d(x,y)=√(x−y)t(x−y),x,y∈Rn

Our overall distance for a chosen algorithm will be the sum of all intercluster distances.

 D:=∑i

Note that we only need to consider since and as is a metric . For the sake of computational ease one can simply define and equivalent

 D=12|CX|∑i=l|CX|∑j=1d(Ci,Cj)

The second distance score will be easier to code, although computationally twice as expensive.

We get the bounds:

 0≤D≤(N2)dmax=Dmax

As there are pairs of clusters to consider. If all clusters are the same distance apart, then we have exactly .

To bring this to a score within we consider our reference point to be since -means will often produce a zero distance. In light of having a potential zero distance we shall scale our score by . Finally, we scale this by . This tells us that we will take the distance at “face-value.” There is some importance to distance, but having a large intercluster distance does not overcome an algorithm’s deficiencies in other scores.

 100D1+Dmax (6.3)

## 7 Covolume

In the current context, we shall take covolume to mean the amount of space which is not filled by our clusters. This is consistent with the physical chemistry definition rather than the number theoretic definition. Thus the scoring is rather straightforward, while the calculation may take a little effort.

Consider a dataset which is a subset of . We calculate the volume as the volume of the convex hull of . Suppose now that is the set of clusters in which we enumerate as

 CX={C1,C2,…,Cm}

The volume of each cluster is the volume of its convex hull. Thus the covolume of is defined as

 CoV(X)=V(X)−m∑i=1V(Ci) (7.1)

We shall score this on as a percentage. The higher the covolume the tighter the cluster bounds which gives us a score of type:

 α(CoV(X)V(X))w

In this case we choose to be our reference point since we have with rare exception a covolume of zero from k-means clustering. That is to say, it does not produce tightly bound clusters. For our purposes we choose since the theoretical maximum is near 1. This will give us a maximum raw score of 100. We recognize that having tightly bound clusters is not of utmost importance and thus we give this a smaller weight, which reduces the percentage.

We then reveal our score for covolume as

 100(CoV(X)V(X))2 (7.2)

## 8 Shape

The idea of “shape” is complex enough that we only give an overview in this section, for a more complete treatment see [11]

Once one has properly identified clusters, the metric of scoring how well an algorithm can classify an arbitrary shape arises. This turns out to be amongst the most complicated metrics to score. For example, many survey papers (cf give some references from sofya’s data clustering book) say that an algorithm picks up an arbitrary shape or it does not. We now ask the question, “how arbitrary?” Can we quantify such a statement? It is the belief of the authors that this too, can be computed in a consistent way.

Our strategy is as follows:

1. Define clusters

2. Define the boundary points of a cluster

3. Fit a “smooth enough” curve or surface (or volume) to the boundary.

4. Compute the integral of curvature squared over the surface.

Defining the clusters is the work of whichever algorithm we are implementing. After this we need to extract the boundary of the cluster. Our initial thought was to compute the Minimal Spanning Tree of the cluster (in the mutual reachability metric) and define the boundary to be all vertices of degree one. A moment of reflection, however will reveal many counterexamples, for example, a long, sparsely connected cluster with two endpoints near each other and all other vertices internal. (include a picture here). A second though was to compute the minimal spanning tree of the entire graph and compute the boundary in the style of Cheeger (give reference)

 ∂S={(u,v)∈E(X)|u∈S,v∉S}

and picking out the vertices and as boundary points. Again, this fails when considering a graph such as

In the example above we have only two boundary points. This can’t uniquely define a “shape.”

In order to compute shape consistently we shall take the approach of polygonization of the boundary undertaken in [8]. This approach uses the DeLauney Triangulation of the cluster and extracts boundary points by oriented the edges in the triangulation. This is similar to the approach of computing the shared nearest neighbor graph as in [7], but not with the intent of building a triangulation. One may also wish to consider a barycentric division in higher dimensions. Our algorithm will be to build a triangulation in 2 or 3 dimensions and extract the boundary in the style of [8].

Once we have extracted the boundary, we need to build a surface which satisfies several criteria. First, we would like the surface to encode some of the more exotic features of the data. That is, we would like to build a curve or surface which is not simply a collection of line segments or planar regions hastily glued together to give a manifold with corners reminiscent of the early 1990s “3D” video games. We will approach this task by the technique of Bzier curves and surfaces [10].

Once we have a surface with some curvature to it, and a reasonably good fit, we shall calculate the complexity of the shape of our cluster by computing the integral of its curvature squared. This can be done efficiently for a curve [9]. For a surface we present the following calculation.

Let be our surface parametrization

 S(u,v)=∑ijPijNi4(u)Nj4(v)

The Gaussian () and mean () curvatures are defined as follow:

 K=κ1κ2 = Suu⋅Svv−S2uv(1+S2u+S2v)2 (8.1) H=κ1+κ22 = (1+S2u)Svv−2SuSvSuv+(1+S2v)Suu(1+S2u+S2v)3/2 (8.2)

Then our curvature is given by the sum squared of principal curvatures

 κ21+κ222=2H2−K (8.3)

Now we integrate

 Shape(C):=∫u1u0∫v1v0(2H2−K)dudv (8.4)

Once we have scored each cluster we give the overall score by scaling as such

 Shape:=α⎛⎝⎛⎝∑Ci∈CXShape(Ci)⎞⎠−β⎞⎠w (8.5)

We wish our overall shape score to be as high as possible. A high shape score signifies that an algorithm picks up an arbitrary shape with high precision. For this reason, we shift our score back against the simplest possible shape to pick up, which is a circle (or sphere) of unit radius. In two dimensions the curvature is constant and thus a constant positive unit. Integrating over the circumference we get . For a sphere we have two principal curvatures each of which is identically one thus we are integrating the constant function 2. Integrating over the surface area we get . Since most of our calculations will be over surfaces, we shall set . This would say that an algorithm picking up a single cluster which is a uniform circular object scores as low as possible. There is no practical limit to how high an individual cluster can score, so we scale by dividing by our maximum cluster score. . Finally, we regard this feature with utmost importance as to an algorithm’s overall accuracy, and thus we shall weight it with . If necessary, a researcher should scale this back if the highest score is arbitrarily high.

## References

• [1] Benchmarking Performance of Clustering Algorithms in Python:
• [2] A Fresh Graduate’s Guide to Software Development Tools and Technique:Chapter 6, Scalability, Khare, Huang, Doan, Kanwal, http://www.comp.nus.edu.sg/seer/book/2e/Ch06.%20Scalability.pdf
• [3] A New graph-Theoretic Approach to Clustering and Segmentation,
M. Pavan, M. Pelillo,

Proceedings of the 2003 IEEE Computer Society on Computer Vision and Pattern Recognition

http://www.dais.unive.it/pelillo/papers/cvpr03.pdf
• [4] Learning on Statistical Manifolds for Clustering and Visualization
K. Carter, R. Raich, A.O. Hero
• [5] Fisher Information Distance: A Geometrical Reading
S. Costa, S. Santos, J. Strapason
https://arxiv.org/pdf/1210.2354.pdf
• [6]

Hierarchical Density Estimates for Data Clustering, Visualization, and Outlier Detection

R. Campello, D. Moulavi, A. Zimek, J. Sander
ACM Transactions on Knowledge Discovery from Data. 10 (1): 1–51. doi:10.1145/2733381.
• [7]

Finding Clusters of Different Sizes, Shapes, and Densities in Noisy, High Dimensional Data

2003
L. Ertösz, M. Steinbach, V. Kumar
http://www-users.cs.umn.edu/kumar/papers/SIAM_snn.pdf
• [8] Polygonization of Point Clusters through Cluster Boundary Extraction for Geographical Data Mining I. Lee, V. Estivill-Castro
• [9] Efficient Squared Curvature C. Nieuwhuis, E. Toeppe, L. Gorelick, O. Vekslert, Yu. Boykov
http://www.csd.uwo.ca/ygorelic/CVPR2014_curvatureTR.pdf
• [10]
• [11] The Shape Metric for Clustering Algorithms
C. Alexander, S. Akhmametyeva, 2017


text:
# select, ? Select

Select all or part of a table, possibly with new columns

## select

Syntax: select [cols] [by groups] from t [where filters]

select retrieves specified columns from a table. It has many forms; not all are described here.

A by clause with no cols specified returns the last row in each group.

q)tbl:([] id:1 1 2 2 2;val:100 200 300 400 500)
q)select by id from tbl
id| val
--| ---
1 | 200
2 | 500

### Limiting results

To limit the returned results you can also use these forms:

select[n]
select[m n]
select[order]
select[n;order]

where

• n limits the result to the first n rows of the selection if positive, or the last n rows if negative
• m is the number of the first row to be returned: useful for stepping through query results one block of n at a time
• order is a column (or table) and sort order: use < for ascending, > for descending
select[3;>price] from bids where sym=s,size>0

This would return the three best prices for symbol s with a size greater than 0.

This construct works on in-memory tables but not on memory-mapped tables loaded from splayed or partitioned files.

Where there is a by-clause, and no sort order is specified, the result is sorted ascending by its key.

Performance characteristic

select[n] applies the where-clause on all rows of the table, and takes the first n rows, before applying the select-clause. So if you are paging it is better to store the result of the query somewhere and select[n,m] from there, rather than run the filter again.

### Performance

• Select only the columns you will use.
• Use the most restrictive constraint first.
• Ensure you have a suitable attribute on the first non-virtual constraint (e.g.p or g on sym).
• Constraints should have the unmodified column name on the left of the constraint operator (e.g. where sym in syms,…)
• When aggregating, use the virtual field first in the by-clause. (E.g. select .. by date,sym from …)

Tip

…where g=,s within …
Maybe rare to get much speedup, but if the g goes to 100,000 and then s is 1 hour of 24 you might see some overall improvement (with overall table of 30 million).

The following pattern will make use of slave threads via peach

select … by sym, … from t where sym in …, …

when sym has a g or p attribute. (Since V3.2 2014.05.02)

It uses peach for both in-memory and on-disk tables. For single-threaded, this is approx 6× faster in memory, 2× faster on disk, and uses less memory than previous releases – but mileage will vary. This is also applicable for partitioned DBs as

select … by sym, … from t where date …, sym in …, …

### Special functions

The following functions (essentially .Q.a0 in q.k) receive special treatment within select:

count, first, last, sum, prd, min, max, med, avg, wsum, wavg, var, dev, cov, cor

When used explicitly, such that it can recognize the usage, q will perform additional steps, such as enlisting results or aggregating across partitions. However, when wrapped inside another function, q does not know that it needs to perform these additional steps, and it is then left to the programmer to insert them.

q)select sum a from ([]a:1 2 3)
a
-
6
q)select {(),sum x}a from ([]a:1 2 3)
a
-
6

Cond is not supported inside q-SQL expressions

Enclose in a lambda or use Vector Conditional instead.

### Name resolution

Resolution of a name within select/exec/update is as follows:

1. column name
2. local name in (or param of) the encapsulating function
3. global name in the current working namespace – not necessarily the space in which the function was defined

Tip

You can refer explicitly to namespaces:

select (. toplevel) x from t

### Implicit arguments

When compiling functions, the implicit args x, y, z are visible to the compiler only when they are not inside the select-, by- and where-clauses. The from-clause is not masked. This can be observed by taking the value of the function and observing the second item: the args.

q)args:{(value x)1}
q)args{} / no explicit args, so x is a default implicit arg of identity (::)
,x
q)/from clause is not masked, y is detected as an implicit arg here
q)args{select from y where a=x,b=z}
xy
q)args{[x;y;z]select from y where a=x,b=z} / x,y,z are now explicit args
xyz
q)/call with wrong number of args results in rank error
q){select from ([]a:0 1;b:2 3) where a=x,b=y}[0;2]
'rank
[0]  {select from ([]a:0 1;b:2 3) where a=x,b=y}[0;2]
^
q)/works with explicit args
q){[x;y]select from ([]a:0 1;b:2 3) where a=x,b=y}[0;2]
a b
---
0 2

Q for Mortals: §9.3 The select Template
Basics: qSQL

## ? Select

For functional Select, see Basics: Functional qSQL

format: plain


text:
create a track with mismatch density from a SAM/bam file
3
0
Entering edit mode
3.6 years ago

I want to identify regions where a larger than average number of apparent varioants suggest an assembly error or a read alignment error.

Any idea how I could parse a SAM/BAM and count differences from the reference for each read which I then save in BED format?

I guess the solution in in the cigar but if someone has solved this before and could share some code, I would be very grateful.

Best S

relates to Getting number of mismatches from bam record where no solution was posted so far

sam bam mismatch • 1.0k views
0
Entering edit mode

how I could parse a SAM/BAM and count differences .... relates to "Getting number of mismatches from bam record " where no solution was posted so far

what about Zev's solution: the NM tag ?

0
Entering edit mode
3.6 years ago

Brilliant; I finally learned what NM was and it is exactly what I needed. Thanks Pierre

Hoping that the read is always right to the start position, I made of it the next command. Does this make sense?

samtools view -f 0x2 mappings.bam   | gawk -v rlen=${read_len} 'BEGIN{FS="\t"; OFS="\t"}{($16~/NM/)?split($16,nm,":"):split($17,nm,":"); print $3,$4,$4+rlen,"NM",nm[3]}' > NM_counts.bed  The NM seems to move around in my BAM between 16 and 17th columns, hence some edits To be then merged / grouped-by and summarised Best Stephane ADD COMMENT 0 Entering edit mode 3.6 years ago NM is not always in the$12 , the END position of a read on the REF is not START+read_len (indels, clipping......)

here is a solution using bioalcidaejdk: http://lindenb.github.io/jvarkit/BioAlcidaeJdk.html

 java -jar dist/bioalcidaejdk.jar -e 'stream().filter(R->!R.getReadUnmappedFlag() && R.hasAttribute("NM")).forEach(R->println(R.getContig()+"\t"+(R.getStart()-1)+"\t"+R.getEnd()+"\t"+R.getIntegerAttribute("NM")));' in.bam

rotavirus   5   75  7
rotavirus   5   75  3
rotavirus   5   75  2
rotavirus   6   74  6
rotavirus   6   76  6
rotavirus   6   71  5
rotavirus   6   76  7
rotavirus   6   76  6
rotavirus   6   76  6
rotavirus   6   76  7
rotavirus   6   76  5

0
Entering edit mode

when I can compile this I will try (THANKS)

0
Entering edit mode
3.6 years ago

meanwhile rediscovered bedtools bamtobed which seems to do precisely what I want (-ed) when I can compile the java above, I will compare. S


text:
+0

# Calculus Derivatives and tangent equations

0
788
6
+1314
Online test questions, you don't have to give me the answer as I do want to learn the process and be able to do it, but I suspect that the way the test is set up, that investigation and getting help is part of the process to encourage learning of difficult material. So answers are not necessary but mighty helpful since, I can see what is wrong, thus feel free to put new variables in. Note there is a few questions here, challenging for me, and since I can not follow the derivative rules to well, or if I do the answers are not put it in the correct form etc. The last answers I got were input right so thank you and that shows that if the process is right the system will accept the answers.

1
http://snag.gy/w8UHZ.jpg

2
http://snag.gy/FrQ15.jpg

3
http://snag.gy/sCKWg.jpg

4
http://snag.gy/eE7hY.jpg
I really would like an explanation of this question and answer, or if there was a another answer to arrive at through a different method and what that method would be. thanks.

I appreciate the help.
Apr 5, 2014

#6
+109783
+5

The chain rule is very basic and I do not think that it is expained to students very well.

Do you know how you can cancel in fractions

eg

speed*time = distance

because

$$\frac{6km}{hour}\times\frac{7hour}{1}=42km$$  Because the hours cancel out!

With calulus the d in front of the x and the y etc just stands for difference.  You can cancel out the units just like I did in the above example.

So for instance

$$\frac{dy}{du}\times \frac{du}{dx}\times \frac{dx}{dt}=\frac{dy}{dt}$$     The du's and dx's cancel out.

That is the chain rule!

Jun 2, 2014

#1
+2353
+5
Stu:

Online test questions, you don't have to give me the answer as I do want to learn the process and be able to do it, but I suspect that the way the test is set up, that investigation and getting help is part of the process to encourage learning of difficult material. So answers are not necessary but mighty helpful since, I can see what is wrong, thus feel free to put new variables in. Note there is a few questions here, challenging for me, and since I can not follow the derivative rules to well, or if I do the answers are not put it in the correct form etc. The last answers I got were input right so thank you and that shows that if the process is right the system will accept the answers.

1
http://snag.gy/w8UHZ.jpg

2
http://snag.gy/FrQ15.jpg

3
http://snag.gy/sCKWg.jpg

4
http://snag.gy/eE7hY.jpg
I really would like an explanation of this question and answer, or if there was a another answer to arrive at through a different method and what that method would be. thanks.

I appreciate the help.

Okay, let's see what I can do here,
I think I'll give you important hints for the first three and show you the whole solution to the fourth one to give you an idea.

Also I think it might help you to look at this site; http://www.mathsisfun.com/calculus/derivatives-rules.html
This website has lot's of simple explanations on various mathematical subjects and this section pretty much summarizes the rules for derivatives.

Now, for the first one, you should look into the product rule. The idea is that f(x) = g(x)*h(x) then f'(x) = g'(x)*h(x) + g(x)*h'(x)

So for example if g(x) = x 2 and h(x) = e x so f(x) = x 2*e x

then f'(x) = 2xe x + x 2e x = (2x+x 2)e x

For the second one, look at the derivatives of trigonometric functions (and learn them by heart). So, f(x) = sin(x) => f'(x) = cos(x) and g(x) = cos(x) => g'(x) = -sin(x)

Also have a look at the chain rule to see what to do with cos(pi*x).

For the third one,

Same as the second one, look at the derivatives of trigonometric functions and the chain rule. That should do the trick

I'll do the fourth one in a seperate post.
Apr 5, 2014
#2
+30386
+5
Here's one possible approach to the first part of the fourth problem. Notice that I've used the df/dx notation for derivatives rather than the f' notation, but it means the same thing.

f(x) = (2x+1) 9(3x-1) 7

Stuproblem.PNG

The steps might seem long-winded, but if you take it step by step it shouldn't be too bad.

There are other ways to approach this (perhaps Reinout will use a different one.)
Apr 5, 2014
#3
+2353
+5
Okay, so f(x) = (2x+1) 9(3x-1) 7.

Now we have two functions so we want to apply the product rule.

The product rule works for functions in the following way f(x) = g(x) * h(x)

in this case g(x) = (2x+1) 9 and h(x) = (3x-1) 7

Since we know the product rule states f'(x) = g'(x)*h(x) + g(x) * h'(x)

we have to calculate the derivatives of g(x) and h(x).

For both we need the chain rule which states f(x) = g(h(x)) => f'(x) = g'(h(x))*h'(x).

That equation might be an appaling sight so let me attempt to state it to you in simpler words.

The derivative of a function 2 within a function 1 is the derivative of the function 1 leaving the function 2 as it is multiplied by the derivative of the function 2

Since this still might seem a little fuzzy let me give you an example with the functions we have g(x) = (2x+1) 9

We could again rewrite this to g(x) = (u(x)) 9. where u(x) = 2x+1 (so u'(x) = 2) then g'(x) = 9*u(x) 8*u'(x) = 9*(2x+1) 8*2 = 18(2x+1) 8

Now, let me continue with the rest of the original question.

We just saw that g'(x) = 18(2x+1) 8

Similarly we can calculate (again using the chain rule) h'(x) = 7*(3x-1) 6*3 = 21*(3x-1) 6

Then for f'(x), we can fill in the blanks.

f'(x) = g'(x)h(x) + g(x)h'(x) = 18(2x+1) 8* (3x-1) 7 + (2x+1) 9*21(3x-1) 6

We can simplify this to 18(2x+1) 8*(3x-1) 6*(3x-1) + (2x+1) * (2x+1) 8 * 21(3x-1) 6

I did this so both terms have (2x+1) 8*(3x-1) 6 in common.

This means I can now simply the equation to (18(3x-1)+21(2x+1)) * (2x+1) 8*(3x-1) 6

Note that: 18(3x-1)+21(2x+1) = 54x-18+42x+21 = 96x+3 = 3(32x+1)

So we calculated that f'(x) = 3(32x+1)(2x+1) 8(3x-1) 6

f"(x) works in quite a similar way, where we can again use f(x) = g(x)h(x) only this time g(x) also is a multiplication of two functions so for g'(x) you'd also need to use the product rule.

Must be a case of productruleception

See whether you can do that one yourself.

Reinout

edit: just saw Alan did the same thing in the mean time
Apr 5, 2014
#4
+111396
+7
1. y = (t^2 + 5)e^t find dy/dt (or y')
There are a couple of different ways we could do this one, but let's call the expression inside the parenthesis f and the other part g.
So, we have y = fg
And, using the product rule, we have y' = f 'g + f g '
so f ' = 2t and g ' = e^t
And putting this together gives us
y' = (2t)e^t + (t^2 + 5)e^t ..... And simplifying we have
y' = e^t(t^2 + 2t + 5)

2. R(x) = 11 - 2cos(Π x)
Find R ' (x)
OK......Let's just concentrate on the "cos(Π x) " part....we'll go back and finish the rest in a sec
Note, that we can use the chain rule here. Call cos(Π x) the "outside" function and call Π x the "inside" function,
So, the derivative of the "outside function" is just -sin(Π x) and the derivative of the "inside" function is just Π
Remembering that the derivative of the constant 11 is just zero, we have
R ' (x) = -2(-sin(Π x) * Π).....And simplifying this, we have
R ' (x) = 2Πsin(Π x)

3. w = sin(8e^t)
Find w'
This is pretty much like the last one. We're going to use the chain rule here, too. Call sin(8e^t) the "outside" function and call 8e^t the "inside" function.
Then the chain rule says to take the derivative of the "outside" times the derivative of the "inside."
So the derivative of sin(8e^t) is just cos(8e^t) and the derivative of 8e^t is just itself.
And putting this together we get
w' = cos(8e^t) * 8e^t or just
8e^t cos(8e^t)

4. f(x) = y = (2x + 1)^9 (3x - 1)^7 .....Find the first and second derivatives.
This one is more "tedious" than difficult. It combines both the chain and product rules (plus a little simplifying).
As before, let's call (2x + 1)^9, "f" and let's call (3x - 1)^7, "g."
Then, y = fg and y' = f 'g + f g '
So, to calculate f ' , we'll need to employ the chain rule. Let's call (2x + 1)^9 the "outside" function and 2x + 1 the "inside" function.
The derivative of the outside is 9(2x + 1)^8 and the derivative of the inside is just 2. And multiplying these together we get 18(2x + 1)^8.
Similarly, we'll need the chain rule again to find g'. Let (3x - 1)^7 be the "outside" function and let 3x - 1 be the "inside" function.
The derivative of the outside is 7(3x - 1)^6 and the derivative of the inside is just 3. And multiplying these together we get 21(3x - 1)^6.
So, putting all this together, we get.
y' = f 'g + f g '
y' = 18(2x + 1)^8 (3x - 1)^7 + (2x + 1)^9 (21(3x - 1)^6)
Let's factor out the lowest powers on the "(2x + 1)" and "(3x - 1)" terms.
This gives (2x + 1)^8 * (3x - 1) ^6 * [18(3x - 1) + 21(2x + 1)]
And simplifying inside the brackets we have (2x + 1)^8 * (3x - 1) ^6 * [96x + 3]
And factoring a "3" out of [96x + 3], we have
3*(2x + 1)^8 * (3x - 1) ^6 * (32x + 1)

To find y '', we just extend the product rule over one more function, i.e.
y' = fgh
y'' = f' gh + fg' h + fgh'
To make things easier, I'm going to put our last answer back into this form....... (2x + 1)^8 * (3x - 1) ^6 * [96x + 3], where "f" is (2x + 1)^8, "g" is (3x - 1) ^6, and "h" is [96x + 3]
To save some time, (And because I think you see how to apply the chain rule now), f ' = 8(2x + 1)^7 * (2) = 16(2x + 1)^7 and g ' = 6(3x - 1) ^5 *(3) = 18(3x - 1) ^5 and h' = 96
Sp...let's put everything together and simplify...we have
y'' = f' gh + fg' h + fgh'
y''= (16(2x + 1)^7) * (3x - 1) ^6 * [96x + 3] + (2x + 1)^8 * 18(3x - 1) ^5 * [96x + 3] + (2x + 1)^8 * (3x - 1) ^6 * [96]
So, (as before), factoring out the lowest powers of the (2x + 1 ) and (3x -1) terms, we have
(2x + 1)^7 * (3x - 1)^5 [(16 (3x - 1)* (96x + 3) +(18) (2x +1) (96x +3) + (2x + 1) (3x -1 ) (96)] =
(2x + 1)^7 * (3x - 1)^5 [ 16 (288x^2 - 87x - 3) + 18 (192x^2 + 102x + 3) + 96(6x^2+ x -1)]
(2x + 1)^7 * (3x - 1)^5 [8640x^2 + 540x - 90]
Finally, we can factor the last term as 10 * (864x^2 + 54X - 9) = 10 * 3 * ( 288x^2 + 18x - 3) = 10 * 3 * 3 * (96x^2 + 6x - 1) = 90 (96x^2 + 6x - 1)
So we get
90 *(2x + 1)^7 * (3x - 1)^5 * (96x^2 + 6x - 1)

Whew!!! That was a long one, huh??

I hope this helps.....
Apr 5, 2014
#5
+1314
0

you mentioned the chain rule a few times, is that, product rule states f'(x) = g'(x)*h(x) + g(x) * h'(x) the same as uv' + vu'. Looks like it. Then what is To find y '', we just extend the product rule over one more function, i.e.
y' = fgh
y'' = f' gh + fg' h + fgh' , and why is it applied to the second derrivative?

Thanks

Jun 1, 2014
#6
+109783
+5

The chain rule is very basic and I do not think that it is expained to students very well.

Do you know how you can cancel in fractions

eg

speed*time = distance

because

$$\frac{6km}{hour}\times\frac{7hour}{1}=42km$$  Because the hours cancel out!

With calulus the d in front of the x and the y etc just stands for difference.  You can cancel out the units just like I did in the above example.

So for instance

$$\frac{dy}{du}\times \frac{du}{dx}\times \frac{dx}{dt}=\frac{dy}{dt}$$     The du's and dx's cancel out.

That is the chain rule!

Melody Jun 2, 2014


text:
Poster
On the Convergence Rate of Training Recurrent Neural Networks
Zeyuan Allen-Zhu · Yuanzhi Li · Zhao Song

Thu Dec 12th 10:45 AM -- 12:45 PM @ East Exhibition Hall B + C #169
How can local-search methods such as stochastic gradient descent (SGD) avoid bad local minima in training multi-layer neural networks? Why can they fit random labels even given non-convex and non-smooth architectures? Most existing theory only covers networks with one hidden layer, so can we go deeper? In this paper, we focus on recurrent neural networks (RNNs) which are multi-layer networks widely used in natural language processing. They are harder to analyze than feedforward neural networks, because the \emph{same} recurrent unit is repeatedly applied across the entire time horizon of length $L$, which is analogous to feedforward networks of depth $L$. We show when the number of neurons is sufficiently large, meaning polynomial in the training data size and in $L$, then SGD is capable of minimizing the regression loss in the linear convergence rate. This gives theoretical evidence of how RNNs can memorize data. More importantly, in this paper we build general toolkits to analyze multi-layer networks with ReLU activations. For instance, we prove why ReLU activations can prevent exponential gradient explosion or vanishing, and build a perturbation theory to analyze first-order approximation of multi-layer networks.


text:
# Convergence of measures — revisited

In this thread, I asked a question about the convergence of measures. The conjecture I posed there, which turned out to be false, was supposed to be a lemma that I wanted to use to prove a proposition, outlined as follows.

Consider the measurable space $(\mathbb R,\mathscr B_{\mathbb R})$. Suppose that $\{\mu_n\}_{n=1}^{\infty}$ is a sequence of finite Radon measures and $\mu$ is a finite Radon measure on $\mathbb R$. Suppose also that $$\lim_{n\to\infty}\mu_n(\mathbb R)=\mu(\mathbb R)\tag{1}$$ and that $\{\mu_n\}_{n=1}^{\infty}$ converges to $\mu$ vaguely, in the sense that $$\lim_{n\to\infty}\int f\,\mathrm d\mu_n=\int f\,\mathrm d\mu$$ for any $f\in C_c$, where $C_c$ is the space of compactly supported, continuous, real-to-real functions. For any $x\in\mathbb R$ and $n\in\mathbb N$, define \begin{align*}F_n(x)\equiv&\,\mu_n((-\infty,x]),\\F(x)\equiv&\,\mu((-\infty,x]).\end{align*}

Proposition:$\quad$ For any $a\in\mathbb R$ and $\varepsilon>0$, $$\limsup_{n\to\infty}F_n(a)\leq F(a+\varepsilon).$$

I figured out a proof that I think is correct, which I now share in order to seek feedback. Your thoughts are much appreciated.

Proof:$\quad$ Let $a\in\mathbb R$ and $\varepsilon>0$ be given. Also, fix $\delta>0$. Since $\mu$ is a finite Radon measure, there exists a compact set $C\subset\mathbb R$ such that $$\mu(\mathbb R)\geq\mu(C)>\mu(\mathbb R)-\frac{\delta}{5}.$$ Since compact sets are bounded, one can choose $K>0$ so large that $$-K<a<a+\varepsilon<K,$$ $C\subseteq[-K,K]$, and $$\mu(\mathbb R)\geq\mu([-K,K])>\mu(\mathbb R)-\frac{\delta}{5}.\tag{2}$$

Pick any $L>K$. Clearly, $[-K,K]\subseteq[-L,L]$. Construct a continuous function $h$ such that $h$ is 1 on $[-K,K]$, it vanishes outside $[-L,L]$, and it is linear on $[-L,-K]$ and on $[K,L]$. Then, $h\in C_c$. By vague convergence, there exists some $N_1\in\mathbb N$ such that $$\int h\,\mathrm d\mu<\int h\,\mathrm d\mu_n+\frac{2\delta}{5}\quad\forall n\geq N_1.\tag{3}$$

Also, by (1), there exists some $N_2\in\mathbb N$ such that $$\mu(\mathbb R)+\frac{\delta}{5}>\mu_n(\mathbb R)>\mu(\mathbb R)-\frac{\delta}{5}\quad\forall n\geq N_2\tag{4}.$$

Now, if $n\geq\max\{N_1,N_2\}$, then, on the one hand, \begin{align*}\mu([-K,K])=&\,\int_{[-K,K]}h\,\mathrm d\mu\leq\int h\,\mathrm d\mu<\int h\,\mathrm d\mu_n+\frac{2\delta}5\\=&\,\int_{[-L,L]}h\,\mathrm d\mu_n+\frac{2\delta}5\leq\mu_n([-L,L])+\frac{2\delta}5;\end{align*} and, on the other hand, $$\mu_n([-L,L])\leq\mu_n(\mathbb R)<\mu(\mathbb R)+\frac{\delta}{5}<\mu([-K,K])+\frac{2\delta}{5},$$ by (2) and (4). Therefore, $$\mu_n([-L,L])-\frac{2\delta}{5}<\mu([-K,K])<\mu_n([-L,L])+\frac{2\delta}{5}\quad\forall n\geq\max\{N_1,N_2\}\tag{5}.$$

Let $M>L$ be arbitrary. Construct a continuous function $g$ such that $g$ is 1 on $[-L,a]$, it vanishes outside $[-M,a+\varepsilon]$, and it is linear on $[-M,-L]$ and on $[a,a+\varepsilon]$. Then, $g\in C_c$. By vague convergence, there exists some $N_3\in\mathbb N$ such that $$\int g\,\mathrm d\mu_n<\int g\,\mathrm d\mu+\frac{\delta}{5}\quad\forall n\geq N_3.\tag{6}$$

Let $n\geq N^*\equiv\max\{N_1,N_2,N_3\}$. Then, \begin{align*} F_n(a)=&\,\mu_n((-\infty,a])=\mu_n((-\infty,-L))+\mu_n([-L,a])\\ =&\,\mu_n(\mathbb R)-\mu_n([-L,L])-\mu_n((L,\infty))+\mu_n([-L,a])\\ \leq&\,\mu_n(\mathbb R)-\mu_n([-L,L])+\mu_n([-L,a])\\ \underbrace{<}_{(5)}&\,\mu_n(\mathbb R)-\mu([-K,K])+\frac{2\delta}5+\mu_n([-L,a])\\ \underbrace{<}_{(4)}&\,\mu(\mathbb R)-\mu([-K,K])+\frac{3\delta}5+\mu_n([-L,a])\\ \underbrace{<}_{(2)}&\,\frac{4\delta}5+\mu_n([-L,a])=\int_{[-L,a]}g\,\mathrm d\mu_n+\frac{4\delta}{5}\\ \leq&\,\int g\,\mathrm d\mu_n+\frac{4\delta}{5}\underbrace{<}_{(6)}\int g\,\mathrm d\mu+\delta=\int_{[-M,a+\varepsilon]}g\,\mathrm d\mu+\delta\\ \leq&\,\mu([-M,a+\varepsilon])+\delta\leq\mu((-\infty,a+\varepsilon])+\delta=F(a+\varepsilon)+\delta. \end{align*}

Since this is true for all $n\geq N^*$, it follows that $$\limsup_{n\to\infty} F_n(a)=\inf_{k\in\mathbb N}\sup_{n\geq k}F_n(a)\leq \sup_{n\geq N^*}F_n(a)\leq F(a+\varepsilon)+\delta.$$ Given that $\delta>0$ can be made arbitrarily small, the claim follows. $\blacksquare$

Note: this proposition is needed to prove Proposition 7.19(b) in Folland (1999). The earlier printings report the result without the assumption (1), in which case the proposition I presented can be shown to be false. The errata sheet points out that the claim is true if (1) is assumed, but gives no proof. That's why I attempted to construct one. Any comments are welcome.

• If additionally $\mu_n(\mathbb{R}) = \mu(\mathbb{R})$ for all sufficiently large $n$, then $F_n(x) \rightarrow F(x)$ at any continuity point of $F$, and $\limsup_{n\rightarrow\infty} \mu_n(A) \leq \mu(A)$ for all closed sets $A$. A good reference is Billingsley's Convergence of Probability Measures, which addresses the type of question you're asking about. – snar Jul 11 '14 at 0:57
• @Snarski Even better: the assumption $\mu_n(\mathbb R)=\mu(\mathbb R)$ for a large $n$ and beyond is not even needed. This is because a somewhat similar argument shows that $\liminf_{n\to\infty} F_n(a)\geq F(a-\varepsilon)$. (In fact, this argument is simpler and does not even rely on the extra assumption (1)). This shows that if $F$ is continuous at $a$, then $\lim_{n\to\infty} F_n(a)=F(a)$. – triple_sec Jul 11 '14 at 1:01
• Neat, thanks. I prefer to be careful as pathological things can happen. For instance, if $\mu_n \Rightarrow \mu$ on $\mathbb{R}$, $X$ is a measurable subset of $\mathbb{R}$ such that $\mu(X) = \mu(\mathbb{R})$, and $f : X \rightarrow \mathbb{R}$ is continuous on $X$, then one expects $\mu_n f^{-1}\Rightarrow \mu f^{-1}$. This is false unless $\mu_n(X) \equiv \mu(X)$ for all $n$ (or except for finitely many $n$). – snar Jul 11 '14 at 4:20
• You will definitely need (1) if you only test against compactly supported functions. Otherwise, take $\mu_n=\delta_{-n}$, which converges to $\mu=0$, but $F_n(a)=1$, $F(a)=0$. – user138530 Jul 11 '14 at 4:23
• @ChristianRemling That's exactly the counterexample brought up on the textbook errata sheet. Assuming (1), though, can prevent the mass from “escaping to infinity.” Intuitively, if (1) is true, then, by regularity, there will exist a compact set on which vague convergence makes the $\{\mu_n\}_{n=1}^{\infty}$ “uniformly tight.” This ensures that only a tiny fraction of the mass can escape from this compact set, and hence the desired approximation argument using compactly supported functions can then be worked out. – triple_sec Jul 11 '14 at 6:04

This turned out to be too long to comment so I'm writing it as an answer even though it is a different question. In this case, it is not the escape of mass but the "placement" of mass. Usually we try to simplify weak convergence results by restricting to a nice subset. To do this we really require $\mu_n(X) = 1$ for all sufficiently large $n$.
To see this, take $X = \mathbb{Q} \cap [0,1]$ and define $\mu_n$ on $[0,1]$ such that $\mu_n(X) = 0$, $\mu_n([0,1]) = 1$ and take $\mu(X) = \mu([0,1]) = 1$.
(For instance, one can take $\{r_i\}_{i \geq 1}$ to be an enumeration of the rationals, set $\mu = \sum_{i=1}^\infty \delta_{r_i}2^{-i}$, $\mu_n = \sum_{i=1}^\infty \delta_{r_i + \pi/n}2^{-i}$.)
Notice that for any $f \in C_b([0,1])$, $$\delta_{r_i + \pi/n} f = f(r_i + \pi/n) \rightarrow f(r_i) = \delta_{r_i}f,$$ and since we can bound the tail of $\mu$ and $\mu_n$, $\mu_n \Rightarrow \mu$. From the mapping theorem, one expects $\mu_n h^{-1} \Rightarrow \mu h^{-1}$ for $h$ such that $\mu(D_h) = 0$, where $D_h$ is the set of discontinuities of $h$.
$$h(x) = \begin{cases} 0 & x \in \mathbb{Q} \\ 1 & x \in [0,1] \setminus\mathbb{Q}\end{cases}.$$ Notice that $h|_X$ is continuous in the sense that for any $x_n \rightarrow x$ for $x_n, x \in X$, we have $h(x_n) \rightarrow h(x)$. However, $$1 = \mu_n([0,1]\setminus \mathbb{Q}) = \mu_n h^{-1}(\{1\}) \geq \mu h^{-1}(\{1\}) = 0.$$ Since $\{1\}$ is a closed set, we do not have $$\limsup_{n\rightarrow\infty} \mu_n h^{-1}(F) \leq \mu h^{-1}(F)$$ for all closed $F$, so $\mu_n h^{-1} \not\Rightarrow \mu h^{-1}.$