Emerging Markets Journal Volume 1 (2012) | ISSN 2158-8708 (online) | DOI 10.5195/emaj.2012.15 | http://emaj.pitt.edu HOW TO GROUP FINANCIAL DATA WITH MAXIMUM HOMOGENEITY? Mehmet Baran Marmara University e-mail: mehmet.baran@marmara.edu.tr Sıtkı Sönmezer – corresponding author Beykent University e-mail: sitkisonmezer@beykent.edu.tr Abstract Grouping may be an obstacle itself or it may have to be improved to extract better information out of a data stream. Finding trends and dividing a population into parts may be crucial for analyses. This paper offers a modified version of Fisher method that may smoothen the cut point transitions and give out better results. Proven methodology is given with a comparison with the original method. The method may be helpful in forming subgroups in financial data, possibly in technical analyses. Keywords: Grouping, Fisher Method, Trends, Cut points This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 United States License. This journal is published by the University Library System of the University of Pittsburgh as part of its D-Scribe Digital Publishing Program, and is cosponsored by the University of Pittsburgh Press Volume 3 (2013) | ISSN 2158-8708 (online) | DOI 10.5195/emaj.2013.36 | http://emaj.pitt.edu http://www.library.pitt.edu/ http://www.pitt.edu/ http://www.library.pitt.edu/articles/digpubtype/index.html http://www.upress.pitt.edu/upressIndex.aspx http://creativecommons.org/licenses/by-nc-nd/3.0/us/ http://emaj.pitt.edu/ How To Group Financial Data With Maximum Homogeneity? Emerging Markets Journal | P a g e | 13 Volume 3 (2012) | ISSN 2158-8708 (online) | DOI 10.5195/emaj.2012.36 | http://emaj.pitt.edu How To Group Financial Data With Maximum Homogeneity? Mehmet Baran, Sıtkı Sönmezer INTRODUCTION It is often the case, when trying to extract information out of a financial time series data; researchers face the problem of dividing the financial data into homogenous parts. Alternatively, when the researchers aim to determine trends within a data set, it may be essential to know how to decompose a sample into sub- samples in which homogeneity is maximized. Intuition or segmenting the data visually may be used for grouping the data, however; these methods lack the efficiency when compared with the statistical methods that are numerous in the literature. Various disciplines have the problem of clustering a set of objects as there are different usages, applications and objective functions, thus, there are many variations of this clustering problem. Maharaj and Inder (1999) and Duncan, Gorr and Szczypula (2001) have given methods of clustering time series data. Therefore, numerous clustering algorithms from different fields of study are present in the literature however; the merits of these algorithms are dubious (Gonzales 1985). The method developed in this study is a modification of the method suggested by Fisher (1958) that tries to find a methodology for grouping and forming sub-samples. It has to be noted that Fisher considered two related, but different problems; first one is introduced as the unrestricted problem and second as the restricted problem. This paper deals with the restricted problem part of the method, which arises in many cases in finance where certain conditions, on the basis of prior information, theory or for convenience, are imposed most of the time and offers a modified version that gives smaller error terms. The first part of the study provides literature survey regarding with the method used in finance related sectors. Secondly, Fisher method and how it is improved is presented in the second part and the final part is concluded with an example showing the improvement. LITERATURE REVIEW Despite defining homogenous groups are studied vastly by statisticians and hydrologists, in this paper, only the articles that have utilized methods that determine homogeneous grouping with financial data are examined. However, one main method, Fisher method, has to be mentioned as it has been used by many studies, including this one. The method introduced by Fisher (1958) attempts to minimize the MSE, takes the decrease n variance into consideration due to combining which decreases variance and ignores the increase in bias. A review of the algorithm is presented here below. Huang and Zhang have investigated structural changes in Singapore’s private housing market and in particular the impact of government policies on housing price determination by utilizing Fisher method to find “1) the specification of the number of changes in the model 2) the detection of the change point, or the boundaries of intervals over which each of the model pieces applies 3) the estimation of the model parameters within each subdomain.” (2012) How To Group Financial Data With Maximum Homogeneity? Emerging Markets Journal | P a g e | 14 Volume 3 (2012) | ISSN 2158-8708 (online) | DOI 10.5195/emaj.2012.36 | http://emaj.pitt.edu Kumar and Patel (2010) have come up with a new method derived from Fisher method which is based on the tradeoff between decreased variance and increased bias arising from combining. With this modified version, it is possible to determine when it is beneficial to combine or not. Adams and Lim also utilized the Fisher method in forming sub groups for their data to minimize sum of squared deviations for growth polarity (2011). REVIEW OF THE CLASSICAL FISHER GROUPING ALGORITHM In order to understand how Fisher grouping algorithm works, consider that a time series consisting of N data points x(i), 1<=i<=N, is given. Assume that this time series is divided into K contiguous and mutually exclusive segments: [ ] [ ] [ ] [ ] (1) where [ ]denotes all the integers between a and b, inclusive, and if r>s. Let the mean for the j th segment [ ]be denoted by : ∑ ( ) (2) Note that and . The mean squares (MS) error term for the jth segment, can be computed as: ∑ ( ( ) ) (3) and the MS error for the whole time series, E, is defined as the sum of the MS errors of all segments ∑ (4) After these preliminary definitions, Fisher grouping problem can be defined as follows: Determine the segment boundaries , , .... , in (1) in such a way that the MS error E defined in Eq. (4) is minimized. The How To Group Financial Data With Maximum Homogeneity? Emerging Markets Journal | P a g e | 15 Volume 3 (2012) | ISSN 2158-8708 (online) | DOI 10.5195/emaj.2012.36 | http://emaj.pitt.edu set of error minimizing segment boundaries ( )is called the Fisher segmentation. Fisher segmentation gives the most homogeneous possible division of any given time series into K segments. The segment boundaries represent the transition regions between neighboring segments. It is possible to solve the Fisher grouping problem via exhaustive search only for small time series. The number of all possible K-segmentations for a time series of length N is ( ) ( ) (5) Which grows exponentially with N. Hence, exhaustive search is impractical for large N. Fortunately, a dynamic programming approach is provided by Fisher. This approach consists of three main steps which is listed herebelow: 1) Calculate the error matrix e[i,j] [ ] ∑ ( ) (6) [ ] ∑ ( ( ) [ ]) (7) Where m[i,j] denotes the mean of all points within [i+1,j], and e[i,j] denotes the variance of all points in the same interval. 2) Compute the vector D[2,r] for all r, r2, compute [ ] ( [ ] [ ]) (9) How To Group Financial Data With Maximum Homogeneity? Emerging Markets Journal | P a g e | 16 Volume 3 (2012) | ISSN 2158-8708 (online) | DOI 10.5195/emaj.2012.36 | http://emaj.pitt.edu Note that D[m,r] denotes the optimal LS cost of the division of time series [1,r] into m segments. Given the above algorithm, one can compute D[K,N] recursively, which is the quantity we are looking for. At the first step, one must calculate the matrix a[i,j]. Then the vectors D[2,2], D[2,3], ...., D[2,N] must be computed. Then using these values, one can compute D[3,3], D[3,4], ...., D[3,N] and so on. The algorithm will stop when it reaches D[K,N], which is the desired quantity. All steps of the algorithm has ( ) complexity, and there are K steps. Hence, the overall complexity is ( ). PROBLEMS OF FISHER GROUPING IN SEGMENTING FINANCIAL DATA Fisher grouping is perfect for time series where the data remains in near-constant regimes for long durations, and the transitions between these near constant regimes are relatively fast. This is one reason why Fisher algorithm found particular favor with hydrologists: Most of the lakes and rivers have near-constant depth for long periods of time, with very rapid change of depth during short intervals of time (ie, spring rains) between them. Unfortunately, financial data does not fit into this pattern. "Trends" in financial data are rarely defined by approximately constant levels. More frequently, trends are defined by approximately constant rates of growth or decay, and changes in the growth rate can be considered as changes in trend. Therefore, Fisher algorithm in its classical form (ie, Equations (1)-(9) given above) is largely unsuitable for discovering trends in financial data, and boundaries between neighboring trends. Below, a more developed version of Fisher's algorithm will be proposed, in which the deficiencies mentioned will be addressed. Fisher's original grouping algorithm is "zero order", as it approximates segments with constants, which are zero order curves. The proposed algorithm, in contrast, will approximate segments with first order curves, i.e. lines, which are ordinary least squares (OLS) approximations of the data in the segment. We will call this newly proposed algorithm as the first order Fisher grouping algorithm. FIRST ORDER FISHER GROUPING ALGORITHM The main difference between zeroth order and the proposed first order algorithms comes from a modification of Eqs. (6)-(7), which calculates the segment error. In Fisher's original article, this error is calculated around the segment mean , via Eqns. (6)-(7). In contrast, we propose the following equations for segment error calculation: How To Group Financial Data With Maximum Homogeneity? Emerging Markets Journal | P a g e | 17 Volume 3 (2012) | ISSN 2158-8708 (online) | DOI 10.5195/emaj.2012.36 | http://emaj.pitt.edu [ ] ∑ ( ) ∑ ∑ ( ) (10) [ ] ∑ ( ∑ ) (11) [ ] [ ] [ ] (12) [ ] ∑ ( ) [ ] ∑ (13) [ ] ∑ ( [ ] [ ] [ ]) (14) Note that these are the well-known linear regression equations. After calculating the e[i,j] matrix, the rest of the first order algorithm is exactly the same with the zeroth order algorithm. Namely: 1) Calculate e[i,j] by using Eqs. (10-14) 2) Calculate D[2,r] for all 2