Text mining targets unstructured text as opposed to structured text in web mining and databases in data mining. and patterns in natural language processing. Data Mining and Natural language processing both find patterns  and information is retrieved with queries while Text mining finds nuggets. That said, text mining has overlap with all of the above.
The processing stages in text mining are text storage, text preprocessing, text transformation or attribute generation, attribute selection, Data mining or pattern discovery and interpretation or evaluation. Storing text doesn't necessarily need to be in raw form only but can be stored as document clusters. Text is characterized by one or more of the following:
source  : human input, automated input in different languages and formats
context : words and phrases create context.
ambiguity : word and sentence are disambiguated based on ontology
noise : erroneous data, misspelt data, stop words, etc
format : normal speech, interactive chat, etc.
sparseness: aka document density percentage in typical document
Text processing involves cleanup, tokenization, part of speech tagging, word sense disambiguation and semantic structures. Text cleanup involves removing junk characters, binary formats, tables, figures and formulas. Tokenization is splitting up into a set of tokens. Part of speech tagging is associating words with parts of speech which can be grammar based or statistically based. Word sense disambiguation is how many distinct senses is used in a given sentence. Semantic processing involves chunking which produces syntactic constructs like noun phrases and verb phrases or full parsing which yields a tree. Chunking is more common.
Text transformation involves text representation and feature selection which characterizes the document. A classifier is used to automatically generate labels (attributes) from the features fed into it.
Feature selection is based on two approaches - one is to select the features before using them in a classifier, which requires a feature ranking method and the othe is to select the features on how well they work in a classifier. In the latter case the classifier is part of the feature selection method and is often an iterative process.  However the classifier needs to be trained and the evaluation is based on actual use. The features are evaluated iteratively. In the former case, there are many more choices to feature selection since this is independent of the classifier. Each feature is evaluated once lowering computational cost. Attributes generated are the labels of the classes automatically produced by the classifier on the selected features.
Attribute selection is done because higher dimensions causes issues with machine learners and hence irrelevant features are removed.
After the attributes are selected, patterns can be found with data mining techniques and the results interpreted.

Review of text mining slides from CSE634 presentation by Chiwara, Al-Ayyoub, Hossain and Gupta
 

Fast Marching Method

In the family of boundary value problem solving methods, Fast Marching method is another numerical method. It solves the Eikonal equation

Introduction

Fast marching method was introduced by Sethian. It was originally designed for forward only propagation of the boundary with positive values for speed, but has later been revised  for including both positive and negative values for speed and this is now called  Generalized Fast Marching Method.

Motivation

This method allows us to convert the problem of  continuously forward or backward moving front into a stationary formulation where the arrival surface gives the front at zero –level. Furthermore, using a grid with unit-distance and  numerical techniques, this method is very fast, efficient and highly stable.

Terminology

Arrival surface: The arrival surface results from the travel time function that gives the arrival of the front at a given point

Narrow band: This is the set of active data points being considered for the calculation of the next level of the front. The travel time of each of the data points is computed based on the gradient between the previous point and the current as well as the gradient between current and the next point.

Initial Data

The speed at a given data point is known. Each data point can have  a different speed

Algorithm

The fast marching method solves boundary value problems that describe how a closed curve evolves as a function of time t with a speed f(x) in the normal direction at a point x on the curve. The speed is given but the time it takes for the contour to pass the point x is calculated by the equation. Different points may have different speeds. The region grows outward from the seed of the area. The more the points considered, the better the contour. The fast marching method makes use of a stationary surface that gives the arrival information of the moving boundary. From the initial curve, build a little bit of the surface upwards, with each iteration always starting from the initial position. It's called fast because it uses a fast heap sort algorithm that can tell the proper data point to update and hence to build the surface. For each of the N points at any given height h, the next point is determined and always in the order from the priority queue. The surface grows with height h in a monotonically increasing order because previously evaluated grid points are not revisited. This is because of non-negative speed and because the heap guarantees that the grid point with the minimum distance is selected first out of the data points in the sweep of N points at any level. Hence the entire operation of determining the next contour takes NlogN time.

This is a numerical method because it tries to view the curve as a set of discrete markers. The fast marching method has applications in image processing such as for region growing.

In the fast march method, let us say there are N points on the zero-level of the surface we track in a N*N*N unit distance grid. The curve is pushed outwards in unit-distances. Then, each step involves the following:

1) The point with the smallest distance is removed from the priority queue and its value is frozen so that we don't have to revisit it again and our direction is strictly outward.

