軟件開(kāi)發(fā)問(wèn)答網(wǎng)站代碼片段自動(dòng)分類方法研究

　　摘 要 諸如 Stack Overflow 這種軟件開(kāi)發(fā)問(wèn)答網(wǎng)站已成為開(kāi)發(fā)者在編程中尋找問(wèn)題解決方案的主要手段，它們通過(guò)眾包的方式為開(kāi)發(fā)者提供解決方案和代碼片段作為參考。自動(dòng)識(shí)別代碼片段的用途將為軟件開(kāi)發(fā)問(wèn)答網(wǎng)站的知識(shí)抽取提供支持。通過(guò)對(duì) Stack Overflow 上的問(wèn)題及代碼片段進(jìn)行研究，總結(jié)出 4 種問(wèn)題類型和 8 種代碼片段類型。在此基礎(chǔ)上，實(shí)現(xiàn)基于樸素貝葉斯的自動(dòng)分類方法。實(shí)驗(yàn)表明，8 個(gè)類型代碼片段的分類準(zhǔn)確率都在 50% 以上，整體準(zhǔn)確率達(dá)到 70% 以上。

　　謝文凱; 彭鑫; 趙文耘， 計(jì)算機(jī)應(yīng)用與軟件 發(fā)表時(shí)間：2021-08-12

　　關(guān)鍵詞 軟件開(kāi)發(fā)問(wèn)答網(wǎng)站 代碼片段 經(jīng)驗(yàn)研究 分類 機(jī)器學(xué)習(xí)

　　0 引 言

　　近些年來(lái)，互聯(lián)網(wǎng)技術(shù)的發(fā)展日新月異。新技術(shù)層出不窮，同時(shí)一些舊的技術(shù)也在加快迭代的速度，煥發(fā)出新的活力，這導(dǎo)致了軟件開(kāi)發(fā)所涉及的技術(shù)體系也越來(lái)越繁瑣、越來(lái)越復(fù)雜。但由于人的精力有限，軟件開(kāi)發(fā)人員也不會(huì)掌握全部的知識(shí)，他們?cè)陂_(kāi)發(fā)過(guò)程中也經(jīng)常會(huì)遇到一些自己難以解決的問(wèn)題。于是，一些能夠?qū)ｉT為開(kāi)發(fā)人員提供交流平臺(tái)的編程類問(wèn)答網(wǎng)站也逐漸變得火熱起來(lái)。用戶能夠針對(duì)自己遇到的問(wèn)題尋求幫助，也能夠針對(duì)別人的問(wèn)題提供自己的見(jiàn)解和解決方案。Stack Overflow 是目前所有的編程類問(wèn)答網(wǎng)站中最活躍、使用最廣泛的其中之一。

　　與以往的用戶能夠自由交流討論、暢所欲言的論壇不同，Stack Overflow 的目標(biāo)是希望成為編程類問(wèn)答的一個(gè)超級(jí)數(shù)據(jù)庫(kù)。在網(wǎng)站建立之初，它就要求用戶在提問(wèn)時(shí)要堅(jiān)持“practical，answerable questions basedon actual problems that you face”的原則，所以網(wǎng)站上的每個(gè)問(wèn)題都不止是為了僅僅幫助提問(wèn)者本人，更重要的是希望將來(lái)當(dāng)別人遇到同樣的問(wèn)題時(shí)，同樣能夠提供幫助。

　　而在 Stack Overflow 的所有問(wèn)答帖中，存在著大量的代碼片段，它們可能是存在問(wèn)題的代碼，也可能是針對(duì)遇到問(wèn)題所提出的解決問(wèn)題的代碼，當(dāng)然也可能僅僅只是一個(gè)可能會(huì)用到的 API 等。如果能將這些代碼片段進(jìn)行合理、準(zhǔn)確的分類，一方面，能夠使得展示在網(wǎng)站上的代碼片段更加直觀、易于理解，能夠幫助開(kāi)發(fā)人員更加容易地分辨清楚哪些是自己需要的作為解決方案的代碼片段，哪些是出現(xiàn)問(wèn)題、需要進(jìn)行修改或者優(yōu)化的代碼片段; 另一方面，如果能夠自動(dòng)化地將問(wèn)答帖中的代碼片段進(jìn)行分類，那么分類后的代碼片段將更能夠幫助構(gòu)建起一個(gè)更加完整、更加結(jié)構(gòu)化的針對(duì) answerable questions 的知識(shí)庫(kù)。

　　1 相關(guān)工作

　　1. 1 Stack Overflow 研究

