This large body of work is entirely centered around dual-tree algorithms, a class of algorithm based on spatial indexing structures that often provide large amounts of acceleration for various problems. This work focuses on understanding dual-tree algorithms using a new, tree-independent abstraction, and using this abstraction to develop new algorithms. Stated more clearly, the thesis of this entire work is that we may improve and expand the class of dual-tree algorithms by focusing on and providing improvements for each of the three independent components of a dual-tree algorithm: the type of space tree, the type of pruning dual-tree traversal, and the problem-specific BaseCase() and Score() functions. This is demonstrated by expressing many existing dual-tree algorithms in the tree-independent framework, and focusing on improving each of these three pieces. The result is a formidable set of generic components that can be used to assemble dual-tree algorithms, including faster traversals, improved tree theory, and new algorithms to solve the problems of max-kernel search and k-means clustering.

This thesis focuses on bare hand gesture recognition by proposing a new architecture to solve the problem of real-time vision-based hand detection, tracking, and gesture recognition for interaction with an application via hand gestures. The first stage of our system allows detecting and tracking a bare hand in a cluttered background using face subtraction, skin detection and contour comparison. The second stage allows recognizing hand gestures using bag-of-features and multi-class Support Vector Machine (SVM) algorithms. Finally, a grammar has been developed to generate gesture commands for application control. Our hand gesture recognition system consists of two steps: offline training and online testing. In the training stage, after extracting the keypoints for every training image using the Scale Invariance Feature Transform (SIFT), a vector quantization technique will map keypoints from every training image into a unified dimensional histogram vector (bag-of-words) after K-means clustering. This histogram is treated as an input vector for a multi-class SVM to build the classifier. In the testing stage, for every frame captured from a webcam, the hand is detected using my algorithm. Then, the keypoints are extracted for every small image that contains the detected hand posture and fed into the cluster model to map them into a bag-of-words vector, which is fed into the multi-class SVM classifier to recognize the hand gesture. Another hand gesture recognition system was proposed using Principle Components Analysis (PCA). The most eigenvectors and weights of training images are determined. In the testing stage, the hand posture is detected for every frame using my algorithm. Then, the small image that contains the detected hand is projected onto the most eigenvectors of training images to form its test weights. Finally, the minimum Euclidean distance is determined among the test weights and the training weights of each training image to recognize the hand gesture. Two application of gesture-based interaction with a 3D gaming virtual environment were implemented. The exertion videogame makes use of a stationary bicycle as one of the main inputs for game playing. The user can control and direct left-right movement and shooting actions in the game by a set of hand gesture commands, while in the second game, the user can control and direct a helicopter over the city by a set of hand gesture commands.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Cette thèse s’inscrit dans la recherche d’images basée sur leur contenu. La recherche opère sur des images eprésentéesdans un domaine transformé et où sont construits directement les vecteurs de caractéristiques ou indices. Deux types detransformations sont explorés : la transformée en cosinus discrète ou Discrete Cosine Transform (DCT) et la transforméen ondelettes discrète ou Discrete Wavelet Transform (DWT), utilisés dans les normes de compression JPEG et JPEG2000. Basés sur les propriétés des coefficients de la transformation, différents vecteurs de caractéristiquessont proposés. Ces vecteurs sont mis en oeuvre dans la reconnaissance de visages et de textures couleur.Dans le domaine DCT, sont proposés quatre types de vecteurs de caractéristiques dénommés «patterns» : Zigzag-Pattern,Sum-Pattern, Texture-Pattern et Color-Pattern. Le premier type est l’amélioration d’une approche existante. Les trois derniers intègrent la capacité de compactage des coefficients DCT, sachant que certains coefficients représentent une information de directionnalité. L’histogramme de ces vecteurs est retenu comme descripteur de l’image. Pour une réduction de la dimension du descripteur lors de la construction de l’histogramme il est défini, soit une adjacence sur des patterns proches puis leur fusion, soit une sélection des patterns les plus fréquents. Ces approches sont évaluées sur des bases de données d’images de visages ou de textures couramment utilisées. Dans le domaine DWT, deux types d’approches sont proposés. Dans le premier, un vecteur-couleur et un vecteur–texture multirésolution sont élaborés. Cette approche se classe dans le cadre d’une caractérisation séparée de la couleur et de la texture. La seconde approche se situe dans le contexte d’une caractérisation conjointe de la couleur et de la texture. Comme précédemment, l’histogramme des vecteurs est choisi comme descripteur en utilisant l’algorithme K-means pour construire l’histogramme à partir de deux méthodes. La première est le procédé classique de regroupement des vecteurs par partition. La seconde est un histogramme basé sur une représentation parcimonieuse dans laquelle la valeur des bins représente le poids total des vecteurs de base de la représentation. / This thesis comes within content-based image retrieval for images by constructing feature vectors directly fromtransform domain. In particular, two kinds of transforms are concerned: Discrete Cosine Transform (DCT) andDiscrete Wavelet Transform (DWT), which are used in JPEG and JPEG2000 compression standards. Based onthe properties of transform coefficients, various feature vectors in DCT domain and DWT domain are proposedand applied in face recognition and color texture retrieval. The thesis proposes four kinds of feature vectors in DCTdomain: Zigzag-Pattern, Sum-Pattern, Texture-Pattern and Color-Pattern. The first one is an improved method based onan existing approach. The last three ones are based on the capability of DCT coefficients for compacting energy and thefact that some coefficients hold the directional information of images. The histogram of these patterns is chosen as descriptor of images. While constructing the histogram, with the objective to reduce the dimension of the descriptor, either adjacent patterns are defined and merged or a selection of the more frequent patterns is done. These approaches are evaluated on widely used face databases and texture databases. In the aspect of DWT domain, two kinds of approaches for color texture retrieval are proposed. In the first one, color-vector and multiresolution texture-vector are constructed, which categorize this approach into the context of extracting color and texture features separately. In contrast, the second approachis in the context of extracting color and texture features jointly: multiresolution feature vectors are extracted from luminance and chrominance components of color texture. Histogram of vectors is again chosen as descriptor and using k-means algorithm to divide feature vectors into partitions corresponding to the bins of histogram. For histogram generation, two methods are used. The first one is the classical method, in which the number of vectors that fall into the corresponding partition is counted. The second one is the proposition of a sparse representation based histogram in which a bin value represents the total weight of corresponding basis vector in the sparse representation.

