In computer displays, filmmaking, television production, video games and other kinetic displays, scrolling is sliding text, images or video across a monitor or display, vertically or horizontally. "Scrolling," as such, does not change the layout of the text or pictures but moves (pans or tilts) the user's view across what is apparently a larger image that is not wholly seen. A common television and movie special effect is to scroll credits, while leaving the background stationary. Scrolling may take place completely without user intervention (as in film credits) or, on an interactive device, be triggered by touchscreen or a keypress and continue without further intervention until a further user action, or be entirely controlled by input devices. Scrolling may take place in discrete increments (perhaps one or a few lines of text at a time), or continuously (smooth scrolling). Frame rate is the speed at which an entire image is redisplayed. It is related to scrolling in that changes to text and image position can only happen as often as the image can be redisplayed. When frame rate is a limiting factor, one smooth scrolling technique is to blur images during movement that would otherwise appear to "jump". == Computing == === Implementation === Scrolling is often carried out on a computer by the CPU (software scrolling) or by a graphics processor. Some systems feature hardware scrolling, where an image may be offset as it is displayed, without any frame buffer manipulation (see also hardware windowing). This was especially common in 8 and 16bit video game consoles. === UI paradigms === In a WIMP-style graphical user interface (GUI), user-controlled scrolling is carried out by manipulating a scrollbar with a mouse, or using keyboard shortcuts, often the arrow keys. Scrolling is often supported by text user interfaces and command line interfaces. Older computer terminals changed the entire contents of the display one screenful ("page") at a time; this paging mode requires fewer resources than scrolling. Scrolling displays often also support page mode. Typically certain keys or key combinations page up or down; on PC-compatible keyboards the page up and page down keys or the space bar are used; earlier computers often used control key combinations. Some computer mice have a scroll wheel, which scrolls the display, often vertically, when rolled; others have scroll balls or tilt wheels which allow both vertical and horizontal scrolling. Some software supports other ways of scrolling. Adobe Reader has a mode identified by a small hand icon ("hand tool") on the document, which can then be dragged by clicking on it and moving the mouse as if sliding a large sheet of paper. When this feature is implemented on a touchscreen it is called kinetic scrolling. Touch-screens often use inertial scrolling, in which the scrolling motion of an object continues in a decaying fashion after release of the touch, simulating the appearance of an object with inertia. An early implementation of such behavior was in the "Star7" PDA of Sun Microsystems ca. 1991–1992. Scrolling can be controlled in other software-dependent ways by a PC mouse. Some scroll wheels can be pressed down, functioning like a button. Depending on the software, this allows both horizontal and vertical scrolling by dragging in the direction desired; when the mouse is moved to the original position, scrolling stops. A few scroll wheels can also be tilted, scrolling horizontally in one direction until released. On touchscreen devices, scrolling is a multi-touch gesture, done by swiping a finger on the screen vertically in the direction opposite to where the user wants to scroll to. If any content is too wide to fit on a display, horizontal scrolling is required to view all of it. In applications such as graphics and spreadsheets there is often more content than can fit either the width or the height of the screen at a comfortable scale, and scrolling in both directions is necessary. === Infinite scrolling === In contrast to material divided into discrete pages, the web design approach of infinite scrolling dynamically adds new material to the user display, leading to a continuous, apparently bottomless or endless scrolling experience. === Text === In languages written horizontally, such as most Western languages, text documents longer than will fit on the screen are often displayed wrapped and sized to fit the screen width, and scrolled vertically to bring desired content into view. It is possible to display lines too long to fit the display without wrapping, scrolling horizontally to view each entire line. However, this requires inconvenient constant line-by-line scrolling, while vertical scrolling is only needed after reading a full screenful. Software such as word processors and web browsers normally uses word-wrapping to display as many words in a single line as will fit the width of the screen or window or, for text organised in columns, each column. === Demos === Scrolling texts, also referred to as scrolltexts or scrollers, played an important part in the birth of the computer demo culture. The software crackers often used their deep knowledge of computer platforms to transform the information that accompanied their releases into crack intros. The sole role of these intros was to scroll the text on the screen in an impressive way. == Film and television == Scrolling is commonly used to display the credits at the end of films and television programs. Scrolling is often used in the form of a news ticker towards the bottom of the picture for content such as television news, scrolling sideways across the screen, delivering short-form content. In the dynamic layout of kinetic typography, scrolling typography can scroll across the flat screen, or can appear to recede or advance. An iconic example is the Star Wars opening crawl inspired by the Flash Gordon serials. == Video games == In computer and video games, scrolling of a playing field allows the player to control an object in a large contiguous area. Early examples of this method include Taito's 1974 vertical-scrolling racing video game Speed Race, Sega's 1976 forward-scrolling racing games Moto-Cross (Fonz) and Road Race, and Super Bug. Previously the flip-screen method was used to indicate moving backgrounds. The Namco Galaxian arcade system board introduced with Galaxian in 1979 pioneered a sprite system that animated pre-loaded sprites over a scrolling background, which became the basis for Nintendo's Radar Scope and Donkey Kong arcade hardware and home consoles such as the Nintendo Entertainment System. Parallax scrolling, which was first featured in Moon Patrol, involves several semi-transparent layers (called playfields), which scroll on top of each other at varying rates in order to give an early pseudo-3D illusion of depth. Belt scrolling is a method used in side-scrolling beat 'em up games with a downward camera angle where players can move up and down in addition to left and right. == Studies == A 1993 article by George Fitzmaurice studied spatially aware palmtop computers. These devices had a 3D sensor, and moving the device caused the contents to move as if the contents were fixed in place. This interaction could be referred to as “moving to scroll.” Also, if the user moved the device away from their body, they would zoom in; conversely, the device would zoom out if the user pulled the device closer to them. Smartphone cameras and “optical flow” image analysis utilize this technique nowadays. A 1996 research paper by Jun Rekimoto analyzed tilting operations as scrolling techniques on small screen interfaces. Users could not only tilt to scroll, but also tilt to select menu items. These techniques proved especially useful for field workers, since they only needed to hold and control the device with one hand. A study from 2013 by Selina Sharmin, Oleg Špakov, and Kari-Jouko Räihä explored the action of reading text on a screen while the text auto-scrolls based on the user's eye tracking patterns. The control group simply read text on a screen and manually scrolled. The study found that participants preferred to read primarily at the top of the screen, so the screen scrolled down whenever participants’ eyes began to look toward the bottom of the screen. This auto-scrolling caused no statistically significant difference in reading speed or performance. An undated study occurring during or after 2010 by Dede Frederick, James Mohler, Mihaela Vorvoreanu, and Ronald Glotzbach noted that parallax scrolling "may cause certain people to experience nausea."
Tabletopia
Tabletopia is an online portal for users to play and create virtual tabletop games. The platform is developed by Tabletopia Inc and initially was released as a web browser based service after a successful crowdfunding campaign in August 2015. In December 2016 Tabletopia was released on Steam, and later in 2018 became available in AppStore and Google Play. == Gameplay == Tabletopia is a sandbox system for running any game. That means no AI or rules enforcement. Participating players will have to know how to play the game. Nevertheless, the platform has some automated actions available, like card-shuffling and dealing, dice-rolling, magnetic placement of components in special zones, hand management, and some others. Tabletopia also features ready game setups for various player numbers to facilitate gameplay. It also has customisable camera controls which let players save camera positions and switch between them using hot keys. People can use the Game Designer mode to design and create their own board games using the component library. They can then monetise the games with a 70/30 split to the game designer. == Development == Tabletopia was created in early 2014, by Tim Bokarev and his partners Artem Zinoviev and Dmitry Sergeev. These co-founders already had experience in the video and board games industry. Their other projects include Promo Interactive, an internet advertising agency, Playtox, a mobile MMORPG, Igrology, a game studio, and Tesera.ru, the main Russian-speaking board gaming portal. By Spring 2014, Artem, Dmitry and Tim created Tabletopia Inc. USA and started development. Tabletopia is a multinational crew that includes professionals from USA, Ukraine, Australia, Ireland, and Germany. The Kickstarter campaign in August 2015 earned $133,721 by 2,545 backers. Tabletopia received Green Light on Steam in September 2015 and was released on Steam in March 2016. The platform remained in Early Access until December 2016, when it was officially released on Steam and on the web. In February 2018 it was released as a stand-alone app for iOS tablets, and in September 2018 for Android tablets.
Principal component analysis
Principal component analysis (PCA) is a linear dimensionality reduction technique with applications in exploratory data analysis, visualization and data preprocessing. The data are linearly transformed onto a new coordinate system such that the directions (principal components) capturing the largest variation in the data can be easily identified. The principal components of a collection of points in a real coordinate space are a sequence of p {\displaystyle p} unit vectors, where the i {\displaystyle i} -th vector is the direction of a line that best fits the data while being orthogonal to the first i − 1 {\displaystyle i-1} vectors. Here, a best-fitting line is defined as one that minimizes the average squared perpendicular distance from the points to the line. These directions (i.e., principal components) constitute an orthonormal basis in which different individual dimensions of the data are linearly uncorrelated. Many studies use the first two principal components in order to plot the data in two dimensions and to visually identify clusters of closely related data points. Principal component analysis has applications in many fields such as population genetics, microbiome studies, and atmospheric science. == Overview == When performing PCA, the first principal component of a set of p {\displaystyle p} variables is the derived variable formed as a linear combination of the original variables that explains the most variance. The second principal component explains the most variance in what is left once the effect of the first component is removed, and we may proceed through p {\displaystyle p} iterations until all the variance is explained. PCA is most commonly used when many of the variables are highly correlated with each other and it is desirable to reduce their number to an independent set. The first principal component can equivalently be defined as a direction that maximizes the variance of the projected data. The i {\displaystyle i} -th principal component can be taken as a direction orthogonal to the first i − 1 {\displaystyle i-1} principal components that maximizes the variance of the projected data. For either objective, it can be shown that the principal components are eigenvectors of the data's covariance matrix. Thus, the principal components are often computed by eigendecomposition of the data covariance matrix or singular value decomposition of the data matrix. PCA is the simplest of the true eigenvector-based multivariate analyses and is closely related to factor analysis. Factor analysis typically incorporates more domain-specific assumptions about the underlying structure and solves eigenvectors of a slightly different matrix. PCA is also related to canonical correlation analysis (CCA). CCA defines coordinate systems that optimally describe the cross-covariance between two datasets while PCA defines a new orthogonal coordinate system that optimally describes variance in a single dataset. Robust and L1-norm-based variants of standard PCA have also been proposed. == History == PCA was invented in 1901 by Karl Pearson, as an analogue of the principal axis theorem in mechanics; it was later independently developed and named by Harold Hotelling in the 1930s. Depending on the field of application, it is also named the discrete Karhunen–Loève transform (KLT) in signal processing, the Hotelling transform in multivariate quality control, proper orthogonal decomposition (POD) in mechanical engineering, singular value decomposition (SVD) of X (invented in the last quarter of the 19th century), eigenvalue decomposition (EVD) of XTX in linear algebra, factor analysis (for a discussion of the differences between PCA and factor analysis see Ch. 7 of Jolliffe's Principal Component Analysis), Eckart–Young theorem (Harman, 1960), or empirical orthogonal functions (EOF) in meteorological science (Lorenz, 1956), empirical eigenfunction decomposition (Sirovich, 1987), quasiharmonic modes (Brooks et al., 1988), spectral decomposition in noise and vibration, and empirical modal analysis in structural dynamics. == Intuition == PCA can be thought of as fitting a p-dimensional ellipsoid to the data, where each axis of the ellipsoid represents a principal component. If some axis of the ellipsoid is small, then the variance along that axis is also small. To find the axes of the ellipsoid, we must first center the values of each variable in the dataset on 0 by subtracting the mean of the variable's observed values from each of those values. These transformed values are used instead of the original observed values for each of the variables. Then, we compute the covariance matrix of the data and calculate the eigenvalues and corresponding eigenvectors of this covariance matrix. Then we must normalize each of the orthogonal eigenvectors to turn them into unit vectors. Once this is done, each of the mutually-orthogonal unit eigenvectors can be interpreted as an axis of the ellipsoid fitted to the data. This choice of basis will transform the covariance matrix into a diagonalized form, in which the diagonal elements represent the variance of each axis. The proportion of the variance that each eigenvector represents can be calculated by dividing the eigenvalue corresponding to that eigenvector by the sum of all eigenvalues. Biplots and scree plots (degree of explained variance) are used to interpret findings of the PCA. == Details == PCA is defined as an orthogonal linear transformation on a real inner product space that transforms the data to a new coordinate system such that the greatest variance by some scalar projection of the data comes to lie on the first coordinate (called the first principal component), the second greatest variance on the second coordinate, and so on. Consider an n × p {\displaystyle n\times p} data matrix, X, with column-wise zero empirical mean (the sample mean of each column has been shifted to zero), where each of the n rows represents a different repetition of the experiment, and each of the p columns gives a particular kind of feature (say, the results from a particular sensor). Mathematically, the transformation is defined by a set of size l {\displaystyle l} (where l {\displaystyle l} is usually selected to be strictly less than p {\displaystyle p} to reduce dimensionality) of p {\displaystyle p} -dimensional vectors of weights or coefficients w ( k ) = ( w 1 , … , w p ) ( k ) {\displaystyle \mathbf {w} _{(k)}=(w_{1},\dots ,w_{p})_{(k)}} that map each row vector x ( i ) = ( x 1 , … , x p ) ( i ) {\displaystyle \mathbf {x} _{(i)}=(x_{1},\dots ,x_{p})_{(i)}} of X to a new vector of principal component scores t ( i ) = ( t 1 , … , t l ) ( i ) {\displaystyle \mathbf {t} _{(i)}=(t_{1},\dots ,t_{l})_{(i)}} , given by t k ( i ) = x ( i ) ⋅ w ( k ) f o r i = 1 , … , n k = 1 , … , l {\displaystyle {t_{k}}_{(i)}=\mathbf {x} _{(i)}\cdot \mathbf {w} _{(k)}\qquad \mathrm {for} \qquad i=1,\dots ,n\qquad k=1,\dots ,l} in such a way that the individual variables t 1 , … , t l {\displaystyle t_{1},\dots ,t_{l}} of t considered over the data set successively inherit the maximum possible variance from X, with each coefficient vector w constrained to be a unit vector. The above may equivalently be written in matrix form as T = X W {\displaystyle \mathbf {T} =\mathbf {X} \mathbf {W} } where T i k = t k ( i ) {\displaystyle {\mathbf {T} }_{ik}={t_{k}}_{(i)}} , X i j = x j ( i ) {\displaystyle {\mathbf {X} }_{ij}={x_{j}}_{(i)}} , and W j k = w j ( k ) {\displaystyle {\mathbf {W} }_{jk}={w_{j}}_{(k)}} . === First component === In order to maximize variance, the first weight vector w(1) thus has to satisfy w ( 1 ) = arg max ‖ w ‖ = 1 { ∑ i ( t 1 ) ( i ) 2 } = arg max ‖ w ‖ = 1 { ∑ i ( x ( i ) ⋅ w ) 2 } {\displaystyle \mathbf {w} _{(1)}=\arg \max _{\Vert \mathbf {w} \Vert =1}\,\left\{\sum _{i}(t_{1})_{(i)}^{2}\right\}=\arg \max _{\Vert \mathbf {w} \Vert =1}\,\left\{\sum _{i}\left(\mathbf {x} _{(i)}\cdot \mathbf {w} \right)^{2}\right\}} Equivalently, writing this in matrix form gives w ( 1 ) = arg max ‖ w ‖ = 1 { ‖ X w ‖ 2 } = arg max ‖ w ‖ = 1 { w T X T X w } {\displaystyle \mathbf {w} _{(1)}=\arg \max _{\left\|\mathbf {w} \right\|=1}\left\{\left\|\mathbf {Xw} \right\|^{2}\right\}=\arg \max _{\left\|\mathbf {w} \right\|=1}\left\{\mathbf {w} ^{\mathsf {T}}\mathbf {X} ^{\mathsf {T}}\mathbf {Xw} \right\}} Since w(1) has been defined to be a unit vector, it equivalently also satisfies w ( 1 ) = arg max { w T X T X w w T w } {\displaystyle \mathbf {w} _{(1)}=\arg \max \left\{{\frac {\mathbf {w} ^{\mathsf {T}}\mathbf {X} ^{\mathsf {T}}\mathbf {Xw} }{\mathbf {w} ^{\mathsf {T}}\mathbf {w} }}\right\}} The quantity to be maximised can be recognised as a Rayleigh quotient. A standard result for a positive semidefinite matrix such as XTX is that the quotient's maximum possible value is the largest eigenvalue of the matrix, which occurs when w is the corresponding eigenvector. With w(1) found, the first principal component of a data vector
Clustering illusion
The clustering illusion is the tendency to erroneously consider the inevitable "streaks" or "clusters" arising in small samples from random distributions to be non-random. The illusion is caused by a human tendency to underpredict the amount of variability likely to appear in a small sample of random or pseudorandom data. Thomas Gilovich, an early author on the subject, argued that the effect occurs for different types of random dispersions. Some might perceive patterns in stock market price fluctuations over time, or clusters in two-dimensional data such as the locations of impact of World War II V-1 flying bombs on maps of London. Although Londoners developed specific theories about the pattern of impacts within London, a statistical analysis by R. D. Clarke originally published in 1946 showed that the impacts of V-2 rockets on London were a close fit to a random distribution. == Similar biases == Using this cognitive bias in causal reasoning may result in the Texas sharpshooter fallacy, in which differences in data are ignored and similarities are overemphasized. More general forms of erroneous pattern recognition are pareidolia and apophenia. Related biases are the illusion of control which the clustering illusion could contribute to, and insensitivity to sample size in which people don't expect greater variation in smaller samples. A different cognitive bias involving misunderstanding of chance streams is the gambler's fallacy. == Possible causes == Daniel Kahneman and Amos Tversky explained this kind of misprediction as being caused by the representativeness heuristic (which itself they also first proposed).
Dynamic time warping
In time series analysis, dynamic time warping (DTW) is an algorithm for measuring similarity between two temporal sequences, which may vary in speed. For instance, similarities in walking could be detected using DTW, even if one person was walking faster than the other, or if there were accelerations and decelerations during the course of an observation. DTW has been applied to temporal sequences of video, audio, and graphics data — indeed, any data that can be turned into a one-dimensional sequence can be analyzed with DTW. A well-known application has been automatic speech recognition, to cope with different speaking speeds. Other applications include speaker recognition and online signature recognition. It can also be used in partial shape matching applications. In general, DTW is a method that calculates an optimal match between two given sequences (e.g. time series) with certain restriction and rules: Every index from the first sequence must be matched with one or more indices from the other sequence, and vice versa The first index from the first sequence must be matched with the first index from the other sequence (but it does not have to be its only match) The last index from the first sequence must be matched with the last index from the other sequence (but it does not have to be its only match) The mapping of the indices from the first sequence to indices from the other sequence must be monotonically increasing, and vice versa, i.e. if j > i {\displaystyle j>i} are indices from the first sequence, then there must not be two indices l > k {\displaystyle l>k} in the other sequence, such that index i {\displaystyle i} is matched with index l {\displaystyle l} and index j {\displaystyle j} is matched with index k {\displaystyle k} , and vice versa We can plot each match between the sequences 1 : M {\displaystyle 1:M} and 1 : N {\displaystyle 1:N} as a path in a M × N {\displaystyle M\times N} matrix from ( 1 , 1 ) {\displaystyle (1,1)} to ( M , N ) {\displaystyle (M,N)} , such that each step is one of ( 0 , 1 ) , ( 1 , 0 ) , ( 1 , 1 ) {\displaystyle (0,1),(1,0),(1,1)} . In this formulation, we see that the number of possible matches is the Delannoy number. The optimal match is denoted by the match that satisfies all the restrictions and the rules and that has the minimal cost, where the cost is computed as the sum of absolute differences, for each matched pair of indices, between their values. The sequences are "warped" non-linearly in the time dimension to determine a measure of their similarity independent of certain non-linear variations in the time dimension. This sequence alignment method is often used in time series classification. Although DTW measures a distance-like quantity between two given sequences, it doesn't guarantee the triangle inequality to hold. In addition to a similarity measure between the two sequences (a so called "warping path" is produced), by warping according to this path the two signals may be aligned in time. The signal with an original set of points X(original), Y(original) is transformed to X(warped), Y(warped). This finds applications in genetic sequence and audio synchronisation. In a related technique sequences of varying speed may be averaged using this technique see the average sequence section. This is conceptually very similar to the Needleman–Wunsch algorithm. == Implementation == This example illustrates the implementation of the dynamic time warping algorithm when the two sequences s and t are strings of discrete symbols. For two symbols x and y, d ( x , y ) {\displaystyle d(x,y)} is a distance between the symbols, e.g., d ( x , y ) = | x − y | {\displaystyle d(x,y)=|x-y|} . int DTWDistance(s: array [1..n], t: array [1..m]) { DTW := array [0..n, 0..m] for i := 0 to n for j := 0 to m DTW[i, j] := infinity DTW[0, 0] := 0 for i := 1 to n for j := 1 to m cost := d(s[i], t[j]) DTW[i, j] := cost + minimum(DTW[i-1, j ], // insertion DTW[i , j-1], // deletion DTW[i-1, j-1]) // match return DTW[n, m] } where DTW[i, j] is the distance between s[1:i] and t[1:j] with the best alignment. We sometimes want to add a locality constraint. That is, we require that if s[i] is matched with t[j], then | i − j | {\displaystyle |i-j|} is no larger than w, a window parameter. We can easily modify the above algorithm to add a locality constraint (differences marked). However, the above given modification works only if | n − m | {\displaystyle |n-m|} is no larger than w, i.e. the end point is within the window length from diagonal. In order to make the algorithm work, the window parameter w must be adapted so that | n − m | ≤ w {\displaystyle |n-m|\leq w} (see the line marked with () in the code). int DTWDistance(s: array [1..n], t: array [1..m], w: int) { DTW := array [0..n, 0..m] w := max(w, abs(n-m)) // adapt window size () for i := 0 to n for j:= 0 to m DTW[i, j] := infinity DTW[0, 0] := 0 for i := 1 to n for j := max(1, i-w) to min(m, i+w) DTW[i, j] := 0 for i := 1 to n for j := max(1, i-w) to min(m, i+w) cost := d(s[i], t[j]) DTW[i, j] := cost + minimum(DTW[i-1, j ], // insertion DTW[i , j-1], // deletion DTW[i-1, j-1]) // match return DTW[n, m] } == Warping properties == The DTW algorithm produces a discrete matching between existing elements of one series to another. In other words, it does not allow time-scaling of segments within the sequence. Other methods allow continuous warping. For example, Correlation Optimized Warping (COW) divides the sequence into uniform segments that are scaled in time using linear interpolation, to produce the best matching warping. The segment scaling causes potential creation of new elements, by time-scaling segments either down or up, and thus produces a more sensitive warping than DTW's discrete matching of raw elements. == Complexity == The time complexity of the DTW algorithm is O ( N M ) {\displaystyle O(NM)} , where N {\displaystyle N} and M {\displaystyle M} are the lengths of the two input sequences. The 50 years old quadratic time bound was broken in 2016: an algorithm due to Gold and Sharir enables computing DTW in O ( N 2 / log log N ) {\displaystyle O({N^{2}}/\log \log N)} time and space for two input sequences of length N {\displaystyle N} . This algorithm can also be adapted to sequences of different lengths. Despite this improvement, it was shown that a strongly subquadratic running time of the form O ( N 2 − ϵ ) {\displaystyle O(N^{2-\epsilon })} for some ϵ > 0 {\displaystyle \epsilon >0} cannot exist unless the Strong exponential time hypothesis fails. While the dynamic programming algorithm for DTW requires O ( N M ) {\displaystyle O(NM)} space in a naive implementation, the space consumption can be reduced to O ( min ( N , M ) ) {\displaystyle O(\min(N,M))} using Hirschberg's algorithm. == Fast computation == Fast techniques for computing DTW include PrunedDTW, SparseDTW, FastDTW, and the MultiscaleDTW. A common task, retrieval of similar time series, can be accelerated by using lower bounds such as LB_Keogh, LB_Improved, or LB_Petitjean. However, the Early Abandon and Pruned DTW algorithm reduces the degree of acceleration that lower bounding provides and sometimes renders it ineffective. In a survey, Wang et al. reported slightly better results with the LB_Improved lower bound than the LB_Keogh bound, and found that other techniques were inefficient. Subsequent to this survey, the LB_Enhanced bound was developed that is always tighter than LB_Keogh while also being more efficient to compute. LB_Petitjean is the tightest known lower bound that can be computed in linear time. == Average sequence == Averaging for dynamic time warping is the problem of finding an average sequence for a set of sequences. NLAAF is an exact method to average two sequences using DTW. For more than two sequences, the problem is related to that of multiple alignment and requires heuristics. DBA is currently a reference method to average a set of sequences consistently with DTW. COMASA efficiently randomizes the search for the average sequence, using DBA as a local optimization process. == Supervised learning == A nearest-neighbour classifier can achieve state-of-the-art performance when using dynamic time warping as a distance measure. == Amerced Dynamic Time Warping == Amerced Dynamic Time Warping (ADTW) is a variant of DTW designed to better control DTW's permissiveness in the alignments that it allows. The windows that classical DTW uses to constrain alignments introduce a step function. Any warping of the path is allowed within the window and none beyond it. In contrast, ADTW employs an additive penalty that is incurred each time that the path is warped. Any amount of warping is allowed, but each warping action incurs a direct penalty. ADTW significantly outperforms DTW with windowing when applied as a nearest neighbor classifier on a set of benchmark time series classification tasks. == Alternative approaches == In functional data analysis, time series are regarde
Closest point method
The closest point method (CPM) is an embedding method for solving partial differential equations on surfaces. The closest point method uses standard numerical approaches such as finite differences, finite element or spectral methods in order to solve the embedding partial differential equation (PDE) which is equal to the original PDE on the surface. The solution is computed in a band surrounding the surface in order to be computationally efficient. In order to extend the data off the surface, the closest point method uses a closest point representation. This representation extends function values to be constant along directions normal to the surface. == Definitions == Closest Point function: Given a surface S , c p ( x ) {\displaystyle {\mathcal {S}},cp(\mathbf {x} )} refers to a (possibly non-unique) point belonging to S {\displaystyle {\mathcal {S}}} , which is closest to x {\displaystyle \mathbf {x} } [SE]. Closest point extension: Let S {\displaystyle {\mathcal {S}}} , be a smooth surface in R d {\displaystyle \mathbb {R} ^{d}} . The closest point extension of a function u : S → R {\displaystyle u:{\mathcal {S}}\rightarrow \mathbb {R} } , to a neighborhood Ω {\displaystyle \Omega } of S {\displaystyle {\mathcal {S}}} , is the function v : Ω → R {\displaystyle v:\Omega \rightarrow \mathbb {R} } , defined by v ( x ) = u ( c p ( x ) ) {\displaystyle v(\mathbf {x} )=u(cp(\mathbf {x} ))} . == Closest point method == Initialization consists of these steps [EW]: If it is not already given, a closest point representation of the surface is constructed. A computational domain is chosen. Typically this is a band around the surface. Replace surface gradients by standard gradients in R 3 {\displaystyle \mathbb {R} ^{3}} . Solution is initialized by extending the initial surface data on to the computational domain using the closest point function. After initialization, alternate between the following two steps: Using the closest point function, extend the solution off the surface to the computational domain. Compute the solution to the embedding PDE on a Cartesian mesh in the computational domain for one time step. == Banding == The surface PDE is extended into R 3 {\displaystyle \mathbb {R} ^{3}} however it is only necessary to solve this new PDE near the surface. Hence, we solve the PDE in a band surrounding the surface for efficient computational purposes. Ω c x : ‖ x − c p ( x ) ‖ 2 ≤ λ {\displaystyle \Omega _{c}{x:\|x-cp(x)\|_{2}\leq \lambda }} where λ {\displaystyle \lambda } is the bandwidth. == Example: Heat equation on a circle == Using initial profile u S ( θ , t ) = sin ( θ ) {\displaystyle u_{S}(\theta ,t)=\sin(\theta )} leads to the solution u S ( θ , t ) = exp ( − t ) sin ( θ ) {\displaystyle u_{S}(\theta ,t)=\exp(-t)\sin(\theta )} for the heat equation. Forward Euler time-stepping is used with relation Δ t = 0.1 Δ x 2 {\displaystyle \Delta t=0.1\Delta x^{2}} and degree-four interpolation polynomials for the interpolations. Second-order centered differences are used for the spatial discretization. The CPM results in the expected second order error in the solution u {\displaystyle u} . == Applications == The closest point method can be applied to various PDEs on surfaces. Reaction–diffusion problems on point clouds [RD], eigenvalue problems [EV], and level set equations [LS] are a few examples.
Density-based clustering validation
Density-Based Clustering Validation (DBCV) is a metric designed to assess the quality of clustering solutions, particularly for density-based clustering algorithms like DBSCAN, Mean shift, and OPTICS. This metric is particularly suited for identifying concave and nested clusters, where traditional metrics such as the Silhouette coefficient, Davies–Bouldin index, or Calinski–Harabasz index often struggle to provide meaningful evaluations. Unlike traditional validation measures, which often rely on compact and well-separated clusters, DBCV index evaluates how well clusters are defined in terms of local density variations and structural coherence. This metric was introduced in 2014 by David Moulavi and colleagues in their work. It utilizes density connectivity principles to quantify clustering structures, making it especially effective at detecting arbitrarily shaped clusters in concave datasets, where traditional metrics may be less reliable. The DBCV index has been employed for clustering analysis in bioinformatics, ecology, techno-economy, and health informatics , as well as in numerous other fields. == Definition == DBCV index evaluates clustering structures by analyzing the relationships between data points within and across clusters. Given a dataset X = x 1 , x 2 , . . . , x n {\displaystyle X={x_{1},x_{2},...,x_{n}}} , a density-based algorithm partitions it into K clusters C 1 , C 2 , . . . , C K {\displaystyle {C_{1},C_{2},...,C_{K}}} . Each point x i {\displaystyle x_{i}} belongs to a specific cluster, denoted as C c l u s t e r ( x i ) {\displaystyle C_{cluster(x_{i})}} A key concept in DBCV index is the notion of density-connected paths. Two points within the same cluster are considered density-connected if there exists a sequence of intermediate points linking them, where each consecutive pair meets a predefined density criterion. The density-based distance between two points is determined by identifying the optimal path that minimizes the maximum local reachability distance along its trajectory. DBCV index extends the Silhouette coefficient by redefining cluster cohesion and separation using density-based distances: Within-cluster density distance measures how closely a point is related to other members of its cluster: a i = 1 | C c l u s t e r ( x i ) | − 1 ∑ x j ∈ C c l u s t e r ( x i ) , y ≠ x d d e n s i t y ( x j , x i ) {\displaystyle a_{i}={\frac {1}{|C_{cluster(x_{i})}|-1}}\sum _{x_{j}\in C_{cluster(x_{i})},y\neq x}d_{density}(x_{j},x_{i})} Nearest-cluster density distance quantifies how far a point is from the closest external cluster: b i = min C ≠ C cluster ( x i ) C ∈ { C 1 , … , C K } ( 1 | C | ∑ x j ∈ C d density ( x i , x j ) ) . {\displaystyle b_{i}=\min _{C\neq C_{{\text{cluster}}(x_{i})} \atop C\in \{C_{1},\dots ,C_{K}\}}\left({\frac {1}{|C|}}\sum _{x_{j}\in C}d_{\text{density}}(x_{i},x_{j})\right).} Using these measures, the DBCV index is computed as: D B C V = 1 n ∑ i = 1 n b i − a i max ( a i , b i ) {\displaystyle DBCV={\frac {1}{n}}\sum _{i=1}^{n}{\frac {b_{i}-a_{i}}{\max(a_{i},b_{i})}}} == Explanation == DBCV index values range between −1 and +1: +1: Strongly cohesive and well-separated clusters. 0: Ambiguous clustering structure. −1: Poorly formed clusters or incorrect assignments. By leveraging density-based distances instead of traditional Euclidean measures, DBCV index provides a more robust evaluation of clustering performance in datasets with irregular or non-spherical distributions.