　　Stack Overflow 是隸屬于 Stack Exchange 旗下的編程類問(wèn)答網(wǎng)站，自 2009 年創(chuàng)建以來(lái)，每隔 2 ～ 3 個(gè)月 Stack Exchange 都會(huì)將進(jìn)行處理后的網(wǎng)站數(shù)據(jù)公開(kāi)發(fā)布，需要的用戶可以直接去官網(wǎng)下載相應(yīng)的 dmp 文件。得益于此，現(xiàn)在每年都會(huì)有大量基于 Stack Overflow 所做的研究。然而，大部分關(guān)于 Stack Overflow 的文獻(xiàn)主要的關(guān)注點(diǎn)還是集中于 Stack Overflow 本身或是網(wǎng)站所提供的數(shù)據(jù)進(jìn)行的[1 - 4]，例如對(duì)網(wǎng)站數(shù)據(jù)文本的挖掘、問(wèn)題和內(nèi)容的分析等。

　　Arora 等[2]基于 Stack Overflow 提供的數(shù)據(jù)，采用了一種將問(wèn)題向量轉(zhuǎn)換為特征空間中的不同向量的方法，不同于以往單獨(dú)地從問(wèn)題中學(xué)習(xí)分類邊界，對(duì)離散項(xiàng)空間、從文獻(xiàn)載體嵌入了實(shí)數(shù)的連續(xù)向量空間進(jìn)行探索，實(shí)現(xiàn)了一種能夠?qū)⑿掳l(fā)布的問(wèn)題進(jìn)行分類的方法，將分類的準(zhǔn)確率提高了 8% 。Joorabchi 等[3]采用了一種啟發(fā)式研究方法，結(jié)合文本挖掘的方法來(lái)研究 Stack Overflow 網(wǎng)站上問(wèn)答帖的主題和類別，對(duì)近 18 600 個(gè)問(wèn)答帖進(jìn)行了分析，使用維基百科對(duì)人群進(jìn)行分類，建立它們之間的語(yǔ)義關(guān)系，并通過(guò) Gephi 等可視化軟件將數(shù)據(jù)轉(zhuǎn)化為圖像呈現(xiàn)出來(lái)，確定發(fā)布回答是否確切主題，并縮小其類別，以幫助確定學(xué)習(xí)者的學(xué)習(xí)難題。Ye 等[4]利用 Stack Overflow 所提供的數(shù)據(jù)，在現(xiàn)有的命名實(shí)體識(shí)別技術(shù)的基礎(chǔ)上，提出了一種應(yīng)用于軟件工程領(lǐng)域的基于機(jī)器學(xué)習(xí)的命名實(shí)體識(shí)別技術(shù)，可以識(shí)別廣泛的流行編程語(yǔ)言、平臺(tái)、API 等軟件實(shí)體。

　　而對(duì)于問(wèn)答帖中的大量存在的代碼片段等，幾乎沒(méi)有專門針對(duì)此內(nèi)容的研究，從這一方面著手開(kāi)展研究存在著很大的潛力。

　　1. 2 機(jī)器學(xué)習(xí)

　　機(jī)器學(xué)習(xí)主要致力于研究如何通過(guò)計(jì)算的手段，利用經(jīng)驗(yàn)來(lái)改善系統(tǒng)自身的性能。在計(jì)算機(jī)系統(tǒng)中， “經(jīng)驗(yàn)”通常以“數(shù)據(jù)”的形式存在，因此，機(jī)器學(xué)習(xí)所研究的主要內(nèi)容是關(guān)于在計(jì)算機(jī)上從數(shù)據(jù)中產(chǎn)生“模型”的算法，即“學(xué)習(xí)算法”。學(xué)習(xí)算法能夠基于提供的經(jīng)驗(yàn)數(shù)據(jù)產(chǎn)生模型; 在面對(duì)新情況時(shí)，模型會(huì)提供相應(yīng)的判斷。如果說(shuō)計(jì)算機(jī)科學(xué)是研究關(guān)于“算法”的學(xué)問(wèn)，那么類似地，可以說(shuō)機(jī)器學(xué)習(xí)是研究關(guān)于“學(xué)習(xí)算法”的學(xué)問(wèn)[5]。

