線性函數演算法

❶ 解線性規劃數學模型有哪些方法

模型建立：
從實際問題中建立數學模型一般有以下三個步驟；
1.根據影響所要達到目的的因素找到決策變數；
2.由決策變數和所在達到目的之間的函數關系確定目標函數；
3.由決策變數所受的限制條件確定決策變數所要滿足的約束條件。
線性規劃難題解法
所建立的數學模型具有以下特點：
1、每個模型都有若干個決策變數（x1，x2，x3……，xn），其中n為決策變數個數。決策變數的一組值表示一種方案，同時決策變數一般是非負的。
2、目標函數是決策變數的線性函數，根據具體問題可以是最大化或最小化，二者統稱為最優化。
3、約束條件也是決策變數的線性函數。
當我們得到的數學模型的目標函數為線性函數，約束條件為線性等式或不等式時稱此數學模型為線性規劃模型。
例：
生產安排模型：某工廠要安排生產Ⅰ、Ⅱ兩種產品，已知生產單位產品所需的設備台時及A、B兩種原材料的消耗，如表所示，表中右邊一列是每日設備能力及原材料供應的限量，該工廠生產一單位產品Ⅰ可獲利2元，生產一單位產品Ⅱ可獲利3元，問應如何安排生產，使其獲利最多？
解：
1、確定決策變數：設x1、x2分別為產品Ⅰ、Ⅱ的生產數量；
2、明確目標函數：獲利最大，即求2x1+3x2最大值；
3、所滿足的約束條件：
設備限制：x1+2x2≤8
原材料A限制：4x1≤16
原材料B限制：4x2≤12
基本要求：x1，x2≥0
用max代替最大值，s.t.（subject to 的簡寫）代替約束條件，則該模型可記為：
max z=2x1+3x2
s.t. x1+2x2≤8
4x1≤16
4x2≤12
x1，x2≥0
解法
求解線性規劃問題的基本方法是單純形法，已有單純形法的標准軟體，可在電子計算機上求解約束條件和決策變數數達 10000個以上的線性規劃問題。為了提高解題速度，又有改進單純形法、對偶單純形法、原始對偶方法、分解演算法和各種多項式時間演算法。對於只有兩個變數的簡單的線性規劃問題，也可採用圖解法求解。這種方法僅適用於只有兩個變數的線性規劃問題。它的特點是直觀而易於理解，但實用價值不大。通過圖解法求解可以理解線性規劃的一些基本概念。

❷ 線性插值法計算公式是什麼

線性插值法計算公式：Y=Y1+(Y2-Y1)×(X-X1)/(X2-X1)。其中Y2>Y1，X2>X>X1。線性插值是指插值函數為一次多項式的插值方式，其在插值節點上的插值誤差為零。線性插值相比其他插值方式，如拋物線插值，具有簡單、方便的特點。線性插值可以用來近似代替原函數，也可以用來計算得到查表過程中表中沒有的數值。

線性插值使用的原因

目前，線性插值演算法使用比較廣泛。在很多場合我們都可以使用線性插值。其中，最具代表性的使用方法是變數之間的對應關系沒有明確的對應關系，無法使用公式來描述兩個變數之間的對應關系，在這種情況下使用線性插值是比較好的解決辦法。可以在變數的變化區間上取若干個離散的點，以及對應的輸出值，然後將對應關系分成若干段，當計算某個輸入對應的輸出時，可以進行分段線性插值。

❸ 什麼是線性時間演算法

計算公式：K（N）=AO（N）+B

線性時間
在計算復雜性理論，一個被稱為線性時間或 Ο（n）時間的演算法，表示此演算法解題所需時間正比於輸入資料的大小，通常以n表示。換句話說，執行時間與輸入資料大小為線性比例。例如將一列數字加總的所需時間，正比於串列的長度。

❹ 線性模型-分類模型

線性模型也可用於分類問題。我們首先來看二分類。我們可以利用下面的公式預測：

y^=w[0]x[0]+w[1]x[1]+...+w[p]*x[p]+b>0

這個公式與線性回歸的公式非常相似，但我們沒有返回特徵的加權求和，而是為預測設置了閾值（0）。如果函數值小於0，我們就預測類別-1，如果函數值大於0，我們就預測類別+1。對於所有用於分類的線性模型，這個預測規則都是通用的。同樣，有很多不同的方法來找出系數（w）和截距（b）。
對於用於回歸的線性模型，輸出y^是特徵的線性函數，是直線、平面或超平面（對於更高維的數據集）。對於用於分類的線性模型， 決策邊界 是輸入的線性函數。換句話說，（二元）線性分類器是利用直線、平面或超平面來分開兩個類別的分類器。
學習線性模型有很多種演算法。這些演算法的區別在於以下兩點：
1.系數和截距的特定組合對訓練數據擬合好壞的度量方法；
2.是否使用正則化，以及使用哪種正則化方法。
不同的演算法使用不同的方法來度量「對訓練集擬合好壞」。由於數學上的技術原因，不可能調節w和b使得演算法產生的誤分類數量最少。對於我們的目的，以及對於許多有用而言，上面第一點（稱為 損失函數 ）的選擇並不重要。
最常見的兩種線性分類演算法是 Logistic回歸（logistic regression） 和 線性支持向量機（linear support vector machine,線性SVM） 。

Python version:3.7.1 (default, Dec 10 2018, 22:54:23) [MSC v.1915 64 bit (AMD64)]
pandas version:0.23.4
matplotlib version:3.0.2
Numpy version:1.15.4
Scipy version:1.1.0
IPython version:7.2.0
scikit-learn version:0.20.1

