哈囉，各位好，我是Teresa，本集的重點是二元分類問題，會說明感知器以及PLA演算法。以下先讓我們回顧上集說了什麼吧～ EP.1回顧 在機器學習中，為了找到一個最適合的假說，存在著演算法(Learning Algorithm A)和假說集合(Hypothesis Set H)。演算法A 從大量資料集合D 進行觀察，接著從假說集合H 中挑選一個最符合我們期望的函式g。 上集提到的例子是如果銀行想要做出一個機器學習來判斷：當客戶申請核發信用卡時，銀行應不應該發卡給該客戶。由這個例子我們可以清楚的知道此機器學習需要提供的答案只有兩種：發卡或是不發卡。這類型的問題我們可以稱為二元分類問題。從客戶提交的申請資料x中經過函式g，來得到y（發卡）或是n（不發卡）的結果。 完整筆記可點此連結 感知器假設集（Perceptron Hypothesis Set） 銀行從過往的經驗中掌握了客戶的屬性資料，如：性別、年齡、職業、薪資、信用狀況......。這些資料都可以轉換成以下式子。 銀行也能針對這些屬性資料進行重要性的排序，給予權重，例如：薪資權重給2，信用狀況如是負債權重給-1等等。 銀行會設立一個門檻值T(threshold)，當上述條件的總分大於門檻值，才會發卡給客戶，反之，則不發卡。雖然有機率總分會剛好等於門檻值，但機率非常小，可忽略不管。 為了方便識別，我們將輸出的結果y(發卡、不發卡、忽略不計)轉為符號表示，這樣的符號在機器學習裡被稱為label。 從算式中，我們很難直接知道畫面看起來是什麼樣子，如果應用在二維平面上，會如下圖，有一條直線將畫面切割成兩個平面，而資料中的點會落在線的兩側，一側為正；一側為負。而機器學習所期望的目標便是找出一條直線，能將不同的label正確劃分在兩個平面上。這樣的感知器便被稱作二元線性分類器(Linear…
前言這篇文章將為排序篇章做一個結尾，文章會介紹選擇排序 (Selection Sort) 與插入排序 (Insertion Sort) 兩種排序法，透過上圖的排序法複雜度一覽表可以發現他們的執行效能相比其他排序法來的差一點，因此比較不常被使用，但要強調的是他們仍然有適合使用的情境，本篇文章將會簡單紀錄這兩個演算法的定義與程式碼實作。選擇排序法 (Selection Sort) 選擇排序法示意圖簡單來說選擇排序法一直重複的做兩件事:從尚未經過排序的陣列中找到最小值將當前找到最小值擺到最左邊時間複雜度 O(n²)程式碼範例這邊先設陣列的第一個數字是目前的最小值，然後往後把陣列的數值一個一個讀取，如果讀取的下個數比最小值大，就不作處理。而如果讀取到的數比目前的最小值小，就把目前的最小值換成這個數。重複這個方法把所有陣列裡的數都讀過一遍，就能確保目前的最小值為整個數列的最小值，扣除掉已經確定的最小值，剩下未確定的元素再重複執行以上步驟，直到陣列完成排序。function selectionSort(array) { const length = array.length; for(let i = 0;…
氣泡排序法 Bubble Sort其實氣泡排序法算是最容易理解的排序法，也常作為初學者入門學習的演算法，相信經過前兩篇較為複雜的快速排序法、合併排序法後，可以快速理解氣泡排序法的內容與實作方法。氣泡排序法定義氣泡排序法的過程會從陣列最左邊開始將元素兩兩比較，每一輪都會把最大的數值移動到陣列末端，這個行為就好像氣泡不斷從底部冒出一樣，因此被稱作氣泡排序法。氣泡排序法的實作步驟如下：比較相鄰的兩個元素，若前面的元素較大就進行交換。重複進行1的動作直到最後面，最後一個元素將會是最大值。重複進行1,2的動作，每次比較到上一輪的最後一個元素。重複進行以上動作直到沒有元素需要比較。 把文章一開始示意圖的第一部份拆過來看，一開始把陣列的第一個元素跟第二個元素比較，如果前面的元素比後者大，就將兩元素交換，如果前者元素比後者小，就不做調整。這邊因為 5 比 1 大，因此將兩元素交換，接著看第二個元素跟第三個元素，依此類推，最後會將陣列中最大的元素放到陣列最後頭，接著重複以上步驟，直到所有元素都經過排列，排序才結束。時間複雜度因為實作會使用到雙重迴圈，因此平均時間複雜度為 O(n²)平均： O(n^2)空間複雜度因為沒有額外建立其他資料結構，因此空間複雜度為：O(1)程式碼範例function bubbleSort(array) { const length = array.length; for (let i = 0;…
合併排序法 Merge Sort合併排序法定義合併演算法與上一篇介紹的快速排序法一樣，都運用了 Devide and Conquer 的概念，基本上分為兩個步驟：分割與整合。首先利用遞迴把原先未排序的陣列平均分割成兩半，直到各邊都只剩下一個元素（上圖紫色方塊），接著排序後再一一整合起來，最後會合併成一個排序後的陣列（上圖綠色區塊）。分割 （紫色區塊）把大陣列分一半成為兩個小陣列把從上一步驟切好的兩個小陣列再各自分一半重複步驟 2 直到每個小陣列都只剩一個元素整合 （綠色區塊）排序兩個只剩一個元素的小陣列並將其合併把上一步驟排序好的小陣列合併並排序成一個陣列重複步驟二直到所有小陣列都合併成一個大陣列讀者比較有疑問的也許會是這個部分： Q: [2,3,7,16] 跟 [4,9,11,24] 這兩個陣列是如何合併成最終的已排序陣列呢？A: 因為這兩個陣列在合併前就已經各自完成排序了，因此只要比較各自最左邊的元素的大小，將比較小的元素放進新陣列中，最後就能完成排序囉！其實從一開始只有一個元素要進行合併時就是運用這個方法喔（只有一個元素的陣列視為已排序）！時間複雜度最佳：O(n log n)最差：O(n log n)平均：O(n…
大家好我是老莫，也可以叫我 Kyle為什麼要寫這個主題？之前在尋找實習職缺的過程中，遇到幾次當面或者電話面試考資料結構與演算法等技術題，測驗結束才發現自己沒有透徹了解這些概念，有些概念懂了卻不知道怎麼用程式語言實作出來，想當然面試結果並不理想。因此我決定設定這樣的主題，並以自己最擅長的語言 JavaScript 將資料結構或演算法實作出來，除了能夠了解背後的概念外，也有能力可以透過程式語言實作出來，並利用這些概念去解決真實狀況遇到的技術問題。主題涵蓋的範圍？這次 “JS 學資料結構與演算法” 系列預計會包含以下範圍：排序 (sort)搜尋 (sesrch)動態程式規劃 (dynamic programming)Hash Table 雜湊表Linked List 鏈結串列Stack 堆疊Queue 佇列Tree 樹Graph 圖形Recursion 遞迴其中各類別可能又會往下細分子類別依次介紹（如排序下細分各種排序法），我想這會是一個漫長的主題，但相信踏實地走完這趟旅程一定會讓基礎更加扎實，也能幫助像我一樣對這些觀念一知半解的讀者能有更透徹的理解，如果對這個主題有興趣的朋友們記得追蹤我囉！*此後內容皆假設讀者了解基本演算法定義與時間複雜度概念快速排序法演算法定義：快速排序法採用…
演算法對一個工程師來說是一個非常重要的技能，先撇開在工作上面的實務影響不管，光在求職的過程中，就有許多面試需要考試，而考的內容八九不離十是演算法考題，所以對於一個厲害的工程師來說，演算法尤其的重要，偏偏我的數學跟資料結構沒有這麼厲害，所以我也需要花點苦工來好好的學習，接下來我就會透過leetcode這個演算法考題的網站，學習演算法，把我寫好的題目來分享給大家，可以一起討論。 (more…)
前言 : 以下內容皆使用Weka 3.8.2去做演算法的分析，並且文章會根據分群分析、分類分析，按照這個排序分成兩大部分做探討。 兩個部分皆採用兩種不同類型的Datasets ，「現有Dataset」與「創意Dataset」；此外，每一個Dataset都會用兩種屬於該分群分析或分類分析的演算法。 分群分析會使用的演算法為① K-Means(K-平均法)與② Expectation Maximization, EM(期望最大化法)；分類分析會使用的演算法為① Decision Tree(決策樹)與② REPTree(快速決策樹)。 (more…)
何謂物件導向 傳統的程式設計主張將程式看作一系列函式的集合，或者直接就是一系列對電腦下達的指令，物件導向可以被看成在程式中包含各種獨立而又互相呼叫的物件的思想，這與傳統的思想剛好相反，物件導向程式設計中的每一個物件都應該能夠接受資料、處理資料並將資料傳達給其它物件，因此它們都可以被看作一個小型的「機器」，即物件。目前已經被證實的是，物件導向程式設計推廣了程式的靈活性和可維護性，並且在大型專案設計中廣為應用。 (more…)