　　現(xiàn)如今，機(jī)器學(xué)習(xí)已經(jīng)發(fā)展成為一個(gè)相當(dāng)大的學(xué)科領(lǐng)域。從學(xué)習(xí)方式的角度來(lái)分，機(jī)器學(xué)習(xí)可以分為無(wú)監(jiān)督學(xué)習(xí)、有監(jiān)督學(xué)習(xí)和半監(jiān)督學(xué)習(xí)。有監(jiān)督學(xué)習(xí)的常見(jiàn)場(chǎng)景如分類問(wèn)題和回歸問(wèn)題，無(wú)監(jiān)督學(xué)習(xí)的常見(jiàn)場(chǎng)景包括關(guān)聯(lián)規(guī)則的學(xué)習(xí)和聚類等，半監(jiān)督學(xué)習(xí)的常見(jiàn)算法包括圖論推理算法等[6]。而從算法的角度來(lái)分，則可以分為基于樹(shù)的算法、基于神經(jīng)網(wǎng)絡(luò)的算法、貝葉斯方法等。其中，貝葉斯方法的主要原理就是貝葉斯公式，這一類方法主要應(yīng)用于分類問(wèn)題。而樸素貝葉斯方法是一種基于條件獨(dú)立假設(shè)的貝葉斯方法，與其他的方法相比，其收斂速度更快，模型也更加簡(jiǎn)單，也有很多的學(xué)者運(yùn)用樸素貝葉斯方法做了大量的研究。

　　Catal 等[7]為 Java 程序開(kāi)發(fā)了一款能夠基于 Eclipse 的軟件故障檢測(cè)工具，并運(yùn)用了樸素貝葉斯方法，將軟件度量與軟件數(shù)據(jù)故障相結(jié)合，來(lái)簡(jiǎn)化故預(yù)測(cè)過(guò)程。 Zhang 等[8]針對(duì)云計(jì)算環(huán)境中調(diào)度算法的重復(fù)性和分配的不均衡，提出了一種基于樸素貝葉斯算法的負(fù)載均衡技術(shù)，該技術(shù)利用心跳機(jī)制全面收集每個(gè)節(jié)點(diǎn)的負(fù)載信息，從而基于樸素貝葉斯算法對(duì)所有節(jié)點(diǎn)的負(fù)載狀態(tài)進(jìn)行分類，根據(jù)分類對(duì)每個(gè)節(jié)點(diǎn)的任務(wù)和資源進(jìn)行合理調(diào)度。

　　2 經(jīng)驗(yàn)研究

　　2. 1 問(wèn)題類型

　　若想能夠?qū)?Stack Overflow 上的代碼片段進(jìn)行比較全面、完整的分類，首先就需要先了解開(kāi)發(fā)者經(jīng)常會(huì)提問(wèn)的問(wèn)題的類型。在研究開(kāi)始之前，首先對(duì) Stack Overflow 上包含 Java 標(biāo)簽的問(wèn)答帖進(jìn)行了大量的分析和研究。經(jīng)過(guò)大量的分析后，本文將 Stack Overflow 上包含代碼片段的問(wèn)題主要?dú)w納為以下幾個(gè)類型，并總結(jié)了這些問(wèn)題類型的特點(diǎn)。

　　1) 第一類問(wèn)題是 debug 類型的問(wèn)題，這一類問(wèn)題主要是開(kāi)發(fā)者在實(shí)際開(kāi)發(fā)的過(guò)程中實(shí)際得到結(jié)果與預(yù)期不相符并且自己又難以解決時(shí)提出的。在提問(wèn)時(shí)，開(kāi)發(fā)者一般首先會(huì)對(duì)自己所做的工作及遇到的問(wèn)題進(jìn)行簡(jiǎn)單的描述，大部分情況下也會(huì)貼出存在問(wèn)題的代碼片段或者出現(xiàn)問(wèn)題時(shí)的報(bào)錯(cuò)棧等，這一類問(wèn)題通常會(huì)包括“error”“exception”等單詞，在網(wǎng)站上比較常見(jiàn)。例如，在問(wèn)題“Getting Invalid Address with javax. mail when the addresses are fine”中，開(kāi)發(fā)者在利用 javax. mail 開(kāi)發(fā)郵件系統(tǒng)時(shí)使用合法的郵件地址卻拋出了 “Invalid Address”的異常，于是貼出自己的問(wèn)題代碼求助，得到了其他開(kāi)發(fā)者合理的解答。

　　2) 第二類問(wèn)題屬于改進(jìn)類型的問(wèn)題，這一類問(wèn)題主要是因?yàn)殚_(kāi)發(fā)者對(duì)當(dāng)前程序性能不太滿意，例如耗時(shí)較長(zhǎng)等，希望在原有的版本基礎(chǔ)上尋求更加優(yōu)化的方案而提出的。在提問(wèn)時(shí)通常會(huì)包括“need a better method”“not efficient”等語(yǔ)句。例如，在問(wèn)題“Get Last Friday of Month in Java”中，開(kāi)發(fā)者在沒(méi)有利用現(xiàn)有 API 的情況下實(shí)現(xiàn)了一個(gè)能夠得到每月的最后一個(gè)星期五的程序，但是效率不夠高而且代碼比較繁瑣，可重用性較差，希望能夠得到一個(gè)效率更高的代碼，其屬于改進(jìn)類型的問(wèn)題。

