-
Notifications
You must be signed in to change notification settings - Fork 1
/
PPgSI-modeloQualiDissertacaoLatex-Final-v1.tex
5061 lines (4221 loc) · 414 KB
/
PPgSI-modeloQualiDissertacaoLatex-Final-v1.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
%% abtex2-modelo-trabalho-academico.tex, v-1.9.2 laurocesar
%% Copyright 2012-2014 by abnTeX2 group at http://abntex2.googlecode.com/
%%
%% This work may be distributed and/or modified under the
%% conditions of the LaTeX Project Public License, either version 1.3
%% of this license or (at your option) any later version.
%% The latest version of this license is in
%% http://www.latex-project.org/lppl.txt
%% and version 1.3 or later is part of all distributions of LaTeX
%% version 2005/12/01 or later.
%%
%% This work has the LPPL maintenance status `maintained'.
%%
%% The Current Maintainer of this work is the abnTeX2 team, led
%% by Lauro César Araujo. Further information are available on
%% http://abntex2.googlecode.com/
%%
%% This work consists of the files abntex2-modelo-trabalho-academico.tex,
%% abntex2-modelo-include-comandos and abntex2-modelo-references.bib
%%
% ------------------------------------------------------------------------
% ------------------------------------------------------------------------
% abnTeX2: Modelo de Trabalho Academico (tese de doutorado, dissertacao de
% mestrado e trabalhos monograficos em geral) em conformidade com
% ABNT NBR 14724:2011: Informacao e documentacao - Trabalhos academicos -
% Apresentacao
% ------------------------------------------------------------------------
% ------------------------------------------------------------------------
%-------------------------------------------------------------------------
% Modelo adaptado especificamente para o contexto do PPgSI-EACH-USP por
% Marcelo Fantinato, com auxílio dos Professores Norton T. Roman, Helton
% H. Bíscaro, e Sarajane M. Peres, em 2016, com muitos agradecimentos aos
% criadores da classe e do modelo base.
%-------------------------------------------------------------------------
\documentclass[
% -- opções da classe memoir --
12pt, % tamanho da fonte
% openright, % capítulos começam em pág ímpar (insere página vazia caso preciso)
oneside, % para impressão apenas no anverso (apenas frente). Oposto a twoside
a4paper, % tamanho do papel.
% -- opções da classe abntex2 --
%chapter=TITLE, % títulos de capítulos convertidos em letras maiúsculas
%section=TITLE, % títulos de seções convertidos em letras maiúsculas
%subsection=TITLE, % títulos de subseções convertidos em letras maiúsculas
%subsubsection=TITLE,% títulos de subsubseções convertidos em letras maiúsculas
% -- opções do pacote babel --
english, % idioma adicional para hifenização
%french, % idioma adicional para hifenização
%spanish, % idioma adicional para hifenização
brazil % o último idioma é o principal do documento
]{abntex2ppgsi}
% ---
% Pacotes básicos
% ---
% \usepackage{lmodern} % Usa a fonte Latin Modern
% \usepackage[T1]{fontenc} % Selecao de codigos de fonte.
\usepackage[utf8]{inputenc} % Codificacao do documento (conversão automática dos acentos)
\usepackage{lastpage} % Usado pela Ficha catalográfica
\usepackage{indentfirst} % Indenta o primeiro parágrafo de cada seção.
\usepackage{color} % Controle das cores
\usepackage{graphicx} % Inclusão de gráficos
\usepackage{caption}
\usepackage{subcaption}
\usepackage{microtype} % para melhorias de justificação
\usepackage{pdfpages} %para incluir pdf
\usepackage{algpseudocode} %para ilustrações do tipo algoritmo
\usepackage{mdwlist} %para itens com espaço padrão da abnt
% \usepackage[noend]{algpseudocode} %para ilustrações do tipo algoritmo
\usepackage{longtable, multirow}
\usepackage{amsmath,amssymb,amsfonts,amsthm,mathtools}
\usepackage{dsfont}
\usepackage{rotating}
\usepackage{mathrsfs}
% \usepackage{subfig}
% \usepackage{subfigure}
%%% SARA COLOCOU ISSO AQUI - se der problema com numeracao de footnote, tirar isso.
\newcommand\blfootnote[1]{%
\begingroup
\renewcommand\thefootnote{}\footnote{#1}%
\addtocounter{footnote}{-1}%
\endgroup
}
%%%%%%%%%%%%%%
\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\diag}{diag}
\DeclarePairedDelimiter\abs{\lvert}{\rvert}
\DeclarePairedDelimiter\norm{\lVert}{\rVert}
% Swap the definition of \abs* and \norm*, so that \abs
% and \norm resizes the size of the brackets, and the
% starred version does not.
\makeatletter
\let\oldabs\abs
\def\abs{\@ifstar{\oldabs}{\oldabs*}}
%
\let\oldnorm\norm
\def\norm{\@ifstar{\oldnorm}{\oldnorm*}}
\makeatother
\newcounter{parms} \renewcommand{\theparms}{[\arabic{parms}]}
\newcommand{\newparm}[1]{
\refstepcounter{parms}\arabic{parms}\label{#1}%
}
\newcommand*{\horzbar}{\rule[.5ex]{2.5ex}{0.5pt}}
\newcommand*{\vertbar}{\rule[-1ex]{0.5pt}{2.5ex}}
\newtheorem{definition}{Definição}
\newtheorem{problem}{Problema}
\newtheorem{theorem}{Teorema}
\newtheorem{corollary}{Corolário}
\newtheorem{proposition}{Proposição}
% \renewcommand\qedsymbol{$\blacksquare$}
% ---
% Pacotes adicionais, usados apenas no âmbito do Modelo Canônico do abnteX2
% ---
\usepackage{lipsum} % para geração de dummy text
% ---
% ---
% Pacotes de citações
% ---
\usepackage[brazilian,hyperpageref]{backref} % Paginas com as citações na bibl
\usepackage[alf]{abntex2cite} % Citações padrão ABNT
% ---
% CONFIGURAÇÕES DE PACOTES
% ---
% ---
% Configurações do pacote backref
% Usado sem a opção hyperpageref de backref
\renewcommand{\backrefpagesname}{Citado na(s) página(s):~}
% Texto padrão antes do número das páginas
\renewcommand{\backref}{}
% Define os textos da citação
\renewcommand*{\backrefalt}[4]{
\ifcase #1 %
Nenhuma citação no texto.%
\or
Citado na página #2.%
\else
Citado #1 vezes nas páginas #2.%
\fi}%
% ---
% ---
% Informações de dados para CAPA e FOLHA DE ROSTO
% ---
%-------------------------------------------------------------------------
% Comentário adicional do PPgSI - Informações sobre o ``título'':
%
% Em maiúscula apenas a primeira letra da sentença (do título), exceto
% nomes próprios, geográficos, institucionais ou Programas ou Projetos ou
% siglas, os quais podem ter letras em maiúscula também.
%
% O subtítulo do trabalho é opcional.
% Sem ponto final.
%
% Atenção: o título da Dissertação na versão corrigida não pode mudar.
% Ele deve ser idêntico ao da versão original.
%
%-------------------------------------------------------------------------
%\titulo{Fatoração de matrizes no problema de coagrupamento}
%\titulo{Fatoração de matrizes no problema de coagrupamento com sobreposição}
\titulo{Fatoração de matrizes no problema de coagrupamento com sobreposição de colunas}
%\titulo{Fatoração de matrizes no problema de coagrupamento com sobreposição de cogrupos}
%\titulo{Fatoração de matrizes no problema de coagrupamento com sobreposição: Uma aplicação em mineração de textos}
%\titulo{Fatoração de matrizes no problema de coagrupamento com sobreposição de colunas: Uma aplicação em mineração de textos}
%-------------------------------------------------------------------------
% Comentário adicional do PPgSI - Informações sobre o ``autor'':
%
% Todas as letras em maiúsculas.
% Nome completo.
% Sem ponto final.
%-------------------------------------------------------------------------
\autor{\uppercase{Lucas Fernandes Brunialti}}
%-------------------------------------------------------------------------
% Comentário adicional do PPgSI - Informações sobre o ``local'':
%
% Não incluir o ``estado''.
% Sem ponto final.
%-------------------------------------------------------------------------
\local{São Paulo}
%-------------------------------------------------------------------------
% Comentário adicional do PPgSI - Informações sobre a ``data'':
%
% Colocar o ano do depósito (ou seja, o ano da entrega) da respectiva
% versão, seja ela a versão original (para a defesa) seja ela a versão
% corrigida (depois da aprovação na defesa).
%
% Atenção: Se a versão original for depositada no final do ano e a versão
% corrigida for entregue no ano seguinte, o ano precisa ser atualizado no
% caso da versão corrigida.
% Cuidado, pois o ano da ``capa externa'' também precisa ser atualizado
% nesse caso.
%
% Não incluir o dia, nem o mês.
% Sem ponto final.
%-------------------------------------------------------------------------
\data{2016}
%-------------------------------------------------------------------------
% Comentário adicional do PPgSI - Informações sobre o ``Orientador'':
%
% Se for uma professora, trocar por ``Profa. Dra.''
% Nome completo.
% Sem ponto final.
%-------------------------------------------------------------------------
\orientador{Profa. Dra. Sarajane Marques Peres}
%-------------------------------------------------------------------------
% Comentário adicional do PPgSI - Informações sobre o ``Coorientador'':
%
% Opcional. Incluir apenas se houver co-orientador formal, de acordo com o
% Regulamento do Programa.
%
% Se for uma professora, trocar por ``Profa. Dra.''
% Nome completo.
% Sem ponto final.
%-------------------------------------------------------------------------
%\coorientador{Prof. Dr. Valdinei Freire Silva}
\tipotrabalho{Dissertação (Mestrado)}
\preambulo{
%-------------------------------------------------------------------------
% Comentário adicional do PPgSI - Informações sobre o texto ``Versão
% original'':
%
% Não usar para Qualificação.
% Não usar para versão corrigida de Dissertação.
%
%-------------------------------------------------------------------------
Versão original
%-------------------------------------------------------------------------
% Comentário adicional do PPgSI - Informações sobre o ``texto principal do
% preambulo'':
%
% Para Qualificação, trocar por: Texto de Exame de Qualificação apresentado à Escola de Artes, Ciências e Humanidades da Universidade de São Paulo como parte dos requisitos para obtenção do título de Mestre em Ciências pelo Programa de Pós-graduação em Sistemas de Informação.
%
%-------------------------------------------------------------------------
\newline \newline \newline Dissertação apresentada à Escola de Artes, Ciências e Humanidades da Universidade de São Paulo para obtenção do título de Mestre em Ciências pelo Programa de Pós-graduação em Sistemas de Informação.
%
\newline \newline Área de concentração: Metodologia e Técnicas da Computação
%-------------------------------------------------------------------------
% Comentário adicional do PPgSI - Informações sobre o texto da ``Versão
% corrigida'':
%
% Não usar para Qualificação.
% Não usar para versão original de Dissertação.
%
% Substituir ``xx de xxxxxxxxxxxxxxx de xxxx'' pela ``data da defesa''.
%
%-------------------------------------------------------------------------
%\newline \newline \newline Versão corrigida contendo as alterações solicitadas pela comissão julgadora em xx de xxxxxxxxxxxxxxx de xxxx. A versão original encontra-se em acervo reservado na Biblioteca da EACH-USP e na Biblioteca Digital de Teses e Dissertações da USP (BDTD), de acordo com a Resolução CoPGr 6018, de 13 de outubro de 2011.
}
% ---
% ---
% Configurações de aparência do PDF final
% alterando o aspecto da cor azul
\definecolor{blue}{RGB}{41,5,195}
% informações do PDF
\makeatletter
\hypersetup{
%pagebackref=true,
pdftitle={\@title},
pdfauthor={\@author},
pdfsubject={\imprimirpreambulo},
pdfcreator={LaTeX com abnTeX2 adaptado para o PPgSI-EACH-USP},
pdfkeywords={abnt}{latex}{abntex}{abntex2}{qualificação de mestrado}{dissertação de mestrado}{ppgsi},
colorlinks=true, % false: boxed links; true: colored links
linkcolor=blue, % color of internal links
citecolor=blue, % color of links to bibliography
filecolor=magenta, % color of file links
urlcolor=blue,
bookmarksdepth=4
}
\makeatother
% ---
% ---
% Espaçamentos entre linhas e parágrafos
% ---
% O tamanho do parágrafo é dado por:
\setlength{\parindent}{1.25cm}
% Controle do espaçamento entre um parágrafo e outro:
\setlength{\parskip}{0cm} % tente também \onelineskip
\renewcommand{\baselinestretch}{1.5}
% ---
% compila o indice
% ---
\makeindex
% ---
% Controlar linhas orfas e viuvas
\clubpenalty10000
\widowpenalty10000
\displaywidowpenalty10000
% ----
% Início do documento
% ----
\begin{document}
% Retira espaço extra obsoleto entre as frases.
\frenchspacing
% ----------------------------------------------------------
% ELEMENTOS PRÉ-TEXTUAIS
% ----------------------------------------------------------
% \pretextual
% ---
% Capa
% ---
%-------------------------------------------------------------------------
% Comentário adicional do PPgSI - Informações sobre a ``capa'':
%
% Esta é a ``capa'' principal/oficial do trabalho, a ser impressa apenas
% para os casos de encadernação simples (ou seja, em ``espiral'' com
% plástico na frente).
%
% Não imprimir esta ``capa'' quando houver ``capa dura'' ou ``capa brochura''
% em que estas mesmas informações já estão presentes nela.
%
%-------------------------------------------------------------------------
\imprimircapa
% ---
% ---
% Folha de rosto
% (o * indica que haverá a ficha bibliográfica)
% ---
\imprimirfolhaderosto*
% ---
% ---
% Inserir a autorização para reprodução e ficha bibliografica
% ---
%-------------------------------------------------------------------------
% Comentário adicional do PPgSI - Informações sobre o texto da
% ``autorização para reprodução e ficha bibliografica'':
%
% Página a ser usada apenas para Dissertação (tanto na versão original
% quanto na versão corrigida).
%
% Solicitar a ficha catalográfica na Biblioteca da EACH.
% Duas versões devem ser solicitadas, em dois momentos distintos: uma vez
% para a versão original, e depois outra atualizada para a corrigida.
%
% Atenção: esta página de ``autorização para reprodução e ficha
% catalográfica'' deve ser impressa obrigatoriamente no verso da folha de
% rosto.
%
% Não usar esta página para Qualificação.
%
% Substitua o arquivo ``fig_ficha_catalografica.pdf'' abaixo referenciado
% pelo PDF elaborado pela Biblioteca
%
%-------------------------------------------------------------------------
\begin{fichacatalografica}
\includepdf{fig_ficha_catalografica.pdf}
\end{fichacatalografica}
% ---
% Inserir errata
% ---
%-------------------------------------------------------------------------
% Comentário adicional do PPgSI - Informações sobre ``Errata'':
%
% Usar esta página de errata apenas em casos de excepcionais, e apenas
% para a versão corrigida da Dissertação. Por exemplo, quando depois de
% já depositada e publicada a versão corrigida, ainda assim verifica-se
% a necessidade de alguma correção adicional.
%
% Se precisar usar esta página, busque a forma correta (o modelo correto)
% para fazê-lo, de acordo com a norma ABNT.
%
% Não usar esta página para versão original de Dissertação.
% Não usar esta página para Qualificação.
%
%-------------------------------------------------------------------------
%\begin{errata}
%Elemento opcional para versão corrigida, depois de depositada.
%\end{errata}
% ---
% ---
% Inserir folha de aprovação
% ---
\begin{folhadeaprovacao}
%-------------------------------------------------------------------------
% Comentário adicional do PPgSI - Informações sobre ``Folha da aprovação'':
%
% Para Qualificação, trocar por: Texto de Exame de Qualificação de autoria de Fulano de Tal, sob o título \textbf{``\imprimirtitulo''}, apresentado à Escola de Artes, Ciências e Humanidades da Universidade de São Paulo, como parte dos requisitos para obtenção do título de Mestre em Ciências pelo Programa de Pós-graduação em Sistemas de Informação, na área de concentração Sistemas de Informação, aprovado em \_\_\_ de \_\_\_\_\_\_\_\_\_\_\_\_\_\_ de \_\_\_\_\_\_ pela comissão examinadora constituída pelos doutores:
%
% Substituir ``Fulano de Tal'' pelo nome completo do autor do trabalho, com
% apenas as iniciais em maiúsculo.
%
% Substiuir ``___ de ______________ de ______'' por:
% - Para versão original de Dissertação: deixar em branco, pois a data
% pode mudar, mesmo que ela já esteja prevista.
% - Para versão corrigida de Dissertação: usar a data em que a defesa
% efetivamente ocorreu.
%
%-------------------------------------------------------------------------
\noindent Dissertação de autoria de Lucas Fernandes Brunialti, sob o título \textbf{\imprimirtitulo}, apresentada à Escola de Artes, Ciências e Humanidades da Universidade de São Paulo, para obtenção do título de Mestre em Ciências pelo Programa de Pós-graduação em Sistemas de Informação, na área de concentração Sistemas de Informação, aprovada em \_\_\_ de \_\_\_\_\_\_\_\_\_\_\_\_\_\_ de \_\_\_\_\_\_ pela comissão julgadora constituída pelos doutores:
\vspace*{3cm}
\begin{center}
%-------------------------------------------------------------------------
% Comentário adicional do PPgSI - Informações sobre ``assinaturas'':
%
% Para Qualificação e para versão original de Dissertação: deixar em
% branco (ou seja, assim como está abaixo), pois os membros da banca podem
% mudar, mesmo que eles já estejam previstos.
%
% Para versão corrigida de Dissertação: usar os dados dos examinadores que
% efetivamente participaram da defesa.
%
% Em nenhum caso há realmente necessidade de assinaturas.
%
% Para versão corrigida de Dissertação: em caso de ``professora'', trocar
% por ``Profa. Dra.''
%
% Para versão corrigida de Dissertação: ao colocar os nomes dos
% examinadores, remover o sublinhado
%
% Para versão corrigida de Dissertação: ao colocar os nomes dos
% examinadores, usar seus nomes completos, exatamente conforme constam em
% seus Currículos Lattes
%
% Para versão corrigida de Dissertação: ao colocar os nomes das
% instituições, remover o sublinhado e remover a palavra ``Instituição:''
%
% Não abreviar os nomes das instituições.
%
%-------------------------------------------------------------------------
\textbf{Prof. Dr. \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_}
\\ Presidente
\\ Instituição: \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_
\vspace*{2cm}
\textbf{Prof. Dr. \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_}
\\ Instituição: \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_
\vspace*{2cm}
\textbf{Prof. Dr. \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_}
\\ Instituição: \_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_
\end{center}
\end{folhadeaprovacao}
% ---
% ---
% Dedicatória
% ---
%-------------------------------------------------------------------------
% Comentário adicional do PPgSI - Informações sobre ``Dedicatória'':
%
% Opcional para Dissertação.
% Não sugerido para Qualificação.
%
%-------------------------------------------------------------------------
\begin{dedicatoria}
\vspace*{\fill}
\centering
\noindent
\textit{À minha noiva Beatriz, aos meus pais Sandra e Ronaldo, aos meus orientadores Sarajane e Valdinei, e aos amigos e empresas que me apoiaram nesses três anos}
\vspace*{\fill}
\end{dedicatoria}
% ---
% ---
% Agradecimentos
% ---
%-------------------------------------------------------------------------
% Comentário adicional do PPgSI - Informações sobre ``Agradecimentos'':
%
% Opcional para Dissertação.
% Não sugerido para Qualificação.
%
% Lembrar de agradecer agências de fomento e outras instituições similares.
%
%-------------------------------------------------------------------------
% \begin{agradecimentos}
% Texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo.
% Texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo.
% Texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo.
% Texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo.
% Texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo, texto de exemplo.
% \end{agradecimentos}
% ---
% ---
% Epígrafe
% ---
%-------------------------------------------------------------------------
% Comentário adicional do PPgSI - Informações sobre ``Epígrafe'':
%
% Opcional para Dissertação.
% Não sugerido para Qualificação.
%
%-------------------------------------------------------------------------
% \begin{epigrafe}
% \vspace*{\fill}
% \begin{flushright}
% \textit{``Escreva aqui uma epígrafe, se desejar, ou remova esta página...''\\
% (Autor da epígrafe)}
% \end{flushright}
% \end{epigrafe}
% ---
% ---
% RESUMOS
% ---
% resumo em português
\setlength{\absparsep}{18pt} % ajusta o espaçamento dos parágrafos do resumo
\begin{resumo}
%-------------------------------------------------------------------------
% Comentário adicional do PPgSI - Informações sobre ``referência'':
%
% Troque os seguintes campos pelos dados de sua Dissertação (mantendo a
% formatação e pontuação):
% - SOBRENOME
% - Nome1
% - Nome2
% - Nome3
% - Título do trabalho: subtítulo do trabalho
% - AnoDeDefesa
%
% Mantenha todas as demais informações exatamente como estão.
%
% [Não usar essas informações de ``referência'' para Qualificação]
%
%-------------------------------------------------------------------------
\begin{flushleft}
BRUNIALTI, Lucas Fernandes. \textbf{Fatoração de matrizes no problema de coagrupamento com sobreposição de colunas}. \imprimirdata. \pageref{LastPage} f. Dissertação (Mestrado em Ciências) – Escola de Artes, Ciências e Humanidades, Universidade de São Paulo, São Paulo, 2016.
\end{flushleft}
Coagrupamento é uma estratégia para análise de dados capaz de encontrar grupos de dados, então denomidados cogrupos, que são formados considerando subconjuntos diferentes das características descritivas dos dados.
Contextos de aplicação caracterizados por apresentar subjetividade, como mineração de texto, são candidatos a serem submetidos à estratégia de coagrupamento; a flexibilidade em associar textos de acordo com características parciais representa um tratamento adequado à tal subjetividade.
Um método para implementação de coagrupamento capaz de lidar com esse tipo de dados é a fatoração de matrizes.
Nesta dissertação de mestrado são propostas duas estratégias para coagrupamento baseadas em fatoração de matrizes não-negativas, capazes de encontrar cogrupos organizados com sobreposição de colunas em uma matriz de valores reais positivos.
As estratégias são apresentadas em termos de suas definições formais e seus algoritmos para implementação.
Resultados experimentais quantitativos e qualitativos são fornecidos a partir de problemas baseados em conjuntos de dados sintéticos e em conjuntos de dados reais, sendo esses últimos contextualizados na área de mineração de texto.
Os resultados são analisados em termos de quantização do espaço e capacidade de reconstrução, capacidade de agrupamento utilizando as métricas Índice de Rand e Informação Mútua Normalizada e geração de informação (interpretabilidade dos modelos).
Os resultados confirmam a hipótese de que as estratégias propostas são capazes de descobrir cogrupos com sobreposição de forma natural, e que tal organização de cogrupos fornece informação detalhada, e portanto de valor diferenciado, para as áreas de análise de agrupamento e mineração de texto.
Palavras-chaves: Coagrupamento. Fatoração de Matrizes Não-negativas. Análise de Agrupamento. Mineração de Texto.
\end{resumo}
% resumo em inglês
%-------------------------------------------------------------------------
% Comentário adicional do PPgSI - Informações sobre ``resumo em inglês''
%
% Caso a Qualificação ou a Dissertação inteira seja elaborada no idioma inglês,
% então o ``Abstract'' vem antes do ``Resumo''.
%
%-------------------------------------------------------------------------
\begin{resumo}[Abstract]
\begin{otherlanguage*}{english}
%-------------------------------------------------------------------------
% Comentário adicional do PPgSI - Informações sobre ``referência em inglês''
%
% Troque os seguintes campos pelos dados de sua Dissertação (mantendo a
% formatação e pontuação):
% - SURNAME
% - FirstName1
% - MiddleName1
% - MiddleName2
% - Work title: work subtitle
% - DefenseYear (Ano de Defesa)
%
% Mantenha todas as demais informações exatamente como estão.
%
% [Não usar essas informações de ``referência'' para Qualificação]
%
%-------------------------------------------------------------------------
\begin{flushleft}
BRUNIALTI, Lucas Fernandes. \textbf{Matrix factorization for overlapping columns coclustering}. \imprimirdata. \pageref{LastPage} p. Dissertation (Master of Science) – School of Arts, Sciences and Humanities, University of São Paulo, São Paulo, DefenseYear.
\end{flushleft}
Coclustering is a data analysis strategy which is able to discover data clusters, known as coclusters.
This technique allows data to be clustered based on different subsets defined by data descriptive features.
Application contexts characterized by subjectivity, such as text mining, are applicable candidates for applying coclustering strategy due to the flexibility to associate documents according to partial features.
The coclustering method can be implemented by means of matrix factorization, which is suitable to handle this type of data.
In this thesis two strategies are proposed in non-negative matrix factorization for coclustering.
These strategies are able to find column overlapping coclusters in a given dataset of positive data and are presented in terms of their formal definitions as well as their algorithms' implementation.
Quantitative and qualitative experimental results are presented through applying synthetic datasets and real datasets contextualized in text mining.
This is accomplished by analyzing them in terms of space quantization, clustering capabilities and generated information (interpretability of models).
The well known external metrics Rand Index and Normalized Mutual Information are used to achieve the analysis of clustering capabilities.
Results confirm the hypothesis that the proposed strategies are able to discover overlapping coclusters naturally.
Moreover, these coclusters produced by the new algorithms provide detailed information and are thus valuable for future research in cluster analysis and text mining.
Keywords: Coclustering. Non-negative Matrix Factorization. Cluster Analysis. Text Mining.
\end{otherlanguage*}
\end{resumo}
% ---
% ---
% inserir lista de figuras
% ---
\pdfbookmark[0]{\listfigurename}{lof}
\addtocontents{toc}{\protect\sloppy}
\listoffigures*
\cleardoublepage
% ---
% ---
% inserir lista de algoritmos
% ---
\pdfbookmark[0]{\listalgorithmname}{loa}
\listofalgorithms
\cleardoublepage
% ---
% inserir lista de tabelas
% ---
\pdfbookmark[0]{\listtablename}{lot}
\listoftables*
\cleardoublepage
% ---
% ---
% inserir lista de abreviaturas e siglas
% ---
%-------------------------------------------------------------------------
% Comentário adicional do PPgSI - Informações sobre ``Lista de abreviaturas
% e siglas'':
%
% Opcional.
% Uma vez que se deseja usar, é necessário manter padrão e consistência no
% trabalho inteiro.
% Se usar: inserir em ordem alfabética.
%
%-------------------------------------------------------------------------
% \begin{siglas}
% \item[Sigla/abreviatura 1] Definição da sigla ou da abreviatura por extenso
% \item[Sigla/abreviatura 2] Definição da sigla ou da abreviatura por extenso
% \item[Sigla/abreviatura 3] Definição da sigla ou da abreviatura por extenso
% \item[Sigla/abreviatura 4] Definição da sigla ou da abreviatura por extenso
% \item[Sigla/abreviatura 5] Definição da sigla ou da abreviatura por extenso
% \item[Sigla/abreviatura 6] Definição da sigla ou da abreviatura por extenso
% \item[Sigla/abreviatura 7] Definição da sigla ou da abreviatura por extenso
% \item[Sigla/abreviatura 8] Definição da sigla ou da abreviatura por extenso
% \item[Sigla/abreviatura 9] Definição da sigla ou da abreviatura por extenso
% \item[Sigla/abreviatura 10] Definição da sigla ou da abreviatura por extenso
% \end{siglas}
% ---
% ---
% inserir lista de símbolos
% ---
%-------------------------------------------------------------------------
% Comentário adicional do PPgSI - Informações sobre ``Lista de símbolos'':
%
% Opcional.
% Uma vez que se deseja usar, é necessário manter padrão e consistência no
% trabalho inteiro.
% Se usar: inserir na ordem em que aparece no texto.
%
%-------------------------------------------------------------------------
% \begin{simbolos}
% \item[$ \Gamma $] Letra grega Gama
% \item[$ \Lambda $] Lambda
% \item[$ \zeta $] Letra grega minúscula zeta
% \item[$ \in $] Pertence
% \end{simbolos}
% ---
% ---
% inserir o sumario
% ---
% \pdfbookmark[0]{\contentsname}{toc}
% \tableofcontents*
% \cleardoublepage
\pdfbookmark[0]{\contentsname}{toc}
\addtocontents{toc}{\protect\sloppy}
\tableofcontents*
\cleardoublepage
% ---
% ----------------------------------------------------------
% ELEMENTOS TEXTUAIS
% ----------------------------------------------------------
\textual
%-------------------------------------------------------------------------
% Comentário adicional do PPgSI - Informações sobre ``títulos de seções''
%
% Para todos os títulos (seções, subseções, tabelas, ilustrações, etc):
%
% Em maiúscula apenas a primeira letra da sentença (do título), exceto
% nomes próprios, geográficos, institucionais ou Programas ou Projetos ou
% siglas, os quais podem ter letras em maiúscula também.
%
%-------------------------------------------------------------------------
% Example of table
% \begin{table}[htbp]
% \centering
% \caption{Exemplo de título de tabela}
% \begin{tabular}{p{1in} p{1in} p{1in} p{1in} } \hline
% Cabeçalho 1 & Cabeçalho 2 & Cabeçalho 3 & Cabeçalho 4 \\ \hline
% Texto & número & número & número \\
% Texto & número & número & número \\
% Texto & número & número & número \\
% Texto & número & número & número \\
% Texto & número & número & número \\ \hline
% \end{tabular}
% \label{tab:ExemploDeTabela1}
% \source{Marcelo Fantinato, 2016}
% \end{table}
\chapter{Introdução}
\label{cap:intro}
% Não há padronização nas representações para as melhores representações.
% - Não colocar que uma representação é melhor que a outra
% - Conclusao:
% * pensei nos algos, qual contribuição:
% - entender os algoritmos originais
% - propor mudança de concepcao no modelo
% - verificar se isso era possivel
% - teste empirico
% - derivação
% - experimentacao onde percebo algos, destaque especifico para os algoritmos BinOvNMTF
% - Hipotese: pq eles se destacam
% Introducao:
% - como os algos da literatura tratam sobreposicao
% - estudando quantizacao, etc (final cap 3 e 5)
Segundo~\citeonline{Jain1999}, a análise de agrupamento pode ser vista como uma tarefa exploratória que tem o objetivo de organizar uma coleção de dados em um conjunto de grupos, segundo a similaridade ou dissimilaridade existente entre esses dados.
Tradicionalmente, os métodos usados para análise de agrupamento são desenvolvidos para minimizar a similaridade intragrupos e maximizar a similaridade intergrupos; e precisam encontrar uma organização ``natural'' em grupos que acomode cada dado do conjunto sob análise em um grupo específico.
Estratégias de diferentes naturezas -- particional, hierárquica, baseada em densidade, etc~\cite{Han2011,Xu2005} -- podem ser usadas para alcançar o objetivo da análise de agrupamento, e cada uma delas possui características que as fazem mais ou menos suscetíveis para conjuntos de dados de diferentes naturezas.
Ainda, sob o contexto clássico da tarefa de agrupamento, os métodos precisam lidar com a similaridade entre os dados tomando como base a comparação de todas as suas características descritivas e, de alguma forma, precisam ser capazes de descobrir quais características de fato tornam dados em um grupo de dados mais similares entre si.
Ao longo do tempo, pesquisadores da área de análise de agrupamento vêm propondo flexibilizações na definição da tarefa de agrupamento de forma a adequá-la a contextos mais realísticos, nos quais a organização natural dos dados em um conjunto de dados não pressupõe restrições como a pertinência de um dado a um único grupo ou a possibilidade de agrupar dados de acordo com similaridades em subconjuntos de atributos descritivos~\cite{Bezdek1981,Han2011,Peres2012}.
Essa forma de tratar a tarefa de agrupamento permite melhorias no processo de descoberta de agrupamentos sob dois aspectos: facilita o trabalho do método que busca os grupos, pois flexibiliza a maneira como os atributos descritivos dos dados ou a pertinência do dado aos grupos influencia o processo de agrupamento; fornece um conjunto de informações diferenciado que permite que análises mais refinadas sejam realizadas quando da interpretação dos grupos apresentados como resultado.
Esse diferencial pode ser especialmente útil quando o contexto da aplicação da análise de agrupamento apresenta alguma subjetividade em termos de interpretação de resultados, um fato bastante comum em tarefas de mineração de texto, por exemplo.
Considere um contexto de uma aplicação de mineração de texto em que o objetivo é encontrar notícias similares à uma notícia fornecida como entrada, seja para recomendação, aumentando o engajamento de usuários em um portal de notícias, ou até mesmo para descoberta de conhecimento, a fim de ajudar na tomada de decisões de negócio nesse portal de notícias, por exemplo.
A análise de agrupamento com base na similaridade que considera todos os atributos (palavras), em um conjunto de notícias que representam os temas esportes (colunas \#1, \#2 e \#3 na figura~\ref{fig:sistema:a}) e música (colunas \#4, \#5 e \#6 na figura~\ref{fig:sistema:a}), seria capaz de particionar as notícias em dois grupos, que representariam esses dois temas.
Embora essas recomendações pareçam ser ideais, e sob algum aspecto de análise elas são, é factível assumir que essa análise de agrupamento é prática, mas talvez menos útil e interessante do que poderia ser.
Uma possibilidade de melhoria dessa aplicação hipotética seria usar um algoritmo de análise de agrupamento que permitisse descobrir uma organização de grupos de notícias baseada em similaridades parciais ou baseada em partes~\cite{Franca2010,Ho2008}.
Assim, seria possível encontrar grupos que não são encontrados quando se considera todas as características na análise de agrupamento.
Considerando tal possibilidade, a aplicação seria dotada da capacidade de perceber, por exemplo, que algumas notícias podem trazer conteúdo referente a diferentes contextos se forem analisadas apenas sob determinados aspectos.
Nesse caso, os grupos formados durante a análise de agrupamento seriam capazes de refletir a diversidade de contextos abordados em uma notícia, fazendo-a pertencer a diferentes grupos, por diferentes motivos.
Por exemplo, é sabido que eventos de beisebol -- o \textit{superbowl} -- possuem uma abertura cultural na qual grandes artistas da música fazem apresentações; ou eventos de esportes radicais, como tirolesa, acontecem em eventos de música contemporâneos -- \textit{rock in rio}.
Tais notícias deveriam aparecer em grupos caracterizados por notícias referentes à esportes, notícias referentes à música, ou notícias referentes à esporte e música (Figuras~\ref{fig:sistema:b} e~\ref{fig:sistema:c}).
\begin{figure} [htpb]
\centering
\caption{
Representação de uma aplicação de mineração de dados implementada a partir de análise de agrupamento com similaridade total (a) e similaridade parcial (b,c). Os grupos são diferenciados por cores.
}
\begin{subfigure}[b]{0.45\textwidth}
\includegraphics[width=\textwidth]{img/sistema0.png}
\caption{}
\label{fig:sistema:a}
\end{subfigure}
~
\begin{subfigure}[b]{0.45\textwidth}
\includegraphics[width=\textwidth]{img/sistema1.png}
\caption{}
\label{fig:sistema:b}
\end{subfigure}
~
\begin{subfigure}[b]{0.45\textwidth}
\includegraphics[width=\textwidth]{img/sistema2.png}
\caption{}
\label{fig:sistema:c}
\end{subfigure}
\source{Lucas Fernandes Brunialti, 2016}
\end{figure}
Nas figuras~\ref{fig:sistema:b} e~\ref{fig:sistema:c} é introduzido graficamente o conceito de coagrupamento.
Nesse contexto, o problema de mineração de texto é modelado como o problema de encontrar uma organização dos textos em grupos considerando similaridades parciais.
Assim, um texto pode pertencer a um ou mais cogrupos, a depender dos atributos descritivos sendo considerados.
Portanto, nessa aplicação, uma análise de agrupamento com maior capacidade de extração de informação e interpretabilidade, consideraria que o grupo de notícias referentes aos assuntos esportes e música tem sobreposição nas palavras que formam o grupo de notícias sobre música e o grupo de notícias sobre esportes (Figura~\ref{fig:sistema:c}).
A nomenclatura coagrupamento deriva da estratégia de análise de dados executada durante o processo de descoberta de grupos.
Nesse caso, tanto os dados (linhas) quanto os seus atributos descritivos (colunas) são mutuamente submetidos a uma análise de similaridade, e portanto, grupos de dados (linhas) são estabelecidos com respeito a grupos de atributos (colunas), e grupos de atributos (colunas) também são estabelecidos com respeito a grupos de dados (linhas).
A associação da análise de coagrupamentos a mineração de texto é interessante pois essa tarefa constitui-se como um problema no qual é preciso lidar com a necessidade de apresentação de resultados que gerem informações passíveis de serem interpretadas.
Esse problema pode ser bem resolvido com a estratégia de coagrupamento pois os grupos de atributos que são gerados por ela podem revelar informação antes escondida nos dados~\cite{Tjhi2009}, e que em um processo de agrupamento tradicional não poderiam ser, pelo menos diretamente, descobertas.
Dentre os diferentes métodos existentes na literatura referentes à implementação de análise de coagrupamento~\cite{Franca2010,Mirkin1996,Madeira2004}, métodos que usam fatoração de matrizes não negativas~\cite{lee:nnmf00,lee99} têm sido vistos como uma boa alternativa a ser aplicada no contexto de mineração de texto, dado que esses métodos têm vantagens para lidar com dados representados como matrizes positivas~\cite{Xu2003,Shahnaz2006373,Yoo2010}.
Este trabalho explora o uso dos métodos de fatoração de matrizes não-negativas no contexto de coagrupamento, com atenção especial ao tratamento natural de cogrupos com sobreposição de colunas.
Como forma de ilustrar a aplicabilidade das soluções propostas, o contexto de mineração de texto é analisado sob a ótica de coagrupamento.
% ********************************************************************************************
\section{Definição do problema}
\label{sec:problemdef}
% - resolver o overlap de colunas de forma "natural"
% -> tratamento diferente do overlap
% -> motivando de forma que esse overlap de forma "natural" é bom p/ mineracao de textos
% qual é o problema?
% -- o overlap existe
% no contexto de análise de coagrupamentos, as similaridades parciais entre os atributos que caracterizam a pertinência de dados aos grupos pode ser diferente no contexto de cada grupo.
% -- o overlap precisa ser considerado pelo processo de análise
%Isso implica que organizações diferentes para os cogrupos de colunas podem ser necessárias para uma boa caracterização dos cogrupos de linhas. Então, o problema a ser resolvido é tratar esse contexto de maneira adequada.
%Considerando os métodos de fatoração de matrizes como uma alternativa para resolução da tarefa de coagrupamento, a adequação dos algoritmos para trabalhar bem nesse problema é necessária.
Para definição do problema é necessário o entendimento da tarefa de coagrupamento, e como a tarefa de coagrupamento se conecta com fatoração de matrizes.
A estratégia de coagrupamento pode ser apresentada como o processo de agrupamento simultâneo de linhas e colunas em uma matriz de dados, de forma que seja possível encontrar cogrupos nos quais um grupo de objetos (linhas) associado a um grupo de atributos (colunas) diz respeito a objetos que são similares entre si considerando este grupo de atributos (colunas), formando então, um cogrupo.
Com maior formalidade, dada uma matriz $X$ com $n$ linhas e $m$ colunas, a tarefa de coagrupamento pode ser vista como encontrar $k$ grupos de linhas de $X$, denotados pelos conjuntos que contém as linhas da matriz de dados $\mathcal{K}_p, \forall p \in \{1, \dots, k\}$, e $l$ grupos de colunas de $X$, denotados pelos conjuntos que contém as colunas de atributos $\mathcal{L}_q, \forall q \in \{1, \dots, l\}$.
Fatorar uma matriz consiste em encontrar duas, ou mais, novas matrizes que, ao serem combinadas, reconstroem a matriz original.
Considerando a matriz $X$, a sua fatoração em duas novas matrizes consiste em encontrar duas matrizes, $U$ com $n$ linhas e $k$ colunas e $C$ com $k$ linhas e $m$ colunas, tal que $X \approx UC$.
Se $k$ é escolhido tal que seja muito menor do que $n$ e $m$, então é dito que $U$ e $C$ são representações compactas de $X$.
Se a matriz $X$ e as suas decomposições são não-negativas, tem-se o caso de Fatoração de Matrizes Não-negativas (NMF - \textit{Non-negative Matrix Factorization})~\cite{lee:nnmf00}, que pode ser interpretado como um método de agrupamento quando faz-se a análise sobre a matriz $U$, sendo $k$ o número de grupos de linhas.
Se três matrizes são geradas na fatoração, $U$ com $n$ linhas e $k$ colunas, $S$ com $k$ linhas e $l$ colunas, e $V$ com $m$ linhas e $l$ colunas, fazendo a aproximação $X \approx USV^T$, e se $k$ e $l$ são escolhidos tal que sejam menores que $n$ e $m$, respectivamente, então é dito que $U$, $S$ e $V$ são representações compactas de $X$ e imbutem a noção de $k$ grupos de linhas e $l$ grupos de colunas.
A interpretação de $S$ pode incluir uma noção de pesos que relacionam grupos de linhas e grupos de colunas, de modo que o número de grupos de linhas ($k$) pode ser diferente do número de grupo de colunas ($l$).
Desta maneira, o problema de coagrupamento pode ser modelado de tal forma que a fatoração de matrizes é capaz de fornecer uma aproximação da organização em cogrupos presente no conjunto de dados sob análise.
O problema deste trabalho é propor soluções algorítmicas que são capazes de solucionar a tarefa de coagrupamento no qual cogrupos de colunas têm intersecção (sobreposição): $\mathcal{L}_q \cap \mathcal{L}_{q'} \neq \emptyset$ para $q \neq q'$.
Assim é possível que uma coluna pertença à dois ou mais grupos de colunas.
% ************************************************************************
% essa ilustração deveria ser deixada para um capítulo de coagraupamento
%O problema de Biclusterização pode ser ilustrado na Figura~\ref{fig:bicluster-exp}, onde se tem um conjunto de dados que possui objetos $x_1, x_2, x_3, x_4, x_5$ e $x_6$ que são representados pelos atributos $y_1, y_2, y_3, y_4, y_5$ e $y_6$, onde $N,M = 6$.
%Na Figura~\ref{fig:bicluster-exp} também estão ilustrados dois biclusters hipotéticos: o primeiro formado pelos objetos $x_5$ e $x_6$ e todos os atributos ($y_1, \dots, y_6$), representando um bicluster com \textit{modelo global}; e o segundo formado pelos objetos $x_2, x_3, x_4$ e $x_5$ e atributos $y_4, y_5$ e $y_6$, representando um bicluster com \textit{modelo local}, que leva em consideração apenas um subconjunto dos atributos.
%\begin{figure}[h]
%\centering
%\includegraphics[width=80mm]{img/bicluster.png}
%\caption{Conjunto de dados com dois biclusters encontrados.}
%\label{fig:bicluster-exp}
%\end{figure}
% ************************************************************************
\section{Hipótese}
Fatorar matrizes considerando a decomposição da matriz original em uma matriz $U$, uma matriz $S$ e um conjunto de matrizes $V$, isto é $X \approx USV_{(1)}^T \dots V_{(k)}^T$, tal que seja possível encontrar cogrupos, possibilita que o processo de busca seja beneficiado pela flexibilidade de ajuste de $U$ e o conjunto de matrizes $V$, sendo mais adequado do que o processo tradicional de fatoração de matrizes, exposto na seção~\ref{sec:problemdef}, para o tratamento da tarefa de coagrupamento com sobreposição de colunas.
A adequação deste processo manterá informações da matriz original a fim de permitir a sua reconstrução, propiciará um resultado mais adequado em termos de agrupamento de linhas seguindo a avaliação clássica de quantização, e possibilitará a extração de informações diferenciadas a partir da análise da fatoração gerada, agregando valor à solução de um problema de mineração de texto.
% ************************************************************************
\section{Objetivos}
O objetivo geral deste trabalho foi o desenvolvimento de novas estratégias de coagrupamento baseadas em fatoração de matrizes, aqui então nomeadas \textit{OvNMTF} e \textit{BinOvNMTF}, capazes de lidar com a existência de cogrupos de colunas com sobreposição, de maneira mais adequada que os algoritmos atualmente apresentados na literatura.
A adequabilidade das estratégias propostas foi avaliada em termos de: capacidade de quantização do espaço e capacidade de reconstrução da matriz original, capacidade de agrupamento e capacidade de possibilitar a extração de informação.
Como objetivos específicos, este trabalho:
\begin{itemize}
\item apresentou a derivação formal das regras de atualização de matrizes usadas nas estratégias propostas (\textit{OvNMTF} e \textit{BinOvNMTF});
\item apresentou a aplicação das novas estratégias em ambientes controlados (bases de dados sintéticas) e em um contexto de aplicação real (análise de dado textuais);
\item apresentou um novo conjunto de dados textual, em língua portuguesa, referente ao contexto de notícias.
\end{itemize}
O atendimento aos objetivos delineados permitiu a esse trabalho:
\begin{itemize}
\item aprimorar a área de coagrupamento baseado em algoritmos de fatoração de matrizes, de forma a contribuir com a pesquisa em análise de agrupamento;
\item demonstrar que as estratégias de coagrupamento propostas têm potencial de revelar informações úteis provenientes da sobreposição natural dos atributos descritivos de um dado real, em especial para aplicações de mineração de texto.
\end{itemize}
% ************************************************************************
\section{Método}
A análise exploratória da literatura especilizada foi escolhida como estratégia para a aquisição de conhecimento sobre a área de coagrupamento e fatoração de matrizes aplicada à resolução da tarefa de coagrupamento.
A partir da análise exploratória, os algoritmos \textit{BVD}~\cite{Long2005}, \textit{ONMTF}~\cite{Ding06,Yoo2010} e \textit{FNMTF}~\cite{Wang2011} foram estudados em profundidade com o fim de verificar a sua adequabilidade para tratar a análise de coagrupamento sobre dados sintéticos e textuais, considerando a sobreposição de colunas.
Nesse estudo verificou-se a possibilidade da proposição de melhorias no tratamento do problema, e então, os algoritmos \textit{OvNMTF} e \textit{BinOvNMTF} foram criados.
Para cada um deles, o problema formal de otimização foi definido e uma derivação formal foi realizada usando cálculo em matrizes com o intuito de propor uma solução algorítmica para tais problemas.
A fim de permitir a validação das estratégias propostas e, portanto, a verificação da hipótese delineada neste trabalho, fez-se necessária a definição de: (a) um ambiente de teste controlado, representado por uma coleção de conjuntos de dados sintéticos, contendo em cada um dos conjuntos situações diferentes referentes às estruturas de coagrupamento; e (b) um contexto para realização de uma experimentação com dados reais.
Para tal experimentação foi escolhido usar o conteúdo referente à notícias publicadas no portal iG\footnote{\url{http://ig.com.br/}} e trabalhos acadêmicos publicadas na conferência \textit{NIPS}.
iG é um portal de notícias brasileiro muito conhecido, com um grande volume de notícias categorizadas em canais, os quais representam os assuntos dessas notícias.
Essas características conferem liberdade para a configuração de experimentos de diferentes naturezas, como experimentos considerando determinadas categorias de notícias, tipos de notícias ou datas de publicação das notícias.
A partir do conteúdo de notícias do portal iG foi construído um corpus de dados textuais, categorizados de acordo com as categorias já usadas no referido portal.
Todo o conteúdo do corpus passou por rotinas de pré-processamento comuns na área de mineração de texto: \textit{tokenização}~\cite{Lops2011}, filtragem de \textit{stopwords}~\cite{Lops2011}, representação da relação ``termos $\times$ documentos'' usando estratégias de frequência de termos, como $\text{\textit{tf-idf}}$~\cite{Salton1975}.
Os resultados da aplicação das estratégias de coagrupamento foram validados utilizando:
\begin{itemize}
\item inspeção visual e erro de quantização para análise da capacidade de reconstrução;
\item técnicas de avaliação externa representadas pelo índice de Rand e pela informação mútua normalizada, para análise da capacidade de agrupamento;
\item análise empírica por meio de experimentos qualitativos para avaliação da capacidade de extração de informação e interpretabilidade dos modelos.
\end{itemize}
% ************************************************************************
\section{Organização do documento}
Esta dissertação é composta por $6$ capítulos incluindo esta introdução.
No capítulo~\ref{ch:conceitos} são apresentados os principais conceitos referentes à teoria de matrizes, agrupamento e coagrupamento.
O objetivo deste capítulo é fornecer diretrizes para entendimento dos assuntos tratados nos capítulos posteriores e indicar literatura na qual podem ser encontradas informações mais detalhadas sobre tais assuntos.
Estratégias de fatoração de matrizes aplicadas à resolução da tarefa de coagrupamento são discutidas no capítulo~\ref{ch:fatoracao}.
A discussão é apresenta em termos da definição de problemas e apresentação de soluções algorítmicas para os problemas.
Algumas discussões sobre os problemas e algoritmos são apresentadas sempre que um conceito é mais relevante para o entendimento da proposta deste trabalho.
Detalhes sobre cada um dos problemas e algoritmos são encontrados na literatura sugerida nesse capítulo.
A principal contribuição deste trabalho, estratégias algorítmicas baseadas em fatoração de matrizes para encontrar cogrupos com sobreposição de colunas, é apresentada em detalhes no capítulo~\ref{ch:proposedalgs}.
As definições de problemas, regras de derivação e implementações algorítimicas foram formuladas originalmente neste estudo.
Os experimentos a cerca dos algoritmos apresentados nos outros capítulos são apresentados no capítulo~\ref{ch:experiments}.
Os experimentos apresentados no capítulo~\ref{ch:experiments} ilustram a aplicabilidade e adequabilidade das estratégias apresentadas nos capítulos~\ref{ch:fatoracao} e~\ref{ch:proposedalgs}, com destaque para as vantagens e limitações das estratégias propostas neste trabalho de mestrado.
As análises apresentadas neste capítulo são de natureza quantitativa e qualitativa.
E, por fim, as conclusões deste trabalho são apresentadas no capítulo~\ref{ch:conclusoes}, destacando as contribuições aqui elaboradas e as questões em aberto na área, sendo algumas delas decorrentes de novas hipóteses, cuja formulação se tornou possível por conta das proposições realizadas no presente trabalho.
% ************************************************************
% ************************************************************
% ************************************************************
\chapter{Conceitos Fundamentais}
\label{ch:conceitos}
Este capítulo introduz os principais conceitos e definições necessárias para suportar a leitura dos demais capítulos deste trabalho.
São apresentados os conceitos e notações referentes à teoria de matrizes e álgebra linear (seção~\ref{sec:matrix-alglin}), em seguida são mostrados técnicas e conceitos referentes à agrupamento (seção~\ref{sec:clustering}), e por fim, os conceitos referentes à coagrupamento (seção~\ref{sec:coclustering}).
\section{Teoria de Matrizes e Álgebra Linear}
\label{sec:matrix-alglin}
Considere $\mathbb{R}$ o conjunto de todos os números reais, então, uma matriz no espaço $\mathbb{R}^{n \times m}$ é definida como uma tabela com $n$ linhas e $m$ colunas, na forma:
\[
A \in \mathbb{R}^{n \times m} \Leftrightarrow A = \begin{bmatrix}
a_{1 1} & \hdots & a_{m 1} \\
\vdots & & \vdots \\
a_{n 1} & \hdots & a_{n m}
\end{bmatrix}
\]
sendo $a_{i j} = (A)_{ij} \in \mathbb{R}, \forall i, j$ o elemento da $i$-ésima linha e $j$-ésima coluna da matriz $A$, e os índices $i \in \{1, \dots, n\}$ e $j \in \{1, \dots, m\}$ para indexar as linhas e colunas dessa matriz, respectivamente.
Na notação usada neste trabalho, letras maiúsculas representam matrizes (ex.: $A$), e letras minúsculas com duas letras subscritas representam valores na matriz (ex.: $a_{ij}$ representa um valor da matriz $A$).