2) Points are added to the priority queue to maintain unit-thickness

3) The distance of the neighbors of the removed point are recomputed. The finite difference is a multivariable quadratic equation.

we did not discuss the partial differential equation (PDE) or how to solve it numerically. Specifically, we did not discuss the distance function (time cost) based on which the next data point is selected. Here we mention it with an example.

We start from a data point whose travel time is frozen i.e. we don't change it again and proceed outwards to the neighboring points from it. We put these neighboring points in a priority queue where the points are sorted based on the minimum travel time. Then the top point in this priority queue is removed which gives the minimum travel time. This point is then frozen. The neighboring points are updated with the Euclidean norm of the gradients. The gradients are along the x,y,z axes and are computed as derivatives (inverse of speed) defined as the difference in the travel time between the new point and the old point on the same axes over a unit distance. We take the maximum of this gradient. The gradients are also taken between the next point and the new point in the normal direction. We take the minimum of this gradient. The Eucledian norm is nothing but a sum of squares just like we measure a hypotenuse. So we take the squares of the maximum and minimum respectively for each of the three axes. This gives us a quadratic  in travel time t at the new point and speed v that has a well-defined solution as one of either the travel time at the previous point + (unit-distance / speed) or the next point + (unit-distance/speed). In the fast marching method, we simplify this computation to take forward only direction and at zero-level plane so only x and y co-ordinates.

We repeat this for all other neighboring points around the one we removed from the priority queue.

It might so happen that one or more of the neighboring points are in the active set  i.e. in the priority queue. If we take a new point for which we want to compute the travel time as the center, then there are four neighbours around it and one of them is the smallest of all the trial values. Then there are four cases we need to consider.  1) where none of the neighbors are in the active set, 2) one of the neighbors is in the active set 3) two of the neighbors are in the active set and 4) all three of these neighbors are in the active set.

In the case where none of the neighbors are in the active set, the travel time of the new point is the sum of that of A and the inverse speed function f (f is based on the unit-distance).

In the case where one of the neighboring points b is already in the active set, then we know that its travel time is more than the one we just removed and also that the travel time of the new point will be lesser than the sum of the travel time for b and the inverse speed function f.

If two of the neighbors are in the active set and one of them is frozen, then this point is in the forward direction and will be the contributor to the inverse speed function since the frozen value will not be changed and this degenerates to the case 1)

If three of the neighbors are in the active set, the smallest values in each co-ordinate direction is taken and this degenerates to the cases discussed above.

Thus we obtain the travel times of the neighboring points as well and add them to the priority queue

The neighboring points are typically referred to as the narrow band and we locate the grid point with the minimum travel time.

 

Computational Complexity

The entire operation of determining the next contour takes NlogN time.

 

Error Analysis

There are two limitations of this approach.

This method does not apply to continuous boundaries

There is a potential large error in the first step of the numerical calculation.

Courtesy : Al Khalifa, S. Fomel : Fast Marching Implementation, Sethian : Fast Marching Method.

 

rebuilding the contour in fast marching method

In the previous post, we did not discuss the partial differential equation (PDE) or how to solve it numerically. Specifically, we did not discuss the distance function (time cost) based on which the next data point is selected. In this post we mention it with an example.
We start from a data point whose travel time is frozen i.e. we don't change it again and proceed outwards to the neighboring points from it. We put these neighboring points in a priority queue where the points are sorted based on the minimum travel time. Then the top point in this priority queue is removed which gives the minimum travel time. This point is then frozen. The neighboring points are updated with the Euclidean norm of the gradients. The gradients are along the x,y,z axes and are computed as derivatives (inverse of speed) defined as the difference in the travel time between the new point and the old point on the same axes over a unit distance. We take the maximum of this gradient. The gradients are also taken between the next point and the new point in the normal direction. We take the minimum of this gradient. The Eucledian norm is nothing but a sum of squares just like we measure a hypotenuse. So we take the squares of the maximum and minimum respectively for each of the three axes. This gives us a quadratic  in travel time t at the new point and speed v that has a well-defined solution as one of either the travel time at the previous point + (unit-distance / speed) or the next point + (unit-distance/speed). In the fast marching method, we simplify this computation to take forward only direction and at zero-level plane so only x and y co-ordinates.
We repeat this for all other neighboring points around the one we removed from the priority queue.
It might so happen that one or more of the neighboring points are in the active set  i.e. in the priority queue. If we take a new point for which we want to compute the travel time as the center, then there are four neighbours around it and one of them is the smallest of all the trial values. Then there are four cases we need to consider.  1) where none of the neighbors are in the active set, 2) one of the neighbors is in the active set 3) two of the neighbors are in the active set and 4) all three of these neighbors are in the active set.
In the case where none of the neighbors are in the active set, the travel time of the new point is the sum of that of A and the inverse speed function f (f is based on the unit-distance).
In the case where one of the neighboring points b is already in the active set, then we know that its travel time is more than the one we just removed and also that the travel time of the new point will be lesser than the sum of the travel time for b and the inverse speed function f.
If two of the neighbors are in the active set and one of them is frozen, then this point is in the forward direction and will be the contributor to the inverse speed function since the frozen value will not be changed and this degenerates to the case 1)
If three of the neighbors are in the active set, the smallest values in each co-ordinate direction is taken and this degenerates to the cases discussed above.
Thus we obtain the travel times of the neighboring points as well and add them to the priority queue
The neighboring points are typically referred to as the narrow band and we locate the grid point with the minimum travel time.