　　3) 第三類問(wèn)題是具體實(shí)現(xiàn)的問(wèn)題，這一類問(wèn)題主要是因?yàn)殚_(kāi)發(fā)者相對(duì)缺乏當(dāng)前開(kāi)發(fā)程序所需的知識(shí)，在開(kāi)發(fā)過(guò)程中遇到了困難而提出的。通常，在這類問(wèn)題中會(huì)包括“how can I”等詞語(yǔ)。例如，在問(wèn)題“How do I restrict JFileChooser to a directory?”中，開(kāi)發(fā)者希望對(duì)用戶的瀏覽目錄進(jìn)行限制，而“Parent Directory”可以瀏覽任意目錄，開(kāi)發(fā)者希望能夠?qū)で蟊容^完整的具體實(shí)現(xiàn)的代碼片段。

　　4) 第四類問(wèn)題與第三類問(wèn)題相對(duì)，屬于抽象類型的問(wèn)題。在這類問(wèn)題中，開(kāi)發(fā)者不再是針對(duì)具體的實(shí)現(xiàn)問(wèn)題尋求解決方案，而是上升到了比較抽象的層面，一般在回答中的代碼片段只是用來(lái)舉例，使抽象的問(wèn)題更加具體化，通常，會(huì)包括“what”等詞語(yǔ)。例如在問(wèn)題“What is the difference between an int and an Integer in Java and C#?”中，回答中包含的代碼片段如“Integer i = new Integer( 6) ; ”“int i = 6; ”只是為了說(shuō)明 Integer 和 int 的區(qū)別，而并不是針對(duì)問(wèn)題提出的解決方案。

　　2. 2 種類劃分

　　在 Stack Overflow 網(wǎng)站上的所有問(wèn)答帖中，代碼片段一般由兩種存在形式: 一種是一段完整的代碼片段，與其他的文本描述分隔開(kāi)來(lái)，被包裹在 < pre > < code > < /code > < /pre > 標(biāo)簽中; 另一種主要存在于問(wèn)題和答案的文本之間，一般只是用來(lái)表示變量、數(shù)據(jù)類型等，被包裹在 < code >  < /code > 標(biāo)簽中。按照標(biāo)簽的不同，可以將代碼片段分為“大代碼片段”和“小代碼片段”兩種類型。

　　根據(jù) 2. 1 節(jié)中對(duì) Stack Overflow 問(wèn)答帖的研究，本文將“大代碼片段”劃分為了如下六個(gè)類型:

　　1) 開(kāi)發(fā)者在開(kāi)發(fā)過(guò)程中出現(xiàn)問(wèn)題或 bug 的完整代碼，這類代碼主要存在于問(wèn)答帖的問(wèn)題中。

　　2) 開(kāi)發(fā)者在開(kāi)發(fā)過(guò)程中的完整代碼，沒(méi)有明顯的 bug 和 error，但是可以進(jìn)行優(yōu)化的代碼，這類代碼主要存在于問(wèn)答帖的問(wèn)題中。

　　3) 沒(méi)有 bug 或 error，用來(lái)作為舉例說(shuō)明的代碼，這類代碼即為 2. 1 節(jié)中第四類問(wèn)題使用的代碼，在問(wèn)答帖的問(wèn)題和回答中都會(huì)存在。

　　4) Stack Overflow 用戶針對(duì)開(kāi)發(fā)者所遇到的問(wèn)題、 bug 或針對(duì)可優(yōu)化的代碼提出的解決方案，這類代碼主要存在于問(wèn)答帖的回答中，在網(wǎng)站中最為常見(jiàn)。

　　5) 開(kāi)發(fā)者在問(wèn)題或回答中對(duì)內(nèi)容進(jìn)行補(bǔ)充說(shuō)明時(shí)所用到的輸入輸出，這類雖然不是真正的代碼，但是也由“大代碼片段”標(biāo)簽包裹，在問(wèn)答帖的問(wèn)題和回答中都會(huì)存在。

　　6) 開(kāi)發(fā)者對(duì)表述內(nèi)容進(jìn)行補(bǔ)充說(shuō)明時(shí)所用到的程序出現(xiàn)問(wèn)題時(shí)拋出的異常信息、報(bào)錯(cuò)棧等，主要存在于問(wèn)答帖的問(wèn)題中。

