In this thesis, we consider contextual newsvendor problems where one seeks to determine ordering quantities of perishable products based on the observations of past demands and some features (such as seasonality, weather forecasts, economic indicators, etc.) related to the demand. We propose solving the problems via a single-step optimal decision-tree approach. Unlike the traditional two-step approach that first predicts a demand distribution based on given features and then optimizes the order quantity, our approach seeks to determine a tree-based ordering policy that directly maps given features to optimal order quantities. We show how the optimal policies can be found by solving mixed-integer programming (MIP) problems. The tree structure overcomes the black-box nature of most machine learning algorithms while reaching better performance than simple solutions such as linear regression. In addition to risk-neutral newsvendor problems, we further extend the method to address risk-averse newsvendor problems formulated based on Conditional Value-at-Risk (CVaR). Numerical experiments on synthetic and real-world data suggest that our approach outperforms existing approaches with the same objective function, such as the ERM-based convex optimization model which is referred to as Ban and Rudin's big data newsvendor model, and quantile regression decision trees.

Decision trees have long been a prevalent area within machine learning. With streaming data environments as well as large datasets becoming increasingly common, researchers have developed decision tree algorithms adapted to streaming data. One such algorithm is SPDT, which approaches the streaming data problem by making use of workers on a network combined with a dynamic histogram approximation of the data. There exist several implementations for decision trees on GPU, but those are uncommon in a streaming data setting. In this research, conducted at RISE SICS, the possibilities of accelerating the SPDT algorithm on GPU is investigated. An implementation is successfully created using the CUDA platform. The implementation uses a set number of data samples per layer to better fit the GPU platform. Experiments were conducted to investigate the impact on both accuracy and speed. It is found that the GPU implementation performs as well as the CPU implementation in terms of accuracy, suggesting that using small subsets of the data in each layer is sufficient for making accurate split decisions. The GPU implementation is found to be up to 113 times faster than the reference Scala CPU implementation for one of the tested datasets, and 13 times faster on average over all the tested datasets. Weak parts of the implementation are identified, and further improvements are suggested to increase both accuracy and runtime performance. / Beslutsträd har länge varit ett betydande område inom maskininlärning. Strömmandedata och stora dataset har blivit allt vanligare, vilket har lett till att forskare utvecklat algoritmer för beslutsträd anpassade till dessa miljöer. En av dessa algoritmer är SPDT. Denna algoritm använder sig av flera arbetare i ett nätverk kombinerat med en dynamisk histogram-representation av data. Det existerar flera implementationer av beslutsträd på grafikkort, men inte många för strömmande data. I detta forskningsarbete, utfört på RISE SICS, undersöks möjligheten att snabba upp SPDT genom att accelerera beräkningar med hjälp av grafikkort. En lyckad implementation skriven i CUDA beskrivs. Implementationen anpassar sig till grafikkortsplattformen genom att använda sig utav ett bestämt antal datapunkter per lager. Experiment som undersöker effekten på noggrannhet och hastighet har genomförts. Resultaten visar att GPU-implementationen presterar lika väl som CPU-implementationen vad gäller noggrannhet, vilket påvisar att användandet av en mindre del av data i varje lager är tillräckligt för goda resultat. GPU-implementationen är upp till 113 gånger snabbare jämfört med en existerande CPU-implementation skriven i Scala, och är i medel 13 gånger snabbare. Svagheter i implementationen identifieras, och vidare förbättringar till implementationen föreslås för att förbättra både noggrannhet och hastighetsprestanda.