The fast marching method solves boundary value problems that describe how a closed curve evolves as a function of time t with a speed f(x) in the normal direction at a point x on the curve. The speed is given but the time it takes for the contour to pass the point x is calculated by the equation. Different points may have different speeds. The region grows outward from the seed of the area. The more the points considered, the better the contour. The fast marching method makes use of a stationary surface that gives the arrival information of the moving boundary. From the initial curve, build a little bit of the surface upwards, with each iteration always starting from the initial position. It's called fast because it uses a fast heap sort algorithm that can tell the proper data point to update and hence to build the surface. For each of the N points at any given height h, the next point is determined and always in the order from the priority queue. The surface grows with height h in a monotonically increasing order because previously evaluated grid points are not revisited. This is because of non-negative speed and because the heap guarantees that the grid point with the minimum distance is selected first out of the data points in the sweep of N points at any level. Hence the entire operation of determining the next contour takes NlogN time.
This is a numerical method because it tries to view the curve as a set of discrete markers. The fast marching method has applications in image processing such as for region growing.
(Courtesy: Sethian @ Berkeley)
In the fast march method, let us say there are N points on the zero-level of the surface we track in a N*N*N unit distance grid. The curve is pushed outwards in unit-distances. Then, each step involves the following:
1) The point with the smallest distance is removed from the priority queue and its value is frozen so that we don't have to revisit it again and our direction is strictly outward.
2) Points are added to the priority queue to maintain unit-thickness
3) The distance of the neighbors of the removed point are recomputed. The finite difference is a multivariable quadratic equation.
Each point in the N*N*N is removed once from the priority queue.
(courtesy: Sean Mauch and David Breen from Caltech)
There are several data structures used by such level set methods. For example, there are :
1) narrow band : This data structure restricts contour propagation calculations to a thin band of data points adjacent to the boundary instead of the three dimensional surface. The data points in this narrow band are rebuild again for each step of the propagation as mentioned but not detailed above.
2) sparse field : This sparse field level set method uses a set of linked lists instead of the priority queue in the narrow band. The linked lists are populated with the same active data points around the boundary as above.
3) sparse block : This divides the volume into small cubic blocks of a set of active data points each. Then another coarse grid stores the pointers only to those blocks that meet the zero-level narrow band
4) Octree : The octree level set method uses a tree of nested cubes and the leaf nodes of this tree contain the distance value.  5) The Run length encoding compresses the region away from the narrow band with the sign but the compression is not applied to the narrow band. An additional acceleration lookup table based on the number of runs per cross section is also used.
(courtesy: Wikipedia)

I came across an interesting problem today and I will mention it here verbatim and try to solve it. The question was how do you delete a node from a singly linked list if the head is not given. So we only have the current node and the node has to be freed. Futhermore, the singly linked list is not a circular list that we can traverse to find the head.  Since we don't know the head and we can't traverse the list, we don't know the previous node to update its reference.
By deleting the node and not the knowing the previous node, we have broken the list and created dangling references. So one solution I suggested was that we treat the list as immutable physically and overlay a layer that shows the logical list by skipping over the nodes that are deleted. So we pass through the nodes that are deleted during traversal without doing any operation on them. We can keep additional state per node in a wrapper that says if it is deleted or not. Another approach is to scan the memory for all occurance of the current pointer and set it to null now that the current node is freed though this could break users of the structures that may not be expecting a null pointer where it was previously expecting a valid pointer. That may depend on how the list is used.
 