　　“小代碼片段”主要存在于問(wèn)答帖的文本描述中，用于表示開(kāi)發(fā)者在問(wèn)題或答案中可能會(huì)涉及到的 API、變量等。與“大代碼片段”相比，這些“小代碼片段”價(jià) 值 相 對(duì) 較 低。“小 代 碼 片 段”分 為 如 下 兩 個(gè)類型:

　　1) 開(kāi)發(fā)者在編寫問(wèn)題或答案時(shí)可能會(huì)用到的代碼中的類名、API 等信息，在問(wèn)題和回答中都會(huì)存在。

　　2) 對(duì)于“小代碼片段”，除去上述第一類，其余全部都?xì)w于此類中，常見(jiàn)的如變量名、數(shù)據(jù)及一些軟件工程相關(guān)的通用知識(shí)等，同樣在問(wèn)題和回答中都會(huì)存在。

　　3 自動(dòng)分類

　　3. 1 數(shù)據(jù)篩選

　　代碼片段的上下文非常重要，那么選取合適的文本作為上下文就極為關(guān)鍵。文本太短可能會(huì)導(dǎo)致相同類型的不同代碼片段上下文之間沒(méi)有太多的相似性;過(guò)長(zhǎng)又可能會(huì)帶來(lái)更多的噪聲，造成相同類型的不同代碼片段上下文之間的無(wú)關(guān)聯(lián)系增加，干擾判斷。

　　為最大限度地選取合適的上下文內(nèi)容，保證上下文內(nèi)容的質(zhì)量，本文針對(duì)“大代碼片段”和“小代碼片段”采取了兩種不同的策略。

　　“小代碼片段”策略比較簡(jiǎn)單，因?yàn)槠浯嬖谟诔啥蔚奈谋局校煌温渲g影響較小，因此其上下文內(nèi)容均為其所在段落的文本。

　　而對(duì)于“大代碼片段”而言，經(jīng)過(guò)分析發(fā)現(xiàn)可以以 “小代碼片段”所在的段落作為邊界，因?yàn)樵?ldquo;大代碼片段”附近出現(xiàn)的“小代碼片段”，很大程度上是為了解釋“大代碼片段”中的一些信息。因此可以采取如下策略: ( 1) 從“大代碼片段”的位置向上( 下) 查找直到某段文本中出現(xiàn)“小代碼片段”為止( 包含此段文本) ; ( 2) 如果沒(méi)有“小代碼片段”，則與相鄰“大代碼片段”之間的文本作為相應(yīng)的上文或下文; ( 3) 如果以上情況( 1) 、( 2) 均不存在，則該代碼片段上( 下) 面的所有文本作為相應(yīng)的上( 下) 文。

　　3. 2 數(shù)據(jù)預(yù)處理

　　Stack Exchange 在發(fā)布數(shù)據(jù)文件時(shí)，只是將從 HTML 中提取出的數(shù)據(jù)放入到數(shù)據(jù)庫(kù)中，并沒(méi)有對(duì)其做相應(yīng)的去標(biāo)簽化處理。同時(shí)，因?yàn)殚_(kāi)發(fā)者在 Stack Overflow 網(wǎng)站的問(wèn)答帖中編輯問(wèn)題或答案時(shí)，在描述時(shí)有時(shí)會(huì)用到一些符號(hào)，簡(jiǎn)單的分詞和分句會(huì)造成分詞不正確，例如“exception) ”“question，”，會(huì)導(dǎo)致程序在處理數(shù)據(jù)時(shí)出現(xiàn)誤差; 此外，單詞在不同場(chǎng)景下，會(huì)有不同表示形式，例如“question”和“questions”是同一個(gè)單詞的單復(fù)數(shù)形式，“better”是“good”的比較級(jí); 不同的代碼片段之間的上下文之間可能會(huì)出現(xiàn)重復(fù)現(xiàn)象，如果同一段文本的重復(fù)次數(shù)過(guò)多，在進(jìn)行特征詞提取時(shí)，會(huì)導(dǎo)致重復(fù)文本出現(xiàn)次數(shù)異常增多，在最后的特征詞集中也會(huì)出現(xiàn)過(guò)多的噪聲，對(duì)最后的預(yù)測(cè)準(zhǔn)確性造成很大的影響。

　　基于以上四種情況，本文對(duì)數(shù)據(jù)進(jìn)行了以下四個(gè)方面的預(yù)處理。