根據過去研究指出，社群網站上的貼文訊息會對群眾情緒造成影響，進而影響股市波動，故對於投資者而言，如果能快速分析大量社群網站的財經文本來推測投資情緒進而預測股市走勢，將可提升投資獲利。 過去文本情感分析的研究中已證實監督式學習方法可以透過簡單量化的方式達到良好的分類效果，但監督式學習方法所使用的訓練資料集須有事先定義好的已知類別，故其有無法預期未知類別的限制，所以本研究透過深度學習方法，從巨量資料及裡抓出有關於股市之文章，並透過財經文本的混合監督式學習與非監督式學習之情感分析方法，透過非監督式學習對微博財經貼文進行文本主題判別、情緒指數計算與情緒傾向標注，並且透過監督式學習的方式，建立分類模型以預測上海指數走勢，最後配合視覺化工具作趨勢線圖分析，找出具有領先指標特性之主題。 在實驗結果中，深度學習方面，本研究透過word2vec抓取有效之股市主題文章，有效篩選了需要分析之文本，主題模型方面，我們最後使用LDA作為本研究標註主題之方法，因為其文本數量大於議題詞數量造成TFIDF矩陣過於稀疏，造成Kmeans分群效果不佳，故後續採用LDA主題模型進行主題標注。情緒傾向標注方面，透過擴充後的情感詞集比起NTUSD有更好的詞性分數判斷效果，計算出的情緒指數之趨勢線能有效預測上海指數之趨勢。此外，並非所有主題模型之情緒指數皆具有領先特性，僅公司表現與上海指數之主題模型的情緒指數能提前反應上海指數趨勢，故本研究用此二主題之文本的情緒指數來建立分類模型。 本研究透過比較情緒指數與單純指數指標分類模型的準確度，前者較後者高出7%的準確率。故證實了情感分析確實能有效提升上海指數趨勢預測準確度，幫助投資者增加股市報酬率。

With social media rising in popularity over the recent years, new so called social bots are infiltrating by spamming and manipulating people all over the world. Many different methods have been presented to solve this problem with varying success. This study aims to compare some of these methods, on a dataset of Twitter account metadata, to provide helpful information to companies when deciding how to solve this problem. Two machine learning algorithms and a human survey will be compared on the ability to classify accounts. The algorithms used are the supervised algorithm random forest and the unsupervised algorithm k-means. There will also be an evaluation of two ways to run these algorithms, using the machine learning as a service BigML and the python library Scikit-learn. Additionally, what metadata features are most valuable in the supervised and human survey will be compared. Results show that supervised machine learning is the superior technique for social bot identification with an accuracy of almost 99%. To conclude, it depends on the expertise of the company and if a relevant training dataset is available but in most cases supervised machine learning is recommended.