As the Web is fast becoming an integral feature in many of our daily lives, designers are faced with the challenge of designing Web-based applications for an increasingly diverse user group. In order to develop applications that successfully meet the needs of this user group, designers have to understand the influence of human factors upon users‘ needs and preferences. To address this issue, this thesis presents an investigation that analyses the influence of three human factors, including cognitive style, prior knowledge and gender differences, on users‘ preferences for Web-based applications. In particular, two applications are studied: Web search tools and Web-based instruction tools. Previous research has suggested a number of relationships between these three human factors, so this thesis was driven by three research questions. Firstly, to what extent is the similarity between the two cognitive style dimensions of Witkin‘s Field Dependence/Independence and Pask‘s Holism/Serialism? Secondly, to what extent do computer experts have the same preferences as Internet experts and computer novices have the same preferences as Internet novices? Finally, to what extent are Field Independent users, experts and males alike, and Field Dependent users, novices and females alike? As traditional statistical analysis methods would struggle to effectively capture such relationships, this thesis proposes an integrated data mining approach that combines feature selection and decision trees to effectively capture users‘ preferences. From this, a framework is developed that integrates the combined effect of the three human factors and can be used to inform system designers. The findings suggest that firstly, there are links between these three human factors. In terms of cognitive style, the relationship between Field Dependent users and Holists can be seen more clearly than the relationship between Field Independent users and Serialists. In terms of prior knowledge, although it is shown that there is a link between computer experience and Internet experience, computer experts are shown to have similar preferences to Internet novices. In terms of the relationship between all three human factors, the results of this study highlighted that the links between cognitive style and gender and between cognitive style and system experience were found to be stronger than the relationship between system experience and gender. This work contributes both theory and methodology to multiple academic communities, including human-computer interaction, information retrieval and data mining. In terms of theory, it has helped to deepen the understanding of the effects of single and multiple human factors on users‘ preferences for Web-based applications. In terms of methodology, an integrated data mining analysis approach was proposed and was shown that is able to capture users‘ preferences.