　　1) 去標(biāo)簽化。對(duì)于數(shù)據(jù)中存在的 HTML 標(biāo)簽，因?yàn)槠浔容^固定，均是包裹在“< … > ”中，而數(shù)據(jù)中原本存 在 的“ < ”和“ > ”，則是由轉(zhuǎn)義字符“< ”和 “> ”表示。因此，將數(shù)據(jù)中原本由“< … > ”包裹的所有標(biāo)簽替換掉，而對(duì)原本在數(shù)據(jù)中表示“<”“> ”等的轉(zhuǎn)義字符，按照對(duì)照表修改為對(duì)應(yīng)的字符即可。

　　2) 去字符化。與中文不同，在英文中可能為了縮寫某些單詞會(huì)在單詞中間添加標(biāo)點(diǎn)符號(hào)等作為標(biāo)志，同時(shí)在某些字段中間的一些字符也需要進(jìn)行保留，例如“C: \Users”等，這就導(dǎo)致不能以偏概全的將單詞中所有出現(xiàn)的字符、標(biāo)點(diǎn)等全部去除掉。在這樣的前提下，本文通過(guò)數(shù)據(jù)分析，歸納出了單詞中的無(wú)用字符出現(xiàn)的一些特點(diǎn):

　　( 1) 在單詞開(kāi)頭或結(jié)尾地方出現(xiàn)的字符一般為無(wú)用字符，例如“( exception”、“example，”等;

　　( 2) 一些特殊的字符，如“/”“<”“> ”和不在單詞結(jié)尾的“. ”等，有特殊的含義，不可去掉。

　　結(jié)合單詞的這些特點(diǎn)，本文采用正則表達(dá)式對(duì)單詞進(jìn)行匹配，對(duì)于不符合條件的單詞去除相應(yīng)的字符來(lái)實(shí)現(xiàn)單詞的去符號(hào)化。

　　3) 詞干化。本文利用 Java 庫(kù) TT4J( TreeTagger for Java) 進(jìn)行詞干化，這個(gè)庫(kù)的主要功能是識(shí)別語(yǔ)句中每個(gè)單詞在語(yǔ)句中的詞性，并能夠根據(jù)單詞的詞性得到單詞的詞干。不僅如此，在不同的環(huán)境下相同的單詞可能因?yàn)檎Z(yǔ)境的不同可以得到不同的結(jié)果，例 如， “better”在不同的語(yǔ)境下可能會(huì)被轉(zhuǎn)化為“good”或 “well”。

　　4) 去重。兩段代碼片段的上下文之間出現(xiàn)重復(fù)現(xiàn)象，如果這兩段代碼片段的類型一樣，那么就直接把重復(fù)的上下文去除掉，不考慮重復(fù)文本; 如果這兩段代碼片段的類型不同，那么就按照正常的邏輯將重復(fù)文本劃為不同類型，對(duì)于每段代碼片段都采用這樣的方式檢查。

　　3. 3 樸素貝葉斯算法

　　樸素貝葉斯法是指基于條件獨(dú)立假設(shè)和貝葉斯定理的分類方法[9 - 10]。設(shè) x = { a1，a2，…，am } 為一個(gè)待分類項(xiàng)，而 x 中的每個(gè)元素 ai為 x 的特征屬性，設(shè) C = { y1，y2，…，yn } 為類別集合，C 中每個(gè)元素 yi為每個(gè)可能的類別。分別計(jì)算 P( y1 x) 、P( y2 x) 、…、P( yn x) ，如果 P( yk x) = max( P( y1 x) ，P( y1 x) ，…，P( y1 x) ) ，則 x∈yk。

　　若想得到 x 屬于 C 中的哪個(gè)類別，關(guān)鍵就是得到各個(gè)條件概率，根據(jù)貝葉斯定理:

　　( 1) 確定已知分類的數(shù)據(jù)集合作為訓(xùn)練樣本 N;

　　2) 對(duì)于每個(gè)特征屬性在各個(gè)類別下的條件概率: P( a1 y1 ) ，P( a2 y1 ) ，…，P( am y1 ) ; …; P( a1 yn ) ， P( a2 yn ) ，…，P( am yn ) 。

　　可以通過(guò)極大似然估計(jì)來(lái)求得，公式如下: P( am yn ) = N( am yn) Nyn ( 1)

　　( 3) 根據(jù)條件獨(dú)立假設(shè)及貝葉斯定理，可得: P( yi x) = P( x yi ) P( yi ) P( X) ( 2)

　　( 4) 因?yàn)榉帜钢械?P( X) 對(duì)于所有類別來(lái)說(shuō)都是常數(shù)，因此只需保證分子最大化即可。又因?yàn)楦鱾€(gè)特征屬性是條件獨(dú)立的，故 P( x yi ) P( yi ) = P( a1 yi ) P( a2 yi ) … P( am yi ) P( yi ) = P( yi ) ∏ m j = 1 P( aj yi ) 。在實(shí)際的編碼中，大量的乘法計(jì)算會(huì)導(dǎo)致計(jì)算的時(shí)間開(kāi)銷比較大。因此，本文采取通過(guò)比較 x 在不同類型 yi情況下互信息量的大小來(lái)對(duì)應(yīng) x 在不同類型 yi 情況下的概率的大小。