Made available in DSpace on 2016-08-10T10:40:24Z (GMT). No. of bitstreams: 1 Carolina Palma Pimenta Furlan.pdf: 1336228 bytes, checksum: 0e211203f57a4ebf656390682932eb68 (MD5) Previous issue date: 2014-09-04 / The advent of Internet enabled various means of communication among people and among them there are the social networking platforms, becoming a new form of relationship. Explore this new environment has become increasingly appreciated for researchers as well as for managers in a way in general. This environment provided the formation of communities and through them it is possible to identify the formation of groups through their interests. Most visualization algorithms for social networks are represented in graphs. The environment of this research consists in the subgroup Tocantins digital social of network Facebook, which has more than 10.000 members. In this paper the k-means algorithm for clustering of data represented by the five groups as the best solution found, and also the centrality measure of intermediation which revealed the existence of three most influential members in your posts, and four products or services was applied most Viewed within the subgroup. / O advento da Internet possibilitou vários meios de comunicação entre as pessoas e dentre elas destacam-se as plataformas de redes sociais, tornando-se uma nova forma de relacionamento. Explorar esse novo ambiente tornou-se cada vez mais apreciado para os pesquisadores, tanto quanto para os gestores de um modo em geral. Esse ambiente proporciona a formação de comunidades e através delas é possível a identificação de formação de grupos através dos seus interesses. A maioria dos algoritmos de visualização de redes sociais são representados em grafos. O ambiente dessa pesquisa consiste no subgrupo Tocantins digital da rede social Facebook, o qual possui mais de 10.000 membros. Neste ambiente utilizou-se a ferramenta API, na qual foi possível desenvolver aplicações para se coletar informações das postagens dos membros do grupo pesquisado. Neste trabalho foi aplicado o algoritmo k-médias para o agrupamento de dados representados pelos cinco grupos como a melhor solução encontrada, e também a medida centralidade de intermediação onde revelou a existência de três membros com maior influência em suas postagens, e quatro produtos ou serviços mais visualizados dentro do subgrupo.

Orientador: Luís Roberto Almeida Gabriel Filho / Coorientador: Luiz Fernando Sommaggio Coletta / Coorientador: Camila Pires Cremasco Gabriel / Resumo: O presente trabalho buscou identificar padrões na produção de cana de por meio da utilização de Inteligência Artificial. Para tanto, foi realizada coleta de informações de fontes secundárias, com dados estatísticos fornecidos por órgãos públicos sobre a área cultivada e a produção de cana de açúcar, índices como pluviométricos e de temperatura e o tipo de solo dos municípios do estado de São Paulo, no ano de 2017, por meio de pesquisa documental. Com a utilização dos métodos Floresta dos Caminhos Ótimos (OPF), K-means e Fuzzy C-means (FCM) buscou-se identificar clusters, ou padrões, que representem essas características produtivas. Além disso, o trabalho testou a utilização do algoritmo OPF como ferramenta de apoio à decisão no setor agroindustrial e fez a comparação do método com os agrupadores de padrões K-means e FCM. Após o processamento dos dados foi possível identificar padrões na produção de cana de açúcar pelos três algoritmos, sendo que o OPF proporcionou resultados muito parecidos com o K-means e FCM, confirmando a eficiência do método. Além disso, foi possível identificar, no ano de 2017, um padrão de produção com municípios com alta produtividade, grandes áreas destinadas a produção de cana de açúcar e produção da cultura, com temperatura média alta e índices pluviométricos baixos. Os municípios que possuem pequenas áreas com plantação de cana de açúcar possuem uma variabilidade muito grande em resultados de produtividade. O padrão de município com baixa produtivi... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: The present work sought to identify patterns in sugarcane production through the use of Artificial Intelligence. For this purpose, information was collected from secondary sources, with statistical data provided by public agencies on cultivated area and sugarcane production, rainfall and temperature indices, and the soil type of the municipalities of the State of São Paulo, in the year 2017, through documentary research. Using Optimum-Path Forest (OPF), K-means and Fuzzy C-means (FCM) methods, the aim was to identify clusters, or patterns, that represent these productive characteristics. In addition, the work tested the use of OPF algorithm as a decision support tool in the agribusiness sector and compared the method with the K-means and FCM standards groupers. After data processing, it was possible to identify patterns in sugarcane production by the three algorithms, and OPF provided results very similar to K-means and FCM, confirming the efficiency of the method. In addition, it was possible to identify, in the year 2017, a production pattern of municipalities with high productivity, large areas destined to the production of sugar cane and crop production, with high average temperature and low rainfall. Municipalities that have small areas with sugar cane plantation have a very large variability in productivity results. The municipal pattern with low productivity is accompanied by very low average temperature, very high rainfall rates and soils of the type Cambisols, Neosols and Spodosols. The soil type pattern that provided the highest productivity for the municipalities was the Oxisol. / Mestre