對於LogisticRegression和LinearSVC,決定正則化強度的權衡參數叫作C。C值越大，對應的正則化越弱。換句話說，如果參數C值較大，那麼LogisticRegression和LinearSVC將盡可能將訓練集擬合到最好，而如果C值較小，那麼模型更強調使系數向量（w）接近於0。
參數C的作用還有另一個有趣之處。較小的C值可以讓演算法盡量適應「大多數」數據點，而較大的C值強調每個數據點都分類正確的重要性。
mglearn.plots.plot_linear_svc_regularization()

Training set score:0.953
Test set score:0.958
C=1的默認值給出了相當好的性能，在訓練集和測試集上都達到95%的精度。但由於訓練集和測試集的性能非常接近，所以模型很可能是欠擬合的。我們嘗試增大C來擬合一個更靈活的模型：

Training set score:0.972
Test set score:0.965
使用C=100可以得到更高的訓練集精度，也得到了稍高的測試集精度，這也證實了我們的直覺，即更復雜的模型應該性能更好。

Training set score:0.934
Test set score:0.930
最後，看一下正則化參數C取三個不同的值模型學到的系數：

LogisticRegression模型默認應用L2正則化。更強的正則化使的系數更趨向於0，但系數永遠不會正好等於0。進一步觀察圖像，還可以第3個系數那裡發現有趣之處，這個系數是「平均周長」（mean perimeter）。C=100和C=1時這個系數為正，其絕對值比C=1時還要大。在解釋這樣的模型時，系數可以告訴我們某個特徵與哪個類別有關。例如，人們可能會認為高「紋理錯誤」（texture error）特徵與「惡性」樣本有關。但「平均周長」系數的正負號發生變化，說明較大的「平均周長」可以被當作「良性」的指標或「惡性」的指標，具體取決於我們考慮的是哪個模型。這也說明，對線性模型系數的解釋應該始終持保留態度。
如果想要一個可解釋性更強的模型，使用L1正則化可能更好，因為它約束模型只使用少數幾個特徵：

Training accuracy of l1 logreg with C=0.001:0.91
Test accuracy of l1 logreg with C=0.001:0.92
Training accuracy of l1 logreg with C=1.000:0.96
Test accuracy of l1 logreg with C=1.000:0.96
Training accuracy of l1 logreg with C=100.000:0.99
Test accuracy of l1 logreg with C=100.000:0.98

將二分類演算法推廣到多分類演算法的一種常見方法是「一對多餘」（one-vs.-rest）方法。在「一對多餘」方法中，對每個類別都學習一個二分類模型，將這個類別與所有其他類別盡量分開，這樣就生成了與類別格式一樣多的二分類偶像。在測試點上運行所有二分類器來進行預測。在對應類別上分數最高的分類器「勝出」，將這個類別標簽返回作為預測結果。
每個類別都對應一個二類分類器，這樣每個類別都有一個系數（w）向量與一個截距（b）。
我們將「一對多餘」方法應用在一個簡單的三分類數據集上。我們用到了一個二維數據集，每個類別的數據都是從一個高斯分布中采樣得出的：

在上面的數據集上訓練一個LinearSVC分類器：

Coefficient shape: (3, 2)
Intercept shape: (3,)
我們看到，coef_的形狀是(3,2),說明coef_每行包含三個類別之一的系數向量，每列包含某個特徵（這個數據集有2個特徵）對應的系數值。現在intercetp_是一維數組，保存每個類別的截距，我們將這3個二分類器給出的直線可視化：

你可以看到，訓練集中所有屬於類別0的點都在類別0對應的直線上方，這說明它們位於這個二分類器屬於「類別0」的那一側。屬於類別0的點位於與類別2對應的直線上方，這說明它們被類別2的二分類器劃為「其餘」。屬於類別0的點位於與類別1對應的直線左側，這說明類別1的二元分類器將它們劃為「其餘」。因此，這一區域的所有點都會被最終分類器劃為類別0（類別0的分類器的分類置信方程的結果大於0，其他兩個類別對應的結果小於0）。
但圖像中間的三角形區域屬於哪一個類別呢，3個分類器都將這一區域內的點劃為「其餘」。這里的點應該應該劃歸到哪一個類別呢？答案是分類方程結果最大的那個類別，即最接近的那條線對應的類別。

線性模型的主要參數是正則化參數，在回歸模型中叫作alpha,在LinearSVC和LogisticRegression中叫作C。alpha值較大或C值較小，說明模型比較簡單。特別是對於回歸模型而言，調節這些參數非常重要。通常在對數尺度上對C和alpha進行搜索。你還需要確定的是用L1正則化還是L2正則化。如果你假定只有幾個特徵是真正重要的，那麼你應該用的是L1正則化，否則默認使用L2正則化。如果模型的可解釋性很重要的話，使用L1也會有幫助。由於L1隻用到幾個特徵，所以更容易解釋哪些特徵對模型時重要的，以及這些特徵的作用。
線性模型的訓練速度非常快，預測速度也很快。這種模型可以推廣到非常大的數據集，對稀疏數據也很有效。如果你的數據包含數十萬甚至上百萬個樣本，你可能需要研究使用LogisticRegression和Ridge模型的solver='sag'選項，在處理大型數據時，這一選項比默認值要更快。其他選項還有SGDClassifier類和SGDRegressor類，它們對線性模型實現了可擴展性更強的版本。
線性模型的另一個優點在於，利用我們之前見過的用於回歸和分類的公式，理解如何進行預測是相對比較容易的。不幸的是，往往並不完全清楚系數為什麼是這樣的。如果你的數據集中包含高度相關的特徵，這一問題尤為突出。在這種情況下，可能很難對系數做出解釋。
如果特徵數量大於樣本數量，線性模型的表現通常都很好。它也常用於非常大的數據集，只是尤為訓練其他模型並不可行。但在更低維的空間中，其他模型的泛化性能可能更好。