　　3. 4 互信息

　　互信息主要用于度量?jī)蓚€(gè)事件集合之間的相關(guān)性，可以看成是一個(gè)隨機(jī)變量由于已知另一個(gè)隨機(jī)變量而減少的不肯定性[11]。

　　設(shè)兩個(gè)隨機(jī)變量( X，Y) 的聯(lián)合分布為 P( X，Y) ，邊際分布分別為 P( X) 、P( Y) ，互信息 I( X; Y) 是聯(lián)合分布 P( X，Y) 與乘積分布 P( X) P( Y) 的相對(duì)熵，即: I( X; Y) = ∫X ∫Y P( X，Y) log P( X，Y) P( X) P( Y) ( 3) 對(duì)于本文來(lái)講，設(shè)變量 X 表示數(shù)據(jù)集中的不同文本，變量 Y 表示可選擇類型，互信息 I( X; Y) 就可以表示不同的文本與可選擇類型的聯(lián)系程度，互信息越大，那么該文本與該類型之間的聯(lián)系越緊密，該文本屬于該類型的概率也就越大。

　　3. 5 算法流程

　　本文主要運(yùn)用了機(jī)器學(xué)習(xí)中的樸素貝葉斯算法，根據(jù)通過(guò)分析、總結(jié)出的 Stack Overflow 中的八種常見(jiàn)的代碼片段的類型，實(shí)現(xiàn)了對(duì)提取出的代碼片段的種類進(jìn)行預(yù)測(cè)的算法。算法流程如算法 1 所示。

　　算法 1 樸素貝葉斯分類器 1. function classification( ) { 2. InitialCode = readData( ) 3. CodeSnippets = preprocess( InitialCode) 4. TrainSet = part of CodeSnippets 5. TestSet = part of CodeSnippets 6. FeatureWords = extractFeatureWords( TrainSet) 7. BayesModel = trainModel( FeatureWords) 8. Result = predict( FeatureWords，BayesModel，TestSet) 9. return Result 10. }

　　首先，從數(shù)據(jù)庫(kù)中讀取出未經(jīng)處理過(guò)的原始數(shù)據(jù)集，經(jīng)過(guò)數(shù)據(jù)預(yù)處理后，得到可以用于樸素貝葉斯算法的數(shù)據(jù)集，并將該數(shù)據(jù)集隨機(jī)劃分為訓(xùn)練集和測(cè)試集，其中訓(xùn)練集與測(cè)試集的比例為 9 ∶ 1。

　　對(duì)訓(xùn)練集中的數(shù)據(jù)，進(jìn)行提取特征詞操作，計(jì)算訓(xùn)練集中的每條數(shù)據(jù)中所有單詞對(duì)于不同類型的互信息，對(duì)于每種類型提取出 50 個(gè)互信息較大的單詞，合并后作為特征詞集。

　　接著，對(duì)訓(xùn)練集的數(shù)據(jù)進(jìn)行訓(xùn)練，計(jì)算特征詞集中的每個(gè)單詞在不同類型下出現(xiàn)的概率，作為訓(xùn)練好的貝葉斯模型。

　　最后，對(duì)測(cè)試集中的數(shù)據(jù)進(jìn)行種類預(yù)測(cè)，計(jì)算測(cè)試集中的每條數(shù)據(jù)在不同類型中的概率，得到該數(shù)據(jù)最可能的類型。

　　4 實(shí) 驗(yàn)

　　本實(shí)驗(yàn)為探究不同類型數(shù)據(jù)對(duì)準(zhǔn)確率的影響程度，即探究算法能夠比較高效的預(yù)測(cè)哪些類型的數(shù)據(jù)、對(duì)哪些類型的數(shù)據(jù)預(yù)測(cè)能力較差，主要測(cè)試了算法對(duì)測(cè)試集中不同類型的數(shù)據(jù)進(jìn)行預(yù)測(cè)所得到的準(zhǔn)確率和召回率，并通過(guò)對(duì)所得結(jié)果進(jìn)行分析，總結(jié)出產(chǎn)生這些差異的原因。

　　4. 1 實(shí)驗(yàn)設(shè)置