This thesis focuses on bare hand gesture recognition by proposing a new architecture to solve the problem of real-time vision-based hand detection, tracking, and gesture recognition for interaction with an application via hand gestures. The first stage of our system allows detecting and tracking a bare hand in a cluttered background using face subtraction, skin detection and contour comparison. The second stage allows recognizing hand gestures using bag-of-features and multi-class Support Vector Machine (SVM) algorithms. Finally, a grammar has been developed to generate gesture commands for application control. Our hand gesture recognition system consists of two steps: offline training and online testing. In the training stage, after extracting the keypoints for every training image using the Scale Invariance Feature Transform (SIFT), a vector quantization technique will map keypoints from every training image into a unified dimensional histogram vector (bag-of-words) after K-means clustering. This histogram is treated as an input vector for a multi-class SVM to build the classifier. In the testing stage, for every frame captured from a webcam, the hand is detected using my algorithm. Then, the keypoints are extracted for every small image that contains the detected hand posture and fed into the cluster model to map them into a bag-of-words vector, which is fed into the multi-class SVM classifier to recognize the hand gesture. Another hand gesture recognition system was proposed using Principle Components Analysis (PCA). The most eigenvectors and weights of training images are determined. In the testing stage, the hand posture is detected for every frame using my algorithm. Then, the small image that contains the detected hand is projected onto the most eigenvectors of training images to form its test weights. Finally, the minimum Euclidean distance is determined among the test weights and the training weights of each training image to recognize the hand gesture. Two application of gesture-based interaction with a 3D gaming virtual environment were implemented. The exertion videogame makes use of a stationary bicycle as one of the main inputs for game playing. The user can control and direct left-right movement and shooting actions in the game by a set of hand gesture commands, while in the second game, the user can control and direct a helicopter over the city by a set of hand gesture commands.

Protein tertiary structure plays a very important role in determining its possible functional sites and chemical interactions with other related proteins. Experimental methods to determine protein structure are time consuming and expensive. As a result, the gap between protein sequence and its structure has widened substantially due to the high throughput sequencing techniques. Problems of experimental methods motivate us to develop the computational algorithms for protein structure prediction. In this work, the clustering system is used to predict local protein structure. At first, recurring sequence clusters are explored with an improved K-means clustering algorithm. Carefully constructed sequence clusters are used to predict local protein structure. After obtaining the sequence clusters and motifs, we study how sequence variation for sequence clusters may influence its structural similarity. Analysis of the relationship between sequence variation and structural similarity for sequence clusters shows that sequence clusters with tight sequence variation have high structural similarity and sequence clusters with wide sequence variation have poor structural similarity. Based on above knowledge, the established clustering system is used to predict the tertiary structure for local sequence segments. Test results indicate that highest quality clusters can give highly reliable prediction results and high quality clusters can give reliable prediction results. In order to improve the performance of the clustering system for local protein structure prediction, a novel computational model called Clustering Support Vector Machines (CSVMs) is proposed. In our previous work, the sequence-to-structure relationship with the K-means algorithm has been explored by the conventional K-means algorithm. The K-means clustering algorithm may not capture nonlinear sequence-to-structure relationship effectively. As a result, we consider using Support Vector Machine (SVM) to capture the nonlinear sequence-to-structure relationship. However, SVM is not favorable for huge datasets including millions of samples. Therefore, we propose a novel computational model called CSVMs. Taking advantage of both the theory of granular computing and advanced statistical learning methodology, CSVMs are built specifically for each information granule partitioned intelligently by the clustering algorithm. Compared with the clustering system introduced previously, our experimental results show that accuracy for local structure prediction has been improved noticeably when CSVMs are applied.