Abstract Sentiment analysis deals with opinions in documents and relies on sentiment lexicons; however, Turkish is one of the poorest languages in regard to having such ready-to-use sentiment lexicons. In this article, we propose a domain- independent Turkish sentiment seed lexicon, which is extended from an initial seed lexicon, consisting of 62 positive/negative seeds. The lexicon is completed by using the beam search method to propagate the sentiment values of initial seeds by exploiting synonym and antonym relations in the Turkish Semantic Relations Dataset. Consequently, the proposed method assigned 94 words as positive sentiments and 95 words as negative sentiments. To test the correctness of the sentiment seeds and their values the first sense, the total sum and weighted sum algorithms, which are based on SentiWordNet and SenticNet 3, are used. According to the weighted sum, experimental results indicate that the beam search algorithm is a good alternative to automatic construction of a domain-independent sentiment seed lexicon.

References

[1] Abdul-Mageed M., Diab M., and Korayem M., “Subjectivity and Sentiment Analysis of Modern 6WDQGDUG $UDELF´in Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies: Shortpapers, Portland, pp. 587- 591, 2011.

[2] Araya I. and Riff M., “A Beam Search Approach to the Container Loading Problem,” Computers and Operations Research, vol. 43, pp. 100-107, 2014.

[3] Baccianella S., Esuli A., and Sebastiani F., “SentiWordNet 3.0: An Enhanced Lexical Resource for Sentiment Analysis and Opinion Mining,” in Proceedings of the 7th International Conference on Language Resources and Evaluation, Valletta, pp. 2200-2204, 2010.

[4] Banea C., Mihalcea R., and Wiebe J., “A Bootstrapping Method for Building Subjectivity Lexicons for Languages with Scarce Resources,” in Proceedings of the 6th International Conference on Language Resources and Evaluation, Marrakech, pp. 2764-2767, 2008.

[5] Bautista J., Pereira J., and Adenso-Diaz B., “A Beam Search Approach for the Optimization Version of the Car Sequencing Problem,” Annals of Operations Research, vol. 159, no. 1, pp. 233- 244, 2008.

[6] Bennell J. and Song X., “A Beam Search Implementation for the Irregular Shape Packing Problem,” Journal of Heuristics, vol. 16, no. 2, pp. 167-188, 2010.

[7] Blum C., “Beam-ACO-Hybridizing Ant Colony Optimization with Beam Search: An Application to Open Shop Scheduling,” Computers and Operations Research, vol. 32, no. 6, pp. 1565- 1591, 2005.

[8] Brooke J., Tofiloski M., and Taboada M., “Cross- Linguistic Sentiment Analysis: from English to Spanish,” in Proceedings of International Conference Recent Advances in Natural Language Processing, Borovets, pp. 50-54, 2009.

[9] Cakmak O., Kazemzadeh A., Yildirim S., and Narayanan S., “Using Interval Type-2 Fuzzy Logic to Analyze Turkish Emotion Words,” in Proceedings of Signal and Information Processing Association Annual Summit and Conference, Hollywood, pp. 1-4, 2012.

[10] Cambria E., Havasi C., and Hussain A., “SenticNet 2: A Semantic and Affective Resource for Opinion Mining and Sentiment Analysis,” in Proceedings of the 25th International Florida Artificial Intelligence Research Society Conference, Palo Alto, pp. 202-207, 2012.

[11] Cambria E., Olsher D., and Rajagopal D., “SenticNet 3: A Common and Common-Sense Knowledge Base for Cognition-Driven Sentiment Analysis,” in Proceedings of the 28th AAAI Conference on Artificial Intelligence, Québec City, pp. 1515-1521, 2014.

[12] Clematide S. and Klenner M., “Evaluation and Extension of a Polarity Lexicon for German,” in Proceedings of the 1st Workshop on Computational Approaches to Subjectivity and Sentiment Analysis, Portugal, pp. 7-13, 2010.

[13] Cruz F., Troyano J., Pontes B., and Ortega F., “Building Layered, Multilingual Sentiment Lexicons At Synset and Lemma Levels,” Expert Systems with Applications, vol. 41, no. 13, pp. 5984-5994, 2014.

[14] Das A. and Bandyopadhyay S., “SentiWordNet IRU ,QGLDQ /DQJXDJHV´in Proceedings of the 8th Workshop on Asian Language Resources, Beijing, pp. 56-63, 2010.