The two most popular classification tree algorithms in machine learning and statistics - C4.5 and CART - are compared in a benchmark experiment together with two other more recent constant-fit tree learners from the statistics literature (QUEST, conditional inference trees). The study assesses both misclassification error and model complexity on bootstrap replications of 18 different benchmark datasets. It is carried out in the R system for statistical computing, made possible by means of the RWeka package which interfaces R to the open-source machine learning toolbox Weka. Both algorithms are found to be competitive in terms of misclassification error - with the performance difference clearly varying across data sets. However, C4.5 tends to grow larger and thus more complex trees. (author's abstract) / Series: Research Report Series / Department of Statistics and Mathematics

Health plans are constantly seeking ways to assess and improve the quality of patient experience in various ambulatory and institutional settings. Standardized surveys are a common tool used to gather data about patient experience, and a useful measurement taken from these surveys is known as the Net Promoter Score (NPS). This score represents the extent to which a patient would, or would not, recommend his or her physician on a scale from 0 to 10, where 0 corresponds to "Extremely unlikely" and 10 to "Extremely likely". A large national health plan utilized automated calls to distribute such a survey to its members and was interested in understanding what factors contributed to a patient's satisfaction. Additionally, they were interested in whether or not NPS could be predicted using responses from other questions on the survey, along with demographic data. When the distribution of various predictors was compared between the less satisfied and highly satisfied members, there was significant overlap, indicating that not even the Bayes Classifier could successfully differentiate between these members. Moreover, the highly imbalanced proportion of NPS responses resulted in initial poor prediction accuracy. Thus, due to the non-linear structure of the data, and high number of categorical predictors, we have leveraged flexible methods, such as decision trees, bagging, and random forests, for modeling and prediction. We further altered the prediction step in the random forest algorithm in order to account for the imbalanced structure of the data.

Dentre as diversas tarefas em que os algoritmos evolutivos têm sido empregados, a indução de regras e de árvores de decisão tem se mostrado uma abordagem bastante atrativa em diversos domínios de aplicação. Algoritmos de indução de árvores de decisão representam uma das técnicas mais populares em problemas de classificação. Entretanto, os algoritmos tradicionais de indução apresentam algumas limitações, pois, geralmente, usam uma estratégia gulosa, top down e com particionamento recursivo para a construção das árvores. Esses fatores degradam a qualidade dos dados, os quais podem gerar regras estatisticamente não significativas. Este trabalho propõe o algoritmo LEGAL-Tree, uma nova abordagem baseada em algoritmos genéticos para indução de árvores de decisão. O algoritmo proposto visa evitar a estratégia gulosa e a convergência para ótimos locais. Para isso, esse algoritmo adota uma abordagem multi-objetiva lexicográfica. Nos experimentos realizados sobre bases de dados de diversos problemas de classificação, a função de fitness de LEGAL-Tree considera as duas medidas mais comuns para avaliação das árvores de decisão: acurácia e tamanho da árvore. Os resultados obtidos mostraram que LEGAL-Tree teve um desempenho equivalente ao algoritmo SimpleCart (implementação em Java do algoritmo CART) e superou o tradicional algoritmo J48 (implementação em Java do algoritmo C4.5), além de ter superado também o algoritmo evolutivo GALE. A principal contribuição de LEGAL-Tree não foi gerar árvores com maior acurácia preditiva, mas sim gerar árvores menores e, portanto, mais compreensíveis ao usuário do que as outras abordagens, mantendo a acurácia preditiva equivalente. Isso mostra que LEGAL-Tree obteve sucesso na otimização lexicográfica de seus objetivos, uma vez que a idéia era justamente dar preferência às árvores menores (em termos de número de nodos) quando houvesse equivalência de acurácia / Among the several tasks evolutionary algorithms have been successfully employed, the induction of classification rules and decision trees has been shown to be a relevant approach for several application domains. Decision tree induction algorithms represent one of the most popular techniques for dealing with classification problems. However, conventionally used decision trees induction algorithms present limitations due to the strategy they usually implement: recursive top-down data partitioning through a greedy split evaluation. The main problem with this strategy is quality loss during the partitioning process, which can lead to statistically insignificant rules. In this thesis we propose the LEGAL-Tree algorithm, a new GA-based algorithm for decision tree induction. The proposed algorithm aims to prevent the greedy strategy and to avoid converging to local optima. For such, it is based on a lexicographic multi-objective approach. In the experiments which were run in several classification problems, LEGAL-Tree\'s fitness function considers two of the most common measures to evaluate decision trees: accuracy and tree size. Results show that LEGAL-Tree performs similarly to SimpleCart (CART Java implementation) and outperforms J48 (C4.5 Java implementation) and the evolutionary algorithm GALE. LEGAL-Tree\'s main contribution is not to generate trees with the highest predictive accuracy possible, but to provide smaller (and thus more comprehensible) trees, keeping a competitive accuracy rate. LEGAL-Tree is able to provide both comprehensible and accurate trees, which shows that the lexicographic fitness evaluation is successful since its goal is to prioritize smaller trees (fewer number of nodes) when there is equivalency in terms of accuracy

by Chun Gu. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1999. / Includes bibliographical references (leaves 69-71). / Abstract also in Chinese. / Chapter 1 --- Introduction --- p.3 / Chapter 2 --- Definitions --- p.7 / Chapter 3 --- Some Previous Work on OBDD --- p.13 / Chapter 3.1 --- The Work of Bryant --- p.13 / Chapter 3.2 --- Some Variations of the OBDD --- p.14 / Chapter 3.3 --- Previous Work on Variable Ordering of OBDD --- p.16 / Chapter 3.3.1 --- The FIH Heuristic --- p.16 / Chapter 3.3.2 --- The Dynamic Variable Ordering --- p.17 / Chapter 3.3.3 --- The Interleaving method --- p.19 / Chapter 4 --- Two Level Logic Function and OBDD --- p.21 / Chapter 5 --- DSCF Algorithm --- p.25 / Chapter 6 --- Thin Boolean Function --- p.33 / Chapter 6.1 --- The Structure and Properties of thin Boolean functions --- p.33 / Chapter 6.1.1 --- The construction of Thin OBDDs --- p.33 / Chapter 6.1.2 --- Properties of Thin Boolean Functions --- p.38 / Chapter 6.1.3 --- Thin Factored Functions --- p.49 / Chapter 6.2 --- The Revised DSCF Algorithm --- p.52 / Chapter 6.3 --- Experimental Results --- p.54 / Chapter 7 --- A Pattern Merging Algorithm --- p.59 / Chapter 7.1 --- Merging of Patterns --- p.60 / Chapter 7.2 --- The Algorithm --- p.62 / Chapter 7.3 --- Experiments and Conclusion --- p.65 / Chapter 8 --- Conclusions --- p.67

Data mining is emerging as an important tool in many areas of research and industry. Companies and organizations are increasingly interested in applying data mining tools in order to increase the value added by their data collections systems. Nowhere is this potential more important than in the healthcare industry. As medical records systems become more standardized and commonplace, data quantity increases with much of it going unanalyzed. Data mining can begin to leverage some of this data into tools that help clinicians organize data and make decisions. These modeling techniques are explored in the following text. Through the use of clustering and classification techniques, accurate models of a dialysis patient's current status are derived.

Thesis (M.S.)--Ohio University, June, 2006. / Title from PDF t.p. Includes bibliographical references (p. 125-130)

Aquesta tesi tracta sobre la utilització d'arbres de decisió petits per a la classificació i la mineria de dades. La idea intuïtiva darrera d'aquesta tesi és que una seqüència d'arbres de decisió petits pot rendir millor que un arbre de decisió gran, reduint tan el cost d'entrenament com el d'explotació.El nostre primer objectiu va ser desenvolupar un sistema capaç de reconèixer diferents tipus d'elements presents en un document com ara el fons, text, línies horitzontals i verticals, dibuixos esquemàtics i imatges. Aleshores, cada element pot ser tractat d'acord a les seves característiques. Per exemple, el fons s'elimina i no és processat, mentre que les altres regions serien comprimides usant l'algorisme apropiat, JPEG amb pèrdua per a les imatges i un mètode sense pèrdua per a la resta, per exemple. Els primers experiments usant arbres de decisió varen mostrar que els arbres de decisió construïts eren massa grans i que patien de sobre-entrenament. Aleshores, vàrem tractar d'aprofitar la redundància espacial present en les imatges, utilitzant una aproximació de resolució múltiple: si un bloc gran no pot ser correctament classificat, trencar-lo en quatre sub-blocs i repetir el procés recursivament per a cada sub-bloc, usant tot el coneixement que s'hagi calculat amb anterioritat. Els blocs que no poden ser processats per una mida de bloc donada s'etiqueten com a "mixed", pel que la paraula progressiu pren sentit: una primera versió de poca resolució de la imatge classificada és obtinguda amb el primer classificador, i és refinada pel segon, el tercer, etc., fins que una versió final és obtinguda amb l'últim classificador del muntatge. De fet, l'ús de l'esquema progressiu porta a l'ús d'arbres de decisió més petits, ja que ja no cal un classificador complex. En lloc de construir un classificador gran i complex per a classificar tot el conjunt d'entrenament, només provem de resoldre la part més fàcil del problema de classificació, retardant la resta per a un segon classificador, etc.La idea bàsica d'aquesta tesi és, doncs, un compromís entre el cost i la precisió sota una restricció de confiança. Una primera classificació es efectuada a baix cost; si un element és classificat amb una confiança elevada, s'accepta, i si no ho és, es rebutja i s'efectua una segona classificació, etc. És bàsicament, una variació del paradigma de "cascading", on un primer classificador s'usa per a calcular informació addicional per a cada element d'entrada, que serà usada per a millorar la precisió de classificació d'un segon classificador, etc. El que presentem en aquesta tesi és, bàsicament, una extensió del paradigma de "cascading" i una avaluació empírica exhaustiva dels paràmetres involucrats en la creació d'arbres de decisió progressius. Alguns aspectes teòrics relacionats als arbres de decisió progressius com la complexitat del sistema, per exemple, també són tractats. / This thesis is about using small decision trees for classification and data mining. The intuitive idea behind this thesis is that a sequence of small decision trees may perform better than a large decision tree, reducing both training and exploitation costs.Our first goal was to develop a system capable to recognize several kinds of elements present in a document such as background, text, horizontal and vertical lines, line drawings and images. Then, each element would be treated accordingly to its characteristics. For example, background regions would be removed and not processed at all, while the other regions would be compressed using an appropriate algorithm, the lossy JPEG standard operation mode for images and a lossless method for the rest, for instance. Our first experiments using decision trees showed that the decision trees we built were too large and they suffered from overfitting. Then, we tried to take advantage of spatial redundancy present in images, using a multi-resolution approach: if a large block cannot be correctly classified, split it in four subblocks and repeat the process recursively for each subblock, using all previous computed knowledge about such block. Blocks that could not be processed at a given block size were labeled as mixed, so the word progressive came up: a first low resolution version of the classified image is obtained with the first classifier, and it is refined by the second one, the third one, etc, until a final version is obtained with the last classifier in the ensemble. Furthermore, the use of the progressive scheme yield to the use of smaller decision trees, as we no longer need a complex classifier. Instead of building a large and complex classifier for classifying the whole input training set, we only try to solve the easiest part of the classification problem, delaying the rest for a second classifier, and so.The basic idea in this thesis is, therefore, a trade-off between cost and accuracy under a confidence constraint. A first classification is performed at a low cost; if an element is classified with a high confidence, it is accepted, and if not, it is rejected and a second classification is performed, and so. It is, basically, a variation of the cascading paradigm, where a first classifier is used to compute additional information from each input sample, information that will be used to improve classification accuracy by a second classifier, and so on. What we present in this thesis, basically, is an extension of the cascading paradigm and an exhaustive empirical evaluation of the parameters involved in the creation of progressive decision trees. Some basic theoretical issues related to progressive decision trees such as system complexity, for example, are also addressed. / Esta tesis trata sobre la utilización de árboles de decisión pequeños para la clasificación y la minería de datos. La idea intuitiva detrás de esta tesis es que una secuencia de árboles de decisión pequeños puede rendir mejor que un árbol de decisión grande, reduciendo tanto el coste de entrenamiento como el de explotación. Nuestro primer objetivo fue desarrollar un sistema capaz de reconocer diferentes tipos de elementos presentes en un documento, como el fondo, texto, líneas horizontales y verticales, dibujos esquemáticos y imágenes. Entonces, cada elemento puede ser tratado de acuerdo a sus características. Por ejemplo, el fondo se elimina y no se procesa, mientras que las otras regiones serían comprimidas usando el algoritmo apropiado, JPEG con pérdida para las imágenes y un método sin pérdida para el resto, por ejemplo. Los primeros experimentos usando árboles de decisión mostraron que los árboles de decisión construidos eran demasiado grandes y que sufrían de sobre-entrenamiento. Entonces, se trató de aprovechar la redundancia espacial presente en las imágenes, utilizando una aproximación de resolución múltiple: si un bloque grande no puede ser correctamente clasificado, romperlo en cuatro sub-bloques y repetir el proceso recursivamente para cada sub-bloque, usando todo el conocimiento que se haya calculado con anterioridad. Los bloques que no pueden ser procesados para una medida de bloque dada se etiquetan como "mixed", por lo que la palabra progresivo toma sentido: una primera versión de poca resolución de la imagen clasificada se obtiene con el primer clasificador, y se refina por el segundo, el tercero, etc., hasta que una versión final es obtenida con el último clasificador del montaje. De hecho, el uso del esquema progresivo lleva al uso de árboles de decisión más pequeños, ya que ya no es necesario un clasificador complejo. En lugar de construir un clasificador grande y complejo para clasificar todo el conjunto de entrenamiento, sólo tratamos de resolver la parte más fácil del problema de clasificación, retardando el resto para un segundo clasificador, etc.La idea básica de esta tesis es, entonces, un compromiso entre el coste y la precisión bajo una restricción de confianza. Una primera clasificación es efectuada a bajo coste; si un elemento es clasificado con una confianza elevada, se acepta, y si no lo es, se rechaza y se efectúa una segunda clasificación, etc. Es básicamente, una variación del paradigma de "cascading", donde un primer clasificador se usa para calcular información adicional para cada elemento de entrada, que será usada para mejorar la precisión de clasificación de un segundo clasificador, etc. Lo que presentamos en esta tesis es, básicamente, una extensión del paradigma de "cascading" y una evaluación empírica exhaustiva de los parámetros involucrados en la creación de árboles de decisión progresivos. Algunos aspectos teóricos relacionados con los árboles de decisión progresivos como la complejidad del sistema, por ejemplo, también son tratados.