I want to discuss a technical problem I came across today. I will change the problem domain and entities so that I can present the salient points. Let us consider there is a hypothetical web service with multiple data providers. These data providers are not isolated. They may provide data from their own source and/or they might get/update the data in other providers. You need the existing data providers and more can be added at any time. Adding or deleting more data providers is seamless and does not hamper the web service operations.  Data providers can fail but these don't affect the overall operation since there is redundancy in the data owned by any node and there are at least three copies. The web service, however, can go online or offline and presents a single point of failure. We would like to discuss the replacement strategy for the web service  and particularly the test plan around it. For example, we would like to know whether there was any regression in any of the queries from the customer to the web service. How do we go about the testing ?
The data comes from different sources and the web service maintains state in its own database. Typically the web server and the database server are provisioned on separate virtual machines. This is so because the web server requires more cpu and the database server requires more memory and storage. However, in this case let us assume that we treat the web server and database together and that they are hosted on the same virtual machine. It is this virtual machine that we want to replace.
Initially we could treat the whole system as a black box and test the system with different workloads on the web server. Most of these can be capture and replay workloads from the previous web server. However, that is not sufficient in itself because the workloads may not detect all regression. So we look at the changes and scope them to the layers and components and then we design specific tests around them. For example, these tests could be breadth and depth oriented on the data that they operate on. They could also cover edge cases and if the queries use strings, then try lower case, upper case, different unicode characters and long strings. We may also need performance and security tests. The Service level agreement such as the SLA could include metrics for performance and availability.  Since the system has multiple points of failure, availability could be interpreted as a cumulative of the quorum of available resources. This could be a weighted mean since the web server is also involved. However, addition and deletion of data providers does not affect availability unless it falls short of the minimum needed.
Changes to the system could also span layers in which case we may have to test as isolated as well as end to end. For example, we can test one layer by checking against the data from the lower layers. In addition, we can test end to end to include different data providers.
 

The fast marching method solves boundary value problems that describe how a closed curve evolves as a function of time t with a speed f(x) in the normal direction at a point x on the curve. The speed is given but the time it takes for the contour to pass the point x is calculated by the equation. Different points may have different speeds. The region grows outward from the seed of the area. The more the points considered, the better the contour. The fast marching method makes use of a stationary surface that gives the arrival information of the moving boundary. From the initial curve, build a little bit of the surface upwards, with each iteration always starting from the initial position. It's called fast because it uses a fast heap sort algorithm that can tell the proper data point to update and hence to build the surface. For each of the N points at any given height h, the next point is determined and always in the order from the priority queue. The surface grows with height h in a monotonically increasing order because previously evaluated grid points are not revisited. This is because of non-negative speed and because the heap guarantees that the grid point with the minimum distance is selected first out of the data points in the sweep of N points at any level. Hence the entire operation of determining the next contour takes NlogN time.
This is a numerical method because it tries to view the curve as a set of discrete markers. The fast marching method has applications in image processing such as for region growing.
(Courtesy: Sethian @ Berkeley)
We will revisit the fast marching method for its implementation and discuss clustering but for now let us look at the other partial differential methods in that category.
The partial differential equation (PDE) based methods solve PDE equations by a numerical scheme.  When we use PDE for curve propagation, we use a cost function and use a minimization technique to find the next data point to consider.
There are three different PDE methods. The first one that we discussed earlier was the fast marching method. In this we consider the distance function to be always positive so that the curve expands outwards from the seed. However, the distance function can be both positive and negative and so a variation of the method that takes into consideration the sign of the distance function has been proposed and that is called the generalized fast marching method.
The other two methods are the Parametric methods and the level set methods. The parametric methods are based on parameterizing the contour based on some sampling strategy and then evolve each element according to the surrounding data points and the internal terms. When the parameters involve the sum of internal and external energy associated to a current contour  and tries to minimize it, we delineate an object outline and these outlines are called snakes. The snake calculation is fast and easy and therefore valuable in video processing as well which consists of tracking the snake on the series of images in a video.
The level set method uses the contour as obtained from a height h on the stationary surface that gives arrival information. This is called the zero-level which gives the contour. As opposed to fast marching methods, the level set method can have distances that are positive or negative. The level set method does not use parameters but generalizes the approach by going to a higher dimension (third) which is the geometric properties of the evolving structure.
The PDE methods have to consider topology changes such as curve splitting or merging.
If the data points cross over each other, or if the shape breaks into two, then the curve propagation should still be able to continue.