[15] De Albornoz J., Plaza L., and Gervás P., “Sentisense: An Easily Scalable Concept-Based Affective Lexicon for Sentiment Analysis,” in Proceedings of the 8th International Conference on Language Resources and Evaluation, Istanbul, pp. 3562-3567, 2012.

[16] Dehkharghani R., Saygın Y., Yanıkoğlu B., and Oflazer K., Language Resources and Evaluation, Springer-Netherlands, pp. 1-19, 2015.

[17] Demirtaş E., Cross-Lingual Sentiment Analysis with Machine Translation, Master’s Thesis, Eindhoven University of Technology, 2013.

[18] Ding X., Liu B., and Yu P., “A Holistic Lexicon-Based Approach to Opinion Mining,” in Proceedings of the International Conference on Web Search and Data Mining, Palo Alto, pp. 231-240, 2008.

[19] Duyu T., Bing Q., LanJun Z., KamFai W., YanYan Z., and Ting L., “Domain-Specific Sentiment Word Extraction by Seed Expansion and Pattern Generation,” Retrieved September 1, 852 The International Arab Journal of Information Technology, Vol. 16, No. 5, September 2019 2015 from http://arxiv.org/pdf/1309.6722v1.pdf, Last Visited, 2013.

[20] Esuli A. and Sebastiani F., “Determining the Semantic Orientation of Terms Through Gloss Classification,” in Proceedings of the 14th ACM International Conference on Information and Knowledge Management, Bremen, pp. 617-624, 2005.

[21] Esuli A. and Sebastiani F., “SENTIWORDNET: A Publicly Available Lexical Resource for Opinion Mining,” in Proceedings of the 5th International Conference on Language Resources and Evaluation, Genoa, pp. 417-422, 2006.

[22] Fellbaum C., WordNet: An Electronic Lexical Database, MA: MIT Press, 1998.

[23] Hu M. and Liu B., “Mining and Summarizing &XVWRPHU 5HYLHZV´in Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Seattle, pp. 168-177, 2004.

[24] Kaji N. and Kitsuregawa M., “Building Lexicon for Sentiment Analysis from Massive Collection of HTML Documents,” in Proceedings of the Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, Prague, pp. 1075- 1083, 2007.

[25] Kamps J., Marx M., Mokken R., and De Rijke M., “Using Wordnet to Measure Semantic Orientation of Adjectives,” in Proceedings of the 4th International Conference on Language Resources and Evaluation, Lisbon, pp. 1115- 1118, 2004.

[26] Kaur A. and Gupta V., “A Novel Approach for Sentiment Analysis of Punjabi Text using SVM,” The International Arab Journal of Information Technology, vol. 14, no. 5, pp. 707-712, 2014.

[27] Kim S. and Hovy E., “Determining the Sentiment RI 2SLQLRQV´in Proceedings of the 20th International Conference on Computational Linguistics, Geneva, pp. 1367-1373, 2004.

[28] Liu B., Sentiment Analysis and Opinion Mining, Morgan and Claypool Publishers, 2012.

[29] López-Ibáñez M. and Blum C., “Beam-ACO for the Travelling Salesman Problem with Time Windows,” Computers and Operations Research, vol. 37, no. 9, pp. 1570-1583, 2010.

[30] Lu B., Song Y., Zhang X., and Tsou B., “Learning Chinese Polarity Lexicons by Integration of Graph Models and Morphological Features,” in Proceedings 6th Asia Information Retrieval Societies Conference, Taipei, pp. 466- 477, 2010.

[31] Mahyoub F., Siddiqui M., and Dahab M., “Building an Arabic Sentiment Lexicon Using Semi-Supervised Learning,” Journal of King Saud University-Computer and Information Sciences, vol. 26, no. 4, pp. 417-424, 2014.

[32] Miller G., “WordNet: A Lexical Database for English,” Communications of the ACM, vol. 38, no. 11, pp. 39-41, 1995.

[33] Mousavi S., Bahri F., and Tabataba F., “An Enhanced Beam Search Algorithm for the Shortest Common Supersequence Problem,” Engineering Applications of Artificial Intelligence, vol. 25, no. 3, pp. 457-467, 2011.

[34] Nielsen F., “A new ANEW: Evaluation of a Word List for Sentiment Analysis in Microblogs,” in Proceedings of the ESWC2011 Workshop on 'Making Sense of Microposts': Big Things Come in Small Packages (MSM), Heraklion, pp. 93-98, 2011.

[35] Ow P. and Morton T., “Filtered Beam Search in 6FKHGXOLQJ´International Journal of Production Research, vol. 26, no. 1, pp. 35-62, 1988.