　　本文所使用的數(shù)據(jù)主要來(lái)自 2019 年 3 月發(fā)布的公共數(shù)據(jù)集，主要選取了包含 Java 標(biāo)簽的 31 153 條數(shù)據(jù)作為原始數(shù)據(jù)集，其中，4 998 條數(shù)據(jù)屬于問(wèn)答帖中的問(wèn)題，而剩余 26 155 條數(shù)據(jù)屬于問(wèn)答帖中的回答部分。隨機(jī)對(duì) 8 000 條數(shù)據(jù)進(jìn)行了人工標(biāo)注，得到每種代碼片段類型的數(shù)據(jù)量如表 1 所示。

　　實(shí)驗(yàn)一共選取了 800 個(gè)不同的代碼片段作為總數(shù)據(jù)集，其中每個(gè)類別各包含 100 個(gè)代碼片段。一共進(jìn)行兩次實(shí)驗(yàn)，每次分別取各種類型數(shù)據(jù)的一半一共 400 個(gè)代碼片段進(jìn)行實(shí)驗(yàn)，最后取兩次實(shí)驗(yàn)的平均值作為最后的結(jié)果。

　　實(shí)驗(yàn)環(huán)境是在 macOS 操作系統(tǒng)的 PyCharm 編譯器，運(yùn)行服務(wù)器配置為 2. 3 GHz 四核 Intel Core i5 和 16 GB 內(nèi)存，實(shí)驗(yàn)的評(píng)價(jià)標(biāo)準(zhǔn)是準(zhǔn)確率 P 和召回率 R。

　　4. 2 實(shí)驗(yàn)結(jié)果

　　利用本文的自動(dòng)分類方法進(jìn)行實(shí)驗(yàn)，得到八種代碼片段對(duì)應(yīng)的準(zhǔn)確 率 和 召 回 率 分 別 如 圖 1 和 圖 2 所示。

　　可以看出，大代碼片段中第一種和第六種代碼片段及兩種小代碼片段類型對(duì)應(yīng)的準(zhǔn)確率較高，均達(dá)到了 70% 以上; 第二和第三種類型的代碼片段準(zhǔn)確率較低，在 50% ～ 60% 之間，第四種和第五種類型代碼片段準(zhǔn)確率在 60% ～ 70% 之間。大代碼片段中前五種類型的召回率比較低，均在 50% ～ 75% 之間，第六種類型數(shù)據(jù)的召回率較高; 小代碼片段中第七種類型數(shù)據(jù)的召回率超過(guò)了 90% ，而第八種類型的召回率在 70% ～ 80% 之間。

　　4. 3 結(jié)果分析

　　對(duì)于預(yù)測(cè)準(zhǔn)確率較高的大代碼片段中的第一種和第六種類型，這兩種類型的代碼片段上下文更容易提取特征詞，例如，在第一類代碼的上下文描述中，一般都會(huì)用“I have a /an question /exception”等語(yǔ)句來(lái)引出存在問(wèn)題的代碼片段，question、exception 等單詞出現(xiàn)的評(píng)率較高。兩種小代碼片段類型因?yàn)樯舷挛膬H選取了所在的段落，遇到的噪聲較小，特征更加明顯，準(zhǔn)確率也更高。

　　而準(zhǔn)確率較差的這幾種代碼片段類型，通過(guò)對(duì)它們的代碼片段上下文及所提取的特征詞集的分析，發(fā)現(xiàn)它們之間的差異并不明顯，一方面是因?yàn)橛?xùn)練集中這幾種類型的數(shù)據(jù)較少，特征詞的頻率較低，另外一方面是因?yàn)槔锰卣髟~進(jìn)行預(yù)測(cè)還不能獲取到所有的信息，還需要進(jìn)一步結(jié)合上下文描述中語(yǔ)義層次的信息，采用一些諸如 word embedding 的技術(shù)來(lái)提升實(shí)驗(yàn)效果。

　　5 結(jié) 語(yǔ)

　　本文基于機(jī)器學(xué)習(xí)算法，利用 Stack Overflow 網(wǎng)站中大量存在的代碼片段，對(duì)代碼片段的用途分類進(jìn)行研究。通過(guò)對(duì) Stack Overflow 網(wǎng)站上的問(wèn)答帖的大量分析，歸納出了八種比較常見(jiàn)的代碼片段的類別，并利用機(jī)器學(xué)習(xí)中的樸素貝葉斯方法實(shí)現(xiàn)了這種分類方法。實(shí)驗(yàn)結(jié)果表明，預(yù)測(cè)的準(zhǔn)確率能夠達(dá)到 70% 以上，在一定程度上解決了最初提出的問(wèn)題，未來(lái)可以考慮利用一些更加成熟的技術(shù)來(lái)對(duì)效果進(jìn)行改進(jìn)。