Nonsmooth DC programming approach to clusterwise linear regression : Optimality conditions and algorithms
- Authors: Bagirov, Adil , Ugon, Julien
- Date: 2018
- Type: Text , Journal article
- Relation: Optimization Methods and Software Vol. 33, no. 1 (2018), p. 194-219
- Relation: http://purl.org/au-research/grants/arc/DP140103213
- Full Text: false
- Reviewed:
- Description: The clusterwise linear regression problem is formulated as a nonsmooth nonconvex optimization problem using the squared regression error function. The objective function in this problem is represented as a difference of convex functions. Optimality conditions are derived, and an algorithm is designed based on such a representation. An incremental approach is proposed to generate starting solutions. The algorithm is tested on small to large data sets. © 2017 Informa UK Limited, trading as Taylor & Francis Group.
Solving minimax problems : Local smoothing versus global smoothing
- Authors: Bagirov, Adil , Sultanova, Nargiz , Al Nuaimat, Alia , Taheri, Sona
- Date: 2018
- Type: Text , Conference proceedings
- Relation: 4th International Conference on Numerical Analysis and Optimization, NAO-IV 2017; Muscat, Oman; 2nd-5th January 2017; published in Numerical Analysis and Optimization NAO-IV (part of the Springer Proceedings in Mathematics and Statistics book series PROMS, volume 235) Vol. 235, p. 23-43
- Full Text: false
- Reviewed:
- Description: The aim of this chapter is to compare different smoothing techniques for solving finite minimax problems. We consider the local smoothing technique which approximates the function in some neighborhood of a point of nondifferentiability and also global smoothing techniques such as the exponential and hyperbolic smoothing which approximate the function in the whole domain. Computational results on the collection of academic test problems are used to compare different smoothing techniques. Results show the superiority of the local smoothing technique for convex problems and global smoothing techniques for nonconvex problems. © 2018, Springer International Publishing AG, part of Springer Nature.
- Description: Springer Proceedings in Mathematics and Statistics
A proximal bundle method for nonsmooth DC optimization utilizing nonconvex cutting planes
- Authors: Joki, Kaisa , Bagirov, Adil , Karmitsa, Napsu , Makela, Marko
- Date: 2017
- Type: Text , Journal article
- Relation: Journal of Global Optimization Vol. 68, no. 3 (2017), p. 501-535
- Relation: http://purl.org/au-research/grants/arc/DP140103213
- Full Text: false
- Reviewed:
- Description: In this paper, we develop a version of the bundle method to solve unconstrained difference of convex (DC) programming problems. It is assumed that a DC representation of the objective function is available. Our main idea is to utilize subgradients of both the first and second components in the DC representation. This subgradient information is gathered from some neighborhood of the current iteration point and it is used to build separately an approximation for each component in the DC representation. By combining these approximations we obtain a new nonconvex cutting plane model of the original objective function, which takes into account explicitly both the convex and the concave behavior of the objective function. We design the proximal bundle method for DC programming based on this new approach and prove the convergence of the method to an -critical point. The algorithm is tested using some academic test problems and the preliminary numerical results have shown the good performance of the new bundle method. An interesting fact is that the new algorithm finds nearly always the global solution in our test problems.
Batch clustering algorithm for big data sets
- Authors: Alguliyev, Rasim , Aliguliyev, Ramiz , Bagirov, Adil , Karimov, Rafael
- Date: 2017
- Type: Text , Conference proceedings
- Relation: 10th IEEE International Conference on Application of Information and Communication Technologies, AICT 2016; Baku, Azerbaijan; 12th-14th October 2016 p. 1-4
- Full Text: false
- Reviewed:
- Description: Vast spread of computing technologies has led to abundance of large data sets. Today tech companies like, Google, Facebook, Twitter and Amazon handle big data sets and log terabytes, if not petabytes, of data per day. Thus, there is a need to find similarities and define groupings among the elements of these big data sets. One of the ways to find these similarities is data clustering. Currently, there exist several data clustering algorithms which differ by their application area and efficiency. Increase in computational power and algorithmic improvements have reduced the time for clustering of big data sets. But it usually happens that big data sets can't be processed whole due to hardware and computational restrictions. In this paper, the classic k-means clustering algorithm is compared to the proposed batch clustering (BC) algorithm for the required computation time and objective function. The BC algorithm is designed to cluster large data sets in batches but maintain the efficiency and quality. Several experiments confirm that batch clustering algorithm for big data sets is more efficient in using computational power, data storage and results in better clustering compared to k-means algorithm. The experiments are conducted with the data set of 2 (two) million two-dimensional data points. © 2016 IEEE.
DC programming algorithm for clusterwise linear L1 regression
- Authors: Bagirov, Adil , Taheri, Sona
- Date: 2017
- Type: Text , Journal article
- Relation: Journal of the Operations Research Society of China Vol. 5, no. 2 (2017), p. 233-256
- Relation: http://purl.org/au-research/grants/arc/DP140103213
- Full Text: false
- Reviewed:
- Description: The aim of this paper is to develop an algorithm for solving the clusterwise linear least absolute deviations regression problem. This problem is formulated as a nonsmooth nonconvex optimization problem, and the objective function is represented as a difference of convex functions. Optimality conditions are derived by using this representation. An algorithm is designed based on the difference of convex representation and an incremental approach. The proposed algorithm is tested using small to large artificial and real-world data sets. © 2017, Operations Research Society of China, Periodicals Agency of Shanghai University, Science Press, and Springer-Verlag Berlin Heidelberg.
New diagonal bundle method for clustering problems in large data sets
- Authors: Karmitsa, Napsu , Bagirov, Adil , Taheri, Sona
- Date: 2017
- Type: Text , Journal article
- Relation: European Journal of Operational Research Vol. 263, no. 2 (2017), p. 367-379
- Relation: http://purl.org/au-research/grants/arc/DP140103213
- Full Text: false
- Reviewed:
- Description: Clustering is one of the most important tasks in data mining. Recent developments in computer hardware allow us to store in random access memory (RAM) and repeatedly read data sets with hundreds of thousands and even millions of data points. This makes it possible to use conventional clustering algorithms in such data sets. However, these algorithms may need prohibitively large computational time and fail to produce accurate solutions. Therefore, it is important to develop clustering algorithms which are accurate and can provide real time clustering in large data sets. This paper introduces one of them. Using nonsmooth optimization formulation of the clustering problem the objective function is represented as a difference of two convex (DC) functions. Then a new diagonal bundle algorithm that explicitly uses this structure is designed and combined with an incremental approach to solve this problem. The method is evaluated using real world data sets with both large number of attributes and large number of data points. The proposed method is compared with two other clustering algorithms using numerical results. © 2017 Elsevier B.V.
Optimization based clustering algorithms for authorship analysis of phishing emails
- Authors: Seifollahi, Sattar , Bagirov, Adil , Layton, Robert , Gondal, Iqbal
- Date: 2017
- Type: Text , Journal article
- Relation: Neural Processing Letters Vol. 46, no. 2 (2017), p. 411-425
- Relation: http://purl.org/au-research/grants/arc/DP140103213
- Full Text: false
- Reviewed:
- Description: Phishing has given attackers power to masquerade as legitimate users of organizations, such as banks, to scam money and private information from victims. Phishing is so widespread that combating the phishing attacks could overwhelm the victim organization. It is important to group the phishing attacks to formulate effective defence mechanism. In this paper, we use clustering methods to analyze and characterize phishing emails and perform their relative attribution. Emails are first tokenized to a bag-of-word space and, then, transformed to a numeric vector space using frequencies of words in documents. Wordnet vocabulary is used to take effects of similar words into account and to reduce sparsity. The word similarity measure is combined with the term frequencies to introduce a novel text transformation into numeric features. To improve the accuracy, we apply inverse document frequency weighting, which gives higher weights to features used by fewer authors. The k-means and recently introduced three optimization based algorithms: MS-MGKM, INCA and DCClust are applied for clustering purposes. The optimization based algorithms indicate the existence of well separated clusters in the phishing emails dataset. © 2017, Springer Science+Business Media New York.
Prediction of monthly rainfall in Victoria, Australia : Clusterwise linear regression approach
- Authors: Bagirov, Adil , Mahmood, Arshad , Barton, Andrew
- Date: 2017
- Type: Text , Journal article
- Relation: Atmospheric Research Vol. 188, no. (2017), p. 20-29
- Relation: http://purl.org/au-research/grants/arc/DP140103213
- Full Text: false
- Reviewed:
- Description: This paper develops the Clusterwise Linear Regression (CLR) technique for prediction of monthly rainfall. The CLR is a combination of clustering and regression techniques. It is formulated as an optimization problem and an incremental algorithm is designed to solve it. The algorithm is applied to predict monthly rainfall in Victoria, Australia using rainfall data with five input meteorological variables over the period of 1889–2014 from eight geographically diverse weather stations. The prediction performance of the CLR method is evaluated by comparing observed and predicted rainfall values using four measures of forecast accuracy. The proposed method is also compared with the CLR using the maximum likelihood framework by the expectation-maximization algorithm, multiple linear regression, artificial neural networks and the support vector machines for regression models using computational results. The results demonstrate that the proposed algorithm outperforms other methods in most locations. © 2017 Elsevier B.V.
An algorithm for clustering using L1-norm based on hyperbolic smoothing technique
- Authors: Bagirov, Adil , Mohebi, Ehsan
- Date: 2016
- Type: Text , Journal article
- Relation: Computational Intelligence Vol. 32, no. 3 (2016), p. 439-457
- Relation: http://purl.org/au-research/grants/arc/DP140103213
- Full Text: false
- Reviewed:
- Description: Cluster analysis deals with the problem of organization of a collection of objects into clusters based on a similarity measure, which can be defined using various distance functions. The use of different similarity measures allows one to find different cluster structures in a data set. In this article, an algorithm is developed to solve clustering problems where the similarity measure is defined using the L1-norm. The algorithm is designed using the nonsmooth optimization approach to the clustering problem. Smoothing techniques are applied to smooth both the clustering function and the L1-norm. The algorithm computes clusters sequentially and finds global or near global solutions to the clustering problem. Results of numerical experiments using 12 real-world data sets are reported, and the proposed algorithm is compared with two other clustering algorithms. ©2015 Wiley Periodicals, Inc.
Constrained self organizing maps for data clusters visualization
- Authors: Mohebi, Ehsan , Bagirov, Adil
- Date: 2016
- Type: Text , Journal article
- Relation: Neural Processing Letters Vol. 43, no. 3 (2016), p. 849-869
- Full Text: false
- Reviewed:
- Description: High dimensional data visualization is one of the main tasks in the field of data mining and pattern recognition. The self organizing maps (SOM) is one of the topology visualizing tool that contains a set of neurons that gradually adapt to input data space by competitive learning and form clusters. The topology preservation of the SOM strongly depends on the learning process. Due to this limitation one cannot guarantee the convergence of the SOM in data sets with clusters of arbitrary shape. In this paper, we introduce Constrained SOM (CSOM), the new version of the SOM by modifying the learning algorithm. The idea is to introduce an adaptive constraint parameter to the learning process to improve the topology preservation and mapping quality of the basic SOM. The computational complexity of the CSOM is less than those with the SOM. The proposed algorithm is compared with similar topology preservation algorithms and the numerical results on eight small to large real-world data sets demonstrate the efficiency of the proposed algorithm. © 2015, Springer Science+Business Media New York.
Nonsmooth DC programming approach to the minimum sum-of-squares clustering problems
- Authors: Bagirov, Adil , Taheri, Sona , Ugon, Julien
- Date: 2016
- Type: Text , Journal article
- Relation: Pattern Recognition Vol. 53, no. (2016), p. 12-24
- Relation: http://purl.org/au-research/grants/arc/DP140103213
- Full Text: false
- Reviewed:
- Description: This paper introduces an algorithm for solving the minimum sum-of-squares clustering problems using their difference of convex representations. A non-smooth non-convex optimization formulation of the clustering problem is used to design the algorithm. Characterizations of critical points, stationary points in the sense of generalized gradients and inf-stationary points of the clustering problem are given. The proposed algorithm is tested and compared with other clustering algorithms using large real world data sets. © 2015 Elsevier Ltd. All rights reserved.
A heuristic algorithm for solving the minimum sum-of-squares clustering problems
- Authors: Ordin, Burak , Bagirov, Adil
- Date: 2015
- Type: Text , Journal article
- Relation: Journal of Global Optimization Vol. 61, no. 2 (2015), p. 341-361
- Relation: http://purl.org/au-research/grants/arc/DP140103213
- Full Text: false
- Reviewed:
- Description: Clustering is an important task in data mining. It can be formulated as a global optimization problem which is challenging for existing global optimization techniques even in medium size data sets. Various heuristics were developed to solve the clustering problem. The global k-means and modified global k-means are among most efficient heuristics for solving the minimum sum-of-squares clustering problem. However, these algorithms are not always accurate in finding global or near global solutions to the clustering problem. In this paper, we introduce a new algorithm to improve the accuracy of the modified global k-means algorithm in finding global solutions. We use an auxiliary cluster problem to generate a set of initial points and apply the k-means algorithm starting from these points to find the global solution to the clustering problems. Numerical results on 16 real-world data sets clearly demonstrate the superiority of the proposed algorithm over the global and modified global k-means algorithms in finding global solutions to clustering problems.
A history of water distribution systems and their optimisation
- Authors: Mala-Jetmarova, Helena , Barton, Andrew , Bagirov, Adil
- Date: 2015
- Type: Text , Journal article
- Relation: Water Science and Technology-Water Supply Vol. 15, no. 2 (2015), p. 224-235
- Relation: http://purl.org/au-research/grants/arc/LP0990908
- Full Text: false
- Reviewed:
- Description: Water distribution systems have a very long and rich history dating back to the third millennium B.C. Advances in water supply and distribution were followed in parallel by discoveries and inventions in other related fields. Therefore, it is the aim of this paper to review both the history of water distribution systems and those related fields in order to present a coherent summary of the complex multi-stranded discipline of water engineering. Related fields reviewed in this paper include devices for raising water and water pumps, water quality and water treatment, hydraulics, network analysis, and optimisation of water distribution systems. The review is brief and concise and allows the reader to quickly gain an understanding of the history and advancements of water distribution systems and analysis. Furthermore, the paper gives details of other existing publications where more information can be found.
An incremental clustering algorithm based on hyperbolic smoothing
- Authors: Bagirov, Adil , Ordin, Burak , Ozturk, Gurkan , Xavier, Adilson
- Date: 2015
- Type: Text , Journal article
- Relation: Computational Optimization and Applications Vol. 61, no. 1 (2015), p. 219-241
- Relation: http://purl.org/au-research/grants/arc/DP140103213
- Full Text: false
- Reviewed:
- Description: Clustering is an important problem in data mining. It can be formulated as a nonsmooth, nonconvex optimization problem. For the most global optimization techniques this problem is challenging even in medium size data sets. In this paper, we propose an approach that allows one to apply local methods of smooth optimization to solve the clustering problems. We apply an incremental approach to generate starting points for cluster centers which enables us to deal with nonconvexity of the problem. The hyperbolic smoothing technique is applied to handle nonsmoothness of the clustering problems and to make it possible application of smooth optimization algorithms to solve them. Results of numerical experiments with eleven real-world data sets and the comparison with state-of-the-art incremental clustering algorithms demonstrate that the smooth optimization algorithms in combination with the incremental approach are powerful alternative to existing clustering algorithms.
An incremental piecewise linear classifier based on polyhedral conic separation
- Authors: Ozturk, Gurkan , Bagirov, Adil , Kasimbeyli, Refail
- Date: 2015
- Type: Text , Journal article
- Relation: Machine Learning Vol. 101, no. 1-3 (2015), p. 397-413
- Relation: http://purl.org/au-research/grants/arc/DP140103213
- Full Text: false
- Reviewed:
- Description: In this paper, a piecewise linear classifier based on polyhedral conic separation is developed. This classifier builds nonlinear boundaries between classes using polyhedral conic functions. Since the number of polyhedral conic functions separating classes is not known a priori, an incremental approach is proposed to build separating functions. These functions are found by minimizing an error function which is nonsmooth and nonconvex. A special procedure is proposed to generate starting points to minimize the error function and this procedure is based on the incremental approach. The discrete gradient method, which is a derivative-free method for nonsmooth optimization, is applied to minimize the error function starting from those points. The proposed classifier is applied to solve classification problems on 12 publicly available data sets and compared with some mainstream and piecewise linear classifiers. © 2014, The Author(s).
Diagnostic with incomplete nominal/discrete data
- Authors: Jelinek, Herbert , Yatsko, Andrew , Stranieri, Andrew , Venkatraman, Sitalakshmi , Bagirov, Adil
- Date: 2015
- Type: Text , Journal article
- Relation: Artificial Intelligence Research Vol. 4, no. 1 (2015), p. 22-35
- Full Text:
- Reviewed:
- Description: Missing values may be present in data without undermining its use for diagnostic / classification purposes but compromise application of readily available software. Surrogate entries can remedy the situation, although the outcome is generally unknown. Discretization of continuous attributes renders all data nominal and is helpful in dealing with missing values; particularly, no special handling is required for different attribute types. A number of classifiers exist or can be reformulated for this representation. Some classifiers can be reinvented as data completion methods. In this work the Decision Tree, Nearest Neighbour, and Naive Bayesian methods are demonstrated to have the required aptness. An approach is implemented whereby the entered missing values are not necessarily a close match of the true data; however, they intend to cause the least hindrance for classification. The proposed techniques find their application particularly in medical diagnostics. Where clinical data represents a number of related conditions, taking Cartesian product of class values of the underlying sub-problems allows narrowing down of the selection of missing value substitutes. Real-world data examples, some publically available, are enlisted for testing. The proposed and benchmark methods are compared by classifying the data before and after missing value imputation, indicating a significant improvement.
Exploration of the trade-offs between water quality and pumping costs in optimal operation of regional multiquality water distribution systems
- Authors: Mala-Jetmarova, Helena , Barton, Andrew , Bagirov, Adil
- Date: 2015
- Type: Text , Journal article
- Relation: Journal of Water Resources Planning and Management Vol. 141, no. 6 (2015), p. 1-16
- Relation: http://purl.org/au-research/grants/arc/LP0990908
- Full Text: false
- Reviewed:
- Description: This paper explores the trade-offs between water quality and pumping costs objectives in optimization of operation of regional multiquality water distribution systems. The optimization model is designed to concurrently minimize each objective, where water quality is represented by the deviations of constituent concentrations from required values and pumping costs are represented by energy consumed by the pumps. The optimization problem is solved using an optimization software, incorporating the nondominated sorting genetic algorithm II (NSGA-II), linked with network analysis software. Two typical but purposefully different example networks are used. First, a network with multiple water sources of different qualities and second, a network with one water source only, which was converted to represent a regional nondrinking water distribution system. The trade-offs between water quality and pumping costs are explored using a total of 14 scenarios reflecting different water quality configurations of these networks. Those scenarios, into which time variability was introduced for both source water quality and customer water quality requirements, were systematically developed to represent real-life situations that could be found in practice. The results indicate that for the majority of the scenarios, there is a trade-off with a competing nature between water quality and pumping costs objectives. Additionally, it was discovered that multiobjective optimization problems with water quality (i.e., concentration deviations) and pumping costs objectives could be reduced in certain instances into a single-objective problem of minimizing pumping costs. In fact, a regional water distribution system in which water quality is represented by a single conservative constituent can produce either a trade-off or single-objective solution between those two objectives, and this outcome is dependent on both the water quality configuration of the system and system operational flexibility. Last, some particular conclusions are drawn for both a water distribution system with multiple water sources and a water distribution system with a single water source, which suggest how changes in source water qualities or customer water quality requirements may impact system operation. It is, therefore, demonstrated that water utilities which operate regional multiquality nondrinking water distribution systems could benefit from the exploration of trade-offs between water quality and pumping costs for the purpose of operational planning.
Impact of water-quality conditions in source reservoirs on the optimal operation of a regional multiquality water-distribution system
- Authors: Mala-Jetmarova, Helena , Barton, Andrew , Bagirov, Adil
- Date: 2015
- Type: Text , Journal article
- Relation: Journal of Water Resources Planning and Management Vol. 141, no. 10 (2015), p.1-14
- Relation: http://purl.org/au-research/grants/arc/LP0990908
- Full Text: false
- Reviewed:
- Description: The impact of water quality conditions in source reservoirs on the optimal operation of a regional multiquality water-distribution system is analyzed. The optimization model concurrently minimizes three operational objectives being pump energy costs, turbidity, and salinity deviations at customer demand nodes from allowed values. The optimization problem is solved using the optimization tool GANetXL incorporating the NSGA-II, linked with the network analysis software EPANet. The example network adapted from the literature captures some of the unique features of the Wimmera Mallee Pipeline in Australia. Six scenarios representing different water quality conditions in source reservoirs are analyzed. It was discovered that two types of trade-offs, competing and noncompeting, exist between the objectives and that the type of trade-off is not unique between a particular pair of objectives for all scenarios. These and other findings may be of particular use to system operators in their long-term operational planning and decision making. (C) 2015 American Society of Civil Engineers.
Modified self-organising maps with a new topology and initialisation algorithm
- Authors: Mohebi, Ehsan , Bagirov, Adil
- Date: 2015
- Type: Text , Journal article
- Relation: Journal of Experimental and Theoretical Artificial Intelligence Vol. 27, no. 3 (2015), p. 351-372
- Full Text: false
- Reviewed:
- Description: Mapping quality of the self-organising maps (SOMs) is sensitive to the map topology and initialisation of neurons. In this article, in order to improve the convergence of the SOM, an algorithm based on split and merge of clusters to initialise neurons is introduced. The initialisation algorithm speeds up the learning process in large high-dimensional data sets. We also develop a topology based on this initialisation to optimise the vector quantisation error and topology preservation of the SOMs. Such an approach allows to find more accurate data visualisation and consequently clustering problem. The numerical results on eight small-to-large real-world data sets are reported to demonstrate the performance of the proposed algorithm in the sense of vector quantisation, topology preservation and CPU time requirement. © 2014 Taylor & Francis.
Nonsmooth optimization algorithm for solving clusterwise linear regression problems
- Authors: Bagirov, Adil , Ugon, Julien , Mirzayeva, Hijran
- Date: 2015
- Type: Text , Journal article
- Relation: Journal of Optimization Theory and Applications Vol. 164, no. 3 (2015), p. 755-780
- Relation: http://purl.org/au-research/grants/arc/DP140103213
- Full Text: false
- Reviewed:
- Description: Clusterwise linear regression consists of finding a number of linear regression functions each approximating a subset of the data. In this paper, the clusterwise linear regression problem is formulated as a nonsmooth nonconvex optimization problem and an algorithm based on an incremental approach and on the discrete gradient method of nonsmooth optimization is designed to solve it. This algorithm incrementally divides the whole dataset into groups which can be easily approximated by one linear regression function. A special procedure is introduced to generate good starting points for solving global optimization problems at each iteration of the incremental algorithm. The algorithm is compared with the multi-start Spath and the incremental algorithms on several publicly available datasets for regression analysis.