[36] Özsert C. and Özcan A., “Word Polarity Detection Using a Multilingual Approach,” in Proceedings of International Conference on Computational Linguistics and Intelligent Text Processing, Samos, pp. 75-82, 2013.

[37] Pang B., Lee L., and Vaithyanathan S., “Thumbs up Sentiment Classification using Machine Learning Techniques,” in Proceedings of the Conference on Empirical Methods in Natural Language Processing, Philadelphia, pp. 79-86, 2002.

[38] Rao D. and Ravichandran D., “Semi-Supervised Polarity Lexicon Induction,” in Proceedings of the 12th Conference of the European Chapter of the ACL, Athens, pp. 675-682, 2009.

[39] Riloff E. and Wiebe J., “Learning Extraction 3DWWHUQV IRU 6XEMHFWLYH (

[SUHVVLRQV´in Proceedings of the Conference on Empirical Methods in Natural Language Processing, Sapporo, pp. 105-112, 2003.

[40] Sabuncuoğlu I. and Bayiz M., “Job Shop Scheduling with Beam Search,” European Journal of Operational Research, vol. 118, no. 2, pp. 390-412, 1999.

[41] Stone P., Dunphy D., Smith M., and Ogilvie D., The General Inquirer: A computer Approach to Content Analysis, MA: MIT Press, 1966.

[42] Strapparava C. and Valitutti A., “WordNet- Affect: an Affective Extension of WordNet,” in Proceedings of the 4th International Conference on Language Resources and Evaluation, Lisbon, pp. 1083-1086, 2004.

[43] Taboada M., Brooke J., Tofiloski M., Voll K., and Stede M., “Lexicon-Based Methods for Sentiment Analysis,” Computational Linguistics vol. 37, no. 2, pp. 267-307, 2011.

[44] Tan S. and Wu Q., “A Random Walk Algorithm for Automatic Construction of Domain-Oriented Sentiment Lexicon,” Expert Systems with A New Approach for A Domain-Independent Turkish Sentiment Seed Lexicon Compilation 853 Applications, vol. 38, no. 10, pp. 12094-12100, 2011.

[45] Tang J., Guan J., Yu Y., and Chen J., “Beam Search Combined With MAX-MIN Ant Systems and Benchmarking Data Tests for Weighted Vehicle Routing Problem,” IEEE Transactions on Automation Science and Engineering, vol. 11, no. 4, pp. 1097-1109, 2014.

[46] Vadlamudi S., Aine S., and Chakrabarti P., “Incremental Beam Search,” Information Processing Letters, vol. 113, no. 22-24, pp. 888- 893, 2013.

[47] Vossen P., Maks I., Segers R., and Van Der Vliet H., “Integrating Lexical Units, Synsets, and Ontology in the Cornetto Database,” in Proceedings of the 6th International Conference on Language Resources and Evaluation, Marrakech, pp. 1006-1013, 2008.

[48] Vural A., Cambazoglu B., Senkul P., and Tokgoz Z., A Framework for Sentiment Analysis in Turkish: Application to Polarity Detection of Movie Reviews in Turkish, in Computer and Information Sciences, Springer London, pp. 437- 445, 2013.

[49] Xu G., Meng X., and Wang H., “Build Chinese Emotion Lexicons Using A Graph-based Algorithm and Multiple Resources,” in Proceedings of the 23rd International Conference on Computational Linguistics, Beijing, pp. 1209- 1217, 2010.

[50] Yavuz M., “Iterated Beam Search for the Combined Car Sequencing and Level Scheduling Problem,” International Journal of Production Research, vol. 51, no. 12, pp. 3698-3718, 2013. Ekin Ekinci has received her BEng. in Computer Engineering from Çanakkale Onsekiz Mart University in 2009 and ME. in Computer Engineering from Gebze Teknik University in 2012. She is currently working towards Ph.D. degree in Computer Engineering from Kocaeli University, Turkey. Also, she is currently a Research Assistant of Computer Engineering Department at Kocaeli University in Turkey. Her main research interests include text mining, sentiment analysis, natural language processing and machine learning. Sevinç Omurca was born in Burdur in Turkey at 23th December 1979. She is an associate professor at the Kocaeli University Computer Engineering Department in Turkey. She has a Ph.D. at the Kocaeli University Electronics and Communications Engineering. Her main research interests include text mining, sentiment analysis, natural language processing, machine learning and data mining.